Drop a thousand bouncing crates into a physics world and, before you can push a single one of them apart, you have to answer one deceptively simple question: what is touching what? The lazy answer is to test every crate against every other crate. With n = 1000 objects that is \binom{1000}{2} = 499{,}500 exact overlap tests every single frame — half a million tests sixty times a second, and it only gets worse: the naive cost grows like O(n^2), so ten thousand objects is a hundred times more expensive again. No real engine can afford that.

The way out is to split the work into two phases. A cheap, near-linear broad phase throws away the overwhelming majority of pairs that could not possibly be touching, leaving a short list of candidates; then an exact but more expensive narrow phase tests only those survivors and, for the real hits, produces the contact data the response step needs. This page is about that division of labour — why it exists, the acceleration structures that make the broad phase fast, and the sharp edges (like a bullet passing clean through a wall) that catch the unwary.

Two phases, two jobs

The split works because the two jobs have opposite economics. The broad-phase test is crude and cheap, so you can afford to run it on every object. The narrow-phase test is precise and pricey, so you want to run it on as few pairs as possible. Feed the cheap filter first, and the expensive test only ever sees the handful of pairs that actually matter.

The broad phase must be near-linear

Here is the trap the two-phase structure is built to avoid. Suppose your broad phase itself compares every object's bounding box against every other object's box. That is still O(n^2) work — you have made each test cheaper, but you have not changed the growth rate, so at large n the whole thing collapses back into the quadratic wall you were trying to escape.

A useful broad phase must be sub-quadratic — close to O(n \log n) or O(n) — so that the total cost is dominated by the narrow phase acting on the few real candidates rather than by the culling itself. Three families of acceleration structure achieve this:

These all lean on cheap bounding volumes and spatial partitioning — the same game-dev toolkit reused, now in service of physics.

Seeing sweep-and-prune

In the figure below, three axis-aligned bounding boxes (AABBs) sit in the plane. Beneath them, each box is projected onto the x-axis as an interval. Boxes A and B have overlapping x-intervals, so sweep-and-prune keeps (A, B) as a candidate to hand to the narrow phase. Box C's interval is disjoint from the others, so every pair involving C is pruned immediately — no exact test is ever run on it.

The trick that makes this fast is sorting. Sort the interval endpoints once, sweep through them in order keeping a small "active set" of currently-open intervals, and you find every overlap in roughly O(n \log n) for the sort plus O(n + k) for the sweep, where k is the number of overlapping pairs actually reported.

Worked example: 1000 objects

Put numbers on it. With n = 1000 objects the naive all-pairs approach does

At 60 frames per second that is about 30 million exact overlap tests every second — and each one might be a full convex intersection. Now suppose the objects are spread over a uniform grid so that, on average, only a handful share any cell. The grid visits each object roughly once and checks it against only its neighbours, giving work proportional to n plus the number of genuine near-pairs — call it a few thousand candidate tests instead of half a million.

The narrow phase: exact tests and contact data

Once the broad phase hands over a short candidate list, the narrow phase runs the exact geometry. For two spheres of radii r_1, r_2 at centres c_1, c_2 the test is a single distance comparison:

For two AABBs it is three interval-overlap checks, one per axis; for general convex shapes it is a separating-axis or GJK-style test. But detecting the hit is only half the narrow phase's job. To respond to the collision — push the bodies apart, apply impulses — the solver needs a contact manifold:

A boolean "yes, they overlap" is enough for a trigger volume, but a physical response is blind without the normal and the depth. Producing that manifold cleanly — especially for face-to-face contact with multiple contact points — is most of what makes the narrow phase intricate.

Temporal coherence: objects barely move

Here is the observation that makes real-time broad phases practical: between two consecutive frames, almost nothing moves very far. A crate that was left of another crate this frame is overwhelmingly likely to still be left of it next frame. So the sorted endpoint order that sweep-and-prune built last frame is almost already correct — a few neighbours may have swapped, but the list is nearly sorted.

Re-sorting a nearly-sorted list with insertion sort costs about O(n), not O(n \log n), because each element only drifts a slot or two. This temporal coherence — reusing last frame's structure and patching the small changes — is why incremental sweep-and-prune is a workhorse of real engines, and why the same idea speeds up grids (objects mostly stay in their cell) and BVH refits (boxes mostly stay put).

Discrete vs continuous detection

Everything so far is discrete collision detection: sample each object's pose at frame t, then again at t + \Delta t, and test the two snapshots. That is fine when objects move less than their own size per step. But a small, fast object can leap past a thin obstacle entirely: it is on one side at frame t and already on the far side at t + \Delta t, and neither snapshot overlaps the wall. The engine reports no collision, and the object tunnels straight through.

Continuous collision detection (CCD) fixes this by testing the swept volume — the region the object sweeps out along its path between the two frames — rather than just its endpoints. Instead of asking "do the two poses overlap?" it asks "does the moving shape's trajectory cross the obstacle at any moment in [t, t+\Delta t]?", solving for the earliest time of impact. It costs more, so engines reserve it for the objects that need it — bullets, thin fast debris — and leave slow, chunky objects on cheap discrete tests.