Putting a path tracer in a 3D playground: crash a car, gun a plane, fly a helicopter

Play first. Press "Enter the playground", then click the picture with a mouse and the mouse becomes the camera (Esc releases it); walk with W A S D, and press F next to a car, the helicopter or the aeroplane. On a touch screen use the stick in the corner, and drag to turn the camera. "Expand" at the top right makes it the whole window, and the key hints follow what you are doing.

fig 01/playground / fly

Fetching the playground and building its BVH…

Samples so far

–

One sample

–ms

Triangles that move

–

Their tree, rebuilt per frame

–ms

Pixels actually rendered

960 × 540

Drawn byRasterDirect light onlyFull path tracing

Carry the last frame overBorrow from neighbours (denoise)

Take me toa carthe helicopterthe aeroplane

Time of day 16:00

Click the picture first: the mouse turns the camera (Esc releases it), W A S D walk, and F beside a car, the helicopter or the aeroplane gets in. On touch, use the stick and drag. Any movement throws away every sample so far and the picture is noise again; stand still and it clears.

Controls

Sketchbook by Jan Blaha (swift502), MIT; Rapier (Dimforge), Apache-2.0

Part one ended on a sentence: when the camera or the scene moves, every accumulated sample is void. That room needed hundreds of samples to be clean. Things here move sixty times a second or more, and a frame has time for one sample.

This part is about four things that together make the figure above playable. The result first (my machine, 960×540, full path tracing): 6.8 ms a sample, keeping up with a 120 Hz display while moving (121 frames a second measured), and in motion a fifth of the noise of "start from nothing every frame".

One: the world is built once, and what moves only gets new boxes

Part one's BVH took a second to build and then never changed. Here there is a person, five cars, a helicopter and an aeroplane, 11,275 moving triangles in all, and rebuilding every frame is out of the question.

So there are two trees. The playground itself (ground, ramps, tracks) is built once; what moves has a tree of its own, a ray walks both, and the nearer hit wins.

The moving tree is not rebuilt either. A car does not change shape, and which of its triangles are near which never changes; so each car's tree is built once, at the start, by part one's careful method, and every frame only the box of every node is recomputed from where the triangles are now, leaves first. A person bends arms and legs, but not by much, and the same trick holds. Measured: rebuilding every frame cost 2.8 ms, recomputing the boxes 1.2 ms.

Two: carry the last frame's picture over

One sample a frame is noise. But the last frame had a sample too, and the one before, of almost the same world, and it is a waste to throw them away.

Every frame remembers one more thing: what each pixel's first ray hit (the point in the world, and which triangle). On the next frame every pixel asks: "the point I see now, where was it on the screen a frame ago?" Projecting the point with the previous frame's camera answers that. Then a check: did that pixel see the same triangle then? If so, the colour accumulated there is taken over and added to; if not (the point was hidden then, or off screen), the pixel starts from nothing.

The figure's settings have a switch, "Carry the last frame over": turn it off and walk a few steps. I measured the same walk twice each way, as the difference in brightness between neighbouring pixels (larger is noisier): off, 6.8 and 7.4; on, 3.0 and 2.9. The frame rate is the same.

The first version did nothing at all. I had judged "the same place" by distance, with a threshold of a few centimetres; but a floor is seen at a shallow angle, and two rays through one pixel can land decimetres apart on it, so the whole floor was called "not the same place" on every frame. Comparing triangles is the test that holds.

Things that move need one more step: a point on a car, where was it a frame ago? Its triangle has the same place in the list on both frames, and the point's position inside the triangle does not change, so the previous frame's three corners of that triangle give back where it was.

There is a price, and it shows: the colour carried over is old. After the character runs past, its shadow stays on the ground for a moment. How many samples a carried pixel may count for is a trade; here it is 12. More is steadier, and the shadow trails longer.

Three: borrow from the pixels next door

History carried over is worth twelve samples at most, and the shadows are still grainy. There is one more place to borrow from: neighbouring pixels on the same wall receive almost the same light.

So before the picture is shown, every pixel is averaged with the pixels around it, by weight. Everything is in who may be counted. Averaging blindly is blurring; here a neighbour has to pass four tests at once to count as "the same surface, lit the same way":

1. The same material. A red barrier and the white ground never mix.
2. A normal that agrees. The line where a wall meets the floor does not blur.
3. In the same plane. Measured along this pixel's normal, the neighbour's position may not be far off; that separates a car in front from the ground behind it.
4. A brightness that is not too different. This one keeps the edge of a shadow: inside and outside differ severalfold and do not seep into each other.

The first three use what the second thing already records (the point each pixel sees), plus the normal and the material.

To be of use the borrowing has to reach far, and looking at 29 × 29 neighbours at once costs too much. So the same 5 × 5 filter runs three times, the second time taking every other pixel and the third every fourth: together they reach fourteen pixels away, and each pass still reads 25 points.

The setting "Borrow from neighbours (denoise)" can be turned off to compare. The same walk, measured: both tricks off, 6.8 to 7.4; carrying the last frame only, 3.1; with this as well, 1.3.

It has a price too. The edge of the character's shadow softens, a very thin shadow fades, and highlights in car paint are smoothed a little. And one rule keeps it from doing harm: the more samples a pixel has of its own, the less it listens to its neighbours, less from 8 samples on and not at all from 64. So a picture left standing converges to the unfiltered answer, not to a blurred one.

Four: the ground was the expensive part, not the cars

With the cars in, a sample took over 9 ms, much slower than I expected. I guessed the cars, spent a round improving the moving tree, and gained almost nothing.

Drawing how many nodes each pixel's ray visits (the heat map of part one's figure 05) showed the whole picture saturated, also where no car was. The ground was the problem: this playground's floor is a few triangles over a hundred metres long, a box around one of those holds half the playground, and a ray travelling along the ground has to look into every such box.

The fix is to cut long triangles short. With no edge longer than 12 metres there are more triangles and tighter boxes:

Finer is not better: cut too fine and the tree gets deep and slow again.

I measured this wrong once myself. The first numbers made no sense, and the cause was a counter on the GPU overflowing: part one says it is 32 bits wide, the picture here is larger, and 64 samples at a time take it all the way round. At 16 samples a time the numbers came out right.

The person, the cars, the helicopter, the aeroplane

The scene's geometry, the character, the vehicles and all 34 animation clips are from Sketchbook (opens in a new tab) by Jan Blaha (swift502), under the MIT licence. Its textures are not used: the playground's are photographs that may not be redistributed, and the vehicles' are baked light, which is the very thing this article computes as you watch. So the packed files keep vertices, the skeleton, the animations and the materials' names, and the colours are mine.

The character behaves by Sketchbook's state machine, ported state by state: a start-walk clip chosen by the angle to turn, a stop, turning on the spot, sprinting, two jumps, three landings chosen by how hard the ground was hit; after F it walks to the nearer door by itself, opens it, sits down, closes it from inside (and from the passenger's side, slides over to the wheel), and closes it again after getting out. G gets in as a passenger instead, who stays put; X slides over to the connected seat, and V is first person. The physics is Rapier: the ground is one triangle mesh, the person a capsule, a car four rays on springs (five gears that shift by themselves, a steering wheel that turns, and keys that spin it while it is in the air), the helicopter and the aeroplane rigid bodies, flown by Sketchbook's own arithmetic and keys: W S pitch, A D roll, Q E yaw, Shift to climb or for throttle. The helicopter's engine takes five seconds to come up and it levels itself when you let go; the aeroplane leaves the ground after about eight seconds of full throttle, and its ailerons, elevators and rudder move with the keys.

Drag the time of day past the evening and it gets dark; the cars' head lamps and the helicopter's searchlight come on by themselves (L switches them by hand). The models have no lamps of their own, so the packer adds them: a ray from straight ahead, and a glowing lens where it first meets the body. What lights the road is not that lens but a spot lamp, asked the way the sun is asked: at every bounce one of up to twelve lamps is picked in proportion to what it could give that point, and one shadow ray goes to it. It costs 2 ms a sample (I measured 8.4 → 10.4 ms), and for that a car's lamps fall on the next car and a person standing in the beam casts a shadow, with nothing written for either. A door left open while driving is swung by the car's acceleration, and shuts itself if it swings hard enough.

The character's skeleton (14 bones, 186 triangles) is evaluated on the CPU every frame and goes straight into the moving tree.

What is different from the real thing, and how the numbers were measured

The denoising is the most basic kind. A real system measures how noisy each pixel is (its variance) and borrows more where the noise is large and less where it is small; here the thresholds are fixed. Games today mostly hand this step to a neural network.

A carried picture is wrong when the light changes. Moving the time of day simply throws the history away. A real system detects where the light changed and drops only that.

At night the pool of light trails. The lamps move with the car, but the frame that is carried over remembers where the pool was, so a short fading patch is left on the ground behind it. While lamps are lit the history is capped at 6 samples instead of 12, for a shorter tail.

Reflections and the sea trail. What a mirror shows moves with the camera, but the past is looked up by where the surface itself was, so reflections in car paint and on the sea are half a beat late.

The flying is Sketchbook's arcade flying. The helicopter balances itself; the aeroplane has no real aerodynamics, its velocity is only bent a little at a time towards where the nose points, so holding S takes it straight over in a loop, and pulling up when it is slow drops it. Sketchbook also makes the aeroplane lighter with speed; that part is not here. A door does not fly open while driving. The suspension numbers are mine, because the two physics engines' springs are not alike; the engine's force is Sketchbook's figure scaled to this car's weight.

Without WebGPU there is nothing to play. Part one could show a picture rendered earlier; here that would be pointless.

Where the numbers come from: the readouts in the figure are measured by your browser as it runs. Where the text says "measured", that was Chrome on an M4 Pro at 960×540, with the camera at the spawn point looking over the car park; the method and the full tables are in this project's docs/research/light/RESULTS.md. The cars', the helicopter's and the aeroplane's physics and the character's state machine each have automatic tests that need no GPU (tests/rt/).

Sources

• The scene, the character, the vehicles, the animations and the original design of the character's states: Jan Blaha (swift502), Sketchbook, MIT licence, github.com/swift502/Sketchbook.
• The physics engine: Dimforge, Rapier, Apache-2.0, rapier.rs.
• Reusing the last frame by projecting a surface point back and validating it: Schied et al., Spatiotemporal Variance-Guided Filtering, High Performance Graphics 2017 (its temporal accumulation is done here; the spatial filter is the simpler one of the next entry).
• A filter that samples with holes and stops at edges by normal and position: Dammertz, Sewtz, Hanika, Lensch, Edge-Avoiding À-Trous Wavelet Transform for fast Global Illumination Filtering, High Performance Graphics 2010.
• Recomputing boxes instead of rebuilding the tree for things that deform: Wald, Boulos, Shirley, Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies, ACM Transactions on Graphics, 2007.