Collision Detection

The step where a physics engine works out which objects are touching, where, and how deeply.

Collision detection is a step a physics engine runs on every simulation tick, producing a list of contacts (contact points, normal directions, and penetration depth) that's then handed to the solver to compute contact forces. With n objects in a scene, there are n(n−1)/2 possible pairs, and checking every pair exactly is too slow, so engines generally split the work into two phases: broad phase, which uses cheap methods like bounding-box sorting (such as sweep-and-prune) to quickly rule out pairs that obviously can't be touching; and narrow phase, which does exact geometric computation on the remaining pairs, commonly using the GJK/EPA algorithm for convex shapes. MuJoCo adds a middle layer between the two, based on a bounding-volume hierarchy, and uses contype/conaffinity bitmasks to skip pairs that don't need checking at all. Note that this is a different “collision detection” from the kind used in robot safety systems to detect an actual physical impact.

ExampleIn MuJoCo, all the geometries of a robot, a table, and a block first go through sweep-and-prune to filter down to pairs that might touch, then a bounding-sphere test filters further; finally, basic shapes like spheres and boxes are handled with closed-form formulas, while pairs involving a mesh (first converted to a convex hull) go through GJK/EPA to compute contact points and penetration depth.

Also called

broad phase / narrow phase

Related

Collision Geometry (Collider) · Broad-phase / Narrow-phase Collision Detection · Gilbert-Johnson-Keerthi Algorithm · Bounding Volume (AABB / OBB) · Collision Filtering · Continuous Collision Detection

Sources

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