Why does a real-time ray tracer need a bounding volume hierarchy, and how does a ray traverse one to find its closest hit?
answer
- boxes around groups of triangles
- a missed box skips its subtree
- nearer child first
- prune beyond the closest hit
- sibling boxes may overlap
basics
~20 sA bounding volume hierarchy nests boxes around groups of triangles so a ray tests a few boxes instead of every triangle. Traversal enters only boxes the ray hits, nearest first, and skips boxes beginning beyond the closest hit so far.
solid answer
~40 sTesting a ray against every triangle is linear in the triangle count, which is hopeless at millions of rays per frame. A `BVH` is a tree in which each node stores an axis-aligned box enclosing everything below it, and each leaf holds a few triangles. If a ray misses a node's box, the whole subtree is skipped. For the closest hit you keep a stack, visit the nearer child first, record the nearest triangle hit distance `t`, and prune any node the ray enters only beyond that `t`. Because sibling boxes may overlap, a hit in one child does not end the search. With a well-built tree the work per ray grows roughly logarithmically with triangle count, and a shadow ray can stop at its first hit.
code
pseudocode · 20 linesfunction traceClosest(ray, bvh):
closestT = ray.tMax
closestTri = none
stack = [bvh.root]
while stack is not empty:
node = stack.pop()
-- skip a box the ray misses, or enters only beyond the closest hit so far
if not boxOverlapsRay(node.bounds, ray, ray.tMin, closestT):
continue
if node.isLeaf:
for tri in node.triangles:
t = intersectTriangle(ray, tri) -- none on a miss
if t is not none and t >= ray.tMin and t < closestT:
closestT = t
closestTri = tri
else:
near, far = orderByEntryDistance(ray, node.left, node.right)
stack.push(far) -- pushed first, popped last
stack.push(near)
return closestTri, closestTgo deeper
Recall that a BVH is a tree of boxes around groups of triangles and that a missed box skips everything inside it. Be ready to sketch three levels on a whiteboard.
Walk through closest-hit traversal step by step: nearer child first, the shrinking closest distance, and why overlapping siblings stop you ending at the first hit.
Tie traversal cost to tree quality and ray coherence: why grazing and scattered reflection rays cost more than camera rays, and what that implies for which effects you trace.
Treat traversal cost as an input to the ray budget: which rays are coherent and cheap, which are scattered and expensive, and what each hardware tier can afford.
## The problem a BVH solves A ray tracer answers one query over and over: given a ray with an origin and a direction, which triangle does it hit first, and at what distance `t` along the ray? Testing every triangle answers it correctly, but the cost is linear in the triangle count. A scene of a few million triangles traced by a couple of million rays per frame would need trillions of triangle tests, so brute force is out of reach long before any shading happens. A **bounding volume hierarchy (BVH)** replaces most of those tests with cheap box tests. If a ray misses a box, it misses everything inside it, so one failed test discards a whole group of triangles at once. ## What the tree holds - **Interior nodes** store an **axis-aligned bounding box (AABB)** that encloses everything beneath them, plus links to their children. A binary tree has two children per node; many GPU implementations use wider nodes with four or more children, so that one memory fetch feeds several box tests. - **Leaf nodes** store a small number of triangles, or references to them. - **Object partitioning**: a BVH splits the *triangles* into groups, not *space* into cells. In a plain BVH, without the spatial splits some builders add, every triangle sits in exactly one leaf, so memory is bounded: a binary tree with one triangle per leaf has `N` leaves and `N - 1` interior nodes, `2N - 1` nodes in total. - **Overlap is allowed**: because each box simply wraps its own triangles, sibling boxes can overlap. This property shapes traversal. ## Traversing for the closest hit The usual traversal keeps a stack of nodes still to visit and the closest hit distance found so far. 1. Push the root and set the closest distance to the ray's maximum length. 2. Pop a node and test the ray against its box over the interval from the ray's start to the closest distance. If the box is missed, or entered only beyond the closest hit already found, skip the whole subtree. 3. At a leaf, test the ray against each triangle; when a triangle is hit nearer than the closest distance, record it and shrink the closest distance. 4. At an interior node, push both children, the farther one first, so that the nearer child is popped next. 5. Repeat until the stack is empty, then return the recorded hit. Visiting the nearer child first tends to find a close hit early, after which every box beyond that distance is pruned. It does **not** let traversal stop at the first hit: the sibling box may overlap the near child and contain a triangle even closer. The ray-versus-box slab test and the ray-versus-triangle test are intersection maths covered with geometric tests; the hierarchy only decides which of those tests to run. A **shadow ray** asks a simpler question: is anything between this point and the light? It can end at the first hit it accepts, in any order, so it usually costs less than a closest-hit query. ## What a ray's cost depends on - **Tree quality**: tight boxes that overlap little let most subtrees be pruned. With a well-built tree the work per ray grows roughly logarithmically with triangle count; a badly built tree degrades towards linear. - **Where the ray goes**: a ray grazing dense geometry, such as a low shot across a field of grass, enters many overlapping boxes. - **Coherence**: camera rays from neighbouring pixels follow nearly the same path through the tree, so a SIMD group of 32 or 64 lanes (depending on the GPU) fetches the same nodes. Reflection rays off a bumpy surface scatter in different directions, visit different nodes, miss the caches and diverge across lanes. - **Ray length**: shadow rays limited to the light's distance and short ambient-occlusion rays prune far geometry immediately. ## A BVH compared with other structures | Structure | Splits | A triangle appears | Strength | Weakness | |---|---|---|---|---| | BVH | triangles into groups | in one leaf, without spatial splits | bounded memory; boxes are cheap to update when vertices move | sibling boxes overlap | | kd-tree | space into non-overlapping cells | in every cell it straddles | front-to-back cell order allows an early exit | duplicated triangles; hard to update | | Uniform grid | space into equal cells | in every cell it touches | very fast to build | poor when detail is uneven | Real-time ray tracing settled on the BVH mostly because it can be updated cheaply when meshes move or deform and because its memory size is predictable from the triangle count.
- Why are reflection rays off a bumpy wet surface slower to trace than camera rays, even with the same tree?Camera rays from neighbouring pixels are coherent: they walk nearly the same nodes, so the lanes of a SIMD group share memory fetches and stay in step. Reflection rays off a bumpy surface point in scattered directions, so neighbouring lanes visit different nodes, miss the caches and wait on each other. Tracing them at lower resolution, sorting or binning rays by direction, and letting hardware that can do so regroup hit shading all reduce the penalty.
- How does a shadow ray's traversal differ from a closest-hit ray's?A shadow ray only needs to know whether anything blocks the segment to the light, so it can end at the first hit it accepts instead of searching for the nearest one. Its length is capped at the light's distance, which prunes geometry behind the light, and it usually skips hit shading entirely. Near-first ordering still helps, because an early hit ends the whole query.
Like looking for a book by wing, then aisle, then shelf: once you know the book is not in the east wing you never walk its aisles. Unlike a library, two aisles here may overlap, so finding one copy does not end the search until nothing nearer could remain.
- Once the ray hits a triangle in one child, the sibling child can be skipped.
- A BVH cuts space into non-overlapping cells, like a kd-tree.
- Every ray costs the same, because the tree has a fixed depth.
- The hierarchy removes the need for ray-triangle tests altogether.
- Traversal cost does not depend on where the ray points or how coherent neighbouring rays are.