skip to content

Real-Time Ray Tracing

How ray tracing fits a raster frame: two-level acceleration structures and rebuild cost, which effects get traced, denoising that makes 1 sample per pixel usable. Interviews probe BVH trade-offs.

on this pageshow

explore

questions

6

Why does a real-time ray tracer need a bounding volume hierarchy, and how does a ray traverse one to find its closest hit?

level: juniorimportance: must knowfreq 45%

answer

  1. boxes around groups of triangles
  2. a missed box skips its subtree
  3. nearer child first
  4. prune beyond the closest hit
  5. sibling boxes may overlap

basics

~20 s

A 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 s

Testing 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 lines
pseudocode
function 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, closestT

go deeper

for a junior

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.

for a middle

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.

for a senior

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.

for a principal

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.
open as a page

Why do real-time ray tracers split the scene into bottom-level and top-level acceleration structures, and what does each level hold?

level: middleimportance: must knowfreq 42%

basics

~20 s

A bottom-level structure holds one mesh's triangles in object space; a top-level structure holds instances, each a transform pointing at a bottom-level structure. Moving objects then rebuild only the small top level, and repeated meshes share one bottom level.

open as a page

In a ray-tracing pipeline, what do the ray-generation, closest-hit, any-hit and miss programs each do, and why does alpha-tested foliage need any-hit?

level: middleimportance: should knowfreq 30%

basics

~20 s

Ray generation launches rays per pixel and writes results; closest-hit shades the nearest accepted hit; miss runs when nothing is hit; any-hit runs on candidate hits and can reject them. Foliage needs any-hit to ignore hits where its alpha texture is transparent.

open as a page

Why do hybrid renderers trace about one reflection ray per pixel on rain-wet streets, and how does spatiotemporal denoising make that noisy result usable?

level: seniorimportance: should knowfreq 38%

basics

~20 s

A frame can rarely afford more than one ray per pixel per effect, so each pixel gets one noisy Monte Carlo sample. A denoiser reprojects and accumulates samples over frames, then blurs spatially with edge-stopping weights guided by an estimated per-pixel variance.

open as a page

In a scene with destructible, deforming meshes, when do you refit a bottom-level acceleration structure instead of rebuilding it, and what quality does a refit lose?

level: seniorimportance: should knowfreq 35%

basics

~20 s

Refit when a mesh keeps its triangle list and deforms modestly, like a skinned character: recomputing boxes bottom-up is cheap but keeps the old grouping, so boxes bloat and overlap. Rebuild when topology changes or that bloat makes traces too slow.

open as a page

As rendering lead, how do you decide which effects a hybrid renderer traces, and with what ray budget, across hardware tiers from no ray-tracing support upward?

level: principalimportance: should knowfreq 25%

basics

~20 s

Rank effects by what raster cannot fake (off-screen reflections, area-light shadows, dynamic bounce light) against the cost of rays, structure updates and denoising, then give each hardware tier a budget: fallbacks on the lowest, few reduced-rate effects mid-range, more on top.

open as a page