Part IV · Path tracing · Chapter 14
Aim at the light
A picture lit by a small lamp comes out full of speckles, and stays that way for a long time. The fix is one extra ray at every bounce, aimed at the lamp on purpose. It is called next event estimation, and it is the most useful single trick in a path tracer.
1The question
This chapter builds on two ideas from earlier ones: a picture is an average of many random samples per pixel (Dice and averages), and each sample follows a path that bounces from surface to surface in random directions until it happens to meet a light (Following a path); the figure below shows what you need from them. Each bounce keeps only part of the light, a share called the surface's albedo: after two bounces off surfaces that keep 70%, 0.7 × 0.7 = 0.49 of it is left.
The figure is a small flat room with a lamp near the ceiling, a ball and a box on the floor, and an eye on the left with one row of pixels (the eye's screen is not drawn; each pixel is one direction out of the eye). Every pixel sends paths into the room. A path that hits the lamp brings its light back; a path that never does brings back nothing. The drawn lines are three paths of one pixel: blue while they bounce, orange on the piece that found the lamp, when one does. Other paths draws three more, and Show paths hides them. The circled cross on that pixel's ray chooses which pixel: drag it. The lamp, the ball and the box drag by their circled crosses too.
The first strip under the room is the picture so far, one grey square a pixel (the red frame marks the pixel whose paths are drawn). The dots below it are each pixel's value with its error bar: how far off the average may still be (point at them to read one). It is speckled, and it settles slowly. The lamp is small, so most paths miss it, and the few that hit it make a pixel much too bright for one sample. That speckle is noise.
2Finding a lamp by chance
Look at a single point on the floor. When a path lands here, a matte (diffuse) floor sends it on in a random direction: any direction is possible, those close to straight up a bit more likely. (The surface itself sends light equally brightly every way; the figure picks directions near straight up more often because, by the cosine law, those carry more light, and it divides by that choice, as section 3 explains.) The figure draws 70 such directions. The orange ones happen to point at the lamp and find its light; the grey ones find nothing. The readout's second estimate, aiming, is the next section's.
Make the lamp small. It gives off the same total light (it gets brighter as it shrinks), so the exact light at the point hardly changes. But now almost no random direction finds the lamp, and when one does, it brings back a lot. The answer is still right on average: in the readout, the estimate from 3000 bounces lands within about one error bar of the exact value. (An error bar is not a fence: about one estimate in three lands further than one error bar from the truth, one in twenty further than two.) But each single try is either nothing or far too much. That is exactly the speckle in the room.
The figure can work out the exact value because it holds one lamp and one point. A real scene has no such formula, which is why a renderer estimates at all.
3Aim at it instead
So don't wait for luck. At every bounce, also pick a random point on the lamp and send a shadow ray to it (dashed in the figures). If nothing is in the way, add the light that point sends. Every one of these rays is aimed at the lamp, so every one that is not blocked counts. This is next event estimation, NEE: at each bounce, it estimates the light the next bounce could have found, directly.
Compare the two estimates in the readout. Same answer, within the error bars. But the error bar when aiming is many times smaller than when bouncing: here ± 0.001 against ± 0.009. Why so quiet? Because every aimed try brings back nearly the same amount: the light of one point of the lamp, counted for the whole lamp (the fold-out below says how). Bouncing gives nothing, nothing, nothing, then far too much; aiming gives about the right amount every time. Tries that agree settle fast.
Shadows still work. Put something in the way of part of the lamp: the shadow rays that hit it (red, stopped where they are blocked) bring back nothing, and the estimate drops from about 0.21 to the light that really gets past, about 0.05.
The mathsWhat a shadow ray adds, and why it divides
One point stands in for the whole lamp. Cut a lamp of length ℓ into ℓ pieces of length 1. Pick one point at random, see what it sends, and multiply by ℓ: you have counted the lamp as if every piece sent the same. Over many picks, the pieces that send more and the ones that send less are each picked as often, so the average is exactly the total. (ℓ need not be a whole number: cut it into a thousand pieces of length ℓ/1000 and the argument is the same.) The chance of picking any one exact point is zero, as for any one exact number on a ruler; what can be given is the chance per unit of length: a bit of the lamp 0.1 long is picked with chance 0.1/ℓ. That 1/ℓ is the pdf, and multiplying by ℓ is dividing by it.
The same rule for every choice. If there are two lamps and one is picked half the time, it must count double when it is picked, so that on average it counts once. Divide by the chance of the choice.
The light E arriving at the floor point (its irradiance, as in Rays make a picture) is then estimated, from one point y of the lamp, as
E ≈ Le · cos θx · cos θyr · ℓ (flat world), E ≈ Le · cos θx · cos θyr2 · A (3D, a lamp of area A)
- Le
- how bright the lamp's surface is (its radiance)
- θx
- the angle at the floor point, between its normal and the shadow ray: the cosine law of chapter 1, light at a slant spread over more floor
- θy
- the angle at the lamp: a lamp seen edge-on looks shorter, and sends less this way
- r, r²
- the distance between the two points. Light spreads around a circle in the flat world and over a sphere in 3D, as in chapter 1
- ℓ, A
- the lamp's length, or its area in 3D: dividing by the pdf
That is the light arriving. What the path gets back is that times what the surface sends on towards the eye: for a matte surface, its albedo ρ spread evenly over every direction out, which works out to ρ/2 in the flat world and ρ/π in 3D. Take those on trust for now: dividing by 2, or by π, is exactly what makes all the light leaving, added up over every direction with the cosine law, come to ρ of what arrived (Diffuse and mirror works it out). And times what the path has kept so far from its earlier bounces, its throughput. That is the shadow ray's contribution.
The 3D room in section 5 aims at its lamp a different way: a random direction into the cone the ball fills, divided by the chance of that direction. A different choice, divided by its own chance: the rule does not change.
Which points of the lamp. The lamp in these figures is not a line but a thin capsule, everything within 0.02 of a line, glowing all round its outline, and that outline is what a bounce can hit. So the point is picked on it: on the long side facing the floor point or on the two round ends, and ℓ is the length of that much outline. The long side facing away sends this point nothing, so leaving it out changes nothing on average; a point of a round end that faces away counts 0, and those tries are the aiming's small spread. The flat world once picked points on the middle line, a lamp of no thickness, while the bounces found the capsule: in the room of section 4, given twelve bounces, bouncing read 0.1326 ± 0.0014 and aiming 0.1213 ± 0.0004, nine percent apart (computed). Aim at exactly the light the bounces can find; chapter 30 is the same lesson in the engine.
4In a whole picture
Back to the room, now traced both ways at once: the same number of paths per pixel, one picture without NEE and one with it. The grey dots are the picture without NEE, the blue ones with it (NEE only shows that one alone); the dashed lines in the room are the shadow rays (red and dotted where something blocks them). The pictures head for the same thing (their dots agree within the error bars), but the one with NEE gets there much sooner. The readout gives the average error bar of each.
Shrink the lamp. Without NEE, the picture gets worse and worse: a lamp nothing can find by chance is a lamp the picture never sees. A point light, with no size at all, could never be hit; only NEE could light anything with it. With NEE, the size hardly matters: at the smallest size its error bar is about a fifth of the other's.
Make the lamp large. Now random bounces find it often, and the two pictures are much closer: NEE's error bar is about half the other's. NEE helps most where light is small and bright, and least where light comes from everywhere.
Don't count it twice. With NEE on, a bounce that happens to hit the lamp must not add the lamp's light again: the shadow ray sent from the bounce before already counted all the light reaching that point straight from the lamp. The flat world simply ignores such hits. That rule needs the shadow ray before it to have been able to find the lamp. A camera ray that looks straight at the lamp had no shadow ray before it, so it counts. Neither did a bounce off a mirror (section 6: a shadow ray from a mirror finds nothing), so a mirror's reflected ray that hits the lamp must count too; the flat world has no mirrors yet, so it never meets this. ShadyTracer does something better than ignoring: it keeps both and weighs each by how good it was at finding that light. That is multiple importance sampling, the next chapter.
Not at the last bounce. A path allowed four bounces does not aim at the lamp from the surface where it stops. The bounce from there is never traced, so a path without NEE could never find what that shadow ray would; aiming there would count light one bounce further, and the two pictures would head for different answers. Before the flat world followed this rule, the room allowed one bounce read 0.0870 aiming against 0.0556 without (44,800 paths each, computed). pbrt stops the same way. ShadyTracer's second cap, Max Diffuse Bounces (chapter 13), keeps the rule for its own count: a path that arrives with no diffuse bounce left aims at no light there ().
5And in 3D
The same comparison as a real picture: a small room lit by a glowing ball near the ceiling, path traced on your computer's processor while you watch, without NEE on the left and with it on the right. Both pictures get the same number of samples per pixel. Only the right one aims a shadow ray at the lamp, at every bounce but the last.
In 3D the lamp is aimed at differently from the flat world. Instead of a random point on it, the shadow ray goes in a random direction inside the cone of directions the ball fills, seen from the point. How big that cone is, as a patch of the sky around the point, is its solid angle; the shadow ray divides by the chance of picking its direction in it. ShadyTracer aims at a glowing object it has found in this way: into the cone of a sphere drawn around it, whatever the object's shape.
Shrink the lamp to a bright speck. The left picture is almost black with white dots: a random bounce hardly ever finds the lamp. The right one barely changes.
Make the lamp large. The picture without NEE improves, but here NEE still has about a fifth of its error bar: even at its largest, this lamp is small next to the room.
6Where aiming cannot help
A shadow ray only asks whether the way to the lamp is clear. The other half of what it brings back is the surface's: of the light arriving from that direction, how much does it send on towards the eye? A matte surface answers "some" for every direction. A perfect mirror answers "none" for every direction except one, the exact reflection. A random point on the lamp is never exactly that direction, so for a mirror or clear glass the shadow ray always brings back zero. Such surfaces are called delta surfaces, and the path has to find the light through them by bouncing.
It gets worse with a lamp behind glass, shining through it onto a floor: the bright patterns under a glass of water. A shadow ray from the floor stops at the glass; a random bounce from the floor has to pass through the glass the exact way that leads to the lamp. These caustics need a completely different approach: tracing light from the lamp's side (Caustics, Photon mapping).
7How ShadyTracer does it
The reasoning is written at the top of the light-sampling code, in the renderer's own words (its variance is how much the tries scatter):
ShadyTracer has three kinds of light to aim at: the faces of the light objects you place in the builder, glowing surfaces it has discovered in the scene (Every glowing thing is a light), and the sky with its sun. A light inside an array, a group's copies, is a face at every copy (), and the faces are chosen evenly among themselves. One random number chooses which kind, and each choice is then divided by its probability, as in the fold-out above. The code is WGSL, the GPU's language:
Each branch then multiplies its own chance by the share that picked it: for a discovered emitter, the chance of
its direction times (1.0 - fs) * es
().
Dividing by that product is dividing by the chance of the whole choice, as in the fold-out. The chosen light
produces a direction L, the light arriving from it le, and that chance (pS;
dS is the same number, kept above zero so the division is safe). For a point on a light's face, the
fold-out's cos θy, r² and A are inside it: the chance of the
direction is the share times r² / (A cos θy)
(), so dividing by it
multiplies by A cos θy / r². The contribution is computed once and
handed to a shadow ray. The shadow ray carries it: if
nothing blocks it, it adds exactly that to the pixel.
Shadow rays then get their own kernel, because they need so little:
8Tricks and trade-offs
Each is stamped with how it is known; point at a stamp to see what it means.
Shadow rays are not free. ShadyTracer's developer measured it on their NVIDIA Pascal graphics
card (Chrome 154, Windows, 1280 × 720, ShadyTracer 0.9.2): the Noise library example scene took 184.7 ms of GPU
time a sample with NEE and 136.9 ms without. The shadow rays were about a quarter of the GPU's work, almost all
of it in the occlusion kernel (45.5 ms, against 0.1 ms with NEE off). One run on one machine, recorded in
docs/PERFORMANCE_REVIEW.md §10.1.
What that quarter buys. Noise falls as one over the square root of the samples: four times the samples halve it. So to make an error bar k times smaller without NEE takes k² times the samples. In this page's flat room, NEE's error bar is a little over a quarter of the other's at the lamp's starting size (0.28, so about 13 times the samples to match it) and a sixth at the smallest (about 34 times), for 1.35 times the time a sample in the measurement above. ShadyTracer's own scenes were not measured this way; what would test it is rendering one to the same error bar with NEE on and off, and timing both. NEE stays on.
The sky counts as a light too. Half of the environment's shadow rays go to the sun's disc and half to the sky, spread like a cosine. The comment records why: with shadow rays for the sun alone, the noise fell 36% with the sun turned up but only 4% at the default, "because at the default most of the light in the scene is sky, and nothing was sampling it". (The comment gives no hardware for that measurement.)
Memory only when used. The shadow-ray queue is two more ray-sized buffers, about 200 MB at 1024 × 1024. They are allocated the first time NEE actually runs, and stay one element each while it is off ().
Not on the last round. The GPU processes rays in rounds (Wavefront path tracing), up to a fixed number of them. A shadow ray made in the very last round would have no round left to be traced in, so none is made there. The code's comment says what that costs: the surface "falls back to BSDF sampling alone there", meaning that whatever light reaches it is found only by bouncing, as with NEE off: "noisier, still unbiased", still right on average ().
9What went wrong before
Two edges for one sun. To divide by its probability, a shadow ray to the sun needs to know whether a direction is inside the sun's disc. The light itself had its own test for the same question. The two tests were written differently and disagreed on a thin ring at the disc's edge, where rounding decides. A shadow ray landing in that ring carried the full brightness of the sun divided by the probability of hitting sky (a direction's chance mixes the sun's half of the shadow rays and the sky's half, section 8):
The result was a floor 142 times too bright on average, while its typical (median) pixel looked right: a few pixels were enormous. It was found because a test compared the floor with a number known in advance.
Two sizes for one lamp. In ShadyTracer a lamp is a flat rectangle or disc with no thickness, glowing from its front, its back dark. A ray finds a surface by stepping towards it (Shapes as distances) and never lands exactly on it, so it calls it a hit once it is closer than a small length, the tolerance (half a millimetre in a room-sized scene; Numbers have grain). So a ray passing just beyond the lamp's edge hit it too: to a bouncing ray the lamp was a glowing ring of that width larger all round, a ring that is not really there. A shadow ray only ever aims at points on the lamp itself. The two ways of finding the lamp disagreed about how big it was, as the two tests of the sun's edge had. With NEE on, ShadyTracer does not ignore a bounce that hits the lamp but weighs it (section 4, and the next chapter): a random bounce rarely finds a small lamp, so what it finds counts for almost nothing, and the shadow rays, aimed at the true lamp, gave nearly all the light. The picture was right. With NEE off, the ring counted in full: a lamp 10 by 5 cm lit the floor 5 % too brightly, and 25 % with a tolerance ten times larger. (The ring adds 3 % to the lamp's area seen face on; the floor sees the lamp at a slant, which narrows the lamp but not the ring.) Section 3's rule says aim at exactly the light the bounces can find, and here the two could be made to agree from either side. They were made to agree on the lamp's own size: the ring is no part of the lamp but a side effect of the tolerance, and the lamp's brightness is set from its size, so a larger lamp glowing as brightly sends out more light than it was given. (The flat world's capsule really is 0.02 thick, so its outline is the lamp, and there the aim had to grow.) So the ring now takes the material of the lamp's back: black, and a ray that meets it stops there, as at the back (). This one was also found by a number known in advance, which a scene this simple has: the floor's brightness under a lamp of that size, worked out from a formula.
A comparison that did not compare. When NEE was first written, it could only aim at the sun and the sky. A lamp made of glowing geometry was invisible to it, found only by bouncing. So an NEE-on against NEE-off comparison run in a scene lit by such a lamp measured nothing about NEE at all (). The fix was to make NEE aim at those lights too. The lesson: before believing a measurement, check that the thing being switched actually reaches what is measured.
10Try it
- In the flat room, set the lamp to its smallest size and press Start again. How many samples does the picture without NEE need before you can tell where the ball on the floor is?
- In the single-point figure, find a lamp size where bouncing and aiming have about the same error bar. What does the lamp look like from the point then?
- Drag the room's lamp to one side. Which pixels get noisier without NEE, and why?
- In the 3D room, the ball is aimed at through its cone. Why would picking a random point on the ball's surface, as the flat world does with its lamp, waste about half the shadow rays?
- In ShadyTracer: with the developer settings shown, the Render settings have a Next-Event Estimation switch. Turn it off in a sunlit scene and watch the picture; turn it on again.