Wavefront path tracing

1A sample, iteration by iteration

The words first. A path is a ray's whole journey from the eye: a leg from the eye to the first surface, then a leg from each bounce to the next. To march a leg is to step along it, each step as long as the distance to the nearest surface, until it reaches one (sphere tracing, chapter 2): a leg takes many steps, more where it passes close to things. To shade a point a leg reached is to work out what light it finds there and where the path goes next (chapter 13), from the surface's material and its normal, the direction it faces. NEE, next-event estimation, is the shadow ray each shaded point aims at the sun (chapter 14). And chapter 21's lanes: the card runs threads in lock-step groups of 32, each group as long as its slowest thread, the lanes whose thread has finished waiting idle. (The 32 lanes of a group and the 32 steps of a pass below are the same number by chance, not by design.) A pixel gets 16 paths, each a random guess at its light, averaged (chapter 12): one would be too noisy.

The sunlit room of chapter 20, without its dust, its walls paler so paths go round it: 64 pixels, 16 paths each, 1024 paths in one sample. Every path starts in the first iteration's queue. Each iteration runs the same kernels in turn: the march moves every waiting ray up to 32 steps; shade handles the rays that reached a surface or left the room, queues a shadow ray towards the sun and puts each path's next leg in the next iteration's queue; occlusion traces the shadow rays queued the iteration before. Point at the bars for each iteration's counts. In the first, all 1024 rays marched: 774 reached a surface, 38 left the room, and 212 were still on their way after 32 steps. Only 523 shadow rays were queued from the 774 hits, because a hit queues one only where the sun is above its surface: none from the ceiling, which faces away. That is why the shadow bars zig-zag: legs that start at the eye or the ceiling mostly land on the floor, which faces the sun, and legs from the floor mostly land on the ceiling, which does not. The first iteration traces no shadow rays, since none was queued before it. The strip under the bars is the picture itself.

Paths end at different times: at the sky, at the bounce cap (10 here, ShadyTracer's default), or out of steps: a path may take 400 march steps in all, maxiter. So the queues drain. A path that never needed a second pass for a leg reaches its eleventh surface in iteration 11 and ends there at the cap, so iteration 12 drops from 822 rays to 475: those left had a leg that took more than one pass. Iterations 12 to 19 carry fewer and fewer, and 20 to 24 none at all, but each is still dispatched: the card is told to run zero workgroups, which costs little but not nothing. How many iterations to run is decided before the sample starts, because the program on the main processor does not wait to read the counts back: a number read back from the card arrives only after everything sent before it has finished, so asking would leave the card idle while the program waits for the answer and sends the next iteration.

So ShadyTracer runs the worst case. (An iteration and a pass are the same here: one round of every kernel.) Each pass of 32 steps either ends a leg (the ray reached something) or uses all 32 steps without ending it. Take a path of three legs of 40, 10 and 30 steps: the first leg takes a full pass and then 8 steps of a second pass, the second and third legs one pass each, 4 passes in all, 3 that end a leg and 1 full. A path has at most 11 legs (10 bounces and the first), and at most 400 steps, so at most 12 full passes: 23 passes at most. The budget is (10 + 1) + 400 / 32 rounded up, 24, which leaves the last iteration to trace the shadow rays the 23rd queued.

With 8 iterations, paths still going at the last are stopped, in two ways. A ray still marching on the last pass is flushed: it ends there and hands in the light it has gathered, 88 of them here, and what its later legs would have found is never traced. A path shaded on the last pass has its next leg written for a march that never comes, and casts no shadow ray, since nothing would trace it (the shade kernel skips NEE on the last pass): 775 cut. A path hands its light in only when it ends, so a cut path hands in nothing and is not counted at all: its pixel's average leaves it out (chapter 23's resolve divides by the paths that ended, and skips a pixel none did). Only 249 of the 1024 paths are counted; 2 pixels have none (outlined in the strip). The picture's mean, over the paths counted, reads 0.0152 against 0.0153.

So what a short budget costs is first samples: three quarters of the paths not counted is a noisier picture, as the flush's own comment says ("lowering it now costs convergence", in section 4). One sample cannot show more than that; averaged over 20 runs of this sample with other random numbers, the mean held at 12 and 10 iterations and fell 4% at 8, 14% at 6 and 30% at 4. The shorter the budget, the more of the paths counted are flushed ones, whose later legs were never traced: light that averaging more samples cannot bring back, a bias, as a low bounce cap's is (chapter 13). The light tracer's comment says as much of its own connections (). ShadyTracer's budget is always the worst case, where nothing is flushed or cut. Here with 4 iterations: 181 paths counted, 8 pixels with none. Drag the slider to see where the picture stops changing.

2Queues in the card's memory

Inside one iteration, its eight kernels in turn: prep_march, march, prep_shade, surface (each hit's material and normal from the scene, written beside it), shade, prep_occlude, occlude and flip. The rays wait in one of two ray buffers; the march reads one and writes the other, and the next iteration the two swap, so no ray is read and written in the same place at once (a ping-pong). A ray that reaches something is written to the shade queue instead. Each write takes the next free place by an atomic add on the buffer's count, so a thousand threads writing at once never take the same place.

Before each kernel that works on a queue runs a tiny one, a prep kernel of one thread: it reads the count of rays waiting and writes how many workgroups the next kernel needs, into a buffer the card reads that dispatch's size from (an indirect dispatch). The prep kernels themselves are dispatched with a fixed size, one workgroup. The program on the main processor never learns the counts while the sample runs; it records the whole chain once and the card sizes every queue's work itself.

Surface and shade run over the shade queue. Shade writes each path's next leg after the march's survivors in the buffer being written, and each shadow ray to the write side of the shadow queue, which takes turns the same way.

The flip, one thread: the buffers swap roles, and the counts of the side the next iteration will write are cleared. Press Next kernel to step through.

In iteration 2, occlusion traces the 523 shadow rays shade queued in iteration 1. Why a round late: shade writes its shadow rays to one side of the shadow queue while occlusion reads the other, the side written the iteration before, so no shadow ray is read while it is being written (the engine's comment on the occlusion pass); the flip swaps the sides. Shadow rays march too, 32 steps a round: on the last pass, the occlusion runs again, round after round, until every one has ended, because one counted while still marching would be counted unblocked. How many rounds is worked out from the settings, not from the counts: enough for a shadow ray of the most steps a ray may take, 400, which is six more pairs of rounds at the defaults (raytrace_main.js, the shadow pairs).

Iteration 15: 56 rays marched (47 reached a surface, 1 left the room, 1 ran out of steps, 7 go on); the 49 that stopped go to shade, the one out of steps only to be ended there with what it carries. 18 new legs come of the 47 hits: 29 paths reached the bounce cap. One workgroup of 64, on a card that can run thousands at once; each kernel of the iteration is still dispatched and paid for.

3Why split a path

Chapter 21's lanes again, for the whole sample (its first figure shows one group of 32 waiting for its slowest ray). Written as one big kernel, a thread a path, a group of 32 paths marches each leg as long as its slowest path's leg, shades whenever any of its paths has something to shade, and keeps going until its longest path ends, the finished lanes waiting. As a wavefront, each kernel runs over a queue of rays that all need that step, packed into full groups. Time is counted in lane steps, a shading costing what you set (here 20 march steps; that is a model's number, not a measurement): the big kernel's lanes are busy 46% of the time, the wavefront's 74%, and the big kernel takes 1.6 times as long.

If shading cost no more than a step, the wavefront still wins (61% against 33% busy): most of the big kernel's waste is paths of different lengths kept together to the end.

The dearer the shading, the more both are shading, and the closer they come (86% against 64%). In every setting the busy part, in blue, is the same both ways: the same work, done once. Only the waiting differs. (The model leaves out the prep kernels, the flip and the drained tail's launches.) This is the argument Samuli Laine, Tero Karras and Timo Aila made for this way of working (2013). ShadyTracer's code gives reasons of its own as well: a kernel that only marches need not compile the shading code (the march kernel's comment), and each kernel needs only the buffers its step uses, under the eight a kernel may have (chapter 21).