Taming the Collision Bottleneck: How Modern Engines Partition Space to Simulate Massive Rigid Body Physics

In modern interactive entertainment, immersion lives and dies by physical fidelity. Whether it is an open-world destructible environment, a swarm of thousands of debris chunks collapsing during an explosion, or a high-velocity racing simulation, game physics systems are tasked with delivering believable real-world dynamics.

However, physics calculation carries a harsh computational reality. At a target rendering budget of 120 frames per second, an engine has a total frame window of just 8.33 milliseconds. Subtracting renderer submission, animation blending, game logic, and audio processing leaves a tight frame budget of under 2 milliseconds for the entire physics tick.

The single biggest CPU killer within that physics tick is collision detection. Without optimization, testing whether rigid bodies intersect scales quadratically: $O(N^2)$. If a scene contains 10,000 active objects, a naive algorithm would execute 49,995,000 pairwise collision tests every frame.

To overcome this brute-force limitation, game engine architects rely on spatial partitioning structures - specifically Octrees, Bounding Volume Hierarchies (BVH), and Spatial Hash Grids.

The Core Pipeline: Broadphase, Midphase, and Narrowphase

To prevent the CPU from bogging down in precise mesh-versus-mesh calculations, modern engines split collision detection into a multi-stage pipeline.

flowchart TD
    A["World Entities<br/>(10,000+ Rigid Bodies)"] --> B["Broadphase Filtering<br/>(Octree / BVH / Spatial Hash)"]
    B -->|Potential Overlap Pairs| C["Midphase Filtering<br/>(Sub-mesh / Compound Bounds)"]
    C -->|Confirmed Candidate Pairs| D["Narrowphase Precision<br/>(GJK / EPA / Mesh Triangle Intersections)"]
    D -->|Contact Manifolds| E["Constraint Solver & Rigid Body Integration"]

1. Broadphase: Quickly eliminates pairs of objects that are nowhere near each other. It operates on ultra-cheap bounding volumes like Axis-Aligned Bounding Boxes (AABB) or Bounding Spheres. The primary algorithm's job here is to reduce $O(N^2)$ candidate pairs down to $O(N \log N)$ or $O(N)$.
2. Midphase: For complex composite shapes or static landscape meshes, midphase algorithms isolate which specific sub-sections or triangles of a complex mesh lie near the broadphase collision bounds.
3. Narrowphase: The mathematical heavyweight. For remaining candidate pairs, algorithms like Gilbert-Johnson-Keerthi (GJK) and Expanding Polytope Algorithm (EPA) compute exact intersection points, penetration depths, and contact normals.

Spatial Partitioning Paradigms Compared

How an engine organizes space determines how efficiently it can query potential collisions. The choice of spatial partitioning structure depends entirely on scene topology and state dynamics.

1. Octrees: Top-Down Dynamic Sub-divisions

An Octree is a tree structure where every internal node splits a 3D bounding box into eight equal sub-cubes (octants). - How it works: The root node encompasses the entire game world. As entities are inserted into an octant, if the count of entities within that volume exceeds a defined threshold (e.g., > 8 objects), the node subdivides into eight child octants. - Strengths: Excellent for non-uniform 3D distribution - such as volumetric air space, flight simulators, or cavernous environments. Raycasting through an Octree is extremely fast because sub-trees can be skipped entirely via hierarchical frustum/ray tests. - Weaknesses: Objects straddling boundary planes between two or four octants must either be stored in parent nodes or duplicated across multiple leaves. Furthermore, frequently moving dynamic objects force constant tree re-balancing and node re-allocations, leading to CPU cache misses.

2. Bounding Volume Hierarchies (BVH): Object-Centric Trees

Unlike Octrees (which partition space), BVH trees partition objects. - How it works: A BVH wraps individual rigid bodies in tight bounding boxes, then recursively groups adjacent bounding boxes into parent bounding boxes until a single root box covers all objects. - Strengths: Handles dynamic, moving objects far more efficiently than spatial grids because the geometry is bound to the object rather than fixed coordinates. BVH is the structural backbone of modern GPU Ray Tracing (hardware BVH traversal pipelines) and physics systems like Chaos in Unreal Engine. - Weaknesses: Re-fitting or re-building tree branches as objects move rapidly across large distances can degrade tree quality, producing overlapping bounding boxes that increase broadphase candidate count.

3. Uniform Spatial Hash Grids: Constant-Time Dynamic Lookup

For dense, single-plane environments (such as RTS battlefields, racing tracks, or top-down action titles), Spatial Hashing maps 3D coordinates into a 1D or 2D hash table using a fixed grid cell size. - Strengths: Insertion and lookup operate in constant time $O(1)$. Dynamic dynamic objects require no tree re-balancing - an entity simply updates its hash key based on its new position (x / CellSize, y / CellSize, z / CellSize). - Weaknesses: Highly sensitive to non-uniform object sizes. If a giant dragon entity spans 50 grid cells, it must be indexed across every single cell, destroying performance gains.

Memory Locality & Hardware SIMD Acceleration

In modern C++ engine architectures (such as Unreal Engine's Chaos or Havok), mathematical complexity is often secondary to data locality. Modern CPU registers leverage SIMD (Single Instruction, Multiple Data) vector instructions (AVX-512, ARM Neon) to evaluate 4, 8, or 16 AABB intersections simultaneously in a single CPU cycle.

However, standard pointer-based trees (where nodes contain pointers to child nodes) lead to random memory access and costly CPU cache misses. Engine architects optimize spatial partitioning through Structure-of-Arrays (SoA) memory layouts:

// Poor Cache Locality (Array-of-Structures)
struct Node {
    Vector3 minBounds;
    Vector3 maxBounds;
    Node* childPointer;
};

// SIMD-Optimized (Structure-of-Arrays)
struct BroadphaseNodes {
    float minX[8]; // Packed for 256-bit AVX vectors
    float minY[8];
    float minZ[8];
    float maxX[8];
    float maxY[8];
    float maxZ[8];
};

By flattening tree hierarchies into contiguous arrays, broadphase tree traversal streams through CPU L1/L2 caches with near-zero latency, enabling engines to run tens of thousands of bounding box overlap checks in less than 0.3ms.

The Tunneling Nightmare: Continuous Collision Detection (CCD)

A classic challenge in rigid body simulation is tunneling - a failure where a fast-moving object (like a high-velocity projectile or sports vehicle) passes completely through a thin collision wall in a single frame update.

If an object moves 10 units forward in a single tick, but the wall is only 2 units thick, standard Discrete Collision Detection checks frame $T$ (before the wall) and frame $T+1$ (after the wall). In both frames, no overlap is found, so the object passes through solid geometry unnoticed.

Frame T:     [ Object ]   | Wall |
Frame T+1:                | Wall |   [ Object ]  <-- Missed Collision!

To prevent this without drastically lowering frame rates, modern engines employ two strategies:

1. Swept Volume AABB (Conservative Advancements): The broadphase expands the object’s bounding box to encompass both its start position and end position for the current frame step. If this extended bounding box intersects static geometry, a continuous ray-cast or convex sweep is triggered.
2. Speculative Contacts: Rather than performing expensive continuous mathematical sweeps, the solver detects that a fast object is approaching a wall, creates a speculative contact point ahead of time, and injects a temporary constraint force to prevent the object from penetrating in subsequent steps.

The Next Horizon: Compute Shader Physics Pipelines

As world density demands push beyond thousands to hundreds of thousands of active rigid bodies, traditional multi-core CPU architectures hit a hardware ceiling. The modern frontier of game physics moves both spatial partitioning and narrowphase contact resolution directly onto the GPU via Compute Shaders.

By executing broadphase bit-wise operations across tens of thousands of parallel GPU threads, engines can calculate spatial grid buckets or sweep-and-prune sorting in microseconds. Systems like PhysX GPU and custom GPU-driven particle/rigid body frameworks unlock massive interaction fidelity - transforming spatial partitioning from an architectural optimization into the fundamental pillar of emergent world simulation.