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

[hordurj]

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]

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]

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

[slimsag]

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.

[hordurj]

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