Collision Detection: Broad Phase, Narrow Phase, and the O(n²) Problem

The core problem and the two-phase invariant

Collision detection asks a boolean-plus question for pairs of geometric shapes: are they intersecting, and if so, produce the contact manifold — the penetration depth, the contact normal, and the contact points the physics solver needs to push them apart. Do this exactly for every pair and you pay Θ(n²) shape-vs-shape tests, each of which is far more expensive than a single comparison. The whole discipline is an exercise in avoiding work.

The governing structure is a pipeline with a hard correctness invariant:

• Broad phase — using cheap conservative bounds (usually axis-aligned bounding boxes, AABBs), produce a candidate set of pairs. Invariant: no false negatives. If two objects truly touch, their AABBs overlap, so the pair must survive. False positives (AABBs overlap but shapes don't) are fine — the next stage discards them.
• Narrow phase — run the exact, expensive test (SAT, GJK, or a swept variant) on each surviving pair, producing the real yes/no and the contact manifold.

Because the AABB is a conservative enclosure, the broad phase can be sloppy and fast while the pipeline stays sound. The entire performance win comes from the broad phase turning Θ(n²) into something close to O(n) or O(n log n) candidate pairs, and only the small k actual near-collisions reaching the costly narrow phase.

Broad phase: culling the quadratic pair space

The AABB overlap test itself is the cheapest useful primitive in graphics: two boxes overlap iff their projections overlap on all three axes — six comparisons, O(1), branch-predictable, SIMD-friendly:

bool aabbOverlap(A, B):
  return A.maxX >= B.minX and A.minX <= B.maxX
     and A.maxY >= B.minY and A.minY <= B.maxY
     and A.maxZ >= B.minZ and A.minZ <= B.maxZ

The art is choosing which pairs to feed it. The classic techniques:

• Sweep and prune (SAP) — Baraff (1992), later called "sort and sweep." Keep the interval endpoints [min, max] of every AABB sorted along each axis. Two boxes can only overlap if they overlap on all axes simultaneously; sweeping the sorted list and tracking an "active" set finds overlapping intervals in one pass. Crucially it exploits temporal coherence: between frames objects move little, so the arrays are nearly sorted and an insertion-sort pass fixes them in O(n) amortized. Bullet's btAxisSweep3 and PhysX use SAP variants.
• Uniform spatial hashing — map each AABB to the grid cells it overlaps via a hash of integer cell coordinates; only objects sharing a cell are tested. O(n) build, near-O(n) query when object sizes and density are uniform, but it degrades badly with the teapot-in-a-stadium problem (one huge object plus many tiny ones) or wildly mixed scales.
• Trees — quadtrees/octrees recursively subdivide space; a bounding volume hierarchy (BVH) subdivides objects into a binary tree of AABBs. BVHs give O(log n) average query and are the standard for large static geometry and ray-scene tests; a dynamic BVH "refits" leaf boxes bottom-up in O(n) rather than rebuilding.

All of these hit the same wall: nothing beats Θ(n²) in the adversarial case where all n objects mutually overlap. The bounds above are for realistic, spatially spread scenes.

Narrow phase 1: the Separating Axis Theorem

For the survivors, we need the exact answer. For convex polytopes, the workhorse is the Separating Axis Theorem (SAT): two convex shapes are disjoint if and only if there exists an axis onto which their 1-D projections do not overlap. Contrapositive: if the projections overlap on every candidate axis, the shapes intersect.

The finite set of axes you must test is the shapes' face normals (2-D: edge normals; 3-D convex polyhedra: face normals plus, critically, the cross products of every edge pair to catch edge–edge contacts). For two convex polygons with a and b edges the test is:

for each candidate axis L:          // a + b axes in 2D
  projA = [min,max] of A's verts · L
  projB = [min,max] of B's verts · L
  if projA.max < projB.min or projB.max < projA.min:
     return DISJOINT               // found a separating axis
  track minimum overlap → gives MTV
return OVERLAP

• Complexity: O((a+b)·(a+b)) = O((a+b)²) in 2-D since each of a+b axes projects a+b vertices; effectively O(1) for fixed-vertex-count boxes (a box vs box is just 15 axis tests in 3-D). Space O(1).
• Bonus output: the axis of minimum penetration is the collision normal, and its overlap magnitude is the minimum translation vector (MTV) — exactly what the solver needs to separate the bodies. This free contact data is why SAT dominates for boxes and simple polygons.
• Hard limit: SAT requires convexity. Concave shapes must first be convex-decomposed (e.g. V-HACD) into convex pieces, each tested separately.

Narrow phase 2: GJK and EPA for general convex shapes

When shapes aren't polygonal boxes — spheres, capsules, arbitrary convex hulls, or shapes defined only by a support function — SAT's explicit axis enumeration is awkward. The Gilbert–Johnson–Keerthi (GJK) algorithm (1988) is the elegant answer. Its key idea: two convex sets A and B intersect iff their Minkowski difference A ⊖ B = { a − b : a ∈ A, b ∈ B } contains the origin.

GJK never builds that difference explicitly. It only needs a support function — "give me the farthest point of the shape in direction d" — and iteratively builds a simplex (point → line → triangle → tetrahedron) inside the Minkowski difference, marching it toward the origin:

• Pick a direction, get a support point on A ⊖ B, add it to the simplex.
• Ask: does the simplex contain the origin? If yes → collision. If no, discard the vertex farthest from the origin and pick a new search direction toward the origin.
• If the new support point is no closer to the origin than the last, the origin is outside → no collision (and you get the closest distance for free).

GJK converges in a handful of iterations — effectively O(1) amortized per pair for typical convex shapes, O(1) space (a 4-vertex simplex). It's numerically robust and handles spheres, capsules, and hulls uniformly. When shapes do overlap and you need penetration depth, GJK is paired with the Expanding Polytope Algorithm (EPA), which grows the terminal simplex outward toward the Minkowski surface to recover the exact penetration vector. Bullet, PhysX, and most modern 3-D engines run GJK+EPA as their convex narrow phase.

The tunneling trap: continuous collision detection

Everything above is discrete collision detection — it samples positions once per frame. That's a correctness bug in disguise. A bullet 5 cm long moving at 400 m/s travels ~6.6 m per 60 Hz frame; the wall it should hit is never sampled at an overlapping position, so it tunnels straight through. This is the canonical failure mode.

The fix is continuous collision detection (CCD), which tests the swept volume across the whole timestep rather than the endpoints:

• Swept AABB / swept-sphere: analytically solve for the time-of-impact (TOI) t ∈ [0,1] where the moving box first touches the target, treated as a ray-vs-slab or Minkowski-inflated ray test. O(1) per pair, exact for linear translation.
• Conservative advancement (Mirtich): repeatedly advance the object by the largest step guaranteed not to cause penetration (distance ÷ relative speed), using GJK to measure the gap, until the gap is within tolerance. Handles rotation, converges quickly.
• Bilateral advancement (Zhang et al., 2006): a refinement that clamps both bodies' motion to the earliest TOI.

CCD is expensive, so engines apply it selectively — usually only to fast, small "bullet" bodies (Box2D literally has a bullet flag) — and fall back to cheap discrete tests for slow-moving objects. The trade-off is stark: full CCD on every body can cost several times the discrete budget, so it's a targeted tool, not a default.

Trade-offs, tuning, and where each approach wins

The choice of structures is dictated by scene shape, not dogma:

• Sweep-and-prune wins when motion is coherent and objects cluster along one dominant axis — its incremental resort is near-O(n). It degrades to O(n²) when many intervals overlap on the sweep axis (e.g. a tall stack of boxes all sharing an X-range), so engines often sweep the axis with greatest spread.
• Spatial hashing wins for many similarly-sized objects at uniform density (particles, bullets, agents). Its Achilles heel is cell size: too small and big objects touch dozens of cells (re-insertion cost); too large and every object lands in one cell, collapsing back to Θ(n²). A common heuristic sets cell size ≈ 2× the average object size.
• BVH/quadtree/octree win for large, mostly static geometry and for ray/frustum queries, giving O(log n) traversal — but rebuilding a tree every frame for dynamic scenes is wasteful; refitting or a loose/incremental tree is used instead.
• SAT vs GJK: SAT is simplest and gives the MTV directly for boxes/simple polygons; GJK is the general convex hammer and the only sane choice for smooth or high-vertex hulls. For box-vs-box specifically, hand-tuned SAT often beats GJK on constant factors.

Real engines layer all of this: Box2D uses a dynamic AABB tree broad phase + SAT/clipping narrow phase + selective CCD; Bullet uses a dynamic AABB tree (dbvt) + GJK+EPA; Unity/PhysX use SAP-family broad phase + GJK. The universal rule is make the common case (no collision) cheap — 99% of pairs die in the O(1) AABB test.

Pitfalls, edge cases, and numerical reality

Correct-in-theory collision code fails in practice for a predictable catalog of reasons:

• Floating-point robustness: exact-zero separating axes, near-parallel faces, and degenerate simplices in GJK cause the loop to cycle or accept/reject wrongly. Production GJK uses distance tolerances and iteration caps; some engines use exact/adaptive predicates (Shewchuk's) for the most delicate tests.
• The resting-contact / jitter problem: a box at rest on the floor oscillates between "overlapping" and "separated" as the solver pushes it out and gravity pulls it back. Solutions add a small skin / margin (Bullet inflates hulls by a few mm) and contact caching across frames for stability.
• Contact manifold generation: knowing shapes overlap isn't enough — a stable stack needs multiple simultaneous contact points, not one. Engines clip incident faces against reference faces (Sutherland–Hodgman clipping) to build a full manifold; a single-point contact makes stacks tip over.
• Broad-phase false negatives from bad bounds: if an AABB is computed for the pre-rotation pose but the object rotated, its true extent can exceed the box and a real collision is missed — bounds must enclose the whole timestep's motion, which is exactly why CCD inflates them.
• Adversarial density: every broad phase is Θ(n²) when everything overlaps; a physics "explosion" of intersecting bodies can drop frame rate to a crawl. Engines cap contacts, sleep resting bodies, and use islands to bound the work.

Broad-phase acceleration structures: how they cut the O(n²) pair test

Structure	Build / update	Query cost	Best regime
Brute force (all pairs)	—	Θ(n²)	n ≤ ~100, trivial
Sweep and prune (SAP)	O(n log n) sort, O(n) incremental	~O(n + k) pairs	coherent motion, tight clusters
Uniform spatial hash grid	O(n) insert	~O(n) avg, cell-size sensitive	similar-size objects, even density
Quadtree / Octree	O(n log n) build	O(log n) point, O(n) worst	static or clustered scenes
BVH (AABB tree)	O(n log n) build, refit O(n)	O(log n) query avg	large static meshes, ray/scene queries