Bounding volume hierarchy

Deep dive

How it works

In: boxes to insert, remove or move, plus a query box or ray · Out: ids of the boxes it overlaps (or the nearest ray hit) · State: the tree (box, parent, children per node), kept between calls · Cost: query O(log n + k), insert/remove O(log n)

Dynamic AABB tree (incremental)

1. Insert: descend from the root. At node N with box B, the cost of making the new leaf L N's sibling is 2·area(B ∪ L); descending costs the area growth inside the chosen child plus 2·(area(B ∪ L) − area(B)) inherited by all ancestors. Stop where creating a sibling is cheapest, splice in a new parent, refit boxes up to the root.
2. Remove: delete the leaf and its parent; the sibling takes the parent's place; refit upward.
3. Move: if the new tight box is still inside the stored fat box, do nothing. Otherwise remove and reinsert with a new fat box (margin plus predicted displacement).
4. Pairs: for each proxy that moved this frame, query the tree with its fat box; collect pairs into a set (sort + dedupe).
5. Balance: greedy insertion can degrade under adversarial orders; tree rotations at refit time (swap a child with a grandchild if it lowers area) keep it shallow.

Static BVH (top-down build): recursively split the primitive set; choose the split that minimises the surface area heuristic cost = C_trav + (A_left/A_parent)·N_left·C_isect + (A_right/A_parent)·N_right·C_isect, evaluated on a few bins of centroid positions per axis (binned SAH). Stop when splitting costs more than a leaf.

              [A∪B∪C∪D]
             /          \
        [A∪B]            [C∪D]          query box overlaps [A∪B] only:
        /    \           /    \         C and D are never touched
      [A]    [B]       [C]    [D]

Code

#[derive(Clone, Copy, Debug)]
pub struct Aabb { pub min: [f32; 3], pub max: [f32; 3] }

impl Aabb {
    fn union(&self, o: &Aabb) -> Aabb {
        let mut r = *self;
        for k in 0..3 { r.min[k] = r.min[k].min(o.min[k]); r.max[k] = r.max[k].max(o.max[k]); }
        r
    }
    fn area(&self) -> f32 { // half the surface area: the SAH cost unit
        let d = [self.max[0] - self.min[0], self.max[1] - self.min[1], self.max[2] - self.min[2]];
        d[0] * d[1] + d[1] * d[2] + d[2] * d[0]
    }
    fn overlaps(&self, o: &Aabb) -> bool {
        (0..3).all(|k| self.min[k] <= o.max[k] && o.min[k] <= self.max[k])
    }
}

const NULL: u32 = u32::MAX;

#[derive(Clone, Copy)]
struct Node { aabb: Aabb, parent: u32, left: u32, right: u32 } // leaf: left == NULL

pub struct DynamicTree { nodes: Vec<Node>, free: Vec<u32>, root: u32 }

impl DynamicTree {
    pub fn new() -> Self { DynamicTree { nodes: Vec::new(), free: Vec::new(), root: NULL } }

    fn alloc(&mut self, n: Node) -> u32 {
        if let Some(i) = self.free.pop() { self.nodes[i as usize] = n; i }
        else { self.nodes.push(n); (self.nodes.len() - 1) as u32 }
    }
    fn is_leaf(&self, i: u32) -> bool { self.nodes[i as usize].left == NULL }

    /// Insert a (fattened) box; returns the proxy id.
    pub fn insert(&mut self, aabb: Aabb) -> u32 {
        let leaf = self.alloc(Node { aabb, parent: NULL, left: NULL, right: NULL });
        if self.root == NULL { self.root = leaf; return leaf; }
        // Greedy descent (Box2D v2 style): stop where making a sibling here is cheaper
        // than paying the area increase of descending into either child.
        let mut idx = self.root;
        while !self.is_leaf(idx) {
            let n = self.nodes[idx as usize];
            let combined = n.aabb.union(&aabb).area();
            let cost_here = 2.0 * combined;
            let inherit = 2.0 * (combined - n.aabb.area()); // ancestors grow regardless
            let child_cost = |c: u32| {
                let cb = self.nodes[c as usize].aabb;
                let grow = if self.is_leaf(c) { cb.union(&aabb).area() }
                           else { cb.union(&aabb).area() - cb.area() };
                grow + inherit
            };
            let (c1, c2) = (child_cost(n.left), child_cost(n.right));
            if cost_here < c1 && cost_here < c2 { break; }
            idx = if c1 < c2 { n.left } else { n.right };
        }
        // Replace `idx` by a new internal node holding (idx, leaf).
        let old_parent = self.nodes[idx as usize].parent;
        let joined = self.nodes[idx as usize].aabb.union(&aabb);
        let p = self.alloc(Node { aabb: joined, parent: old_parent, left: idx, right: leaf });
        self.nodes[idx as usize].parent = p;
        self.nodes[leaf as usize].parent = p;
        if old_parent == NULL { self.root = p; } else {
            let op = &mut self.nodes[old_parent as usize];
            if op.left == idx { op.left = p } else { op.right = p }
        }
        self.refit(old_parent);
        leaf
    }

    pub fn remove(&mut self, leaf: u32) {
        self.free.push(leaf);
        if leaf == self.root { self.root = NULL; return; }
        let p = self.nodes[leaf as usize].parent;
        let pn = self.nodes[p as usize];
        let sibling = if pn.left == leaf { pn.right } else { pn.left };
        self.free.push(p);
        self.nodes[sibling as usize].parent = pn.parent; // sibling takes the parent's place
        if pn.parent == NULL { self.root = sibling; return; }
        let gp = &mut self.nodes[pn.parent as usize];
        if gp.left == p { gp.left = sibling } else { gp.right = sibling }
        self.refit(pn.parent);
    }

    fn refit(&mut self, mut i: u32) {
        while i != NULL {
            let n = self.nodes[i as usize];
            self.nodes[i as usize].aabb =
                self.nodes[n.left as usize].aabb.union(&self.nodes[n.right as usize].aabb);
            i = n.parent;
        }
    }

    /// Visit every leaf whose box overlaps `q`. Explicit stack, no recursion.
    pub fn query(&self, q: &Aabb, mut f: impl FnMut(u32)) {
        if self.root == NULL { return; }
        let mut stack = vec![self.root];
        while let Some(i) = stack.pop() {
            let n = &self.nodes[i as usize];
            if !n.aabb.overlaps(q) { continue; }
            if n.left == NULL { f(i) } else { stack.push(n.left); stack.push(n.right); }
        }
    }
}

Complexity and constants

• Query: O(log n + k) when boxes are well separated; worst case O(n) when everything overlaps the query.
• Insert/remove: O(depth) for descent and refit; depth stays near log₂ n only if insertion order is benign or rotations rebalance.
• Each visited node costs one box test (6 compares) and usually one cache miss: the tree is pointer-chasing, so node layout dominates.
• Static binned-SAH build: O(n log n); LBVH (sort by Morton code, split at the highest differing bit) is O(n) after a radix sort and parallelises fully on GPU, at lower tree quality.

Efficiency

• Cost: a query visits order of log₂ n nodes plus the candidates; each visited node is one 6-compare box test and usually one cache miss, so the bound is memory latency, not arithmetic. A node is order of 32-48 bytes. Updates are free while an object stays inside its fat box.
• Levers:
  • fat boxes — skips tree updates for slow objects (Box2D margin 0.1 m) — moving bodies
  • 4- or 8-wide nodes with SoA boxes — half the depth and one SIMD pass per node (Embree, Jolt) — static or rebuilt-per-frame scenes
  • separate static and dynamic trees — static-vs-static pairs never queried (Box2D v3) — mixed scenes
  • bulk build instead of one-by-one insert — Jolt documents one-at-a-time adds as an inefficient tree and offers batch add and OptimizeBroadPhase (Jolt docs) — scene loading
  • binned SAH for quality, LBVH (Morton sort, O(n), parallel) for speed (Karras 2012) — static meshes vs fully dynamic scenes
• Naive → standard → state of the art:
  • test all pairs · O(n²) box tests
  • dynamic AABB tree, area-greedy insert, fat boxes · O(log n + k) query, O(log n) update
  • branch-and-bound insertion with rotations (Bittner 2013) or wide SIMD BVH with SAH/LBVH builds (Embree) · better trees, fewer cache misses per query

Implementation notes

• Node pool: nodes in one Vec, u32 indices, free list. No Box per node; indices survive reallocation and halve pointer size.
• Fat boxes: margin (Box2D: 0.1 m) plus the predicted displacement. Box2D v2 extends the box by 4× the displacement in the direction of motion. Larger margins mean fewer reinserts but more false pairs for the narrowphase.
• Moved buffer: keep the list of proxies reinserted this frame; only those query the tree. Sleeping and static bodies cost zero.
• Separate trees for static and dynamic proxies (Box2D v3 uses one tree per body type): static-vs-static pairs are never queried, and the static tree can be built once with SAH.
• Wide nodes: 4- or 8-wide nodes with children boxes in SoA layout (min_x[4], max_x[4], ...) test all children in one SIMD pass; halves depth and cache misses. Used by ray tracers (BVH4/BVH8) and Jolt's quad-tree broadphase.
• Ray cast: precompute 1/dir, slab test per node, visit the nearer child first, and shrink t_max as hits are found.
• Stack: a fixed array of 64-256 entries suffices in practice; a degenerate tree can exceed it, so fall back to a Vec or assert depth.

Pitfalls

• Reinserting every moving object every frame without fat boxes: tree churn dominates the step.
• Insertion in sorted spatial order (e.g. loading a grid of tiles) builds a degenerate, list-like tree without rotations or a bulk SAH build.
• Querying with each moved proxy and also from the partner side: report pairs once (dedupe with a sorted pair list or a hash set keyed by (min_id, max_id)).
• Using a Vec-allocated stack per query in the hot loop: allocation shows up in profiles; reuse a buffer.
• NaN positions poison min/max in refit and silently break queries for whole subtrees; validate body positions.

Variants and alternatives

In production

Physics engines: Box2D (b2DynamicTree), Bullet (btDbvt), Jolt Physics (4-wide quad-tree broadphase), PhysX scene queries (AABB-tree pruners). Ray tracing: Embree (BVH4/BVH8 over triangles, Wald 2014), the pbrt book's BVH chapter, GPU ray tracers with hardware RT cores. Robotics: MuJoCo mid-phase collision uses a static AABB tree per body (docs); FCL and its fork Coal check mesh collisions for motion planning, and MoveIt 2 ships an FCL collision plugin (moveit_core/collision_detection_fcl). CAD and geometry: the CGAL AABB tree answers ray, segment and closest-point queries on meshes, with a mechanical part as its example (docs). Databases: PostGIS indexes spatial data with an R-tree on top of GiST (docs).

Implementations

Sources

• Christer Ericson, Real-Time Collision Detection, Morgan Kaufmann, 2005 (ch. 6).
• Jeffrey Goldsmith, John Salmon, Automatic Creation of Object Hierarchies for Ray Tracing, IEEE CG&A, 1987. paper
• Ingo Wald, On fast Construction of SAH-based Bounding Volume Hierarchies, IEEE Symposium on Interactive Ray Tracing, 2007. paper
• Tero Karras, Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees, HPG 2012.
• Jiří Bittner, Michal Hapala, Vlastimil Havran, Fast Insertion-Based Optimization of Bounding Volume Hierarchies, Computer Graphics Forum, 2013. paper
• Daniel Kopta, Thiago Ize, Josef Spjut, Erik Brunvand, Al Davis, Andrew Kensler, Fast, Effective BVH Updates for Animated Scenes, I3D 2012. paper
• Erin Catto, Dynamic Bounding Volume Hierarchies, GDC 2019.
• Ingo Wald, Sven Woop, Carsten Benthin, Gregory S. Johnson, Manfred Ernst, Embree: A Kernel Framework for Efficient CPU Ray Tracing, ACM TOG 2014. paper · code
• Matt Pharr, Wenzel Jakob, Greg Humphreys, Physically Based Rendering, 4th ed., 2023, section 7.3. online