How Matter.js Finds Collision Support Vertices

This article explains the algorithms and mathematical techniques Matter.js uses to identify support vertices and generate contact manifolds during collisions between convex shapes. In its narrowphase collision pipeline, Matter.js pairs the Separating Axis Theorem (SAT) with a projection-based extreme point search (dot product maximization) to isolate the exact vertices responsible for physical contact and impulse resolution.

The Collision Pipeline in Matter.js

Matter.js handles rigid body collision detection in two primary stages: the broadphase and the narrowphase. During the broadphase, it quickly discards non-colliding bodies using Axis-Aligned Bounding Boxes (AABB) or spatial hashing grids. Once a potential pair of colliding convex polygons is confirmed, the engine shifts to the narrowphase, where it executes the Separating Axis Theorem (SAT) located in its SAT.js module.

Identifying the Collision Normal via SAT

Before Matter.js can determine the support vertices, it must establish the collision normal and the depth of penetration:

  1. Axis Generation: The engine extracts normal vectors perpendicular to each edge of both convex polygons.
  2. Projection: All vertices from both bodies are projected onto these candidate axes.
  3. Overlap Testing: If an axis exists where the projections of the two shapes do not overlap, the shapes are not colliding.
  4. Minimum Translation Vector (MTV): If overlaps exist across all axes, the shapes intersect. Matter.js selects the axis with the smallest overlap amount as the primary collision normal, which represents the direction of the minimum translation vector required to separate the bodies.

Once the collision normal is identified, Matter.js must locate the support vertices—the points on the shapes that penetrate furthest into each other along that normal.

Matter.js uses an Extreme Point Projection algorithm (often referred to as a support mapping function):

  1. Directional Vector Assignment: The engine uses the collision normal vector (directed from body A to body B) and its inverse to evaluate each body independently.
  2. Dot Product Evaluation: For a given body, the engine iterates through all of its vertices and computes the scalar projection of each vertex onto the collision normal using the vector dot product: \[\text{projection} = \mathbf{v}_i \cdot \mathbf{n}\] Where \(\mathbf{v}_i\) is the position of vertex \(i\), and \(\mathbf{n}\) is the collision normal.
  3. Extreme Point Selection:
    • On the incident body, Matter.js searches for the vertex that minimizes or maximizes this dot product depending on the normal's sign, selecting the vertex positioned deepest along the collision axis.
    • On the reference body, it identifies the corresponding face (edge) or opposing vertex closest to the contact region.

Contact Manifold Generation

After finding the support vertices, Matter.js constructs the contact points used by its constraint and constraint-solving solvers: