A Bounding Volume Hierarchy cuts ray-intersection cost from linear to roughly logarithmic by skipping missed subtrees

Brute-force ray tracing tests every ray against every primitive, O(n) per ray — prohibitive at millions of triangles. A Bounding Volume Hierarchy (BVH) wraps scene primitives in a tree of nested bounding boxes (typically axis-aligned, AABBs), each node storing the box enclosing everything below it. To trace a ray, test the root box first: if the ray misses it, the whole subtree is skipped; if it hits, recurse into child boxes. This turns the per-ray cost into roughly a logarithmic search (in the spirit of binary search), reducing the expected number of primitive tests to a handful — often single digits, generally under ~20 — even for million-triangle scenes, which is the key reason real-time ray tracing is feasible. The cheap ray-AABB test uses the slab method (three pairs of axis-aligned planes); construction splits primitives along the longest-extent axis. BVH is the most common acceleration structure today, though not the only one (kd-trees historically). GPU ray-tracing hardware has dedicated BVH-traversal units, and the scene must be uploaded as an acceleration structure to GPU memory before tracing.

Examples

A 1,000-triangle teapot: brute force needs 1,000 intersection tests per ray; a multi-level BVH needs only a few box tests plus ~3–5 triangle tests. A 1,000-sphere scene with a balanced split: ~10 box tests plus ~1 sphere test per ray on average. When a ray misses the root box, no interior geometry is tested at all.

Assessment

Explain why a BVH enables efficient ray tracing for million-triangle scenes and what happens at traversal when a ray misses the root box entirely. Sketch a BVH over 8 spheres in a 2×2×2 grid and give the minimum node-level tests a miss ray performs.