BVH for Collision Detection: From AABB to Optimal Hierarchies

Table of Contents Why Broad-Phase Exists (and why naive O(N²) dies at 10k objects) Bounding Volume Hierarchy: The Data Structure That Scales Topology Choices: Binary vs. Multi-Branch, Pointer vs. Array Layout Construction Algorithms: From Naive to SAH-Optimal Traversal Strategies for Collision Queries The Static/Dynamic Dichotomy: Why One Tree Cannot Serve Two Masters The Dual-BVH Architecture Preview 1. Why Broad-Phase Exists The Pairwise Problem Every collision detection system faces the same fundamental challenge: given N objects, determine which pairs might be colliding so the expensive narrow-phase (SAT, GJK, EPA) only runs on plausible candidates. The naive approach tests every pair: // Naive O(N²) broad-phase — dies at ~10k objects std :: vector < CollisionPair > broadPhaseNaive ( const std :: vector < Object *>& objects ) { std :: vector < CollisionPair > pairs ; for ( size_t i = 0 ; i < objects . size (); ++ i ) { for ( size_t j = i + 1 ; j < objects . size (); ++ j ) { if ( aabbOverlap ( objects [ i ] -> aabb , objects [ j ] -> aabb )) { pairs . emplace_back ( objects [ i ], objects [ j ]); } } } return pairs ; } Complexity: O ( N ² ) AABB tests. At 60 Hz you have 16.67 ms/frame. At 120 Hz: 8.33 ms. Objects (N) Pairwise Tests @ 3 ns/test Frame Budget (60 Hz) 100 4,950 0.015 ms Trivial 1,000 499,500 1.5 ms Comfortable 10,000 49,995,000 150 ms 10x over budget 100,000 ~5x10^9 15,000 ms Impossible Cache Miss Catastrophe The pairwise loop doesn't just do too much work, it does it poorly . Each iteration accesses two random objects in memory. With 10k objects, you're thrashing L3 cache every frame. The BVH approach exploits spatial coherence: nearby objects in space are nearby in the tree, turning random access into sequential scans. The Real Job: Proving Separation KEY INSIGHT: Broad-phase is a rejection machine. Broad-phase is not about finding collisions. It's about proving separation as cheaply as possible. Every AABB overlap test that returns false is a vic