What problem does the broad phase of collision detection solve, and why do bounding volumes make it cheap?
answer
- count the pairs first
- n(n-1)/2 grows quadratically
- conservative cheap rejection
- sphere, AABB, OBB: fit vs cost
- false positive cheap, miss fatal
basics
~10 sThe broad phase cheaply shortlists pairs of bodies whose simple bounding volumes overlap, so the expensive exact shape test runs only on those candidates instead of on all n(n-1)/2 pairs every physics step.
solid answer
~40 sTesting every pair is quadratic: 5,000 debris pieces make 12,497,500 pairs per step. The broad phase wraps each body in a simple **bounding volume** that fully contains its shape (an axis-aligned box, a sphere or an oriented box) and organises those volumes with sweep-and-prune, a grid or a dynamic AABB tree, so most far-apart pairs are never even visited. Its output is a **conservative** candidate list: a false positive costs one wasted narrow-phase test, but a missed pair means two bodies pass through each other. Axis-aligned boxes dominate because their overlap test is two comparisons per axis and they sort, bucket and nest easily; spheres ignore rotation but fit long objects badly; oriented boxes fit tightly but cost far more to test.
go deeper
Recall the quadratic pair count, that the broad phase shortlists candidates with simple bounding volumes, and that the narrow phase then does the exact test.
Explain why the shortlist must be conservative, how a rotating body's AABB is refreshed, and why axis-aligned boxes beat spheres and oriented boxes for this job.
Show you know where the broad phase stops helping: truly overlapping heaps, oversized static boxes, and filtering that should reject pairs before any narrow-phase cost.
Frame the broad phase as a budget line: how bounding-volume looseness, collision-group design and the chosen structure trade CPU against false candidates across a whole game.
## Why testing every pair is too many A physics world with `n` bodies has `n(n-1)/2` distinct pairs. For 100 bodies that is 4,950 pairs, which is harmless. For a destruction scene where a wall has just shattered into 5,000 debris pieces it is 12,497,500 pairs, every physics step. If each exact shape test took a quarter of a microsecond, that alone would be about three seconds of work per step. Yet almost all of those pairs are far apart: a chunk of rubble at one end of the level cannot touch one at the other end. The **broad phase** exists to skip those pairs without examining them one by one, and to hand the **narrow phase** (the exact, expensive shape-versus-shape test) a short list of **candidate pairs**. ## Bounding volumes: a cheap, conservative stand-in Each body is wrapped in a simple **bounding volume** that fully contains its collision shape. If two bounding volumes do not overlap, the shapes inside cannot touch, so the pair is rejected. If they do overlap, the shapes might touch, and the pair goes on. Three properties follow: - **False positives are acceptable.** A pair whose volumes overlap but whose shapes do not costs one wasted narrow-phase test. - **False negatives are bugs.** A pair the broad phase drops never reaches the narrow phase, so no contact is generated and the bodies pass through each other. - **Static-static pairs are skipped.** Two pieces of level geometry that never move never need a contact, so broad phases normally do not consider them at all. | Volume | Overlap test | Fit | Cost when the body rotates | |---|---|---|---| | Sphere | squared centre distance against the squared sum of radii | loose for long or flat shapes | none: a sphere is rotation-invariant | | Axis-aligned box (AABB) | two comparisons per axis, with early exit | good for axis-aligned shapes, looser as they rotate | must be recomputed for the new orientation | | Oriented box (OBB) | a separating-axis test over many candidate axes | tight for box-like shapes | rotates with the body, no refit | Axis-aligned boxes win in most broad phases. Their test is tiny, and boxes that share the same axes can be sorted along an axis, dropped into grid cells and nested inside one another in a tree, which are the three families of broad-phase structure. Spheres appear where bodies are roughly round or as an extra quick rejection. Oriented boxes are more at home inside the narrow phase than in front of it. ## Keeping the bounds current An AABB lives in world space, so it changes whenever its body moves or rotates. Common ways to refresh it: 1. **Rotate the local box's extents.** With column vectors and a rotation matrix `R` that maps body space to world space, a local box with half-extents `h` has world half-extents `abs(R) * h`, where `abs(R)` replaces every entry by its absolute value, centred on the transformed local centre. It is cheap and conservative, but looser than the shape. 2. **Ask the shape.** A sphere or capsule yields an exact box in a few operations; a convex hull can scan its vertices, which is exact but costs a pass over them. 3. **Enlarge it.** Many broad phases pad the box with a margin, or stretch it along the body's motion, so it stays valid for several steps. These are the "fat" bounds used by dynamic AABB trees. ## The structures that avoid visiting every pair Testing every pair of AABBs is still quadratic, just with a cheaper test. The real saving comes from organising the boxes so that far-apart pairs are never examined: - **Sweep-and-prune** sorts box endpoints along an axis and pairs only boxes whose intervals overlap. - **Uniform grids and spatial hashes** bucket boxes by cell, so only bodies sharing a cell are paired. - **Dynamic AABB trees** nest boxes in a hierarchy, so a query descends only into branches whose boxes overlap it. On well-spread scenes each brings the cost down to roughly linear or `n log n` in the number of bodies, plus the number of pairs reported. None of them can report fewer pairs than truly overlap: a heap of debris whose boxes overlap many neighbours stays expensive whichever structure holds it. ## What the broad phase hands on The output is a list, or a persistent set, of candidate pairs, often already filtered by collision groups so that, for example, small debris never pairs with other small debris. The narrow phase runs the exact test on each survivor and builds contact points for the solver. Keeping that list short, without ever dropping a real pair, is the broad phase's whole job.
- Why not use the tightest possible bounding volume, such as the convex hull itself?The broad phase runs its test on many more pairs than the narrow phase, so its test must be nearly free, and its volumes must sort, bucket or nest cleanly. A convex hull test costs about as much as the narrow phase it is meant to avoid. A slightly loose box that sends a few extra pairs on is cheaper overall than an exact volume tested everywhere.
- How does the broad phase handle a rotating body whose AABB keeps changing shape?It recomputes the world AABB each step from the shape and its orientation: for a box-like bound, the world half-extents are the absolute-valued rotation matrix times the local half-extents. Many broad phases also enlarge the box by a margin so small changes do not force a structure update every step; the box stays conservative, just looser.
- Where should collision-group filtering happen relative to the broad phase?As early as possible: either inside the broad phase, rejecting a pair before it is stored, or immediately after it, before any narrow-phase work. A pair the game never wants to collide, such as debris against debris, should never cost a cached entry or an exact shape test.
Before asking whether two guests at a huge conference have met, you only compare people standing in the same room: two guests in different rooms certainly are not talking, and two in the same room still need a closer look.
- Says the broad phase decides whether two bodies actually touch.
- Thinks occasional missed pairs are fine because the solver corrects penetration later.
- Believes an AABB stays valid when its body rotates.
- Claims testing every pair of AABBs is fine because the AABB test is cheap.
- Confuses broad-phase pair pruning with frustum culling for rendering.