The Problem
Imagine you are writing a ray tracer. For it to work, you need to fire rays and check each one for intersection with the scene geometry. The more rays you fire, the better the output image. But this requires checking ray-triangle intersections.
If you have a geometry with a million triangles and you are shooting a million rays, you now need to calculate ray-triangle intersection a million × million times. That is 1012 intersection tests per frame. Real-time rendering at these numbers is impossible without specialized hardware — and even then, a naive implementation wastes most of it.
The Solution
Divide your geometry into spatial chunks. If a ray doesn't hit the bounding box of a chunk, skip every triangle inside it entirely.
This is the core idea behind Bounding Volume Hierarchy — a tree structure where each node contains a bounding box, and each leaf node references a small set of triangles. To test a ray against the scene, you traverse the tree: if the ray misses a node's bounding box, you prune that entire subtree.
BVH falls under the family of spatial partitioning algorithms, alongside quad trees, octrees, k-d trees, BSP trees, and r-trees. Each has different trade-offs in construction cost, query cost, and memory.
When to Use BVH
BVH is valuable anywhere you need to query for object positions or intersections: ray tracing, physics collision detection, frustum culling, light influence queries. It brings down O(n) or O(n²) search complexity to O(log n) for well-balanced trees.
Trade-offs
- Dynamic scenes: BVH must be rebuilt or refitted when geometry moves. Refitting (updating bounding boxes without restructuring) is fast but degrades tree quality over time. Full rebuilds are expensive but maintain optimal structure.
- Memory: BVH trades memory for speed. The tree itself requires additional storage on top of the original geometry.
- Construction cost: Building a high-quality BVH (e.g., using SAH — Surface Area Heuristic) takes time. For real-time use, construction is typically done offline or with faster approximate methods.
For static geometry — which is most of the geometry in most scenes — BVH construction cost is paid once and query benefits are paid every frame.