Bounding Volume Hierarchy (BVH)

A BVH recursively subdivides a scene's geometric primitives (e.g., triangles, spheres) into a binary or n-ary tree. Each node in the tree represents a bounding volume (like an axis-aligned bounding box or sphere) that encloses all the geometry of its child nodes. This creates a spatial hierarchy where a query can quickly discard large groups of objects by testing against high-level volumes before descending into finer, more expensive detail.

The efficiency of a BVH is determined by its construction method. Common algorithms include:

• Top-Down Construction: The standard approach. Recursively splits a set of primitives, often using a Surface Area Heuristic (SAH) to choose the optimal split plane that minimizes the expected cost of future traversal queries.
• Bottom-Up Construction: Starts with leaf nodes (individual primitives) and iteratively merges them into larger parent nodes.
• Spatial Splits vs. Object Splits: An object split assigns a primitive entirely to one child. A spatial split can clip a primitive if it straddles a partition plane, often leading to tighter bounds but increased tree complexity.

The most common bounding volume type due to computational efficiency. An AABB is defined by its minimum and maximum extents along the X, Y, and Z axes. Key properties:

• Fast Intersection Tests: Ray-AABB intersection requires only a few comparisons and multiplications.
• Memory Efficiency: Can be stored as two 3D vectors (min, max).
• Tightness Trade-off: AABBs are not always the tightest possible fit for rotated geometry, but their speed for traversal outweighs this limitation in most applications.

Traversing the BVH tree is the core of its acceleration. For a ray tracing query:

1. Start at the root node.
2. Test the ray against the node's bounding volume.
3. If it misses, discard the entire subtree.
4. If it hits, recursively test its children.
5. Upon reaching a leaf node, perform an exact intersection test with the contained primitives. Optimizations include front-to-back traversal order (visiting the closer child first to find an early hit) and packed SIMD ray tests (testing one ray against multiple boxes simultaneously).

Static BVHs are built once for immovable geometry and offer optimal traversal speed. Dynamic BVHs must accommodate moving objects. Strategies include:

• Refitting: Update bounding volumes bottom-up after object movement without rebuilding the tree topology. Fast but can lead to progressively looser bounds.
• Incremental Rebuilds: Periodically or partially rebuild sections of the tree that have become inefficient.
• Bounding Volume Types for Dynamics: Spheres or Oriented Bounding Boxes (OBBs) can sometimes provide tighter fits for rotating objects than AABBs, though with a more expensive intersection test.

BVHs are fundamental to real-time and offline systems requiring complex spatial queries:

• Ray Tracing & Path Tracing: The definitive structure for accelerating millions of ray-triangle intersection tests per frame.
• Collision Detection: Used in physics engines (Havok, Bullet) to quickly find potentially colliding pairs of objects in complex scenes.
• Frustum Culling: Determining which objects are within a camera's view by testing against the view frustum's planes.
• Proximity Queries: Finding all objects within a given radius of a point.

The computational process of detecting the intersection of two or more objects within a simulated environment. A BVH is the primary acceleration structure for broad-phase collision detection, which quickly eliminates pairs of objects that are too far apart to possibly collide. This is achieved by testing the overlap of their bounding volumes (like Axis-Aligned Bounding Boxes) before performing expensive exact intersection tests on the object geometry.

A rendering technique that generates images by tracing the path of light rays through a scene. A BVH is the standard acceleration structure for ray tracing, as it allows the renderer to efficiently find which objects a ray intersects. Instead of testing a ray against every triangle in a scene (e.g., millions), the ray traverses the BVH tree, only descending into nodes whose bounding volumes are hit, dramatically reducing computational cost and enabling realistic global illumination effects.

The general class of algorithms that organize geometric objects in space to enable efficient queries. A BVH is a type of spatial partitioning structure. Other common structures include:

• k-d Trees: Space-partitioning trees for organizing points in a k-dimensional space.
• Octrees: A tree data structure where each internal node has exactly eight children, used to partition a 3D space by recursively subdividing it into eight octants.
• Binary Space Partitioning (BSP) Trees: Recursively subdivide space using hyperplanes. Unlike these, a BVH is an object partitioning scheme, grouping objects rather than partitioning the space itself.

The most common type of bounding volume used in a BVH. An AABB is a rectangular box whose edges are aligned with the coordinate axes of the scene. Its alignment simplifies overlap tests and intersection calculations with rays, requiring only min/max comparisons. In a BVH, each node stores an AABB that encloses all geometry within its subtree. The efficiency of the hierarchy depends heavily on how tightly these AABBs fit their contained objects.

A software component that provides an approximate simulation of physical systems like rigid body dynamics and soft body dynamics. Modern real-time physics engines (e.g., NVIDIA PhysX, Bullet, Havok) rely on BVHs or similar structures (like Sweep and Prune with AABBs) to manage the broad-phase of their collision detection pipeline. This allows them to scale to environments with thousands of interacting objects by efficiently culling non-interacting pairs before detailed contact resolution.

A volumetric representation where the value at any point in space is the shortest distance to a shape's surface, with sign indicating inside (negative) or outside (positive). While SDFs offer extremely fast ray intersection and proximity tests, they can be memory-intensive for complex scenes. BVHs and SDFs can be used in a complementary fashion: a BVH can provide coarse scene traversal to quickly locate regions of interest, after which a detailed SDF lookup is performed for precise intersection or collision data.