Broad-phase and narrow-phase collision detection
Testing every pair of a thousand bodies for collision is a million comparisons a frame. Real engines never do that — they filter with a cheap broad phase first, and only run exact geometry math on the handful of pairs that survive.
1. The two-phase pipeline
Every rigid-body engine splits collision detection into two very different jobs. Broad phase answers a cheap, approximate question: "which pairs of bodies could possibly be touching?" using fast bounding-volume tests. Narrow phase then answers the expensive, exact question for each surviving pair: "are these two specific shapes actually touching, and if so, where, and along what normal?"
This article is about the first job — the algorithmic structures that keep it fast as body counts grow. For the exact geometric algorithms narrow phase uses once a pair survives — SAT, GJK, and EPA — see Collision Detection: BVH, SAT, GJK Explained and Rigid Body Physics: SAT and EPA Collision Detection.
2. Naive O(N²)
The simplest broad phase: compare every body against every other body's axis-aligned bounding box (AABB).
At N = 20 that's 190 pairs — trivial. At N = 2000 it's roughly
2 million pair tests per frame, most of them wasted on bodies on
opposite sides of the scene. Naive broadphase is fine for small
scenes and is exactly what Cannon-es' NaiveBroadphase
is meant for: prototyping and debugging, not production scale.
3. Sweep and prune
Sweep-and-prune (SAP) sorts every body's AABB endpoints along one axis (say X) into a single list. Two AABBs can only overlap in 3D if their projections overlap on all three axes — so sweeping along X and tracking which intervals are "open" immediately prunes out most pairs without ever checking Y or Z.
sweep left→right, maintain "active" set
when interval opens: candidate-pair with all currently active
confirm candidates by checking Y and Z overlap too
Because most scenes only change gradually frame to frame, the
sorted list is nearly sorted already — an insertion sort on
mostly-sorted data runs close to O(N), which is why SAP is the
default broadphase in Cannon-es (SAPBroadphase) and in
most other production physics engines.
4. Uniform grids and spatial hashing
A uniform grid divides space into fixed-size cells and buckets each body by the cells its AABB overlaps. Collision candidates are just the other bodies sharing a cell — no sorting required, and insertion/removal is O(1) per body.
- Works best when bodies are roughly the same size and evenly spread — exactly the case for the Granular Materials and sand-pile simulations on this site, where thousands of similarly-sized grains interact locally.
- Degrades when body sizes vary wildly (a huge floor plane plus tiny debris) — a giant AABB touches almost every cell, and the grid stops filtering anything useful.
- Spatial hashing generalizes the same idea to unbounded, sparse worlds: cell coordinates are hashed into a fixed-size hash table instead of a dense array, avoiding the memory cost of allocating cells for empty regions.
5. BVH and AABB trees
A Bounding Volume Hierarchy organizes bodies into a binary tree where every node's box tightly encloses its children's boxes. A query (say, "what does this ray or this moving body touch?") descends the tree, skipping entire subtrees whose bounding box doesn't overlap the query — turning a linear scan into a logarithmic one.
balanced BVH descent: O(log N)
BVHs shine for scenes with wildly different body sizes and for static or semi-static geometry that's expensive to rebuild every frame — a fractured mesh's debris pieces in Solid Body Fracture, for instance, or the static track geometry in Car Physics, which only needs its BVH built once at load time.
For scenes with many moving bodies, engines usually refit a BVH each frame (adjust existing node boxes to the new positions) rather than rebuild it from scratch — much cheaper, at the cost of a slowly degrading tree quality that eventually needs a full rebuild.
6. Complexity comparison
| Structure | Update cost | Query cost | Best case |
|---|---|---|---|
| Naive O(N²) | — | O(N²) | < 50 bodies |
| Sweep & prune | O(N log N) worst, ~O(N) typical | O(N + K) | Coherent, moderately dynamic scenes |
| Uniform grid | O(N) | O(N/cells + K) | Uniform body sizes, dense (granular, particles) |
| Spatial hash | O(N) | O(1) avg per cell | Sparse, unbounded worlds |
| BVH (balanced) | O(N log N) rebuild, O(N) refit | O(log N) | Mixed sizes, static or semi-static geometry |
K = number of true candidate pairs found, typically ≪ N².
7. Where narrow phase takes over
Once broad phase hands over a short list of candidate pairs, narrow phase runs exact tests: the Separating Axis Theorem (SAT) for convex polyhedra, GJK for general convex distance queries, and EPA to extract penetration depth once GJK confirms overlap. These algorithms are O(1)–O(edges) per pair but far too expensive to run on every possible pair in the scene — which is the entire reason broad phase exists. The full math for this half of the pipeline is covered in Collision Detection: BVH, SAT, GJK Explained.
8. Choosing a strategy
- Small scene, < 50 bodies: naive O(N²) — simplicity wins, the cost is negligible.
- General-purpose, moderate body count: sweep and prune — Cannon-es' default, and a good first choice for most simulations.
- Thousands of similar-sized particles: uniform grid or spatial hash — granular materials, SPH fluids, cloth self-collision.
- Mixed sizes, static-heavy scenes: BVH — terrain, fractured debris, large environments with small moving props.
See broad phase at scale
Thousands of grains use a uniform grid; the fracture demo below uses a BVH over convex debris.
🪨 Granular Materials 🧱 Solid Body Fracture