# How Box3D's Broad-Phase Dynamic AABB Tree Computes Collision Pairs

> Discover how Box3D's dynamic AABB tree computes collision pairs. Learn about its parallel processing for efficient overlap detection and filtering of unique pairs for narrow-phase collision.

- Repository: [Erin Catto/box3d](https://github.com/erincatto/box3d)
- Tags: deep-dive
- Published: 2026-08-01

---

**Box3D computes collision pairs by maintaining a dynamic AABB tree where each shape is a leaf node, then running a parallel task that queries the tree for overlapping leaf pairs and filters them through a callback to generate unique, valid collision pairs for the narrow-phase.**

Box3D is a lightweight 3D physics engine that uses a **dynamic AABB tree** as its broad-phase acceleration structure to efficiently compute potential collision pairs. The system incrementally updates the tree as bodies move and performs parallel queries against the tree to identify overlapping axis-aligned bounding boxes. Understanding this pipeline is essential for optimizing collision detection in physics simulations.

## Inserting Shapes into the Dynamic Tree

When a shape is created, Box3D inserts it into the broad-phase tree as a leaf node containing the shape’s **axis-aligned bounding box (AABB)** in world space.

### Creating Proxies with b3DynamicTree_CreateProxy

The entry point for adding a shape is `b3DynamicTree_CreateProxy` in [`src/dynamic_tree.c`](https://github.com/erincatto/box3d/blob/main/src/dynamic_tree.c) (lines 58–77). This function allocates a node via `b3AllocateNode`, stores the leaf’s AABB, category bits, and user data, then calls `b3InsertLeaf` to attach the leaf to the tree.

```c
int proxyId = b3DynamicTree_CreateProxy(&tree, aabb, categoryBits, userData);

```

### Balancing the Tree with b3InsertLeaf

The `b3InsertLeaf` function maintains tree balance using a **surface area heuristic (SAH)** to minimize query cost. The insertion process follows three stages:

- **Find sibling**: `b3FindBestSibling` (lines 165–205) performs a greedy walk down the tree to locate the existing node that would cause the smallest increase in surface area when the new leaf is added as a sibling.
- **Create parent**: A new internal node is allocated to serve as the parent of the leaf and its selected sibling (lines 226–244).
- **Walk up**: The function updates AABBs, heights, and category bits up the ancestor chain, optionally calling `b3RotateNodes` to improve balance (lines 265–284).

This SAH-based insertion ensures the tree remains balanced, keeping future overlap queries efficient.

## Updating AABB Proxies When Bodies Move

As bodies move, their AABBs change and the tree must be updated. Box3D provides two distinct update paths in [`src/dynamic_tree.c`](https://github.com/erincatto/box3d/blob/main/src/dynamic_tree.c):

- **Small movements**: `b3DynamicTree_MoveProxy` (lines 96–108) removes the leaf, updates its AABB, and reinserts it without performing rotations. This is the fast path for typical motion.
- **Large movements**: `b3DynamicTree_EnlargeProxy` (lines 110–138) climbs the ancestor chain and enlarges node AABBs only as necessary, avoiding the cost of full removal and reinsertion when the proxy has moved significantly.

## Querying the Tree for Collision Pairs

During each simulation step, the broad-phase identifies potential collision pairs by querying the tree for overlaps. This happens in parallel for all moved proxies.

### Parallel Pair Finding with b3FindPairsTask

The function `b3FindPairsTask` in [`src/broad_phase.c`](https://github.com/erincatto/box3d/blob/main/src/broad_phase.c) (lines 226–260) is executed as a parallel task for every proxy that has moved since the last step. For each moved proxy, it calls `b3DynamicTree_Query` to search the tree:

```c
static void b3FindPairsTask(int startIndex, int endIndex, int workerIndex, void *context)
{
    // Iterate over moved proxies
    b3DynamicTree_Query(&tree, aabb, maskBits, false, b3PairQueryCallback, &queryContext);
}

```

`b3DynamicTree_Query` (lines 94–150 in [`src/dynamic_tree.c`](https://github.com/erincatto/box3d/blob/main/src/dynamic_tree.c)) implements a depth-first stack walk that reports every leaf whose AABB overlaps the query AABB and whose category bits satisfy the mask.

### Filtering Pairs in b3PairQueryCallback

For each overlapping leaf found, `b3PairQueryCallback` in [`src/broad_phase.c`](https://github.com/erincatto/box3d/blob/main/src/broad_phase.c) (lines 57–124) determines whether to create a collision pair. The callback performs several filtering steps:

- **Compound handling**: If the queried shape is a compound, it recursively queries the compound’s internal tree with a transformed AABB.
- **Proxy-key ordering**: The callback enforces `proxyKey < queryProxyKey` to ensure each unordered pair is considered only once.
- **Moved-proxy check**: If both proxies are moving, the pair is skipped because it was already processed in a previous iteration.
- **Pair-set lookup**: `b3ContainsKey(&broadPhase->pairSet, pairKey)` prevents duplicate contacts that already exist in the simulation.
- **Collision filtering**: The system checks `b3ShouldShapesCollide`, `b3ShouldBodiesCollide`, sensor flags, joint overrides, and any user-defined `customFilterFcn` before recording the pair.

Valid pairs are stored in `broadPhase->movePairs` and linked into per-proxy result lists for consumption by the solver.

## Propagating Pairs to the Narrow-Phase

After all `b3FindPairsTask` jobs complete, the world step collects the results via `b3BroadPhase_CollectPairs`, called indirectly from `b3World_Step` in [`src/physics_world.c`](https://github.com/erincatto/box3d/blob/main/src/physics_world.c) (lines 1408–1460). This function transfers the recorded pairs from the broad-phase buffer to the solver, which then creates contact constraints and proceeds to narrow-phase collision detection.

## Code Examples

### Adding a Box Shape to the World

Creating a shape automatically inserts it into the dynamic AABB tree:

```c
b3ShapeDef shapeDef = b3DefaultShapeDef();
shapeDef.type = b3_boxShape;
shapeDef.box = (b3Box){ .hx = 0.5f, .hy = 0.5f, .hz = 0.5f };

int shapeId = b3World_CreateShape(world, &shapeDef);  // Internally calls b3DynamicTree_CreateProxy

```

### Stepping the Simulation

The broad-phase pair computation runs automatically during the world step:

```c
float dt = 1.0f / 60.0f;
b3World_Step(world, dt, velocityIterations, positionIterations);
// Inside: b3FindPairsTask queries the tree and filters pairs

```

### Implementing a Custom Collision Filter

You can reject pairs before they reach the solver by setting a custom filter function:

```c
bool MyFilter(b3ShapeId a, b3ShapeId b, void* ctx)
{
    // Reject collisions between objects in group 1
    return !(a.group == 1 && b.group == 1);
}

world->customFilterFcn = MyFilter;  // Called from b3PairQueryCallback

```

## Summary

- The **dynamic AABB tree** maintains a balanced bounding volume hierarchy using SAH-based insertion and optional rotations during `b3InsertLeaf`.
- Shape proxies are created via `b3DynamicTree_CreateProxy` in [`src/dynamic_tree.c`](https://github.com/erincatto/box3d/blob/main/src/dynamic_tree.c) and updated using `b3DynamicTree_MoveProxy` (small movements) or `b3DynamicTree_EnlargeProxy` (large movements).
- The parallel `b3FindPairsTask` in [`src/broad_phase.c`](https://github.com/erincatto/box3d/blob/main/src/broad_phase.c) queries the tree for each moved proxy using `b3DynamicTree_Query`, a depth-first stack traversal.
- `b3PairQueryCallback` eliminates duplicate pairs through proxy-key ordering and pair-set checks, then applies collision filters for sensors, joints, and user-defined rules.
- Valid pairs are collected by `b3BroadPhase_CollectPairs` and passed to the narrow-phase solver during `b3World_Step`.

## Frequently Asked Questions

### What is the SAH heuristic in Box3D's dynamic tree?

The **Surface Area Heuristic** minimizes the cost of tree queries by selecting sibling nodes during insertion that result in the smallest increase in bounding box surface area. This greedy strategy, implemented in `b3FindBestSibling`, keeps the tree balanced and ensures overlap queries examine fewer nodes.

### How does Box3D prevent duplicate collision pairs?

The engine prevents duplicates through three mechanisms: **proxy-key ordering** ensures only one thread processes a given unordered pair, a **moved-proxy check** skips pairs where both proxies were already processed in previous iterations, and a **pair-set hash table** (`b3ContainsKey`) verifies the pair does not already exist in the simulation.

### When should MoveProxy versus EnlargeProxy be used?

Use `b3DynamicTree_MoveProxy` for small movements where the AABB shift is minimal; it removes and reinserts the leaf quickly without rotations. Use `b3DynamicTree_EnlargeProxy` when the proxy has moved significantly or the AABB has grown substantially, as it simply expands ancestor node AABBs without the overhead of reinsertion.

### How do custom collision filters affect broad-phase pair generation?

Custom filters set via `world->customFilterFcn` are called within `b3PairQueryCallback` (lines 84–96 in [`src/broad_phase.c`](https://github.com/erincatto/box3d/blob/main/src/broad_phase.c)) after the engine performs its internal filtering. Returning `false` from your filter function prevents that specific pair from being recorded in `movePairs`, effectively excluding it from narrow-phase processing without modifying the tree structure.