Overlap Tests

Once two objects are wrapped in bounding volumes, the broad phase asks one blunt question: are these two touching? For the two shapes that wrap almost everything — spheres and axis-aligned boxes — the answer is a couple of lines of arithmetic with no square roots and no special cases. Here they are, derived.

Sphere–sphere, line by line

Two spheres: centres \vec{c}_1, \vec{c}_2 and radii r_1, r_2.

Step 1 — touching means the centres are within the radius sum. Two balls intersect exactly when the gap between their centres is no more than the two radii laid end to end. The distance between centres is \lVert \vec{c}_1 - \vec{c}_2\rVert, so:

\text{overlap} \iff \lVert \vec{c}_1 - \vec{c}_2\rVert < r_1 + r_2.

(At equality the surfaces just kiss; use \le if a graze counts.)

Step 2 — square both sides to kill the root. Both sides are non-negative, so squaring preserves the inequality — and a square root is the most expensive thing in the line. Drop it:

\lVert \vec{c}_1 - \vec{c}_2\rVert^2 < (r_1 + r_2)^2.

Step 3 — both sides are now rootless. The left is a sum of squared component differences; the right is a single precomputed number:

(c_{1x} - c_{2x})^2 + (c_{1y} - c_{2y})^2 + (c_{1z} - c_{2z})^2 < (r_1 + r_2)^2.

Three subtractions, three squares, a sum, and one comparison — the cheapest collision test there is, run millions of times a frame without a single \sqrt{\ }.

AABB–AABB, line by line

Two axis-aligned boxes, each given by its min and max corner: [\vec{m}_1, \vec{M}_1] and [\vec{m}_2, \vec{M}_2].

Step 4 — a box is the product of three intervals. Because the box is axis-aligned, its x-, y- and z-extents are independent: the box is just the interval [m_x, M_x] on the x-axis, times [m_y, M_y] on the y-axis, times [m_z, M_z] on the z-axis. So overlap on each axis can be checked on its own.

Step 5 — two intervals overlap iff each starts before the other ends. On a single axis, [a, b] and [c, d] touch exactly when a \le d and c \le b — neither lies entirely past the other. For the x-axis that reads:

m_{1x} \le M_{2x} \quad\text{and}\quad m_{2x} \le M_{1x}.

Step 6 — the boxes overlap iff their intervals overlap on every axis. A box is a 3-D solid, so it takes overlap on all three axes at once for the boxes to share any point:

\text{overlap} \iff \bigwedge_{a \in \{x,y,z\}} \big(m_{1a} \le M_{2a}\ \text{and}\ m_{2a} \le M_{1a}\big).

Step 7 — one separating axis is enough to say "no". Read the and the other way: if the intervals fail to overlap on even one axis — a gap on x, say — there is a flat slab of empty space between the boxes, a separating axis, and they cannot be touching. So the test bails the instant any axis shows a gap, usually after just one comparison:

\text{a gap on any axis} \implies \text{no collision}.

This is the baby case of the separating axis theorem: two convex shapes miss each other iff some axis separates their shadows. For axis-aligned boxes the only axes you ever need to try are the three world axes — which is why the test is so cheap.

These tests are deliberately approximate, and that is the point. A bounding sphere or AABB overlap does not prove the meshes touch — it proves only that they might, so the pair is worth a closer look. That is the division of labour every physics engine runs.

The broad phase sweeps all pairs with these cheap volume tests (often accelerated by a spatial grid or a tree, so you don't even compare every pair), and throws out the thousands that clearly miss. The handful of survivors — overlapping volumes — go to the narrow phase, which runs the real, expensive test on the exact shapes: the actual convex hulls, the triangle soup, the precise contact points and penetration depths a physical response needs. Cheap-and-loose discards the many; dear-and-exact resolves the few. Skip the broad phase and the narrow phase drowns; skip the narrow phase and your boxes collide when the swords inside them don't.