Lesson 2

Broadphase and filtering

Turning n² possible pairs into the few dozen worth testing: bounding boxes, sort and sweep, the trees real engines use, fattened bounds, and collision filtering with categories, masks and Jolt's two kinds of layer.

With n bodies there are n(n − 1)/2 pairs. A hundred and fifty bodies make over eleven thousand pairs, and at any moment a few dozen of them are close enough to touch. The broadphase finds those few dozen without testing the rest. It’s the spatial partitioning lesson applied to one specific question, asked every step: which bounding boxes overlap?

Bounding boxes

Every body gets an axis-aligned bounding box (AABB): the smallest box, aligned with the world axes, that contains its shape at its current position. Two AABBs overlap if and only if their intervals overlap on every axis, which is four comparisons in 2D. If the boxes don’t overlap, the shapes can’t touch, so the expensive exact test only runs on pairs whose boxes do.

Switch between Every pair and Sort and sweep. Over two seconds of this box, testing every pair makes about 11,775 box tests a step; sort and sweep makes about 848. Both find the same 26.1 overlapping pairs a step on average: the broadphase changes the cost, never the answer. Try 400 bodies to see the gap widen.

Sort and sweep

Sort and sweep (also called sweep and prune) sorts the boxes by their left edge. Walking the sorted list, each box only needs comparing with the boxes after it whose left edge comes before its right edge; the first box that starts past its right edge ends the scan. The trick that makes it cheap in a physics engine is coherence: bodies barely move between steps, so last step’s order is almost sorted, and an insertion sort fixes it in close to linear time. This page keeps the order between steps for exactly that reason.

It degrades when many boxes line up along the sort axis (a long row of crates on the x axis all overlap in x), which is why real engines prefer trees.

Trees, fattened boxes and layers

The engines you’d use in a game keep their AABBs in trees:

• Box2D and Box3D use a dynamic AABB tree: a bounding volume hierarchy updated incrementally as bodies move, with separate trees for static, kinematic and dynamic bodies, so static geometry is never re-tested against itself.
• Jolt uses quad trees (four children per node), one per broadphase layer. Bodies are best added in batches (AddBodiesPrepare can run on a background thread, AddBodiesFinalize then inserts them atomically), because adding them one at a time builds an inefficient tree.
• PhysX defaults to a broadphase called PABP (parallel automatic box pruning, a multithreaded descendant of sort and sweep).

Trees store fattened boxes: each leaf is the shape’s AABB grown by a margin, often extended along the body’s velocity. A body only needs re-inserting when it leaves its fat box, so most steps change nothing in the tree. The cost is a few extra candidate pairs that the narrowphase rejects.

The spatial partitioning lesson compares grids, quadtrees, BVHs and sweep and prune against each other, and every one of them works as a physics broadphase.

Filtering

Not everything should collide with everything. Debris shouldn’t block the player; a sensor volume should detect characters but not push them; a character’s own ragdoll shouldn’t collide with its capsule. The cheapest place to drop those pairs is the broadphase, before any shape test runs.

Untick blue with orange above: the two layers pass through each other, the orange ones still bounce off each other, and the overlap count falls because those pairs are never generated.

The common scheme, used by Box2D and Box3D, is categories and masks: each shape has a category bit set and a mask of the categories it collides with, and a pair collides only if each one’s category is in the other’s mask.

bool should_collide(const Filter& a, const Filter& b) {
    return (a.category & b.mask) != 0 && (b.category & a.mask) != 0;
}

Jolt splits the idea in two:

• Object layers say what collides with what. An ObjectLayerPairFilter answers ShouldCollide(layerA, layerB).
• Broadphase layers say which tree a body lives in. A BroadPhaseLayerInterface maps each object layer to exactly one broadphase layer, and an ObjectVsBroadPhaseLayerFilter says which trees a layer needs to look in. Keep these few: two (moving and non-moving) is the usual start.

Splitting static and moving bodies into separate trees means the static tree, often the largest, never changes and never needs testing against itself. After layers, Jolt filters further by group, then by body (in queries), then by shape, and finally a ContactListener can still reject a contact after it’s found. Each stage is more expensive and more specific than the last.

Takeaways

• The broadphase turns n² pairs into the few that might touch, using bounding boxes.
• Sort and sweep exploits coherence; trees with fattened boxes are what engines ship, with static and moving bodies kept apart.
• Filter in the broadphase: categories and masks, or Jolt’s object and broadphase layers.