Beyond Static Octrees: Architecting GPU-Driven BVHs and Continuous Collision Detection for High-Density Rigid Body Physics

In modern interactive engine architecture, simulating physics at enterprise scale is no longer limited to basic character character controllers or simple box triggers. Games today demand thousands of interacting fragments, volumetric destruction, dynamic terrain deformation, and dense particle-rigid body interactions - all operating within a strict frame budget of 8.33ms for 120 FPS target performance.

At the core of this challenge lies a fundamental mathematical obstacle: brute-force collision detection between $N$ active entities scales at $O(N^2)$. If a structural collapse event generates 50,000 unique debris fragments, evaluating every object against every other object would require roughly 1.25 billion collision tests per frame.

To overcome this computational barrier, game engine architects rely on advanced spatial partitioning structures, broad-phase pruning, and GPU compute pipelines. While traditional static octrees laid the foundation for spatial organization in early engines, today's high-density physics engines demand a shift toward Dynamic Bounding Volume Hierarchies (BVHs), Loose Octrees, and GPU-accelerated Morton code sorting.

The Physics Pipeline: Broad-Phase vs. Narrow-Phase

Collision processing in modern engines like Chaos, Havok, and PhysX 5 is divided into two distinct computational phases: Broad-Phase and Narrow-Phase.

flowchart TD
    A["Unsorted Rigid Body Transforms<br/>(50,000+ Dynamic Debris Objects)"] --> B["Spatial Partitioning Indexing"]
    B --> C{"Broad-Phase Pruning"}
    C -->|Dynamic BVH / Loose Octree Traversals| D["Potential Colliding Pairs (AABB Overlaps)"]
    D --> E["Narrow-Phase Precision Check"]
    E -->|GJK & EPA Convex Solvers| F["Exact Contact Points & Penetration Depths"]
    E -->|Continuous Collision Detection| G["High-Velocity Sweep Tests (Tunneling Prevention)"]
    F --> H["Rigid Body Constraint & Impulse Solver"]
    G --> H
    H --> I["Updated Physics State (Velocity & Position)"]

1. Broad-Phase Pruning: Scans the entire simulation space to prune object pairs that are too far apart to collide. It substitutes complex mesh geometry with simplified Axis-Aligned Bounding Boxes (AABBs), yielding a manageable list of Potential Colliding Pairs (PCPs) in $O(N \log N)$ or $O(N)$ time.
2. Narrow-Phase Evaluation: Executes rigorous geometric algorithms - such as the Gilbert-Johnson-Keerthi (GJK) algorithm and Expanding Polytope Algorithm (EPA) - strictly on the candidate pairs identified during the broad-phase step.

The Limitations of Static Octrees for Dynamic Rigid Bodies

A standard Octree recursively subdivides a 3D bounding space into eight equal child octants. While octrees excel at organizing static geometry (such as terrain or architectural meshes), they struggle when applied to rapidly moving, high-velocity dynamic debris:

• Boundary Crossings & Re-insertion Overhead: When an object crosses a boundary node in a strict octree, it must be removed and re-inserted higher up the hierarchy. Under heavy debris destruction, hundreds of node re-insertions per frame create severe pointer-chasing operations and cache misses.
• The "Straddling" Problem: An object resting exactly on an internal division plane cannot belong to a single child node. It gets pushed up to the parent node, degrading tree depth efficiency and causing unnecessary candidate pairs downstream.

The Solution: Loose Octrees and Dynamic BVHs

To address these limitations, real-time physics engines employ two primary alternative structures:

1. Loose Octrees

Loose Octrees relax the strict physical boundaries of child nodes by applying an expansion factor $k$ (typically $k = 1.5$ or $2.0). By expanding child node bounds, fast-moving rigid bodies can move within an internal spatial tolerance zone without triggering immediate parent re-insertion. This drastically reduces tree modification overhead while preserving regional spatial grouping.

2. Dynamic Bounding Volume Hierarchies (Dynamic BVH)

Unlike Octrees - which partition space - a BVH partitions objects. A Dynamic BVH wraps individual rigid bodies in leaf AABBs and groups them bottom-up or top-down into a dynamic binary tree.

When objects move, the engine simply inflates the leaf nodes with an extra movement vector (velocity sweep padding). Nodes are rotated or re-balanced on the fly using surface area heuristics (SAH). Because the tree structure adjusts directly to object density rather than fixed spatial boundaries, BVHs accommodate clusters of dynamic fragments with minimal memory overhead.

Solving the Velocity Tunneling Problem: Continuous Collision Detection (CCD)

A persistent issue in dynamic rigid body physics is tunneling. When a fast-moving object - such as a high-velocity projectile or falling shard - moves farther in a single frame than its own physical thickness, discrete collision detection fails to register an intersection.

Discrete Sampling (Tunneling Error):
Frame N:   [ Object ] --------------> Wall --------------> (No Collision Detected) Frame N+1: [ Object ]

Continuous Collision Detection (Swept Volume):
Frame N:   [ Object ]====== Swept Bounding Volume ======> Wall (Collision Intersection Registered)

To eliminate tunneling without sacrificing engine performance, modern engines implement Swept AABB Continuous Collision Detection:

1. Swept Volume Generation: The broad-phase system expands the object's AABB along its linear velocity vector for that frame, creating a dynamic bounding tube.
2. Time-of-Impact (TOI) Speculation: If the swept volume intersects another object's bounding volume during broad-phase traversal, the narrow-phase solver executes a localized Time-of-Impact (TOI) calculation using conservative advancement algorithms.
3. Speculative Contacts: The impulse solver applies speculative contact constraints, slowing or reflecting the body before it penetrates the barrier plane.

GPU-Accelerated Broad-Phase: Linear BVH and Morton Codes

To scale physics simulations past 100,000 active rigid bodies, engines are shifting broad-phase partitioning directly onto compute shaders. Executing spatial trees on the CPU introduces major cache invalidation and multithreading lock contention.

On the GPU, engines generate Linear Bounding Volume Hierarchies (LBVH) using spatial Z-order curves (Morton Codes):

1. Morton Encoding: The 3D centroid of every rigid body's AABB is converted into a 32-bit or 64-bit bitwise Morton code. This code interleaves the binary digits of the $X$, $Y$, and $Z$ coordinates, mapping 3D space into a continuous 1D spatial sequence.
2. Radix Sorting: The GPU executes a parallel Radix Sort on the array of Morton codes. Objects that are spatially adjacent in 3D world space end up side-by-side in contiguous GPU memory buffers.
3. Hierarchy Construction: Compute shaders evaluate bitwise prefix differences across adjacent Morton keys to build binary LBVH node hierarchies in parallel, operating in under < 1.2ms for dense debris fields.

3D Spatial Coordinate (X, Y, Z) ---> Interleaved Bits (Morton Key) ---> Parallel Radix Sort ---> GPU Contiguous LBVH Node Array

By storing tree nodes in flat, linear memory arrays (Structure of Arrays layout) rather than linked node pointers, GPU compute units execute broad-phase raycasts and pair overlaps with maximum cache hit rates and zero pointer-chasing stalls.

Performance Benchmark Matrix: Spatial Partitioning Approaches

The Engineering Frontier: Hybrid Physics Architectures

The future of real-time physics lies in hybrid spatial execution. Core static architecture and character movement constraints remain managed on the CPU via highly optimized Dynamic BVH trees, while dynamic environmental debris, fracture fragments, and secondary rigid body simulations are offloaded entirely to GPU compute streams utilizing Linear BVH pipelines.

By shifting spatial partitioning from static spatial grids to dynamic GPU-driven structures, game engine architects have transformed collision detection from a restrictive performance budget constraint into a scale-free foundation for next-generation interactive environments.