BVHs

BVHs, or bounding volume hierarchies, are a class of data structures used to accelerate geometric queries. They organize primitives into a tree where each internal node contains a bounding volume that encloses all primitives in its subtree, and leaf nodes contain the actual primitives or small groups of primitives. Bounding volumes are often axis-aligned bounding boxes but can also be oriented bounding boxes or k-DOPs.

Construction: The common approach is to build top-down, recursively partitioning the set of primitives and creating child bounding volumes that tightly enclose the partition. Alternatively, bottom-up methods merge primitives into larger bounding volumes. The quality of the BVH is commonly improved by the surface area heuristic (SAH), which estimates the cost of a split considering traversal and intersection tests. Splits are chosen to minimize SAH. For dynamic scenes, BVHs can be updated by refitting bounds or rebuilding affected regions.

Traversal: In ray tracing, a ray is tested against node bounding volumes; traversal proceeds into child nodes only if the ray intersects the node's volume. Leaves test against contained primitives and contribute intersections. The algorithm explores promising branches first to prune quickly.

Variants and performance: BVHs are memory efficient and well suited to hardware acceleration, including GPUs. They are widely used in real-time rendering, ray tracers, and collision detection. The performance depends on tree depth, the tightness of bounds, and the SAH quality. Dynamic BVHs support object motion, while static BVHs are rebuilt when the scene changes.

Examples and related structures: Popular implementations include Embree, OptiX, and PBRT. BVHs compete with other spatial partitioning structures such as kd-trees and octrees, offering good performance for a broad range of scenes and queries.