Spatial Partitioning

01Why partition space

A level has 5,000 crates, barrels and ragdolls, and every frame the physics engine needs to know which ones are touching. Testing every object against every other is O(n²). A physics scene with 5,000 dynamic bodies produces 12.5 million pair tests per frame. At 60 fps on a single core that is roughly 750 million tests per second, each one requiring at least an AABB overlap check (up to six comparisons in 3D). Most of those pairs are nowhere near each other. The purpose of spatial partitioning is to skip them.

The split between broad phase and narrow phase exists for exactly this reason. The broad phase uses a spatial data structure to reduce n² candidate pairs to something closer to n or n log n, then the narrow phase runs the expensive per-pair geometry tests only on the surviving candidates.

The same structures serve other queries. Frustum culling walks the tree and prunes entire branches whose bounding volumes lie outside the camera frustum. Raycasting (mouse picking, line-of-sight checks, bullet traces) traverses the tree along the ray and skips volumes the ray does not intersect. Range queries ("give me every unit within 50 meters of this position") descend into nodes that overlap the query sphere and skip the rest. K-nearest-neighbor queries do the same with a shrinking search radius.

Without an acceleration structure, each of those queries is O(n). With one, the average case drops to O(log n) for tree-based structures or O(1) for hash-based structures, at the cost of O(n) or O(n log n) construction time and O(n) storage.

02A short history

Why does a 1993 shooter's level format contain a tree, and why do today's ray-tracing GPUs walk one in hardware? Spatial data structures emerged from three separate communities: computer graphics (visibility), computational geometry (range searching), and database indexing (spatial queries).

The engine-relevant milestones: BSP trees (1980)^[2] and Doom's use of them (1993)^[7], octrees (1982)^[1], automatic BVH construction with surface area as its cost (1987)^[5], loose octrees (2000)^[8], binned SAH fast enough for per-frame rebuilds (2007)^[9], and BVH traversal in GPU hardware (2018)^[19].

03Uniform grids

A top-down shooter has a few hundred bullets and enemies, all about the same size, and needs every bullet-enemy hit each frame. The simplest spatial structure for that: divide the world into a fixed grid of equal-sized cells. Each cell holds a list of objects whose centers (or bounding volumes) overlap that cell. Insert is O(1): hash the object's position to a cell index, append. Query is O(1) in the number of cells checked: compute which cells the query region overlaps, iterate their contents.

The spatial hash function maps cell coordinates to a flat array index. The usual choice is ((cellX * 73856093) ^ (cellY * 19349663)) % tableSize; the outer parentheses matter, because in C, C++ and Rust % binds tighter than ^. Those two constants are the primes Teschner et al. published in 2003 for exactly this problem, along with 83492791 for the third dimension^[3]. The paper is candid about where they came from: the authors call them "large prime numbers, in our case" those three, say they "have not systematically investigated the characteristics of hash functions", and report that hash quality matters less as the table grows. They are a working choice, not a derived optimum.

Grids win when the objects are roughly uniform in size and roughly uniform in distribution. Particle systems are the canonical example: thousands of similar-sized particles spread over the simulation domain. 2D games where entities are all within a factor of two in bounding-box size (top-down shooters, roguelikes, RTS unit collision) also fit well.

The failure mode is the large-object problem. An object that spans many cells must be inserted into all of them, and every query that touches any of those cells finds it. A single large terrain chunk in a grid of small cells can appear in hundreds of cells, multiplying both insertion cost and query noise. Hierarchical grids (multiple grid resolutions, one per object-size class) mitigate this at the cost of multiple lookups per query.

04Quadtrees

An RTS map has dense clusters of units around bases and wide stretches of empty ground, and a uniform grid spends as much on the empty ground as on the bases. A quadtree recursively subdivides 2D space into four quadrants. Each internal node has exactly four children (NW, NE, SW, SE). Objects are inserted into the deepest node that fully contains them. When a leaf exceeds a capacity threshold, it subdivides.

Two flavors exist. A point quadtree stores point data; each split plane passes through a stored point. A region quadtree splits space uniformly at the midpoint of each axis, regardless of where the points are. Region quadtrees are the usual choice in engines: the split positions are implicit (computable from the node's bounds), so the tree stores no split-plane data.

Depth limits prevent degenerate input (many objects at the same position) from producing infinite recursion. A typical max depth of 8 gives 2⁸ = 256 leaf cells per axis, fine resolution for most 2D scenes. The per-leaf capacity (max objects before subdivision) is usually between 4 and 16.

In the widget below, each click places an entity, and a leaf subdivides as soon as it overflows.

Grid vs quadtree: range query comparison

The practical question is how much each structure touches to answer a range query. A grid visits every cell the query rectangle overlaps, whether those cells hold objects or not. A region quadtree never subdivides empty space, so an empty area is a few large leaves and a query there touches a handful of nodes. Over a dense cluster the balance flips: the quadtree walks down through internal nodes to reach small leaves and can visit more nodes than the grid has cells under the query. For roughly uniform distributions the grid usually wins outright, since it has no traversal at all.

#include <cstddef>
#include <memory>
#include <vector>

struct Entity { float posX, posY; };
struct AABB   { float minX, minY, maxX, maxY; };

struct QuadTreeNode {
    AABB bounds;
    int depth;
    int maxDepth;
    std::size_t maxPerLeaf;   // compared against items.size(), so unsigned like it
    std::vector<Entity*> items;
    std::unique_ptr<QuadTreeNode> children[4]; // NW, NE, SW, SE

    bool contains(float px, float py) const {
        return px >= bounds.minX && px < bounds.maxX
            && py >= bounds.minY && py < bounds.maxY;
    }

    // Children must inherit the limits, or the recursion tests garbage.
    std::unique_ptr<QuadTreeNode> makeChild(AABB childBounds) const {
        auto node = std::make_unique<QuadTreeNode>();
        node->bounds     = childBounds;
        node->depth      = depth + 1;
        node->maxDepth   = maxDepth;
        node->maxPerLeaf = maxPerLeaf;
        return node;
    }

    void subdivide() {
        float midX = (bounds.minX + bounds.maxX) * 0.5f;
        float midY = (bounds.minY + bounds.maxY) * 0.5f;
        children[0] = makeChild({bounds.minX, bounds.minY, midX, midY});
        children[1] = makeChild({midX, bounds.minY, bounds.maxX, midY});
        children[2] = makeChild({bounds.minX, midY, midX, bounds.maxY});
        children[3] = makeChild({midX, midY, bounds.maxX, bounds.maxY});

        // Re-insert existing items into children
        for (Entity* entity : items) {
            for (auto& child : children) {
                if (child->contains(entity->posX, entity->posY)) {
                    child->insert(entity);
                    break;
                }
            }
        }
        items.clear();
    }

    void insert(Entity* entity) {
        if (!contains(entity->posX, entity->posY)) return;

        // Leaf: store here if under capacity or at max depth
        if (!children[0] && (items.size() < maxPerLeaf || depth >= maxDepth)) {
            items.push_back(entity);
            return;
        }
        if (!children[0]) subdivide();

        for (auto& child : children) {
            if (child->contains(entity->posX, entity->posY)) {
                child->insert(entity);
                return;
            }
        }
    }

    // Range query: collect all entities whose positions fall inside queryBox.
    void query(const AABB& queryBox, std::vector<Entity*>& results) const {
        // Prune: if this node does not overlap the query, skip entirely
        if (queryBox.maxX < bounds.minX || queryBox.minX > bounds.maxX ||
            queryBox.maxY < bounds.minY || queryBox.minY > bounds.maxY) return;

        for (Entity* entity : items) {
            if (entity->posX >= queryBox.minX && entity->posX <= queryBox.maxX &&
                entity->posY >= queryBox.minY && entity->posY <= queryBox.maxY) {
                results.push_back(entity);
            }
        }

        if (children[0]) {
            for (const auto& child : children) {
                child->query(queryBox, results);
            }
        }
    }
};

#[derive(Clone, Copy)]
struct Entity { pos_x: f32, pos_y: f32 }

#[derive(Clone, Copy)]
struct AABB { min_x: f32, min_y: f32, max_x: f32, max_y: f32 }

struct QuadTreeNode {
    bounds: AABB,
    depth: u32,
    max_depth: u32,
    max_per_leaf: usize,
    items: Vec<Entity>,
    children: Option<Box<[QuadTreeNode; 4]>>,
}

impl QuadTreeNode {
    // Children inherit the limits, matching makeChild in the C++ pane.
    fn subdivide(&mut self) {
        let mid_x = (self.bounds.min_x + self.bounds.max_x) * 0.5;
        let mid_y = (self.bounds.min_y + self.bounds.max_y) * 0.5;
        let quadrant = |min_x, min_y, max_x, max_y| QuadTreeNode {
            bounds: AABB { min_x, min_y, max_x, max_y },
            depth: self.depth + 1,
            max_depth: self.max_depth,
            max_per_leaf: self.max_per_leaf,
            items: Vec::new(),
            children: None,
        };
        self.children = Some(Box::new([
            quadrant(self.bounds.min_x, self.bounds.min_y, mid_x, mid_y),
            quadrant(mid_x, self.bounds.min_y, self.bounds.max_x, mid_y),
            quadrant(self.bounds.min_x, mid_y, mid_x, self.bounds.max_y),
            quadrant(mid_x, mid_y, self.bounds.max_x, self.bounds.max_y),
        ]));
    }

    fn contains(&self, px: f32, py: f32) -> bool {
        px >= self.bounds.min_x && px < self.bounds.max_x
            && py >= self.bounds.min_y && py < self.bounds.max_y
    }

    fn insert(&mut self, entity: Entity) {
        if !self.contains(entity.pos_x, entity.pos_y) { return; }

        if self.children.is_none()
            && (self.items.len() < self.max_per_leaf
                || self.depth >= self.max_depth)
        {
            self.items.push(entity);
            return;
        }
        if self.children.is_none() { self.subdivide(); }

        let children = self.children.as_mut().unwrap();
        for child in children.iter_mut() {
            if child.contains(entity.pos_x, entity.pos_y) {
                child.insert(entity);
                return;
            }
        }
    }

    // The named lifetime is required: every reference pushed into `results`
    // borrows from `self`, and an elided lifetime would be a fresh one with
    // no relation to `&self`. `&mut Vec<&Entity>` is invariant in its element
    // type, so the compiler cannot silently coerce one into the other.
    fn query<'a>(&'a self, query_box: &AABB, results: &mut Vec<&'a Entity>) {
        // Prune: no overlap with this node
        if query_box.max_x < self.bounds.min_x
            || query_box.min_x > self.bounds.max_x
            || query_box.max_y < self.bounds.min_y
            || query_box.min_y > self.bounds.max_y
        { return; }

        for entity in &self.items {
            if entity.pos_x >= query_box.min_x
                && entity.pos_x <= query_box.max_x
                && entity.pos_y >= query_box.min_y
                && entity.pos_y <= query_box.max_y
            {
                results.push(entity);
            }
        }

        if let Some(children) = &self.children {
            for child in children.iter() {
                child.query(query_box, results);
            }
        }
    }
}

05Octrees

A 3D world adds height: a flying drone, a multi-story building, a cave under a mountain. An octree is a quadtree in three dimensions. Each node splits into eight children (2³). Insert, remove, and query follow the same logic, with an extra axis.

Two storage layouts are common. A pointer-based octree stores eight child pointers per node, same as the quadtree above. A linear octree encodes each node's position as a Morton code and stores all nodes in a flat sorted array. The Morton code (the index along a Z-order curve) interleaves the bits of the x, y, z cell coordinates. A parent's code is its child's code shifted right by three bits, and neighbors are found with bit arithmetic on the interleaved coordinates, so no pointer is ever dereferenced.

Linear layouts matter for GPU work, and three GPU structures that are often lumped together use them differently. Morton-ordered linear hierarchies are the LBVH line: Lauterbach et al. sort primitives by Morton code to build a hierarchy in parallel^[10], and Karras builds every level at once from a binary radix tree over those codes^[11]. Sparse voxel octrees are a different design: Laine and Karras encode topology with 64-bit child descriptors carrying a valid mask, a leaf mask, and a relative child pointer, not with Morton codes^[12]. NVIDIA's GVDB takes a third route: the VDB topology, a sparse hierarchy of grids whose branching factor is configurable per level, indexing into a voxel atlas and built for volumes whose topology changes every frame. An octree is the special case with a branching factor of two per axis, and GVDB's programming guide notes that such a tree "quickly requires more than 5 levels", its default depth limit, so the usual configurations branch much wider^[13].

On the CPU, engine octrees are usually depth-limited and stored either with child pointers or in flat arrays addressed by index. Unreal's generic octree, TOctree2, is the second kind: its nodes live in a TArray with parent links and a free list, which is cheaper to update in place than a web of heap-allocated nodes^[25].

06BSP trees

Without a depth buffer, a renderer has to draw walls in the right order from any viewpoint, or near walls get painted over by far ones. A BSP tree partitions space with arbitrary hyperplanes, not axis-aligned splits. Each internal node stores a plane (in 2D, a line; in 3D, a plane equation ax + by + cz + d = 0). Objects or polygon fragments are classified to the front or back half-space; objects that straddle the plane are split.

The rendering trick: given a viewpoint, traverse the BSP tree in a specific order. If the viewpoint is in front of a node's plane, draw the back subtree first, then the node's polygon, then the front subtree. This gives a back-to-front ordering suitable for the painter's algorithm (draw the farthest surfaces first and let nearer ones paint over them), without a depth buffer, the per-pixel record of the nearest surface drawn so far. For a node whose plane is x − 5 = 0, a viewpoint at (8, 0, 2) gives 8 − 5 = 3, positive, so it's in front: draw the back subtree, then the node's wall, then the front subtree.

Doom (1993) and Quake (1996) depended on BSP trees. The BSP gave Doom's renderer an exact wall order from any viewpoint without a per-pixel depth buffer^[7]. The tree was built offline by the node builder and shipped in the WAD file (the NODES, SSECTORS and SEGS lumps). Doom's renderer reversed the traversal to front-to-back and tracked which screen columns were already fully drawn, so it could stop as soon as the screen was covered instead of overdrawing the way back-to-front painting does. Quake extended BSP with a PVS (potentially visible set), precomputed per BSP leaf. At runtime one decompressed bit row per frame ruled out whole sections of the level.

BSP trees are mostly historical for rendering (modern engines use BVH-based frustum culling and GPU occlusion queries). They remain relevant for CSG (constructive solid geometry) operations: boolean union, intersection, and difference of 3D meshes. Unreal's BSP-based level geometry workflow still exists, though static meshes have replaced it for most content.

07Bounding volume hierarchies

A BVH is a tree of bounding volumes, and it's what a ray tracer uses to avoid testing a ray against a million triangles. Each leaf holds one object (or a small cluster). Each internal node holds the bounding volume that encloses all objects in its subtree. The bounding volume is almost always an AABB because AABB-AABB overlap is six comparisons and AABB-ray intersection (the slab method) is fast and branchless.

Construction is top-down or bottom-up. Top-down: start with all objects, pick a split (axis and position), partition into left and right, recurse. Bottom-up (agglomerative): start with one leaf per object, repeatedly merge the two nodes whose combined bounding volume is smallest. Top-down is simpler and faster to build. Bottom-up can produce tighter trees, but the naive version rescans every pair before each of its n−1 merges, which is O(n³); practical builders cache each cluster's nearest neighbor or search only nearby clusters to bring that down.

Top-down split strategies:

• Median split. Sort objects along the longest axis, split at the median. Produces balanced trees. Simple, O(n log n) per level.
• Midpoint split. Split at the spatial midpoint of the node's bounding volume. Faster than median (no sort), but can produce unbalanced trees if objects are clustered.
• SAH split. Evaluate a cost function at many candidate split positions, pick the one that minimizes expected traversal cost. The surface area heuristic (next section).

The widget below shows a BVH being constructed step by step. Each step picks an axis, evaluates a split, and partitions the objects. The bounding boxes of the resulting nodes are drawn.

In RTX hardware ray tracing, the BVH has two levels. The TLAS (top-level acceleration structure) stores instance transforms and pointers to BLASes. The BLAS (bottom-level acceleration structure) stores the actual triangle geometry for each mesh. Rebuilding the TLAS per frame is cheap (it contains only instance data). Rebuilding a BLAS means processing every triangle of the mesh, so static geometry builds the BLAS once and reuses it.

08Surface area heuristic

The SAH cost model estimates the expected number of node intersection tests a random ray will perform. The key insight is that the probability a uniformly random ray hits a convex bounding volume is proportional to its surface area. The credit is usually given to Goldsmith and Salmon (1987)^[5], who applied it to hierarchy construction; MacDonald and Booth's fuller derivation traces the surface-area-as-probability result itself back to Stone (1975)^[6]. In 2D, surface area is the perimeter; in 3D, the actual surface area.

For a node with bounding volume A containing children L and R, the formula below estimates what a split costs a random ray:

In words: pay once to visit the node, then pay for each child's objects weighted by the chance a ray that hits the parent also hits that child. SA(X) is the surface area of bounding volume X. N_L and N_R are the object counts in the left and right children. C_trav is the cost of traversing one internal node; C_isect is the cost of intersecting one leaf object. The ratio SA(L)/SA(A) is the conditional probability that a ray hitting A also hits L.

The builder evaluates this cost for many candidate splits (every object boundary on each axis, or a fixed number of bins), picks the split with the lowest cost, and recurses. If no split is cheaper than making the node a leaf, the node becomes a leaf.

Binned SAH (Wald 2007^[9]) approximates the exact evaluation by distributing objects into a fixed number of bins (typically 8 to 32) along each axis. The cost is evaluated at each bin boundary, not at every object boundary. This reduces the per-level cost from O(n log n) to O(n). In Wald's tests, a 252K-triangle animated model was rebuilt every frame in under 20 ms, which moved SAH quality into per-frame rebuilds.

09BVH traversal

A player fires a hitscan rifle, and the game needs the nearest thing along that line out of tens of thousands of objects. The canonical BVH traversal for ray queries is a stack-based depth-first search. It pushes the root, then loops: pop a node and test the ray against its AABB; on a miss, discard it; on a hit at a leaf, test the ray against the leaf's objects; on a hit at an internal node, push both children. The stack never holds more entries than the tree is deep plus one, and a million-primitive tree is at least 20 levels deep (log₂ of a million), more when SAH builds it unbalanced.

The slab method for ray-AABB intersection computes entry and exit times on each axis independently, then checks if the intervals overlap. It is branchless, maps well to SIMD (instructions that do the same operation on several values at once), and is the standard in production ray tracers.

#include <algorithm>

struct Vec3 { float x, y, z; };
struct AABB { float minX, minY, minZ, maxX, maxY, maxZ; };

// Slab-method ray-AABB intersection.
// Returns true if the ray [origin, origin + dir * tmax] hits the box.
// On hit, tmin is the entry distance (may be negative if origin is inside).
bool rayAABB(const Vec3& origin, const Vec3& invDir,
             const AABB& box, float& tmin, float tmax)
{
    // invDir = 1.0 / direction, precomputed to avoid division per test
    float t1 = (box.minX - origin.x) * invDir.x;
    float t2 = (box.maxX - origin.x) * invDir.x;
    tmin = std::min(t1, t2);
    tmax = std::min(tmax, std::max(t1, t2));

    t1 = (box.minY - origin.y) * invDir.y;
    t2 = (box.maxY - origin.y) * invDir.y;
    tmin = std::max(tmin, std::min(t1, t2));
    tmax = std::min(tmax, std::max(t1, t2));

    t1 = (box.minZ - origin.z) * invDir.z;
    t2 = (box.maxZ - origin.z) * invDir.z;
    tmin = std::max(tmin, std::min(t1, t2));
    tmax = std::min(tmax, std::max(t1, t2));

    return tmax >= std::max(tmin, 0.0f);
}

#[derive(Clone, Copy)]
struct Vec3 { x: f32, y: f32, z: f32 }

#[derive(Clone, Copy)]
struct AABB {
    min_x: f32, min_y: f32, min_z: f32,
    max_x: f32, max_y: f32, max_z: f32,
}

// Slab-method ray-AABB intersection.
// Returns Some(tmin) on hit, None on miss.
fn ray_aabb(origin: Vec3, inv_dir: Vec3, aabb: &AABB, t_max: f32) -> Option<f32> {
    let t1x = (aabb.min_x - origin.x) * inv_dir.x;
    let t2x = (aabb.max_x - origin.x) * inv_dir.x;
    let mut tmin = t1x.min(t2x);
    let mut tmax = t_max.min(t1x.max(t2x));

    let t1y = (aabb.min_y - origin.y) * inv_dir.y;
    let t2y = (aabb.max_y - origin.y) * inv_dir.y;
    tmin = tmin.max(t1y.min(t2y));
    tmax = tmax.min(t1y.max(t2y));

    let t1z = (aabb.min_z - origin.z) * inv_dir.z;
    let t2z = (aabb.max_z - origin.z) * inv_dir.z;
    tmin = tmin.max(t1z.min(t2z));
    tmax = tmax.min(t1z.max(t2z));

    if tmax >= tmin.max(0.0) { Some(tmin) } else { None }
}

Two optimizations matter in practice:

• Ordered traversal (near child first). When both children are hit, push the far child first and the near child second. The near child is popped and tested first, and any hit in the near child tightens tmax, so when the far child is popped its entry distance often lies beyond the closest hit and the whole subtree is skipped. The saving applies to closest-hit queries; an any-hit shadow ray terminates at its first hit instead of tightening tmax.
• Packet traversal. Test a bundle of coherent rays against the same node at once, using SIMD. If all rays in the packet miss a node, skip it. Ray packets exploit the fact that primary rays from adjacent pixels are nearly parallel and hit similar parts of the BVH.

The widget below fires rays through a 2D BVH built by median split. A click casts a ray from the middle of the left edge toward the click, and the traversal animates one popped node at a time: green boxes are hits, red boxes with X marks are misses, and amber dashed boxes were hit by the ray but start beyond the closest hit already found, so ordered traversal skips them.

10Spatial hashing

An open-world map is too big for a dense grid array, but most of its cells are empty at any moment. A spatial hash is a grid stored as a hash table instead of a dense 2D/3D array. Insert: compute the cell coordinates from the object's position, hash them to a table index, append the object to that bucket. Query: compute which cells overlap the query region, look up each bucket, test the contents.

Cell size selection matters. If cells are too large, each cell contains too many objects and the query degenerates to brute force within the cell. If cells are too small, objects span multiple cells (the large-object problem again). A common heuristic sets the cell size near the typical object diameter (twice the average radius): an object that small can overlap at most two cells per axis, so at most four in 2D and eight in 3D, and a neighbor search around a point needs only the surrounding 3×3 block.

Multi-level hashing uses several hash tables at different cell sizes (e.g., 1x, 4x, 16x). Small objects go in the fine grid, large objects in the coarse grid. A query checks all levels. Each object then lands in a level where it spans only a few cells, which keeps mixed-size scenes out of the large-object problem at the cost of one lookup per level.

#include <cmath>
#include <cstdint>
#include <vector>

struct Entity { float posX, posY; };
struct AABB   { float minX, minY, maxX, maxY; };

struct SpatialHash {
    float cellSize;
    int tableSize;
    std::vector<std::vector<Entity*>> buckets;

    SpatialHash(float cellSize, int tableSize)
        : cellSize(cellSize), tableSize(tableSize),
          buckets(tableSize) {}

    // Hash cell coordinates to a bucket index.
    // The primes are Teschner et al.'s; the unsigned cast matters.
    // On int, cellX * 73856093 overflows at cellX = 30, and signed overflow is
    // undefined behavior, so the compiler is free to assume it never happens.
    // Unsigned arithmetic is defined to wrap, which is what we actually want.
    uint32_t hash(int cellX, int cellY) const {
        uint32_t hx = static_cast<uint32_t>(cellX) * 73856093u;
        uint32_t hy = static_cast<uint32_t>(cellY) * 19349663u;
        return hx ^ hy;   // caller reduces modulo tableSize
    }

    int toCell(float coord) const {
        return static_cast<int>(std::floor(coord / cellSize));
    }

    void insert(Entity* entity) {
        int cx = toCell(entity->posX);
        int cy = toCell(entity->posY);
        int idx = static_cast<int>(hash(cx, cy) % static_cast<uint32_t>(tableSize));
        buckets[idx].push_back(entity);
    }

    // Range query: find all entities within queryBox.
    void query(const AABB& queryBox,
               std::vector<Entity*>& results) const
    {
        int minCX = toCell(queryBox.minX);
        int maxCX = toCell(queryBox.maxX);
        int minCY = toCell(queryBox.minY);
        int maxCY = toCell(queryBox.maxY);

        for (int cx = minCX; cx <= maxCX; ++cx) {
            for (int cy = minCY; cy <= maxCY; ++cy) {
                int idx = static_cast<int>(hash(cx, cy)
                          % static_cast<uint32_t>(tableSize));
                for (Entity* entity : buckets[idx]) {
                    // Two cells of this query can hash to the same bucket.
                    // Report an entity only from its own cell, or a shared
                    // bucket hands back the same entity twice.
                    if (toCell(entity->posX) != cx || toCell(entity->posY) != cy)
                        continue;
                    // Fine check: is this entity actually in the query?
                    if (entity->posX >= queryBox.minX
                        && entity->posX <= queryBox.maxX
                        && entity->posY >= queryBox.minY
                        && entity->posY <= queryBox.maxY)
                    {
                        results.push_back(entity);
                    }
                }
            }
        }
    }

    void clear() {
        for (auto& bucket : buckets) bucket.clear();
    }
};

#[derive(Clone, Copy)]
struct Entity { pos_x: f32, pos_y: f32 }

#[derive(Clone, Copy)]
struct AABB { min_x: f32, min_y: f32, max_x: f32, max_y: f32 }

struct SpatialHash {
    cell_size: f32,
    table_size: usize,
    buckets: Vec<Vec<Entity>>,
}

impl SpatialHash {
    fn new(cell_size: f32, table_size: usize) -> Self {
        SpatialHash {
            cell_size,
            table_size,
            buckets: vec![Vec::new(); table_size],
        }
    }

    // Same primes and the same reinterpret-as-unsigned as the C++ pane.
    // wrapping_mul because i32 multiplication overflows at cell_x = 30 and
    // Rust panics on that in debug builds. Reinterpret with `as u32` rather
    // than taking an absolute value: abs() would map cell -5 and cell 5 onto
    // the same bucket and give away half the table.
    fn hash(&self, cell_x: i32, cell_y: i32) -> usize {
        let raw = (cell_x.wrapping_mul(73856093))
            ^ (cell_y.wrapping_mul(19349663));
        (raw as u32 as usize) % self.table_size
    }

    fn to_cell(&self, coord: f32) -> i32 {
        (coord / self.cell_size).floor() as i32
    }

    fn insert(&mut self, entity: Entity) {
        let cx = self.to_cell(entity.pos_x);
        let cy = self.to_cell(entity.pos_y);
        let idx = self.hash(cx, cy);
        self.buckets[idx].push(entity);
    }

    fn query(&self, query_box: &AABB) -> Vec<&Entity> {
        let mut results = Vec::new();
        let min_cx = self.to_cell(query_box.min_x);
        let max_cx = self.to_cell(query_box.max_x);
        let min_cy = self.to_cell(query_box.min_y);
        let max_cy = self.to_cell(query_box.max_y);

        for cx in min_cx..=max_cx {
            for cy in min_cy..=max_cy {
                let idx = self.hash(cx, cy);
                for entity in &self.buckets[idx] {
                    // Same guard as the C++ pane: two query cells can share
                    // a bucket, so only report an entity from its own cell.
                    if self.to_cell(entity.pos_x) != cx || self.to_cell(entity.pos_y) != cy {
                        continue;
                    }
                    if entity.pos_x >= query_box.min_x
                        && entity.pos_x <= query_box.max_x
                        && entity.pos_y >= query_box.min_y
                        && entity.pos_y <= query_box.max_y
                    {
                        results.push(entity);
                    }
                }
            }
        }
        results
    }

    fn clear(&mut self) {
        for bucket in &mut self.buckets { bucket.clear(); }
    }
}

11Loose bounds and margin

A crowd of NPCs shuffles a few centimeters every frame, and a tree that rebuilds a branch for every centimeter spends its frame on bookkeeping. Tight bounding volumes cause excessive re-insertion in dynamic scenes. When an object moves by one pixel, its AABB changes, and the tree must remove and re-insert it. If most objects move every frame, most leaves are removed and re-inserted every frame, which costs about as much as rebuilding the tree.

Loose octrees (Ulrich 2000^[8]) expand each node's bounds by a factor of two. A node that would normally cover a 10x10 region instead covers 20x20, centered on the same position. The expansion guarantees that any object whose center is in the original region, and whose radius is at most half the original region size, fits entirely within the expanded bounds. Insertion needs no straddle test and no multi-cell registration: the object's radius picks the depth, and its center picks the node at that depth.

Fat AABBs in Box2D's dynamic tree^[20] use a different approach. Each leaf's AABB is enlarged by a margin, and the object moves freely within the fat AABB without triggering a tree update. Only when the object's tight AABB leaves the fat AABB does the tree remove and re-insert the leaf with a new fat box. Box2D v2.4 used a 0.1 m margin and also extended the new box by four times the body's latest displacement, in the direction of motion, so a body moving steadily one way escapes it less often^[24].

The trade-off: larger margins mean fewer re-insertions (good for update cost), but looser bounding volumes mean more false positives in queries (bad for query cost). Catto's GDC 2019 talk gives no formula for the margin: "There are many schemes for enlarging the AABB. Choose one that works well for your game."^[20] Box2D v3 shows the balance moving with the rest of the design. Its margin is capped at 5 cm, and the source comment explains that benchmarks favored a small margin because it produces fewer contacts; the larger margin had existed to avoid insert and remove churn, which v3's broadphase no longer does, having moved to "a two-phase refit and rebuild setup similar to Jolt"^[24].

12Queries

The same tree serves the physics engine's overlap tests, the gun's raycasts, the renderer's culling and the AI's "who's nearby". All of these structures answer the same four query types, but each query traverses the tree differently:

The key difference is how aggressively each query can prune. Ray queries get tighter with every hit (tmax shrinks). K-NN queries get tighter as the k-th neighbor gets closer. Range and frustum queries have fixed bounds and prune only by spatial overlap.

13Sweep and prune

Everything so far builds a structure over space and queries it. Broadphase collision detection asks a narrower question: which pairs of moving objects might be touching this frame? Sweep and prune answers it with no tree at all, by keeping the objects sorted.

Give every object an AABB and project it onto each axis, so each object becomes an interval on x, another on y, another on z. Two AABBs overlap exactly when their intervals overlap on every axis. Cohen, Lin, Manocha and Ponamgi's I-COLLIDE keeps three sorted lists, one per axis, each holding all 2n endpoint values, plus one overlap flag per pair per axis. A pair is a collision candidate when all three of its flags are set^[22].

Sorting 2n values per axis per frame is O(n log n), which buys nothing over testing every pair at small n. The trick is that you never do that sort. At 60 Hz an object moves a fraction of its own size between frames, so last frame's list is already almost in order. That is temporal coherence, and insertion sort on an almost-sorted array costs time proportional to the number of inversions, not to n log n. The paper puts it in one line: "Insertion sort works well for previously sorted lists."^[22]

The flags come along for free. A pair's overlap status on an axis can only change when the sort exchanges a maximum past a minimum: two minima swapping, or two maxima swapping, leaves every interval relationship intact. So the candidate set is maintained by the sort itself, in time proportional to the number of exchanges, and is never recomputed from scratch after the first frame.

That last property is also the failure mode. The linear behavior is an expectation, not a bound: the paper states that in the worst case the number of exchanges on each axis is O(n²), "with an extremely small constant"^[22]. Coherence is an assumption about the input, and games break it on purpose. A level streams in, a ragdoll comes apart, a teleport fires, a shockwave wakes a thousand sleeping bodies at once.

That is why PhysX ships a family rather than one algorithm. Its sweep-and-prune broadphase (eSAP) is documented as "a good generic choice with great performance when many objects are sleeping," whose "performance can degrade significantly though, when all objects are moving, or when large numbers of objects are added to or removed from the broad-phase." Multi box pruning (eMBP) "does not suffer from the same performance issues as eSAP when all objects are moving or when inserting large numbers of objects," but its "generic performance when many objects are sleeping might be inferior to eSAP, and it requires users to define world bounds." Automatic box pruning (eABP) manages those bounds itself, offering "the convenience of eSAP coupled to the performance of eMBP," and the documentation calls it "a good default choice for the broadphase"^[14]. Each option bets on a different pattern of motion.

14Dynamic updates

A physics scene has 3,000 bodies moving every frame, and the broadphase tree has to follow them. Static scenes build the acceleration structure once and query it many times. Dynamic scenes must update the structure every frame. Three strategies:

• Rebuild from scratch. Throw away the old tree, build a new one from the current object positions. Simple, and every frame gets a tree built for the current positions, but it costs O(n log n) per frame. It is practical while the build fits the frame budget, which fast builders such as binned SAH stretch to larger scenes.
• Refit. Walk the existing tree bottom-up and recompute each node's bounding volume from its children. O(n) per frame. Preserves the tree topology, so if objects move a lot the tree degrades (bounding volumes overlap, query performance drops). Refitting, with an occasional rebuild, is the usual treatment for deformable meshes in a BLAS.
• Incremental insert/remove. When an object moves, remove it from the tree, re-insert at the new position. Tree quality holds up if insertion chooses its spot well and repairs the tree on the way back up (rotations, as in Box2D's dynamic tree). Cost per update is about O(log n) for a reasonably balanced tree. The fat-AABB trick (§11) cuts the number of updates.

Erin Catto's GDC 2019 talk^[20] lays out the remove-and-reinsert design Box2D used. Insertion picks the sibling whose pairing adds the least surface area to the tree, found with a branch-and-bound search after Bittner et al., instead of descending greedily. On the way back up, it refits the ancestor boxes and applies local tree rotations chosen to reduce surface area (after Kensler 2008), which also repairs the damage sorted input does to an incrementally built tree. The talk frames those rotations as the BVH counterpart of AVL rotations, but the goal is lower SAH cost, not equal subtree heights.

The widget below shows 15 objects moving. Compare "fat AABBs" mode (objects move freely within their margins, and re-insertion happens only when the tight box leaves the fat box) with "tight AABBs" mode (the stored box is the object's own box, so every move forces a re-insertion). The re-insertion counters show the difference.

15Case studies

Shipping engines rarely use one structure for everything; they pick per job.

Bullet Physics: DbvtBroadphase

Bullet's default broadphase is btDbvtBroadphase^[21], a pair of dynamic AABB trees: one for proxies that have moved recently and one for proxies that have stayed still. The btDbvt class is a dynamic bounding volume tree with incremental insertion and removal. A new leaf descends toward whichever child box is closer by a cheap center-distance test, not an SAH cost, and an incremental optimization pass removes and re-inserts a few leaves each frame, following a different root-to-leaf path each time. Proxies migrate from the moving tree to the still one once they stop, and back when they move.

Unreal Engine: TOctree2

Unreal's generic octree, TOctree2, keeps its nodes in flat arrays (a node array, parent links, and a free list of recycled node slots) rather than as individually allocated nodes^[25]. Elements are added and removed individually, so a moving object is removed and re-added rather than the tree being rebuilt. Physics overlap and trace queries do not go through it: they run against the physics engine's own acceleration structures. Nanite's cluster culling uses yet another structure, covered below.

PhysX (and Unity): broadphase versus scene queries

PhysX, which Unity integrates for 3D physics, does not use a BVH for its broadphase. Its documented broadphase types are sweep-and-prune (eSAP), multi box pruning (eMBP), automatic box pruning (eABP), a parallel variant (ePABP), and a GPU implementation^[14]. PhysX's AABB tree is the scene-query pruner, serving raycasts and overlaps, which is a separate stage from pair-finding. Keeping those two apart matters: the broadphase answers "which pairs might touch this frame", the scene-query structure answers "what does this ray hit". Jolt, used on Horizon Forbidden West, takes a third route: its broadphase is a quadtree of AABBs (four children per node) whose nodes are expanded in place as bodies move, and a tight replacement tree is built in the background during the next physics step and swapped in before the step ends^[15].

Nanite: cluster culling hierarchy

Nanite (Unreal Engine 5) groups triangles into clusters of 128 and simplifies them into a hierarchy that is a DAG rather than a tree, because the merge-and-split step leaves a simplified parent shared by the groups it came from^[23]. Culling runs against a second structure built over the clusters: an eight-wide BVH whose leaves are the group-sized cluster lists and whose internal nodes carry the maximum of their children's ParentError. Keying on ParentError rather than the cluster's own error is the key design choice, and the talk gives the reason: any cluster whose parent error is already under the threshold can be culled, so "an acceleration structure for LOD culling should be based on ParentError, not the ClusterError itself." Both structures are built offline at asset import, not at runtime.

RTX TLAS/BLAS

The DirectX and Vulkan ray tracing APIs expose a two-level BVH. The BLAS contains per-mesh triangle geometry, built once (or refit or rebuilt for deformable meshes). The TLAS contains instance transforms and BLAS references, rebuilt or refit every frame. On NVIDIA hardware, RT Cores accelerate BVH traversal and ray-triangle intersection^[19]. What the driver does inside the build cannot be observed through the API: both DXR and Vulkan describe the acceleration structure as opaque and specify no construction algorithm^[17]. The application's levers are how geometry is split into BLASes and instances, the build-quality hints, update-versus-rebuild, and compaction. Read PREFER_FAST_TRACE as what the spec actually promises, a rule of thumb of "about 2-3 times the build time than default in order to get better tracing performance", rather than as an instruction to run a binned SAH build.

16Pitfalls

• Wrong structure for the workload. A BVH for a uniform particle system is slower than a grid. A grid for a scene with mixed-size objects (1-meter crates and 500-meter terrain chunks) hits the large-object problem. Match the structure to the data distribution and object-size variance.
• Deep trees from degenerate input. A quadtree with many objects at the same position keeps splitting, four children per level, and still ends with all of them in one leaf. Set a depth limit. BVHs have their own version: midpoint splits over exponentially spaced objects, or incremental insertion of sorted input with no rebalancing, can produce a tree as deep as a linked list. Median splits cannot (they halve the count every level), and SAH builds can stop and make a leaf when no split pays for itself.
• Large objects spanning many cells. In a grid, or a quadtree that registers objects in every leaf they overlap, an object that straddles four cells is stored in all four. An object that spans 100 cells is stored in 100. Loose bounds (§11) or hierarchical grids fix this.
• Update cost vs query cost. Fat margins reduce update cost but increase query cost (looser bounds, more false positives). Tight bounds reduce query cost but increase update cost (more re-insertions). The right margin depends on the ratio of queries to updates per frame and the expected object velocity.
• Forgetting to refit after deformation. If the underlying geometry changes (skeletal animation, cloth simulation, destruction) and the BVH is not refitted, queries return stale or incorrect results. Refitting is cheap (O(n)), but forgetting it is a common source of "physics not matching visuals" bugs.

17What's next

In this series the next page is Entity Component System, which organizes the game objects these structures index. Beyond that, GPU BVH construction is an active research area. Karras (2012) builds every node of the tree in parallel from sorted Morton codes^[11], and Apetrei (2014) folded the bottom-up bounding-box pass into the same parallel sweep. Vendor builders behind DXR, Vulkan RT and OptiX are mostly closed, so which algorithm a given driver runs is generally not public.

On the CPU, Embree ships separate builders selected by build quality rather than one layered build, documented as "a high-quality SAH builder using spatial splits, a standard SAH builder, and a very fast Morton builder", plus a refit path^[16]. Mixing Morton and SAH construction in one tree is also a real technique. Lauterbach et al.'s hybrid builds the highest levels with LBVH and the rest with SAH, and reports that it "attains roughly half the construction speed of LBVH while retaining essentially all the quality of the pure SAH-based construction"^[10].

Learned index structures for spatial data are an emerging research direction. Kraska et al. (2018) showed that neural networks can replace B-tree indexes for 1D data. Extending this to spatial data (replacing R-trees or BVHs with learned models that predict which region of space contains relevant objects) is an active area, though nothing has shipped in a game engine yet.

Compressed octrees for voxel data are relevant to voxel engines and sparse volume rendering. Kämpe, Sintorn and Assarsson (2013) turned the sparse voxel octree into a DAG (a directed acyclic graph in which identical subtrees are stored once and shared) and report node counts one to three orders of magnitude lower in every scene they tested, irregular ones included^[26].

18Sources

1. Donald Meagher. "Geometric Modeling Using Octree Encoding." Computer Graphics and Image Processing, 19(2):129-147, June 1982. ScienceDirect. Introduces octree encoding for 3D solid modeling. Storage proportional to surface area; linear-time boolean operations.
2. Henry Fuchs, Zvi M. Kedem, Bruce F. Naylor. "On Visible Surface Generation by A Priori Tree Structures." Computer Graphics (SIGGRAPH '80 Proceedings), 14(3):124-133, July 1980. ResearchGate. The foundational BSP tree paper. Introduces binary space partitioning for front-to-back polygon rendering.
3. Matthias Teschner, Bruno Heidelberger, Matthias Müller, Danat Pomeranets, Markus Gross. "Optimized Spatial Hashing for Collision Detection of Deformable Objects." VMV 2003, pp. 47-54. cgl.ethz.ch (PDF). The origin of the constants in §3 and §10: "p1, p2, p3 are large prime numbers, in our case 73856093, 19349663, 83492791". The paper also states the authors "have not systematically investigated the characteristics of hash functions", and that "the quality of the hash function is less important for larger hash tables".
4. Antonin Guttman. "R-Trees: A Dynamic Index Structure for Spatial Searching." Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57, 1984. ACM DL. The R-tree: a height-balanced tree of bounding rectangles for spatial indexing, the database-side counterpart of the AABB trees used in game physics.
5. Jeffrey Goldsmith, John Salmon. "Automatic Creation of Object Hierarchies for Ray Tracing." IEEE Computer Graphics and Applications, 7(5):14-20, May 1987. IEEE Xplore. First automatic BVH construction algorithm. Introduced surface area as a proxy for ray-hit probability.
6. J. David MacDonald, Kellogg S. Booth. "Heuristics for ray tracing using space subdivision." The Visual Computer 6(3), 1990, pp. 153-166. rose-hulman.edu (PDF). The primary derivation behind the SAH in §8, and the correct attribution chain: it credits the surface-area-as-probability result to Stone (1975), with Goldsmith and Salmon (1987) applying it to hierarchies.
7. Fabien Sanglard. Game Engine Black Book: Doom. Self-published, 2018. fabiensanglard.net/gebbdoom. Detailed technical analysis of Doom's BSP-based renderer, including the node builder and the runtime traversal.
8. Thatcher Ulrich. "Loose Octrees." In Game Programming Gems, Charles River Media, 2000. tulrich.com/geekstuff/partitioning.html. Expand node bounds by 2x to eliminate the straddle problem. Objects always fit in exactly one node.
9. Ingo Wald. "On fast Construction of SAH-based Bounding Volume Hierarchies." Proceedings of the IEEE Symposium on Interactive Ray Tracing, pp. 33-40, 2007. PDF. Binned SAH: approximate the cost function with bins for O(n) per-level construction. Enables per-frame BVH rebuilds.
10. Christian Lauterbach, Michael Garland, Shubhabrata Sengupta, David Luebke, Dinesh Manocha. "Fast BVH Construction on GPUs." Computer Graphics Forum 28(2), Eurographics 2009. luebke.us (PDF). The LBVH origin paper, and the source of the SAH-over-LBVH hybrid in §17: building the top levels with LBVH and the rest with SAH "attains roughly half the construction speed of LBVH while retaining essentially all the quality of the pure SAH-based construction."
11. Tero Karras. "Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees." HPG 2012. research.nvidia.com (PDF). Builds on the Morton-code ordering of Lauterbach et al. [10] and removes its level-by-level serialization: "We present a novel approach that improves scalability by constructing the entire tree in parallel", via an in-place binary radix tree over the sorted codes.
12. Samuli Laine, Tero Karras. "Efficient Sparse Voxel Octrees." I3D 2010, NVIDIA Research. research.nvidia.com (PDF). Cited in §5 for what an SVO stores: "We encode the topology of the octree using 64-bit child descriptors", each holding a child pointer, a valid mask and a leaf mask.
13. Rama Hoetzlein. "GVDB: Raytracing Sparse Voxel Database Structures on the GPU." HPG 2016, and the NVIDIA GVDB Voxels Programming Guide. ramakarl.com (PDF); programming guide (GitHub). Cited in §5: GVDB is a VDB-style "sparse hierarchy of grids" with per-level branching, in which a <1,1,1,1,1> configuration "defines an octree"; the guide notes that "an octree quickly requires more than 5 levels."
14. NVIDIA. "Rigid Body Collision" (Broad-phase Algorithms), PhysX 5.4 documentation. nvidia-omniverse.github.io. The source for §15: PhysX's broadphase types are sweep-and-prune, multi box pruning, automatic box pruning, its parallel variant, and a GPU implementation. None is a BVH.
15. Jorrit Rouwe. "Jolt Physics Architecture." github.com/jrouwe/JoltPhysics. Cited in §15: "Our broad phase is a quad tree, which means each node has 4 children", with a tight-fitting replacement tree built in the background during the physics step and swapped in before it ends.
16. Intel. Embree API documentation (rtcSetSceneBuildQuality and the BVH Builder tutorial). github.com/RenderKit/embree. Cited in §17: Embree exposes "a high-quality SAH builder using spatial splits, a standard SAH builder, and a very fast Morton builder" as separate build qualities, plus a refit path.
17. Microsoft. DirectX Raytracing (DXR) Functional Spec, v1.48. microsoft.github.io/DirectX-Specs. The two-level TLAS/BLAS model (§2, §15), and the point that driver BVH construction is not observable: the API asks the system "to build an opaque acceleration structure", specifies no algorithm, and describes PREFER_FAST_TRACE only as a rule of thumb of "about 2-3 times the build time than default". Vulkan uses the same opaque framing.
18. Ingo Wald, Solomon Boulos, Peter Shirley. "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies." ACM Transactions on Graphics, 26(1), January 2007. ACM DL. Demonstrates BVH refitting for deformable scenes with minimal quality loss compared to full rebuilds.
19. NVIDIA. NVIDIA Turing GPU Architecture (whitepaper WP-09183-001), 2018. nvidia.com (PDF). "RT Cores accelerate Bounding Volume Hierarchy (BVH) traversal and ray/triangle intersection testing (ray casting) functions."
20. Erin Catto. "Dynamic Bounding Volume Hierarchies." GDC 2019. PDF. The broadphase behind Box2D: enlarged AABBs, remove/re-insert on movement, SAH-cost sibling selection by branch and bound, and surface-area-reducing tree rotations (citing Kensler 2008 and Bittner 2015).
21. Erwin Coumans. "Bullet Physics Library." Open source, 2003-present. GitHub. btDbvtBroadphase and btDbvt (src/BulletCollision/BroadphaseCollision): two dynamic AABB trees, one for moving and one for resting proxies, proximity-based leaf insertion, and incremental re-insertion as the optimization pass. Bullet is the rigid-body engine in Blender and was Godot 3's default 3D physics backend.
22. Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav Ponamgi. "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments." I3D 1995, pp. 189-196. cs.princeton.edu (PDF). The sweep-and-prune reference, including the coherence argument this tutorial relies on: keeping the sorted lists between frames means "the lists will be nearly sorted, so we can sort in expected O(n) time."
23. Brian Karis, Rune Stubbe, Graham Wihlidal. "Nanite: A Deep Dive." SIGGRAPH 2021 Advances in Real-Time Rendering in Games. advances.realtimerendering.com (PDF). Cited in §15 for the cluster hierarchy: 128-triangle clusters, a BVH8 over a DAG rather than a tree, and internal nodes keyed on the max of children's ParentError, since "an acceleration structure for LOD culling should be based on ParentError, not the ClusterError itself."
24. Erin Catto. Box2D source: v2.4.1 b2_common.h and b2_dynamic_tree.cpp; v3 constants.h. The fat-AABB margins in §11: v2.4's b2_aabbExtension of 0.1 m and b2_aabbMultiplier of 4 applied to the displacement in MoveProxy; v3's B2_MAX_AABB_MARGIN of 5 cm, with the comment that the broadphase "now uses a two-phase refit and rebuild setup similar to Jolt".
25. Epic Games. "TOctree2." Unreal Engine API reference (Math/GenericOctree.h). dev.epicgames.com. Lists the class's storage in §5 and §15: TreeNodes (a TArray of nodes), ParentLinks, TreeElements and a FreeList of reusable node slots, with per-element AddElement and RemoveElement.
26. Viktor Kämpe, Erik Sintorn, Ulf Assarsson. "High Resolution Sparse Voxel DAGs." ACM Transactions on Graphics 32(4), SIGGRAPH 2013. chalmers.se (PDF). Cited in §17: "In all tested scenes, even the highly irregular ones, the number of nodes is reduced by one to three orders of magnitude."