Optimizing Dynamic Bounding Boxes for Collision Sweeps

In physics-heavy game development, dynamic bounding boxes are crucial for continuous collision detection (CCD), preventing fast-moving objects from tunneling through geometry. This article explores how physics engines optimize these dynamic bounding volumes—specifically swept Axis-Aligned Bounding Boxes (AABBs) and Oriented Bounding Boxes (OBBs)—using velocity-expanded bounds, loose bounding volume hierarchies (BVH), SIMD vectorization, and multi-tiered broad-phase culling to ensure smooth performance without compromising physical accuracy.

The Role of Dynamic Bounding Boxes in Collision Sweeps

Standard discrete collision detection samples an object's position at distinct time steps. When objects move at high velocities or frame rates drop, discrete checks fail because an object can pass completely through an obstacle between two consecutive frames (the tunneling effect).

Continuous collision detection solves this by sweeping the object's geometry along its trajectory from its start position to its target position over a time step \(\Delta t\). Because testing complex concave or convex polygonal geometry along a continuous path is computationally expensive, physics engines use dynamic bounding boxes as conservative proxies during the broad-phase and mid-phase collision pipelines.

Generating Swept AABBs

The most common technique to accelerate sweeps is generating an expanded AABB that encapsulates the object's volume across its entire motion path:

  1. Trajectory Union: Calculate the AABB at \(t_0\) and the AABB at \(t_1\). The swept AABB is the minimal axis-aligned box containing both: \[\text{AABB}_{\text{swept}} = \text{AABB}(t_0) \cup \text{AABB}(t_1)\]
  2. Velocity Extrusion: Alternatively, extend the original bounding box in the direction of the velocity vector \(\vec{v} \cdot \Delta t\).

This dynamic box simplifies the continuous problem into a static overlap test. If two swept AABBs do not intersect, their underlying shapes cannot collide during the frame, allowing the engine to safely skip expensive narrow-phase calculations.

Reducing BVH Churn with "Fat" Bounding Boxes

Dynamic objects change position and velocity constantly, which can cause significant CPU overhead if the spatial partitioning tree (such as a dynamic AABB tree or BVH) must be rebuilt or restructured every frame.

Engines optimize this using fat bounding boxes (or bounding box margins):

  • Predictive Margins: The engine inflates the swept AABB by a fixed spatial margin plus an acceleration factor.
  • Update Avoidance: As long as the object’s motion remains entirely within its inflated fat box, the BVH does not need structural rebalancing or node updates.
  • Tree Refitting: When an object leaves its fat bounds, the tree refits the node locally rather than executing a full tree rebalance, minimizing cache misses and pointer manipulation.

SIMD and Data-Oriented Layouts

During broad-phase checks, thousands of dynamic bounding boxes must be tested simultaneously. Physics engines optimize this phase using data-oriented design (DOD) and Single Instruction, Multiple Data (SIMD) instruction sets:

  • Structure of Arrays (SoA): Storing bounding box coordinates as separate arrays (all \(X_{\min}\), all \(X_{\max}\), etc.) rather than an Array of Structures (AoS) allows SIMD registers (such as SSE, AVX, or ARM NEON) to test 4, 8, or 16 bounding box intersections in a single CPU cycle.
  • Branchless Ray-Box and Box-Box Sweeps: Intersection algorithms are structured without conditional branches to avoid pipeline stalls and CPU branch mispredictions.

Transitioning from Swept AABBs to Narrow-Phase Sweeps

Once the dynamic bounding box overlaps are identified, the engine transitions to progressively tighter checks:

  1. Swept OBB / Conservative Advancement: For elongated or rotating dynamic objects, swept AABBs can introduce excess empty space. Engines may compute a swept Oriented Bounding Box (OBB) or use conservative advancement to step forward through time in safe intervals.
  2. Convex Casts (GJK / EPA): If the dynamic box passes intermediate culling, algorithms like the Gilbert-Johnson-Keerthi (GJK) distance algorithm run a continuous shape cast (e.g., sweeping a capsule or convex hull) to determine the exact time of impact (TOI) and generate contact manifolds.

By limiting precise time-of-impact queries to only the pairs that pass dynamic bounding box tests, physics engines maintain high frame rates even in environments with thousands of concurrent, high-velocity rigid bodies.