Broad-phase / Narrow-phase Collision Detection

Collision detection done in two steps: first a coarse bounding-box pass to find likely pairs, then exact contact computation.

A physics engine has to figure out which objects are touching at every step. With n geometries, there are n(n-1)/2 possible pairs, and checking every pair exactly would be too slow, so the work is split into phases. The broad phase uses simple bounding volumes (such as axis-aligned bounding boxes, or AABBs) for a conservative test that quickly rules out pairs that clearly don't overlap, reporting only “possible collisions”; a common algorithm is sweep-and-prune, which sorts objects along an axis and looks for overlapping intervals. The narrow phase then runs an exact, geometry-specific algorithm (such as GJK/EPA for convex shapes) on the remaining candidate pairs to determine whether they actually touch, along with the contact point, normal, and penetration depth, which is handed to the constraint solver. MuJoCo inserts a mid-phase between the two, further filtering with a bounding-volume hierarchy; PhysX offers several broad-phase algorithms, including SAP, MBP, and a GPU variant. Collision filtering is usually inserted between the broad and narrow phases.

ExampleMuJoCo's broad phase uses a modified sweep-and-prune, sorting along the dominant eigenvector of the covariance matrix of all geometry centers; in the narrow phase, a non-convex mesh gets replaced with its convex hull before being tested.

Also called

Broad Phase / Narrow Phase, Coarse / Fine Collision Detection, Near-phase

Related

Collision Detection · Bounding Volume (AABB / OBB) · Gilbert-Johnson-Keerthi Algorithm · Collision Filtering · Collision Geometry (Collider) · Physics Engine

Sources

MuJoCo Documentation: Computation - Collision detection
NVIDIA PhysX 5 SDK Documentation: Rigid Body Collision
Wikipedia: Collision detection