Bounding Volume Hierarchy (BVH)

A BVH recursively partitions a set of objects by grouping them into nested bounding volumes. The root node bounds the entire scene, and each child node bounds a subset of its parent's objects. This creates a binary tree or n-ary tree structure where spatial locality is preserved, enabling logarithmic-time complexity for queries like ray intersection. The hierarchy allows the system to quickly cull large groups of objects that cannot possibly intersect a query, dramatically reducing computational load compared to brute-force methods.

The most common bounding volume type is the Axis-Aligned Bounding Box (AABB). An AABB is defined by its minimum and maximum extents along the X, Y, and Z axes. Key properties include:

• Simple Intersection Tests: Ray-AABB intersection involves only min/max comparisons, making it extremely fast.
• Tightness: AABBs provide a reasonably good fit for many objects, though they are not rotationally invariant.
• Low Memory Footprint: Storing an AABB requires only six floating-point numbers (min and max vectors). Other volume types include Oriented Bounding Boxes (OBBs) and Bounding Spheres, but AABBs offer the best trade-off between simplicity, performance, and memory for most real-time applications.

Building an optimal BVH is critical for performance. Common construction strategies include:

• Surface Area Heuristic (SAH): The gold-standard method for building high-quality BVHs. It estimates the cost of traversing a node by the surface area of its bounding box and the probability of a ray hitting it. The algorithm evaluates split planes to minimize the expected cost of traversal.
• Median Split: A faster, simpler method that splits primitives based on the median of their centroids along the longest axis of the parent's AABB.
• Binned SAH: An approximation of SAH that divides the space into a fixed number of bins for faster construction, often used for real-time updates. Construction can be offline (precomputed for static scenes) or online (updated dynamically for deformable objects).

The primary use of a BVH is to accelerate ray casting and ray tracing. The traversal algorithm follows a depth-first or breadth-first order using a stack or queue. For each ray, the process is:

1. Test against root node's AABB. If no hit, the entire scene is missed.
2. Recursively test child nodes. If a child's AABB is hit, push it onto the stack for further testing.
3. Primitive intersection: When a leaf node is reached, perform exact intersection tests with the primitives (triangles, spheres) contained within. This hierarchical culling means a ray typically tests only a tiny fraction of the total primitives in a complex scene.

For scenes with moving or deforming objects, the BVH must be updated. Strategies include:

• Refitting: After object motion, the bounding volumes are recalculated (refitted) bottom-up without changing the tree's topology. This is fast but can lead to inefficient, overlapping volumes over time.
• Incremental Rebuild: Periodically or when tree quality degrades past a threshold, sections of the tree are rebuilt using construction algorithms.
• BVHs for Physics: In collision detection systems, dynamic BVHs like Box2D's b2DynamicTree use refitting and node rotations to maintain performance for continuously moving bodies, which is essential for real-time simulation.

BVHs are chosen based on the specific spatial query requirements. Key comparisons:

• vs. k-d Trees: k-d Trees use spatial planes to partition space, not objects. They can generate tighter partitions for ray tracing but are less efficient for dynamic scenes and have more complex construction.
• vs. Uniform Grids: Grids divide space into uniform voxels. They are excellent for evenly distributed primitives but suffer from the "teapot in a stadium" problem (empty cells) and poor performance with non-uniform distributions.
• vs. Octrees: Octrees are a special case of k-d trees with axis-aligned splits at the midpoint. They are simpler but generally less efficient for ray tracing than a well-constructed SAH-based BVH. The BVH's object-centric partitioning makes it the preferred choice for rendering complex, animated meshes and physics collision detection in most modern engines.

An octree is a hierarchical tree data structure that recursively subdivides a 3D volume into eight octants. It is a fundamental spatial partitioning technique used for:

• Voxel-based rendering and terrain generation.
• Level of Detail (LOD) management for geometry.
• Efficient nearest-neighbor searches and frustum culling.

While a BVH typically partitions objects, an octree partitions space. Octrees are often used for uniform spatial data like point clouds or volumetric datasets, whereas BVHs excel with irregular object distributions.

Spatial hashing is a technique that maps 3D coordinates to a hash table index, grouping nearby objects into the same hash bucket. It provides constant-time average lookup for proximity queries and is highly effective for:

• Real-time collision detection in particle systems and physics engines.
• Broad-phase collision culling before precise BVH or geometric tests.
• Dynamic scenes where objects move frequently, as rebuilding a hash grid is often cheaper than updating a tree.

It is a simpler, often faster alternative to tree structures for uniformly distributed, dynamic objects.

A KD-Tree is a binary space-partitioning tree where each node splits the space along an axis-aligned plane. It is optimal for static scenes and excels at:

• Ray tracing and photon mapping for global illumination.
• Nearest neighbor searches in high-dimensional spaces (like feature matching).
• Organizing point data for range queries.

Unlike a BVH, which bounds objects, a KD-Tree partitions space based on geometric primitives (like triangle centroids). BVHs are generally preferred for dynamic scenes due to more efficient update strategies.

A Scene Graph is a hierarchical tree data structure used by game and graphics engines to manage all objects, transformations, and state within a virtual scene. It defines parent-child relationships for spatial transformations and rendering order. Key functions include:

• Managing local and world transformations via matrix composition.
• Organizing renderable meshes, lights, and cameras.
• Enabling culling and LOD selection per subtree.

While a Scene Graph manages logical and render state hierarchy, a BVH is a purely spatial acceleration structure often built from the geometry within the Scene Graph for performance-critical queries.

A Binary Space Partitioning Tree recursively subdivides space using arbitrary hyperplanes (not necessarily axis-aligned). Historically crucial for:

• Hidden surface removal in early software renderers (e.g., for Doom).
• Indoor level rendering and portal culling.
• Solid geometry operations (CSG).

BSP trees create a strictly convex partitioning of space. They are more computationally intensive to build than axis-aligned BVHs but can provide optimal visibility ordering for static architectural environments.

A Uniform Grid is the simplest spatial indexing structure, dividing space into a regular 3D array of axis-aligned cells of equal size. Objects are placed into every cell they intersect. It is highly effective for:

• Scenes with uniformly distributed objects.
• Massively parallel collision detection on GPUs.
• Voxel-based physics and fluid simulation.

Performance degrades with non-uniform object distributions ("teapot in a stadium" problem). It serves as a fast broad-phase complement to a BVH's narrow-phase precision.