№ 011Interactive
How a picture clears from snow: a WebGPU path tracer from scratch
The colour of one pixel is the average of many rays bouncing at random. Watch a picture clear from noise, shoot one ray and see how it becomes a colour, flip one switch that cuts the noise five times, swap in metal and glass, and see how a BVH keeps a million triangles running.
- Published
- Reading time
- 11 min
The room below has had one sample so far, and it is almost all snow. Press Start and your GPU does the rest.
Building the BVH…
How the error is measured: odd and even samples build two pictures of their own; half the gap between them is this picture's error. No reference image is needed. The number is relative to the picture's mean brightness: 10% means a typical pixel is still a tenth of the average brightness off.
Not one pixel of that picture is drawn. There is no code for shadows and no code that says the red wall should tint the floor. Nobody wrote why the corners the lamp cannot reach are still a little bright. The whole picture does one thing, many times: shoot a ray out through a pixel, let it bounce around the room at random, and see whether it ends up at the lamp.
This is path tracing. This article writes it from scratch: the scene, the acceleration structure, a reference version on the CPU and the WGSL kernel on the GPU, about 1,100 lines in all (TypeScript, plus the WGSL written for the GPU; what part two needs outdoors is counted in), with no graphics library. Then it answers a few questions. How does one ray become a colour? How long does the noise take to clear, and can it clear faster? What more do metal and glass need? And why does it still run when a thousand triangles become a million?
This is part one. Part two takes the same engine outdoors: a playground to walk, drive and fly a helicopter and an aeroplane through, every frame computed this way.
One pixel, one ray
Look at a single pixel first. The picture below is the GPU's, finished. The line over it is one path from the pixel inside the dashed circle, traced on your CPU by the same algorithm.
Building the BVH…
- The colour this one path gives
- The mean of 0 paths
- This pixel in the GPU's picture
Click anywhere on the picture to choose another pixel. The paths are traced on your CPU by the same algorithm; a line's colour is what the light is still worth when it gets there.
A path has three rules:
- Leave the eye through this pixel and find the first surface in the way.
- If it is the lamp, the path has a colour: the lamp's brightness, times whatever share is still left after the journey.
- If it is not the lamp, multiply what is left by the surface's colour (a red wall keeps only the red part), leave in a random direction, and go back to rule 2.
Press "Shoot one more" a few times. Most paths never reach the lamp: they leave through the open side of the room, or they run out of energy. Their colour is plain black. For the few pixels I measured, only 3% to 7% of paths found the lamp; those few are very bright, far beyond the white a screen can show.
So the answer of any single path is almost certainly wrong: black, or much too bright. The pixel's real colour is the average of many paths. Press "Shoot 100" and watch the second swatch approach the third. For one pixel on the red wall, the mean of 101 paths was rgb(195, 38, 36) and the GPU's 1,024 paths gave rgb(163, 31, 29): the same red already, but not there yet.
The snow at the start of figure 01 is exactly this. Every pixel had shot one path; most were black and a few were white.
How long the noise takes to clear
How many paths are enough? Go back to the chart at the bottom right of figure 01. Its horizontal axis is samples per pixel, its vertical axis is the error of the whole picture, and both are logarithmic.
The points follow the dashed line, whose slope is −½: the error falls as one over the square root of the sample count. On my machine the measured points lie on that line from 2 samples to 2,000. It is the law of any average estimated with random numbers. It does not depend on what the picture shows, or on how fast the GPU is.
The price is concrete: half the noise costs four times the samples. From "I can tell what it is" to "clean" is not twice the time but a hundred times. That is why figure 01 changes a lot in its first seconds and then seems to stop. It has not stopped; each improvement you can see costs four times as much as the one before.
How is the error measured with no correct answer to compare against? Odd and even samples accumulate into two pictures of their own. Both are pictures of the same room, and they differ only by luck, so half the gap between them is the error of the two put together.
No more samples: ask the lamp instead
So far there is one way to a clean picture: shoot more. But figure 02 already showed what is wrong. Over nine paths in ten never reach the lamp, and all of their work is wasted.
The direction most worth going in is the direction of the lamp. So every hit does one more thing: choose a random point on the lamp, shoot a ray at it, and see whether anything is in the way. If nothing is, the lamp's brightness is counted at once (with the weight that direction deserves), and the path carries on bouncing as before. There is one trap that must be handled: if the path later runs into the lamp by itself, that hit must not count, or the lamp is counted twice and the picture is too bright.
Go back to figure 01, let the error curve draw for a while, then press "Ask the lamp". The picture starts over and the previous curve stays on the chart for comparison. The new curve is parallel to the old one, slope −½ still, because that law cannot be escaped; but all of it sits lower. What I measured: at 256 samples the error fell from 17.7% to 3.3%. An error 5.3 times smaller is what 28 times the samples would buy. It is not free: every hit shoots one more ray, and a sample went from 2.9 ms to 5.7 ms. On balance, for the same time, fourteen times the samples.
This is called next event estimation. The idea behind it matters more than the trick: spend samples where the contribution is large. In part two's playground the sun is asked in just this way; without it an outdoor picture could not be computed in time at all.
How many times light should bounce
Rule 3 says "leave again" and does not say how often. Below is the same room four times over, from exactly the same samples; the only difference is how many times a path may bounce.
Building the BVH…
With 0 bounces only the lamp itself is visible. With 1 you get direct lighting: a surface is bright only where the lamp shines on it, everything else is black, and so is the ceiling, because the lamp faces down. With 2 something appears inside the shadows, and the red and green of the walls seep onto the floor and the tori. None of this is an effect written separately. It is the same rule run one more round.
The tile without a limit is a little brighter and softer than the one with 2. "No limit" does not mean bouncing for ever, though. From the fourth bounce on, every bounce rolls a die: the darker the surface, the likelier the path ends there, and the paths that survive are scaled up to make good the loss, so the average is neither more nor less. The trick is called Russian roulette.
Metal and glass
So far every surface has been matte: light hits it and leaves in much the same way in every direction. Here is another room, with three balls, and the middle one is yours.
Building the BVH…
To a path tracer a material answers one question: light arrives from this direction; where does it go, and how much of it? Rule 3's "a random direction" becomes a direction chosen by that answer, and nothing else changes.
Metal: think of the surface as countless tiny mirrors, each facing a slightly different way. Roughness is how disorderly they are: at 0.02 the ball is a mirror, at 0.6 the reflection is a blur. A metal's colour is not painted on; it is how much red, green and blue it reflects head-on. The more obliquely you look, the closer all three get to total reflection, which is why the ball's rim is whiter than its middle.
Glass: at every surface some light reflects and the rest refracts through; head-on nearly everything passes, at a glancing angle it is a mirror. The index of refraction is how much the light bends: at 1.0 it does not bend and the whole ball disappears; 2.4 is diamond. The bright patch under the ball is light the glass has gathered together. Nobody wrote code for it.
Why a million triangles still run
By now the expensive step is always the same one: what did this ray hit? The honest way is to test every triangle in the scene. This room has 876 of them, the picture is 512×512, and the question is asked for every pixel, every sample and every bounce.
The answer is to put triangles in boxes and boxes in bigger boxes until it is a tree, called a BVH (bounding volume hierarchy). If a ray misses a big box, nothing inside needs a look. The picture below is not shaded: a pixel's colour is how many nodes of the tree its ray had to visit to find its answer.
Building the BVH…
0 48nodes
Take the triangles all the way to a million. The tori get rounder, and the numbers on the right hardly move. This is what I measured (M4 Pro, Chrome, 256×256, camera rays only):
| Triangles | BVH | Nodes visited per ray (or triangles tested) | Rays per second (millions) |
|---|---|---|---|
| 876 | on | 9.5 | 112 |
| 9,612 | on | 10.4 | 170 |
| 101,412 | on | 11.4 | 158 |
| 998,796 | on | 11.9 | 141 |
| 876 | off | 876 | 45 |
| 9,612 | off | 9,612 | 5.4 |
Eleven hundred times the triangles cost each ray 2.4 more nodes. Every level of the tree doubles what it can hold, so the tree for a million triangles is only 23 levels deep. With the BVH off, 9,612 triangles are already thirty times slower. Past ten thousand I locked the switch, because one sample would take long enough for the browser to kill the GPU task.
In the top two rows 876 triangles are slower than 9,612, and the BVH is not the reason: the scene is so small that 64 samples are over before the GPU reaches full speed. Read rays per second as an order of magnitude; the node counts are exact.
The tree is built by binned SAH: whenever a set of triangles has to be split in two, each of the three axes is cut into 16 bins, the 15 planes between them are tried, and the one with the smallest "surface area of each side's box × its number of triangles" wins. A million triangles take about a second to build in your browser, in a worker, so the page does not freeze.
What is different from the real thing, and how the numbers were measured
The glass is perfectly smooth, and very rough metal eats some light. There is no frosted glass. The metal model (GGX) counts light that bounces once among its tiny mirrors; with roughness at 1, I measured the ball returning only three tenths of its light. Production renderers put that back.
Light through glass is still found by luck. A ray asking the lamp is blocked by the glass ball itself, so the bright patch under it is the slowest part of the picture to clear.
No denoising. Real-time path tracing today has one or two samples per pixel per frame; it gets by on averaging with earlier frames and neighbouring pixels, or on a neural network.
Nothing moves. When the camera or the scene moves, every accumulated sample is void. That is the subject of part two.
Where the numbers come from: the readouts in the figures are measured by your browser as it runs, so they will differ from mine. Where the text says "I measured", that was Chrome on an M4 Pro, in this page, recorded in this project's docs/research/light/RESULTS.md. That asking the lamp does not change the answer is held by a test: on three pixels of the CPU version, 6,000 paths each, the means with and without asking differ by no more than the noise allows (tests/rt/strategies.test.ts). The CPU and GPU versions are the same algorithm written twice: on eight pixels of figure 02 (both coloured walls, floor, ceiling, back wall, a torus, the lamp) the mean of 2,001 CPU paths and the GPU's 1,024 samples differ by at most 12 levels out of 255 in any channel, some above and some below. That the BVH finds the same hit as testing every triangle is held by the tests in tests/rt/. A browser without WebGPU gets a picture rendered earlier, and figure 02 still works on it, because its rays are the CPU's.
Sources
- Writing a pixel's colour as an integral and estimating it with random paths: Kajiya, The Rendering Equation, SIGGRAPH 1986.
- Asking the lamp and choosing by the material together, without counting twice: Veach, Guibas, Optimally Combining Sampling Techniques for Monte Carlo Rendering, SIGGRAPH 1995.
- The metal model (GGX) and how to choose its directions: Walter, Marschner, Li, Torrance, Microfacet Models for Refraction through Rough Surfaces, EGSR 2007; Heitz, Sampling the GGX Distribution of Visible Normals, JCGT 2018.
- Building the BVH: Wald, On fast Construction of SAH-based Bounding Volume Hierarchies, IEEE Symposium on Interactive Ray Tracing, 2007.
- The random numbers on the GPU: Jarzynski, Olano, Hash Functions for GPU Rendering, Journal of Computer Graphics Techniques, 2020.
- Squeezing computed brightness into what a screen can show: Narkowicz, ACES Filmic Tone Mapping Curve, 2016.
- The scene is a variation on the Cornell box, which comes from Goral, Torrance, Greenberg, Battaile, Modeling the Interaction of Light Between Diffuse Surfaces, SIGGRAPH 1984.