Linearized Octrees and Cache-Local Spatial Hashing: Overcoming CPU Traversal Bottlenecks in Dynamic Physics Engines

In modern interactive gaming, simulating dense, destructible environments filled with tens of thousands of active rigid bodies is no longer a luxury - it is a baseline expectation. However, as physics engines scale from simulating a few hundred objects to thousands of interacting debris fragments, the primary performance bottleneck shifts away from actual geometric collision response (narrow-phase) to spatial query efficiency (broad-phase).

For decades, the standard tool for spatial partitioning in 3D environments has been the pointer-based octree. By recursively dividing 3D space into eight child nodes, octrees allow physics engines to discard non-colliding entity pairs in $O(\log N)$ time. Yet, on modern hardware architectures, classical pointer-based octrees fail dramatically due to CPU L1/L2 cache invalidation.

To maintain high frame rates at sub-millisecond physics frame budgets, modern game engine architectures are abandoning traditional pointer trees in favor of Linearized Octrees, Loose Octree extensions, and Flat-Array Spatial Hashing.

The Pointer-Chasing Problem in Classical Octrees

A traditional octree represents space using a dynamic tree structure where each node contains pointers to eight potential children. While mathematically elegant, this structure introduces severe hardware performance penalties during broad-phase collision detection:

1. Non-Contiguous Memory Allocation: As rigid bodies move, nodes are continually allocated, split, merged, and freed. This dynamic allocation scatters node structures randomly across heap memory, leading to continuous CPU cache misses during recursive traversal.
2. Pointer Chasing Overhead: Traversing a tree path requires reading memory addresses stored within parent nodes to find children. The CPU pipeline stalls waiting for RAM fetches, as branch predictors cannot efficiently anticipate deeply nested traversal branches.
3. Boundary Oscillation: When a rigid body sits exactly on the plane dividing two octants, standard octrees must push the entity up to a higher parent node. If an object continuously crosses a boundary frame-over-frame, it triggers constant re-insertion and tree rebalancing overhead.

flowchart TD
    A["World Root Node"] --> B["Child Octant 000"]
    A --> C["Child Octant 001"]
    A --> D["Child Octant 010..."]
    
    B --> E["Sub-Octant 000-0"]
    B --> F["Sub-Octant 000-1"]
    
    subgraph NonContiguousRAM["Memory Layout Dispersal (Heap Invalidation)"]
        E
        F
        C
        D
    end

When evaluating 5,000 active rigid bodies moving simultaneously, the time spent traversing pointer chains to populate collision candidate pairs often exceeds the time required to perform precise GJK (Gilbert-Johnson-Keerthi) narrow-phase overlap checks.

Flattening Space: Morton Encoding & Linearized Octrees

To eliminate pointer chasing, modern physics runtimes translate three-dimensional space into continuous one-dimensional arrays using Z-order curves (Morton Codes).

Morton encoding works by interleaving the binary bits of an object's 3D integer coordinates $(X, Y, Z)$. The resulting single integer represents a unique cell index along a space-filling curve that preserves spatial locality: spatially close objects in 3D space map to near-adjacent index locations in 1D array memory.

3D Coordinate Bit Interleaving:
X-bit:  x2  x1  x0
Y-bit:  y2  y1  y0
Z-bit:  z2  z1  z0

Morton Code = [z2 y2 x2] [z1 y1 x1] [z0 y0 x0]

The Linear Octree Advantage

By sorting object Morton codes in flat arrays, the game engine transforms recursive tree traversal into sequential array iterations:

• Zero Pointer Overhead: Nodes do not store explicit memory addresses to children; location hierarchy is implicit in the bitwise structure of the key.
• Cache-Coherent Traversal: Neighboring objects in space are positioned sequentially in memory, maximizing L1/L2 data cache hit ratios during broad-phase scans.
• Vectorization & SIMD Optimization: Broad-phase candidate filtering can be executed using AVX-512 or SIMD vector instructions, comparing multiple bounding boxes per CPU clock cycle.

Mitigating Edge Cases: Loose Octrees vs. Flat Spatial Hashing

While linear octrees optimize memory access, object size variation remains an architectural challenge. A massive ship entity and a tiny bullet casing require drastically different cell resolutions. Modern engines address this via two distinct architectural approaches:

1. Loose Octrees for Variable Rigid Body Sizes

To solve boundary oscillation and handle varying object scales, engine developers expand the half-dimensions of octree nodes by a relaxation factor $k$ (typically $k = 1.5$ or $2.0).

In a Loose Octree, node boundaries overlap. This expansion ensures that an object of radius $R$ always fits entirely inside a single child node at a given hierarchy depth, provided the node's expanded dimensions exceed $2R$. Objects no longer oscillate to parent nodes simply because they intersect a center coordinate plane, drastically reducing dynamic update overhead.

2. Flat-Array Spatial Hashing for Uniform Dynamic Debris

For scenes dominated by uniform rigid body counts (e.g., destructible brick walls or particle-based rigid debris), engines often bypass octrees entirely in favor of Uniform Spatial Hashing:

1. World space is divided into a infinite virtual grid with fixed cell size $S$.
2. Entity positions map to grid coordinates $(i, j, k) = (\lfloor x/S \rfloor, \lfloor y/S \rfloor, \lfloor z/S \rfloor)$.
3. A fast hash function converts $(i, j, k)$ into a bounded array index $H = ((i \times p_1) \oplus (j \times p_2) \oplus (k \times p_3)) \pmod M$.
4. Entities are packed into continuous, cache-aligned array buckets.

Spatial hashing delivers true $O(1)$ insertion and lookup performance, completely eliminating tree building steps.

Performance Comparison: Broad-Phase Architectures

The Compute Shader Pipeline: Physics Broad-Phase on GPU

The transition to flat, cache-local spatial structures enables another critical shift in modern game engines: offloading the broad-phase collision pass entirely to GPU Compute Shaders.

Because Linear Octrees and Spatial Hash Grids store spatial data in contiguous buffers without indirect pointer references, compute passes can execute bitwise Morton sorting and hash mapping across thousands of GPU threads simultaneously.

By keeping both spatial partitioning and broad-phase overlap testing on the GPU, engines eliminate the massive bandwidth pipeline stall traditionally required to copy broad-phase collision pairs from system RAM to VRAM every frame.

Architectural Verdict

As physical interaction becomes increasingly integral to immersion, game engines are undergoing a fundamental transformation in spatial partitioning design. The classic pointer-based octree, once a staple of game physics, is now recognized as a primary cause of CPU cache starvation.

By implementing Linearized Morton-Encoded Octrees for multi-scale environments and Cache-Local Spatial Hashing for uniform rigid body debris, engine architects are achieving multi-fold performance gains in broad-phase collision processing. These data-oriented paradigms maximize modern CPU hardware efficiency while paving the way for fully GPU-driven physics pipelines.