hexops/mach

Fork 0

proposal: add more 2D collision mechanisms to math.collision #1243

New issue

Open

opened 2024-08-09 19:46:57 +00:00 by hordurj · 4 comments

hordurj commented

2024-08-09 19:46:57 +00:00

(Migrated from github.com)

Mach includes a collection of function to determine if various 2D primitives collides.
(this is related to https://github.com/hexops/mach/issues/1084)

The primitives in the collision module are:

Point
Line (a line segment)
Triangle
Polygon
Circle

The following collisions are supported:
Rect: Rect
Circle: Rect, Circle
Point: Rect, Circle, Poly, Triangle, Line
Line: Line

I would like to propose adding the following:

Complete the different possibilities of collision, so any of the provided shapes can be tested with the other.
Add variants of the collision function that also compute contact information.
Document conventions, e.g. Rect pos is bottom left, polygon and triangles are defined in a counterclockwise order.

The point / poly collision test supports non-convex polygons. Testing for concave polygon / polygon collision is complex compared to testing convex polygons. For that reason, I propose that the core polygon functions (excluding the point test) should only support convex polygon. Then for concave polygons provide a function to decompose any polygon into convex polygons.

Collision interface:
Use current interface of including collision functions for the different primitives, but for symmetry have each shape include functions for all the other primitives.

E.g Rect has
pub fn collidesRect(a: Rectangle, b: Rectangle) bool
and Circle has
pub fn collidesRect(a: Circle, b: Rectangle) bool

so the following function could be added to Rect

    pub fn collidesCircle(a: Rectangle, b: Circle) bool {
        return b.collidesRectangle(a);
    }

Contact interface:
In dynamic systems with moving objects. one often wants to resolve the collision between the objects. E.g. when implementing a physics system.

For this I propose adding a contact type and functions for polygon and circles. Lines and triangles can be represented by polygons, and points can be represented by circles.

Contact type

const Contact = struct {
  depth: f32,
  normal: Vec2,
  cp1: ?Vec2,
  cp2: ?Vec2
};

Contact function

fn contactPolygonCircle(a: []const Vec2, b: Circle) ?Contact {...}
fn contactPolygonPolygon(a: []const Vec2, b: []const Vec2) ?Contact {...}
fn contactCircleCircle(a: []const Vec2, b: Circle) ?Contact {...}

In the current interface, polygon and triangle types do not have a specific name, instead they are a slice of vertices, i.e. []const Vec2. It might be worth later to consider if polygons warrant their own type.

Then we could define the contact interface as:

const Polygon = struct {
  ...
  fn contactPolygon(a: Polygon, b: Polygon) ?Contact {...} 

  // Or
  fn contact(a: Polygon, b: anytype) ?Contact {...} 

};

To further simplify function naming it would be possible to use anytype and/or tagged union. Using anytype can be used when the types are known at comptime while tagged union for when types are only known at runtime.

Example:

pub fn contact(a: anytype, b: anytype) Contact? {
  return a.contact(b);
}

or user could just call a.contact(b) directly.

To use tagged union, then that could be added as its own thing and the user would only use it if needed and it fits their particular usage.

Collider tagged union

const Collider = union(enum) {
  polygon: Vec2[],
  circle: Circle,

  pub contact(a: Collider, b: Collider) ?Contact { ... }

Mach includes a collection of function to determine if various 2D primitives collides. (this is related to https://github.com/hexops/mach/issues/1084) The primitives in the collision module are: * Point * Line (a line segment) * Triangle * Polygon * Circle The following collisions are supported: Rect: Rect Circle: Rect, Circle Point: Rect, Circle, Poly, Triangle, Line Line: Line I would like to propose adding the following: 1) Complete the different possibilities of collision, so any of the provided shapes can be tested with the other. 2) Add variants of the collision function that also compute contact information. 3) Document conventions, e.g. Rect pos is bottom left, polygon and triangles are defined in a counterclockwise order. The point / poly collision test supports non-convex polygons. Testing for concave polygon / polygon collision is complex compared to testing convex polygons. For that reason, I propose that the core polygon functions (excluding the point test) should only support convex polygon. Then for concave polygons provide a function to decompose any polygon into convex polygons. **Collision interface:** Use current interface of including collision functions for the different primitives, but for symmetry have each shape include functions for all the other primitives. E.g Rect has ```pub fn collidesRect(a: Rectangle, b: Rectangle) bool``` and Circle has ```pub fn collidesRect(a: Circle, b: Rectangle) bool``` so the following function could be added to Rect ``` pub fn collidesCircle(a: Rectangle, b: Circle) bool { return b.collidesRectangle(a); } ``` **Contact interface:** In dynamic systems with moving objects. one often wants to resolve the collision between the objects. E.g. when implementing a physics system. For this I propose adding a **contact** type and functions for polygon and circles. Lines and triangles can be represented by polygons, and points can be represented by circles. *Contact type* ``` const Contact = struct { depth: f32, normal: Vec2, cp1: ?Vec2, cp2: ?Vec2 }; ``` *Contact function* ``` fn contactPolygonCircle(a: []const Vec2, b: Circle) ?Contact {...} fn contactPolygonPolygon(a: []const Vec2, b: []const Vec2) ?Contact {...} fn contactCircleCircle(a: []const Vec2, b: Circle) ?Contact {...} ``` In the current interface, polygon and triangle types do not have a specific name, instead they are a slice of vertices, i.e. ```[]const Vec2```. It might be worth later to consider if polygons warrant their own type. Then we could define the contact interface as: ``` const Polygon = struct { ... fn contactPolygon(a: Polygon, b: Polygon) ?Contact {...} // Or fn contact(a: Polygon, b: anytype) ?Contact {...} }; ``` To further simplify function naming it would be possible to use anytype and/or tagged union. Using anytype can be used when the types are known at comptime while tagged union for when types are only known at runtime. Example: ``` pub fn contact(a: anytype, b: anytype) Contact? { return a.contact(b); } ``` or user could just call ```a.contact(b)``` directly. To use tagged union, then that could be added as its own thing and the user would only use it if needed and it fits their particular usage. **Collider tagged union** ``` const Collider = union(enum) { polygon: Vec2[], circle: Circle, pub contact(a: Collider, b: Collider) ?Contact { ... } ```

hordurj commented

2024-08-10 08:49:19 +00:00

(Migrated from github.com)

For rectangle this test passes

        const p = Point{ .pos = vec2(0.0, 0.0)};
        const r = Rectangle{.pos = vec2(0.0, 0.0), .size = vec2(1.0, 1.0)};
        try testing.expect(bool, p.collidesRect(r)).eql(true);

while for triangle the test below fails

        const t = [_]Vec2 {
            vec2(0.0, 0.0),  
            vec2(1.0, 0.0),  
            vec2(1.0, 1.0),  
        };
        const p = Point{ .pos = vec2(0.0, 0.0)};
        try testing.expect(bool, p.collidesTriangle(&t)).eql(true);

Another thing to define, is if points on vertices and the boundaries are considered inside the shape or not. In the current implementation there is a mismatch between primitive types. Rectangle and Circle are inclusive but not triangle, polygon, and line. For rectangle this test passes ``` const p = Point{ .pos = vec2(0.0, 0.0)}; const r = Rectangle{.pos = vec2(0.0, 0.0), .size = vec2(1.0, 1.0)}; try testing.expect(bool, p.collidesRect(r)).eql(true); ``` while for triangle the test below fails ``` const t = [_]Vec2 { vec2(0.0, 0.0), vec2(1.0, 0.0), vec2(1.0, 1.0), }; const p = Point{ .pos = vec2(0.0, 0.0)}; try testing.expect(bool, p.collidesTriangle(&t)).eql(true); ```

hordurj commented

2024-08-11 09:43:44 +00:00

(Migrated from github.com)

A common terminology for the set of contact points is collision manifold.

emidoots commented

2024-08-11 17:44:41 +00:00

(Migrated from github.com)

Document conventions, e.g. Rect pos is bottom left, polygon and triangles are defined in a counterclockwise order.

Goal here should be to make sure all collision code operates in sysgpu/webgpu world-space; i.e. (+Y up, left-handed) and use the same winding order as sysgpu/webgpu such that if you were to e.g. use triangle vertices from https://github.com/hexops/mach/blob/main/examples/core/triangle/shader.wgsl#L4-L8 it'd just work the same.

The point / poly collision test supports non-convex polygons. Testing for concave polygon / polygon collision is complex compared to testing convex polygons. For that reason, I propose that the core polygon functions (excluding the point test) should only support convex polygon. Then for concave polygons provide a function to decompose any polygon into convex polygons.

Sounds reasonable

Collision interface

It might be nicer to use a comptime interface or anytype? e.g.

    pub fn collides(a: Rectangle, b: anytype) bool {
        switch (@TypeOf(b)) {
        Rectangle => // ...
        Circle => // ...
        // ...
        }
    }

Contact interface

Fantastic!

To use tagged union, then that could be added as its own thing and the user would only use it if needed and it fits their particular usage.

Collider tagged union

I am hesitant to add a tagged union for representing runtime-known colliders, I think this may not be as generally applicable as the rest of what you have proposed.

If it is isolated / optional, that helps - but I'm not super keen on the idea just yet.

> Document conventions, e.g. Rect pos is bottom left, polygon and triangles are defined in a counterclockwise order. Goal here should be to make sure all collision code operates in sysgpu/webgpu world-space; i.e. (+Y up, left-handed) and use the same winding order as sysgpu/webgpu such that if you were to e.g. use triangle vertices from https://github.com/hexops/mach/blob/main/examples/core/triangle/shader.wgsl#L4-L8 it'd just work the same. > The point / poly collision test supports non-convex polygons. Testing for concave polygon / polygon collision is complex compared to testing convex polygons. For that reason, I propose that the core polygon functions (excluding the point test) should only support convex polygon. Then for concave polygons provide a function to decompose any polygon into convex polygons. Sounds reasonable > Collision interface It might be nicer to use a comptime interface or `anytype`? e.g. ```zig pub fn collides(a: Rectangle, b: anytype) bool { switch (@TypeOf(b)) { Rectangle => // ... Circle => // ... // ... } } ``` > Contact interface Fantastic! > To use tagged union, then that could be added as its own thing and the user would only use it if needed and it fits their particular usage. > > Collider tagged union I am hesitant to add a tagged union for representing runtime-known colliders, I think this may not be as generally applicable as the rest of what you have proposed. If it is isolated / optional, that helps - but I'm not super keen on the idea just yet.

hordurj commented

2024-08-11 21:56:43 +00:00

(Migrated from github.com)

The PR includes the core functions to compute contacts between shapes. I will look into adding generic functions using comptime next.

Regarding naming, in the PR the functions to compute contacts are called contact. But it might make sense to have

  pub fn collides(...) bool 
  pub fn collision(...) Collission

That would match the naming used in Rectangle.

  pub fn collidesRect(...) bool
  pub fn collisionRect(...) Rect

The PR includes the core functions to compute contacts between shapes. I will look into adding generic functions using comptime next. Regarding naming, in the PR the functions to compute contacts are called contact. But it might make sense to have ``` pub fn collides(...) bool pub fn collision(...) Collission ``` That would match the naming used in Rectangle. ``` pub fn collidesRect(...) bool pub fn collisionRect(...) Rect ```