How does a dynamic AABB tree with fat bounds keep broad-phase updates cheap when thousands of debris pieces move beside a static level?
answer
- leaves hold enlarged boxes
- reinsert only on escape
- insert by least area growth
- rotations keep it balanced
- static and dynamic trees apart
basics
~20 sA dynamic AABB tree stores each body as a leaf with an enlarged (fat) box, removes and reinserts it only when its tight box escapes, and keeps the static level in a separate tree that never queries itself.
solid answer
~50 sLeaves hold **fat** AABBs, the tight box enlarged by a margin and often stretched along the body's predicted motion, and each internal node holds the union of its children. Most steps a moving piece stays inside its fat box, so the tree does not change. When it escapes, the leaf is removed (its sibling takes the parent's place and the ancestors are refitted) and reinserted: descend toward the child whose box would grow least in surface area, pair the leaf with the chosen node under a new parent, then refit upward, applying **rotations** that swap a child with a grandchild when that shrinks a node, so the tree does not degenerate. Only moved leaves query, against both trees; the static level sits in its own rarely changing tree. The margin is the knob: larger means fewer reinserts but more false candidates. A shatter is a burst of inserts and of genuinely overlapping pairs.
go deeper
Recall that a dynamic AABB tree nests bodies' boxes in a hierarchy so that a query only visits branches whose boxes overlap.
Explain fat bounds, why a body is reinserted only when its tight box escapes, and the remove and insert steps.
Tune the margin against false candidates, keep static and dynamic trees apart, rebalance with rotations, and handle a shatter's burst of inserts and dense heap.
Choose the broad-phase structure for the game's body mix, and set debris policy, such as collision groups and piece lifetimes, that bounds the worst scene.
## The structure A **dynamic AABB tree** is a binary bounding volume hierarchy built for pair pruning while bodies move. Each **leaf** holds one body's box; each **internal node** holds the box that encloses both children. A query with a box starts at the root and descends only into children whose boxes overlap it, so far-away bodies are never visited. Unlike a hierarchy built once over a static model, it is updated one leaf at a time, every step, for as long as the level runs. ## Fat bounds The tree does not store a body's tight box. It stores a **fat** box: - the tight AABB enlarged by a fixed margin on every side, and often - stretched in the direction of the body's displacement over the next step, scaled by a small factor, so a fast piece does not escape at once. Each step the body's new tight box is computed. If it is still contained in the stored fat box, **nothing in the tree changes**. Only when it escapes is the leaf moved. For thousands of debris pieces that are slowing down or settling, almost every step touches only a few leaves. The margin is a trade: | Margin | Reinserts | Candidate pairs | |---|---|---| | Small | frequent, since boxes escape often | few false candidates | | Large | rare | more pairs whose fat boxes overlap but shapes are apart | ## Remove and insert **Remove** a leaf: its parent node disappears, the leaf's sibling takes the parent's place, and every ancestor's box is refitted on the way up. **Insert** a leaf: 1. Starting at the root, choose a child to descend into by a cost estimate, typically the **surface area** a node's box would gain by absorbing the new leaf, plus the growth already forced on the ancestors. Surface area serves as a proxy for how often a random query will visit a node. 2. At the chosen node, create a new internal node whose children are that node and the new leaf. 3. Walk back to the root, refitting each ancestor's box. With a balanced tree the descent and the refit are both proportional to the tree's height, about `log n`. ## Keeping it balanced Insert and remove alone can produce a lopsided tree. Debris thrown out in a line and inserted in order can build something close to a linked list, and every query then walks most of it. Two common remedies: - **Rotations** during the refit: at each ancestor, test whether swapping one child with a grandchild under its other child would reduce that child's surface area, and swap if it does. - **Height balancing**, rotating to keep the two children's heights within one of each other, as in a self-balancing search tree. Either keeps queries close to logarithmic without ever rebuilding the whole tree. ## Static geometry, sleeping bodies and queries - **Two trees.** The static level goes in its own tree. Static-static pairs never matter, so that tree is never queried against itself; it changes only when the level does, and it can be built top-down once for better quality. - **Only moved leaves query.** A dynamic leaf that was reinserted this step queries the dynamic tree and the static tree; new pairs go into the pair cache. Pairs between leaves that did not move are still valid. - **Sleeping bodies** do not move, so they never escape their fat boxes and cost no tree work until something wakes them. ## The shatter When a wall breaks into thousands of pieces, three costs arrive together: 1. **A burst of inserts.** Thousands of leaves enter the tree in one step. Building a subtree over the new pieces top-down and inserting it as one node is cheaper than inserting them one at a time. 2. **Fast pieces escape often.** Stretching fat boxes along each piece's velocity keeps them valid for a few steps. 3. **The clustered worst case.** As pieces pile up, their fat boxes overlap many neighbours, and those candidate pairs are real as far as any broad phase can tell. A tree still visits only overlapping branches, but a dense heap returns many pairs, and fat margins wider than the spacing between pieces multiply them. The fixes sit outside the tree: collision groups that stop small debris pairing with other small debris, merging or removing pieces after a while, and letting settled pieces sleep. A tree degrades more gracefully than a grid or a single sweep axis because it adapts to density, which is why it is a common default for games with widely varying body sizes.
- Why stretch a fat box along the body's velocity rather than just enlarging it evenly?A fast body escapes an evenly enlarged box within a step or two, forcing a remove and reinsert almost every step. Extending the box in the direction it is about to travel keeps it contained for longer, while adding little size in directions it is not moving, so false candidates grow less than with an equally large uniform margin.
- What goes wrong if the tree never rebalances?Insertion order shapes the tree. Bodies inserted along a line, such as debris thrown in one direction, can produce a chain whose height approaches the number of leaves, so every query and refit walks most of the tree and the broad phase approaches pairwise cost. Rotations or height balancing during refits prevent that.
- Why not refit the whole tree every step instead of removing and reinserting leaves?Refitting keeps the topology and only enlarges boxes, so as bodies drift apart from their original neighbours, internal nodes grow huge and queries visit many branches. Reinserting places a leaf beside bodies it is now near. With fat bounds most bodies need neither, and the few that escape are reinserted.
- Says every moving body is removed and reinserted every step.
- Thinks a larger fat margin can make the tree miss collisions.
- Puts static level geometry in the same tree and lets it query every step.
- Ignores rebalancing, assuming insertion order keeps the tree shallow.
- Believes a better tree can make a dense debris heap cheap.