This page runs from a web server, not from a file: in the repository run python3 -m http.server 8000 and open http://localhost:8000/tutorial/.

Part IV · Path tracing · Chapter 13

Following a path

Light reaches a pixel straight from a lamp, or after one bounce, or two, or ten. A path tracer follows one random route at a time, from the eye, bouncing off whatever it hits (from the eye, because only the light that reaches the eye matters, and most light a lamp gives off never does; chapter 1), and keeps one number along the way: how much of the light at the far end would still make it back. This chapter follows that number, says what is lost by stopping after a fixed number of bounces, and shows a fair way of stopping early.

1One path, bounce by bounce

A ray leaves the eye and hits a wall: one ray is one straight piece of the path, so a path that bounces four times is five rays. The wall is matte: it scatters light in every direction, so the path picks one at random (more often near straight out of the wall, as chapter 8 explains) and carries on. It hits something else, and bounces again, until it happens to hit the lamp. What comes back is the lamp's light, but not all of it: each wall the path bounced off keeps part of the light, here 20%, and passes on its albedo, 0.8. So the path keeps a running product, its throughput, written β ("beta"): 1 on the way out of the eye, 0.8 after the first wall, 0.64 after the second, and so on. When the path finds light, it adds β times that light. This path bounced four times and found the lamp carrying β = 0.41.

Press Another path a few times: most go on bouncing for a long while before they find the lamp, and each brings back a different amount. The pixel's value is their average (chapter 12).

The mathsThe path's estimate

A path with bounces at points 1, 2, … k that ends on a light of brightness L_e (its radiance, chapter 5) returns the light times the product of one factor a bounce; ∏ means "multiply together", as Σ means "add together", here the factors of bounces 1 to k:

L = β_k L_e, β_k = ∏_i=1…k f_i cos θ_ip_i

f: how much light the surface sends from the new direction towards the old (its BSDF, chapter 8)
cos θ: the slant the light arrives at: θ is its angle from the surface's normal, the arrow straight out of it, as in chapter 1
p: how likely the random direction was to be picked (its probability density)

For a matte surface of albedo ρ (the share it passes on), f = ρ/π, and with directions picked in proportion to cos θ, p = cos θ/π (chapter 8 says where the π comes from). So each factor is (ρ/π) cos θ / (cos θ/π) = ρ: everything cancels but the albedo. Averaged over many paths, these estimates add up the light arriving after any number of bounces, which is what the rendering equation asks: the light leaving a point is the light it gives off plus all the light arriving at it, passed on.

A closed room lit by a thin lamp hung under the ceiling, glowing from both faces with a brightness of 1. One path from the eye, each piece labelled with the throughput β it carries; the red dots are its bounces, and the last piece, in the lamp's orange, is the one that finds it.

2Where to stop

In a closed room a path never runs out of walls to hit, so a renderer has to stop it somewhere. The simplest rule is a cap: at most so many bounces. Whatever light the path would have found after that is lost. This figure traces paths from every pixel of the eye's film, each up to 40 bounces, and reads each path's running total (the light it has gathered so far, not its β) as it stood after 0 bounces, after 1, after 2, and so on: what that path would have brought back with that cap. A cap of 0 is the lamp seen straight from the eye. Each bar is the average over all paths, in units of the lamp's brightness, against the red line, a cap of 40. With walls of albedo 0.8, a cap of 1 keeps 46% of the light, 3 keeps 72%, 8 keeps 95%.

White walls (0.95) give back more at every bounce, so more of the light comes late: a cap of 3 keeps only 46% (the same number as before, for a different cap), 8 keeps 76%. A cap makes the picture darker than it should be, and darkest where light bounces most (a white room, a corner, a light shining into a box). That is a bias: no number of samples brings it back. ShadyTracer's cap is 10 bounces by default, and its Render settings take it up to 40 (Max Bounces). A second cap, Max Diffuse Bounces, counts only the bounces off matte and glossy surfaces (section 4).

The room's average light, in units of the lamp's brightness, with a cap of 0, 1, 2, 3, 4, 6, 8, 12, 20 and 40 bounces (evenly spaced, though the caps are not): each bar is the average over every path read at that cap, with its error bar; the red line is the cap of 40. It fills in as paths are traced. Each setting's plot is scaled to fit: the white room is about twice as bright as the light one. A cap of 40 is all but the whole answer in the light room (0.8⁴⁰ is 0.0001), and a little short in the white one, where a path still carries 0.95⁴⁰ = 0.13 after 40 bounces, if it gets that far.

3Stopping fairly

After many bounces a path carries little: at β = 0.1 it can bring back a tenth of what it finds, and it costs as much to trace as a path at full strength. Russian roulette stops it early, fairly. After the third bounce, the path goes on with a probability p equal to its β (kept between 0.1 and 0.95), and stops otherwise. A path that goes on divides its β by p, so it carries more, exactly making up for its stopped companions: on average, nothing is lost. In numbers: ten paths each carrying β = 0.2 would bring back 10 × 0.2 = 2 lamps' worth of light between them. Roulette keeps each with a chance of 0.2: about two go on, each now carrying 0.2 / 0.2 = 1, and 2 × 1 is 2 again. That is true of every survivor: with p equal to β, β / p is exactly 1, so a path that survives carries full strength again, and goes on as long as a fresh one would. The plot shows how many paths end after each number of bounces, without roulette (thin grey) and with it (bold blue). Without it, a path ends only when it finds the lamp (or at the cap of 40); with it, most paths end soon after the third bounce, and the survivors, back at full strength, make the long tail.

The readout compares the two over the same paths; once all 24,000 are traced the averages agree within their error bars. With roulette a path costs 4.7 rays instead of 10.0, and its result is noisier: an error bar of 0.0028 against 0.0020. But the rays one path without roulette costs buy 10.0 / 4.7 = 2.1 paths with it, and an error bar shrinks as one over the square root of the paths (chapter 12): 0.0028 / √2.1 = 0.0019. For the same number of rays, roulette's error bar is 0.96 of the other's. Counted in rays, roulette is a small win in this room; counted in time on a GPU, section 5 says why it has not been, so far.

Now switch off Survivors divide β by p. The game is no longer fair: a path that goes on keeps its β as it was, nothing makes up for the ones stopped, and the average falls to about two-thirds of the light (0.233 against 0.346 once all the paths are in). That is a bias: no number of samples brings it back. Its error bar, for the same rays, reads smaller than the fair game's (about 0.73 of it): an error bar measures how much the tries disagree with each other, never whether they agree on the right answer (chapter 12). Without the survivors' boost the tail is gone too: a path that survives keeps its small β, and is soon stopped.

Switch the boost back on, and the other controls move where roulette starts and change the walls. In a dark room (0.5), the error bar for the same rays is 0.68 of the other's, a clear win; with white walls (0.95) it is 1.60, a loss. There β stays high, so roulette stops few paths and saves few rays (7.4 a path instead of 10.0), while every path it does stop still carried a lot of light, which the survivors make up in jumps (the readout's numbers; the reason is this page's reading of them). Point at the curves to read them.

The mathsWhy nothing is lost

A path whose remaining light would be X is replaced by

X′ = X / p with probability p, 0 otherwise

and the average of X′ is p · X/p + (1 − p) · 0 = X: the same as before, for any p above 0. Only the spread grows, and it grows least when the paths that stop are those that carried little anyway, which is why p follows β. The floor of 0.1 keeps a survivor from carrying more than ten times its β: one lucky survivor of a very weak path would otherwise be a bright speck (a firefly). The ceiling of 0.95 means even a path at full strength takes a 5% chance of stopping: with p = β, a path whose β is 1 or more would never stop, and roulette would do nothing for it.

The same paths with Russian roulette off (thin grey) and on (bold blue): how many end after each number of bounces, as a share of all paths. The dashed line is where roulette starts. The readout compares the two averages, their error bars and their cost in rays.

4How ShadyTracer does it

Each bounce draws a direction from the surface's material and multiplies the ray's throughput by the draw's weight, f cos θ / p:

Then the cap and the roulette, at the end of every bounce:

Between them sits a second cap, Max Diffuse Bounces (version 0.75.0), which counts only the bounces that scatter light about, off a matte surface, rough gloss or a point in dust (the code's EV_EVAL events: a surface a light's connection can evaluate, chapters 18 and 19), and lets mirrors and clear glass pass, which only Max Bounces caps. At 0 a picture is the direct light alone, but still through lenses, mirrors and glass; each step up adds one bounce off a wall. Its count rides in the upper half of a word the ray already had (Ray.counts; the lower half counts the march's steps), since the ray had no room for another field. The comment is long because a picture's light also comes from the light's side, its photons and the photon map (chapters 18 and 19), and the cap must cut the same paths from every side, or light would be counted twice or lost. At 40, the default, or anywhere at or above Max Bounces, it cannot bind, and the kernels are told 0, no cap ().

5Tricks and trade-offs

First, how ShadyTracer runs its paths, which decides what roulette can save. It does not trace each path on its own. It moves every path of a sample one step at a time, all together, in rounds (chapter 22): each round runs five kernels in turn, over the paths still going. Until version 0.10.0 the number of rounds a sample got adapted to its paths: fewer when they ended early. Since then every sample gets the most a path could need: Max Bounces + 1, plus rounds for marching, since a long march to the next surface can take more than one round. A round costs time even when only a few paths are left in it, like a bus that drives its whole route for two passengers, though a nearly empty round costs less than a full one.

Each trick below is stamped with how it is known; point at a stamp to see what it means.

Roulette is fair, measured. Four runs on the user's graphics card (chapter 0: an NVIDIA of the Pascal family), 1024 × 1024, 32 samples, with roulette off and on and a cap of 10 and 40, all landed within 0.15% of each other (the comment above, and docs/TESTING.md, "Russian roulette is unbiased").

And still off. The same bench measured roulette at +0.9% time per sample, inside the noise. Without roulette, 1416 rays were still going when the last round ended them; with it, 360. Fewer rays, the same rounds, no time saved. The comment's verdict, until version 0.67.3: it should earn its keep in a scene deep enough for the rounds to shrink, "and that is the case to find before changing the default".

The rounds no longer shrink. That verdict spoke of rounds that can shrink. Since version 0.10.0 every sample gets the most a path could need, Max Bounces + 1 plus its marching (), so roulette can save only the work inside each round, never a round: a round over fewer paths does less work. On the user's card an added, nearly empty round cost 0.13 to 0.42 ms of the graphics card's time (the comment on the round budget in raytrace_main.js). Whether roulette's saving inside the rounds is ever worth it is not measured. This chapter found the verdict out of date; since 0.67.3 the comment says what this one does, the excerpt's last lines.

A weight of zero ends the path. A direction that carries nothing (a reflection that would go into the surface, say) ends the path at once: marching it would cost a full trace and add nothing (the comment above the bounce).

6What went wrong before

A brightening that was the measurement. Switching roulette on once brightened the picture by 6 to 8%, and the comment recorded it as unexplained, naming its own suspect: the renderer then adapted how many rounds a sample got, and roulette, by ending paths early, pushed that number down, so the two runs were not given the same work. With the adapting pinned off, the gap vanished (the measurement above). Why the unequal work came out brighter rather than darker, neither the comment nor the test says, and the code that did it is gone. The lesson the repository drew: compare two settings only with everything else held still.
Roulette written and switched off. It was in the code, commented out, so every path ran to the cap however little it carried.
A clamp that hid a wrong formula. Each bounce's weight used to be clamped to [0, 10], to cut bright specks at glancing angles. The specks came from a wrong probability for the direction drawn; with that fixed, the weights stay moderate on their own, and the clamp, which would only have biased the picture, is gone.

7Try it

In the first figure, raise the bounce limit to 20 and find a path that bounces more than ten times. What is its β when it finds the lamp?
In the second, compare dark walls with white ones: at which cap does each keep 95% of its light?
In ShadyTracer, set Max Bounces to 1 and then to 10 in the Render settings, in a room scene. Where does the picture darken most?