SAT Narrow-Phase Collision Detection in Matter.js

This article explains how Matter.js utilizes the Separating Axis Theorem (SAT) during its narrow-phase collision pipeline to achieve precise collision detection between convex bodies. It covers the mathematical foundation of SAT, how potential separating axes are derived, how vertex projections detect intersections, and how Matter.js extracts collision manifolds—including penetration depth and normals—to feed its constraint resolution engine.

The Role of Narrow-Phase Collision

In Matter.js, physics updates occur in distinct stages. First, the broad-phase stage uses Axis-Aligned Bounding Boxes (AABBs) or spatial hashing to quickly filter out pairs of bodies that are nowhere near each other. Once candidate pairs are identified, they are passed to the narrow-phase stage.

The narrow-phase engine needs to perform exact geometric testing. Matter.js relies on the Separating Axis Theorem (SAT) for this purpose, evaluating rigid bodies composed of convex polygons and circles.

The Separating Axis Theorem Principle

The Separating Axis Theorem states that two convex shapes do not intersect if there exists a line (an axis) onto which the projections of the two shapes do not overlap. Conversely, if the projections overlap across all possible candidate axes, the two shapes are intersecting.

If even one axis reveals a gap between the projections, Matter.js immediately confirms there is no collision and terminates further checks for that pair, saving computational resources.

Step-by-Step SAT Process in Matter.js

1. Generating Candidate Axes

Matter.js does not need to test an infinite number of axes. For two-dimensional convex polygons, the only axes capable of separating them are the perpendicular vectors (normals) to the edges of both shapes:

• Polygon vs. Polygon: Matter.js iterates through the edges of both bodies, computes the outward-facing edge normal vectors, and normalizes them.
• Polygon vs. Circle: Matter.js tests the polygon's edge normals, along with one additional axis: the axis running from the circle’s center to the closest vertex on the polygon.
• Circle vs. Circle: Instead of running full SAT, Matter.js bypasses the theorem in favor of a simpler distance check between circle centers against the sum of their radii.

2. Projecting Vertices

Once candidate axes are generated, Matter.js projects the vertices of both shapes onto each axis using the vector dot product:

\[\text{projection} = \mathbf{v} \cdot \mathbf{axis}\]

For each shape, the algorithm calculates the minimum and maximum projection values, effectively mapping the 2D polygon into a 1D scalar interval \([ \min, \max ]\) along the axis.

3. Overlap Testing and Early Exits

Matter.js compares the scalar intervals of Body A and Body B on the active axis:

• If \(\max_A < \min_B\) or \(\max_B < \min_A\), an axis of separation is found. Matter.js breaks out of the loop instantly, marking the pair as non-colliding.
• If the intervals overlap, the algorithm records the overlap distance and proceeds to the next candidate axis.

4. Finding the Minimum Translation Vector (MTV)

If projections overlap on every single candidate axis, a collision is confirmed. Matter.js then looks for the axis with the smallest overlap value.

This smallest overlap defines the Minimum Translation Vector (MTV):

• Collision Normal: The direction of the chosen axis, oriented from Body A toward Body B.
• Penetration Depth: The magnitude of the smallest overlap.

The MTV represents the shortest distance and optimal direction required to push the two bodies apart so they no longer overlap.

5. Contact Point Generation

Knowing the normal and depth is not enough to simulate realistic angular momentum and friction; Matter.js also requires specific contact points.

Using the collision normal derived from SAT, the engine finds the "incident" edge and "reference" edge—the edges on each polygon that are most aligned against the collision normal. Matter.js then clips the incident edge against the reference edge planes to extract one or two distinct contact points, forming a contact manifold.

Practical Considerations and Limitations

• Convexity Requirement: SAT strictly functions on convex shapes. To handle concave geometries, Matter.js decomposes concave bodies into a compound set of smaller convex shapes, running SAT across each part.
• Vertex Count: Because the number of axes tested scales with the total number of polygon edges, high vertex counts increase narrow-phase calculation times. Matter.js performs best when shapes are simplified to the minimum number of vertices needed to represent the geometry.