Spatial Partitioning Data Structures: BVH, Octree, k-d Tree, and Grid Hash: Competitive Benchmark Analysis and Hårdvara Interactions

[Lucas Collins]

I’ve been benchmarking spatial partitioning structures for broadphase collision and frustum culling in a high-refresh shooter engine, and I want real-world numbers, not textbook theory. When you’re chasing 240fps with hundreds of dynamic entities repositioning every frame, rebuild cost matters just as much as query cost. Does anyone have measured frametime data comparing SAH-built BVH vs. insertion BVH, octree, k-d tree, and grid hash across dynamic versus

"i7-14700K | 64GB DDR5 6000MHz | Arctic Liquid Freezer III 360"

[Isaac Ward]

Great topic to dissect. The honest takeaway from my benchmarks is that the “best” structure is entirely scene-dependent, and most people over-index on raw query speed while ignoring cache behavior. BVH absolutely dominates for ray tracing and broad-phase collision in heterogeneous scenes—RTX hardware is literally built around it (the RT cores assume a BVH input), and I’ve seen 2-3x traversal speedups just by using a bottom-up SAH build with a small AABB per node to keep the traversal cache-friendly. The catch is rebuild cost: BVHs are static, so

"Benchmark results tested on clean Windows 11 with Core Isolation disabled."

[Author]

Posts