💥 Collision Detection: From AABB to GJK Algorithm

The Two-Phase Architecture

Every practical collision detection system uses a two-phase architecture. The broad phase quickly eliminates pairs of objects that cannot possibly be colliding, using conservative but cheap approximations. The narrow phase then performs precise geometric tests on the small set of candidate pairs that survived the broad phase. This separation is key: the broad phase may miss nothing (no false negatives) but can have false positives; the narrow phase must be exact.

Axis-Aligned Bounding Boxes (AABB)

The simplest bounding volume is the Axis-Aligned Bounding Box: the smallest box, with sides parallel to the coordinate axes, that completely contains the object. For a mesh, the AABB is defined by the minimum and maximum x, y, z coordinates across all vertices.

Testing two AABBs for intersection is a single comparison per axis — six comparisons total:

bool aabbOverlap(AABB a, AABB b) {
  return a.min.x <= b.max.x && a.max.x >= b.min.x
      && a.min.y <= b.max.y && a.max.y >= b.min.y
      && a.min.z <= b.max.z && a.max.z >= b.min.z;
}

AABBs are fast to test and update, but they can be loose for rotated objects — a long diagonal rod has a large AABB that overlaps many other objects. For rotating objects, oriented bounding boxes (OBBs) fit more tightly but are more expensive to test and update.

Spatial Hashing for Broad Phase

Spatial hashing divides space into a regular grid and hashes each cell to a flat array. For each object, compute which grid cells its AABB overlaps and insert it into those cells. To find collision candidates for an object, look up the same cells and return all other objects found there.

function cellKey(x, y, cellSize) {
  const cx = Math.floor(x / cellSize);
  const cy = Math.floor(y / cellSize);
  // Large primes to reduce hash collisions
  return (cx * 92837111) ^ (cy * 689287499);
}

For uniformly distributed objects, spatial hashing achieves O(1) per-object lookup. The cell size should match the average object size — cells too small mean many cells per object; cells too large mean many objects per cell. Spatial hashing is excellent for particle simulations and fluid dynamics where thousands of same-size particles interact.

Bounding Volume Hierarchies (BVH)

A BVH is a tree of bounding volumes. Leaf nodes contain individual primitives (triangles, shapes). Internal nodes contain AABBs that bound all their children. To test object A against a scene, traverse the BVH: if A's AABB doesn't overlap a node's AABB, skip the entire subtree; otherwise recurse into children. This reduces the O(n²) problem to O(n log n) or better for typical scenes.

BVH construction uses splitting heuristics. The Surface Area Heuristic (SAH) minimizes the expected number of intersection tests by splitting at the position that minimizes SA(left)·N(left) + SA(right)·N(right), where SA is surface area and N is triangle count. SAH-built BVHs are used in raytracing (Embree, OptiX) and game physics engines (Bullet, PhysX). Dynamic scenes require BVH refitting or rebuilding each frame — modern GPU BVH builders do this in milliseconds using parallel top-down or Morton-code sorting approaches.

Separating Axis Theorem (SAT)

For convex shapes, the Separating Axis Theorem provides an exact test: two convex shapes do not overlap if and only if there exists a separating axis — a direction along which their projections don't overlap. For polygons/polyhedra, we need only test the face normals and (in 3D) edge cross-products as candidate axes.

For two convex polygons with n and m edges, SAT requires n + m axis tests, each O(1). If any axis separates them, the shapes don't collide. If all axes show overlap, they do. The axis with minimum overlap gives the collision normal and penetration depth for response. SAT is exact, fast, and provides rich contact information — it's the narrow phase algorithm of choice for convex polytopes in engines like Box2D.

The GJK Algorithm

The Gilbert-Johnson-Keerthi algorithm (1988) determines whether two convex shapes overlap by iteratively computing the nearest point on the Minkowski difference to the origin. The Minkowski difference A ⊖ B = {a − b | a ∈ A, b ∈ B} contains the origin if and only if A and B overlap.

GJK exploits support functions: for a direction d, support(A, d) = argmax_{a ∈ A} d·a — the point on A farthest in direction d. For convex shapes with analytic support functions (spheres, capsules, boxes), this is O(1). GJK never explicitly computes the Minkowski difference; it samples it via support function calls and builds a simplex (point, edge, triangle, tetrahedron) converging toward the closest feature.

GJK is warm-started from the previous frame's simplex, making it extremely fast for slowly moving objects — typically converging in 2–4 iterations. Combined with the EPA (Expanding Polytope Algorithm) for penetration depth when overlap is detected, GJK+EPA is the standard narrow phase for general convex shapes in modern physics engines.