Bounding Volumes

A dragon mesh is forty thousand triangles. The crate next to it is twelve. Asking "do the dragon and the crate touch?" by testing every triangle against every triangle is forty thousand times twelve comparisons — for one pair, every frame, with hundreds of pairs in the scene. No engine can afford that. The fix is to wrap each tangled mesh in a bounding volume: a stupidly simple shape that fully contains it, so cheap to test that the vast majority of pairs are thrown out before the real geometry is ever touched. This is the broad phase.

Wrapping a mesh, line by line

Let the mesh have vertices v_1, v_2, \ldots, v_k. We build two classic wrappers from them.

Step 1 — the AABB is the min and max corner. An axis-aligned bounding box (AABB) is the smallest box, with faces parallel to the world axes, that contains every vertex. Its two corners are found by taking the smallest and largest coordinate on each axis independently:

\vec{m} = \Big(\min_i v_{i,x},\ \min_i v_{i,y},\ \min_i v_{i,z}\Big), \qquad \vec{M} = \Big(\max_i v_{i,x},\ \max_i v_{i,y},\ \max_i v_{i,z}\Big).

That is the whole box — one min corner \vec{m}, one max corner \vec{M}. One pass over the vertices (three comparisons each) builds it, and every vertex satisfies \vec{m} \le v_i \le \vec{M} componentwise by construction.

Step 2 — the bounding sphere is a centre and a radius. A bounding sphere wraps the mesh in a ball: a centre \vec{c} and a radius r large enough that no vertex pokes out. A quick, serviceable choice takes the AABB's centre and the distance to the farthest vertex:

\vec{c} = \tfrac{1}{2}(\vec{m} + \vec{M}), \qquad r = \max_i \lVert v_i - \vec{c}\rVert.

Then \lVert v_i - \vec{c}\rVert \le r for every vertex — the ball contains the mesh. (Tighter "minimum enclosing sphere" algorithms exist; this one is cheap and good enough for a broad phase.)

Step 3 — both wrappers are conservative. This is the property that makes them useful. Because the volume contains the mesh, anything the mesh occupies the volume also occupies. Contrapositive: if a ray, a point, or another volume misses the simple shape, it certainly misses the real mesh inside it. So

\text{volume misses} \implies \text{mesh misses}.

A negative from the cheap test is a guaranteed negative — never a false "no". (A positive is only a maybe: the test then hands off to the exact geometry. That asymmetry is exactly what a broad phase wants.)

Step 4 — the broad phase rejects almost everything for almost nothing. An AABB-vs-AABB or sphere-vs-sphere test is a handful of comparisons and adds. Run it first on every pair; the overwhelming majority — the dragon and the crate on opposite sides of the level — fail instantly and are discarded. Only the rare pair whose volumes do overlap survives into the expensive narrow phase, where the actual triangles meet. The cost of collision drops from "every pair, exactly" to "every pair, cheaply; the survivors, exactly".

For a mesh with vertices v_1, \ldots, v_k:

AABB — the axis-aligned box with \vec{m} = (\min_i v_{i,x}, \min_i v_{i,y}, \min_i v_{i,z}) and \vec{M} = (\max_i v_{i,x}, \max_i v_{i,y}, \max_i v_{i,z}): the min and max corners.
Bounding sphere — a centre \vec{c} and radius r = \max_i \lVert v_i - \vec{c}\rVert enclosing every vertex.
Conservative — the volume contains the mesh, so if the volume misses, the mesh misses (a negative is exact; a positive is a maybe).
Broad phase — testing the cheap volumes first rejects the vast majority of pairs for a handful of operations, before any exact narrow-phase test runs.

No single wrapper wins everywhere; engines pick by shape and cost.

The AABB is the cheapest to test — six interval comparisons (next page) — but it is glued to the world axes, so when its mesh rotates the box must be rebuilt and it loosens: a thin sword swung to 45° gets a box twice as fat as the blade, full of empty space that triggers false maybes. The bounding sphere is even cheaper to test (one distance) and is rotation-invariant — spin the mesh and the sphere never changes — but for a long thin object it is hopelessly loose, a giant ball around a needle.

The oriented bounding box (OBB) is an AABB that turns with the mesh: it stays tight at any angle, hugging the sword. The price is the test — instead of comparing axis-aligned intervals you must check for a separating axis in the box's own rotated frame, an order of magnitude more arithmetic. The usual recipe is a hierarchy: cheap, loose spheres or AABBs in the broad phase to reject the obvious misses, then tight OBBs (or the real triangles) only on the few survivors. Loose-and-cheap first, tight-and-dear last.