Collision Detection: Broadphase to GJK/EPA

The collide step turns geometry into a list of contacts: points, normals, penetration depths. It runs in two stages, because testing every pair of bodies exactly would be far too slow.

Broadphase: throw out pairs

With $n$ bodies there are $\sim n^{2}/2$ possible pairs, and almost none of them touch. Broadphase discards the impossible ones cheaply, using bounding volumes: axis-aligned boxes tested by sweep-and-prune, or a bounding-volume hierarchy (an AABB or OBB tree). What comes out is a short list of candidate pairs that might overlap.

Narrowphase: the exact test

For convex shapes the workhorse is GJK.¹ Its idea is one clean fact: two convex sets $A$ and $B$ intersect if and only if the origin lies inside their Minkowski difference $A \ominus B = \{\, a - b : a \in A,\ b \in B \,\}$. GJK searches that set with an evolving simplex, never constructing it in full. Drag the shapes and watch the difference and the origin:

Collision ⟺ the Minkowski difference contains the origininteractive

world (drag the shapes)

Minkowski difference A ⊖ B

origin outside → separated

When the shapes do overlap, GJK by itself only reports distance zero. The Expanding Polytope Algorithm then grows a polytope inside the Minkowski difference to recover the penetration depth and contact normal.² For polytopes there is also the separating-axis theorem: two convex polytopes are disjoint if and only if some axis separates their projections.³

The output feeds the solver

Narrowphase emits, per contact, a point, a normal, and a penetration depth. Those become the constraints the solver operates on next. The stakes are asymmetric: miss a contact and bodies tunnel through each other; report a wrong normal and the solver pushes the wrong way. That is why collision code is judged on robustness as much as speed.

With a contact set in hand, Part 5 asks the harder question: what forces do these contacts imply, and why is the honest answer a complementarity problem?

Footnotes

1. Gilbert, Johnson & Keerthi, A fast procedure for computing the distance between complex objects in three-dimensional space, IEEE J. Robotics and Automation (1988). ↩

2. van den Bergen, Proximity Queries and Penetration Depth Computation on 3D Game Objects, GDC (2001). ↩

3. Gottschalk, Lin & Manocha, OBBTree: A Hierarchical Structure for Rapid Interference Detection, SIGGRAPH (1996). ↩