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 VI · The machine · Chapter 23

Adding up light on a GPU

A path that ends hands its light to its pixel; so does a shadow ray that reaches the sun, and a photon's connection to the camera. In one sample many of them land on the same pixel, from threads running at the same moment, and the sum must come out right. Then the sample is folded into the picture's average, and a picture too big for the graphics card's buffers is traced in pieces that must add up to one sample. This chapter is those three, and the bugs each one had.

1Many hands on one pixel

First, what is being added. A path is a ray's whole journey from the eye, bounce after bounce (chapter 13); a shadow ray is a ray from a point a path reached towards a light, which adds the light's share if nothing blocks it (chapter 14); a photon is a ray sent from the sun, joined to the eye where it lands, which is how the bright patches glass focuses are found (chapter 18). Each is one thread of a kernel, a program the graphics card runs once for every item (chapter 21). A sample is one try at the whole picture: one camera path through every pixel, a random guess at that pixel's light (chapter 12). One sample is noisy, so the picture is the average of the samples so far, and it settles as they come. Two buffers hold this. The frame buffer collects this sample's light, pixel by pixel, from whatever lands there: the paths that end, the shadow rays that reach the sun, the photons joined to the eye, and how many paths ended there, n (normally one). The picture (the accumulation buffer) holds the average. Once a sample, after every ray of it has ended, a kernel called resolve folds each pixel's frame into its average and clears the frame for the next sample (section 4). Folding in is one line of arithmetic: an average of n samples, m, and one more, s, make (m × n + s) ÷ (n + 1); the average of 3 and 5 is 4, and with a third sample of 10 it is (4 × 2 + 10) ÷ 3 = 6.

Two more things resolve does. The average can be given a window, a largest n: past it every new sample gets the same weight, 1 ÷ (window + 1), and each older sample's share shrinks by the same factor every sample, so old samples fade away gradually, an exponential moving average (EMA); with no window set it is the plain average of every sample. And after the camera moves, the count starts again at 0, so the first new sample replaces the picture instead of being averaged into the old view (section 4's reset excerpt). A pixel whose path did not end in this sample (cut short, chapter 22) has n = 0, and resolve leaves its average as it was.

Six threads each add some light to one pixel, 26 in all. The plain way is two steps: load the pixel's number, then store it plus your own. In one group in lock-step every thread loads first, all reading 0, then all store at once, each its own 0 plus its value: one store is kept (which one, the graphics card decides; the figure keeps the last thread's), so the pixel ends at 2, and 24 of the 26 are lost. Point at a box to follow one thread.

Threads of different groups interleave at no set pace, and whether a load and its store have another thread's store between them is luck: here the pixel ends at 10, after falling back more than once to a value a thread loaded long before (follow the top row). ShadyTracer once folded each path into the picture this way, a load, the arithmetic and a store, and lost updates; with one ray a pixel no two threads ever met at a pixel, which hid it (section 6).

An atomic add is one step no other thread can come between: 26, every time. WGSL, the GPU's language (chapter 21), has atomic adds only for whole numbers in a 32-bit word (4 bytes): u32, from 0 to 4,294,967,295. None for a floating-point number, an f32, the kind with a decimal point that the GPU computes light in. So ShadyTracer's frame buffer once held whole numbers: fixed point, 65,536 to a unit of light (section 2).

For a float, a compare-and-swap: load the number, work out the new one, and write it only if the pixel still holds what was loaded; if not, take what it does hold and try again. Every thread's light is counted, at a price when they crowd one pixel. In this figure's model of one group, the swaps on one address go one after another, so one succeeds a round and the others try again: 5 fail in the first round, 4 in the next, then 3, 2, 1, 15 failed swaps for 6 threads (the red staircase).

Sixteen threads on one pixel: 120 failed swaps, 17 rounds where an atomic add takes one. In the model the failures grow as the square of the crowd, n(n − 1)/2. Paths spread over a picture rarely crowd a pixel; light tracing's connections pile into the few pixels of a caustic (chapter 18), and section 5 has a measurement that may be this.

Each row a thread and the light it adds; each column a step in time (a round in lock-step, one thread's step when interleaved); along the top, the pixel's value after it. L loads, S stores (with the value it writes), + is an atomic add, C a compare-and-swap, marked ✗ in red where it failed. The readout counts steps (boxes) and, in lock-step, rounds (columns). Point at a box. Choose the way of adding, the schedule and the threads; run again for other values.

2Numbers that fit the light

The old frame buffer kept light as whole numbers, 65,536 to a unit, so it could use the integer atomic add: a light of 0.3 was stored as round(0.3 × 65,536) = 19,661, which reads back as 0.29998779: off by 0.000012, which is one part in 25,000 of the 0.3 (4 × 10⁻⁵ of it). Fine while the light was a number near 1.

Then ShadyTracer moved to real units (chapter 5), and a sunlit white wall is about 25,000 cd/m² (candela per square metre, the unit of how bright a surface looks). A pixel's word holds at most 4,294,967,295, which at 65,536 to a unit is 65,535 units and a bit, for everything a pixel gets in a sample. Past its largest a whole number wraps round, starting again from 0, so to keep several contributions from wrapping each was clamped at 10,000: the wall lost 60% of its light. An f32 (a 32-bit float) holds 25,000 itself exactly, and values near it to about 0.002.

The sun's disc is about 1.6 × 10⁹ cd/m²: clamped to 10,000, all but six parts in a million gone. These limits came from the number format, not from anything physical.

And at the other end, anything under 1/65,536 was cut to 0: a faint contribution of a millionth vanished whole. An f32 keeps every value on this line to about seven significant digits. Drag the contribution along the line. So the frame buffer holds the bits of f32s now, added by the compare-and-swap loop of section 1.

A line of light values from 10⁻⁸ to 10¹⁰, each mark a hundred times the last (10⁴ is 10,000). Above it, what the old fixed-point frame buffer did with a contribution (kept, hatched in the shadow rays' colour; lost, in red), and what an f32 does (all of it, blue). The values the code names are marked below. Drag the contribution.

3Bigger than the buffer

A sample traces a camera ray for every pixel and every photon the light tracer asked for, and the rays in flight must fit the ray buffers: 1 GiB, 512 bytes a ray (two ray buffers and a shade queue item), 2,097,152 rays. At 1280 × 720, 921,600 camera rays and a million photons fit at once: one batch. The batches' plan here is ShadyTracer's own function, run in this page.

At 3840 × 2160, 8,294,400 camera rays and a million photons are 5 batches. Each batch is a fair slice of every stream (1,658,880 camera rays and 200,000 photons each), runs the whole wavefront chain of chapter 22, and leaves its light in the frame buffer; resolve folds it into the average once, after the last. Each photon carries its share of the light, the light divided by the photons: divided by the sample's whole count, a million, not the batch's 200,000, or each batch would bring a whole sample's light and the five would count five times over. So the batches add up to one sample: the picture's size changes how long a sample takes, and nothing else.

With the photon map on (chapter 19), a camera ray that reaches a surface gathers the photons stored around it, so every photon of the sample must be stored before the first camera ray looks: the photons go in batches of their own, first, 2 batches where 1 would fit.

One sample's batches: each bar a batch, its camera rays blue and its photons above them in the sun's colour, against what the ray buffers hold (dashed, red). Point at a batch. Choose the picture's size and the photons, and switch the photon map on.

4How ShadyTracer does it

Why the frame buffer holds floats, and what adding to it costs:

Once a sample, one thread a pixel folds the frame buffer into the picture: no two threads touch the same pixel, so this read, change and write is safe:

After a camera move, the first sample replaces the picture rather than fading into it:

And the batches' plan, which section 3's figure runs:

5Tricks and trade-offs

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

What crowded deposits may cost. Tests > frame-cost (a row of ShadyTracer's own test page, lib/pathtracer/tests.js) times a scene with light tracing on and off: light tracing is what sends many deposits into a few pixels. Its first run, on the user's Pascal card at 1188 × 969: 70 ms a sample with light tracing, 9 without, 7.8 times, where an earlier benchmark had read about 1.4 times (the row's note). It does not measure the float frame buffer against the old one; it is the case where its crowds would show.

Why, not yet known. The suspect named in that note is section 1's crowd: the learned light tracer (which learns where its photons count, chapter 18) sends most connections into the few pixels of a caustic. But each connection is also a whole shadow ray to the camera; the row's other cases, the same scene with one thing changed each, are there to tell the two apart. The deposit's own comment still says its cost has not been measured at all, which the run above has overtaken ().

Refused at the door. A contribution that is not a number (NaN, what 0/0 gives), infinite, or of negative luminance (less than no light in all) is not added, and is counted. One negative channel alone is kept: an exact colour outside what the display can show has one (resolve's comment calls it outside the gamut). NaN is the one value not equal to itself, but WGSL lets a compiler assume floats are finite, so the test x != x may be thrown away as always false; NaN is found instead by its exponent bits (the bits of an f32 that hold its power of two: all of them set means NaN or infinity; the deposit's comment).

What a pixel costs. The picture 16 bytes, its error bar 8, this sample's frame 16 and the light tracer's splats 16: 56 bytes a pixel, beside the rays. A 4096 × 4096 save, 16.8 million pixels, holds 16.8 million × 32 bytes (the picture's 16 and the frame's 16) = 537 MB of picture and frame until the page gives it back (raytrace_main.js, give the memory back).

6What went wrong before

A race hidden by one ray a pixel. Shade folded each finished path straight into the picture's average, a load, the arithmetic and a store on four separate words, and two paths on one pixel lost an update (). Now paths add to the frame buffer, and the picture is updated once a sample, one thread a pixel.
Light carried into the next sample. Resolve returned early for a pixel no camera path reached, before taking that pixel's shadow deposits and the light tracer's splats, which then counted in the next sample. Now it takes and clears every word first, and returns only after (the two comments at the top of the resolve excerpt; its n == 0 return comes after the exchanges).
A pixel poisoned for good. A NaN went straight into the sum, and stayed there in every sample after ().
"Unlimited", backwards. The setting for the average's window, 0 meaning unlimited, was applied as min(samples, setting), which at 0 pinned the window to 0: every sample replaced the picture. Now the host caps the count only when the setting is above 0, and writes the result as UB.maxaverages ().
Bright spots after a move. A reset used to keep the old picture's share fading as 2/(n + 2), invisible while light was near 1; in cd/m² a highlight of 10⁹ stayed far above white for thousands of samples (the reset excerpt above).
No caustics in a large picture. Before the batches, the camera's rays took the buffer first and the photons shared what was left: above about 2.3 million pixels (the buffer then held 2.31 million rays, a ray taking 464 bytes) they got none, and light tracing switched itself off (photons.js's header; chapter 18).
A light dimmed by the photon map. The shadow queue was capped at the batch's own rays, one place each. But the queue also holds the shadow rays the rounds before have not finished, and a light's photons connect to the camera at every surface they land on. In a batch of camera rays and photons together, the camera rays' unused places left room; in a batch of photons alone (section 3) there was none, and a connection past the cap was dropped with its light. The floor under a point light, seen directly, read about 5 % dark while the map ran (counted on a software GPU). The cap is now what the queue's buffers hold ().

7Try it

In the first figure, with load and store interleaved, run it again a few times. Does the pixel ever come out right? How often?
With compare-and-swap in lock-step, how many swaps fail for 2, 4, 8 and 16 threads?
In the second, find the faintest light the old format kept, and the brightest.
In the third, at 3840 × 2160, how many photons fit in the same 5 batches?