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

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 (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.

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:

• 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 (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:

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) 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 (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 (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:

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:

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:

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 and updated using b3DynamicTree_MoveProxy (small movements) or b3DynamicTree_EnlargeProxy (large movements).
• The parallel b3FindPairsTask in 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) 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}