Many Lights

Chapter 21 sketched the problem: lighting cost grows with pixels times lights, and most of those pairs contribute nothing, because a small light reaches only a few meters. This chapter builds the standard solutions, from screen tiles to 3D clusters, and then the newer stochastic methods that let even shadowed, area-shaped lights number in the thousands.

Part 1 · Tiles

Forward+ and tiled deferred

Lists of lights per screen tile

The first widely used fix, from around 2011, splits the screen into tiles of, say, 16 × 16 pixels. Before lighting, a compute shader works out which lights touch each tile, and writes a short list per tile. Then each pixel loops over its tile's list instead of every light.

"Touch" needs a 3D test. A tile is a narrow pyramid stretching away from the camera: its sides come from the tile's edges on screen. The culling shader reads the depth buffer to find the nearest and furthest surface in the tile, which trims the pyramid to a short slab around what's actually there. A light's sphere of influence that misses the slab is skipped. Applied to deferred shading, this is tiled deferred; applied to forward shading after a depth pre-pass, it was named Forward+ (Takahiro Harada, Jay McKee and Jason Yang, 2012).

Interactive · counting lights per tile

tile size

Forty lights' areas of influence on screen (circles), and the screen split into tiles. Each tile is shaded by how many lights touch it. Drag the lights. Smaller tiles fit the lights more tightly, but each tile's list costs culling work, so 16 × 16 pixels is the usual compromise.

Tiles have one weakness, and it's in depth. A tile that covers the edge of a nearby pillar and the far distant floor behind it has a min/max depth range spanning the whole scene, so it collects every light along its line of sight, near and far. Such depth discontinuities are everywhere in real scenes: foliage, fences, character silhouettes.

Part 2 · Clusters

Clustered shading

Slicing the view in depth too

Clustered shading (Ola Olsson, Markus Billeter and Ulf Assarsson, 2012) divides the view volume in depth as well: each screen tile's pyramid is cut into slices, giving a 3D grid of little boxes called clusters. Lights are listed per cluster, and each pixel finds its cluster from its screen position and its depth. A pixel on the near pillar and a pixel on the far floor, in the same tile, use different clusters and different lists.

The slices get thicker with distance, usually spaced exponentially (each slice a fixed factor deeper than the last), so that clusters stay roughly cube-shaped on screen, the same idea as the logarithmic shadow cascades of Chapter 20. Because the cluster grid doesn't depend on the depth buffer, it can be built before anything is drawn, which suits forward rendering, transparent objects and volumetric fog alike: anything at any depth can look up the lights that reach it.

Interactive · tiles versus clusters, seen from the side

A side view of the camera's view, with one screen tile's column highlighted. Lights (circles) sit at all depths. A near pillar and the far floor both fall inside the tile. With a single depth range, the tile lists every light between them. With depth slices, each slice lists only its own lights; the pixels on the pillar and the floor each look at a short list. Drag the pillar.


// Which cluster is this pixel in?  16 x 9 tiles on screen, 24 slices from NEAR to FAR.
fn clusterIndex(pixel: vec2f, viewDepth: f32) -> u32 {
  let tile = vec2u(pixel / u.screenSize * vec2f(16.0, 9.0));
  let slice = u32(clamp(log(viewDepth / NEAR) / log(FAR / NEAR) * 24.0, 0.0, 23.0));
  return (slice * 9u + tile.y) * 16u + tile.x;
}

// In the fragment shader: only the lights listed for this cluster.
let c = clusterIndex(pixel.xy, viewDepth);
for (var k = 0u; k < lightCounts[c]; k++) {
  let light = lights[lightIndices[c * MAX_PER_CLUSTER + k]];
  color += shade(light, position, normal);
}

Building the lists is a compute pass with one thread per cluster: compute the cluster's box in view space from its tile and slice, then test it against every light's sphere. With 3,456 clusters and 4,096 lights, that's 14 million box-sphere tests, done in well under a millisecond. Big renderers make it cheaper still by first sorting lights into a coarse grid or a bounding volume hierarchy (Chapter 14), and by only building lists for clusters that actually contain visible pixels.

The same lists work for deferred shading (clustered deferred), and modern renderers mix and match: a deferred pass for most surfaces, a clustered forward pass for transparent ones and special materials, all reading the same light lists.

Part 3 · Shadows for many lights

The expensive part

Which lights get shadows?

Culling makes unshadowed lights cheap. Shadows are another matter: each shadow-casting light needs a shadow map (six for a point light), redrawn whenever anything near it moves. Renderers ration them. Shadow maps go into one large atlas texture, with each light given a region sized by how big it appears on screen; only the nearest and most important few dozen lights get shadows at all; static scenery's shadows are cached and reused. Small lights far away are shadowless, and nobody notices.

With ray tracing (Chapter 36), the picture changes: a shadow is just a ray toward the light, so the question becomes which lights to send rays to. That leads to the stochastic methods of Part 4.

Part 4 · Sampling lights

Light trees and ReSTIR

One shadow ray per pixel, chosen well

A path tracer (Chapter 15) doesn't loop over lights at all: at each shading point it picks one light at random, sends one shadow ray, and divides the result by the probability of having picked that light. That's correct on average, but if it picks uniformly among 4,000 lights, nearly every pick is a distant light that barely matters, and the image is pure noise. The fix is to pick lights in proportion to how much they're likely to contribute: importance sampling, again.

Light trees group nearby lights into a bounding volume hierarchy, where each node stores its lights' total power and extent. To pick a light for a shading point, walk down the tree, at each node choosing the child that looks brighter from here with higher probability (Alejandro Conty Estevez and Christopher Kulla, 2018).
Resampled importance sampling (RIS) draws a handful of candidate lights cheaply, scores each by its unshadowed contribution, and keeps one with probability in proportion to its score. Only that one gets a shadow ray.
ReSTIR (Benedikt Bitterli and colleagues, 2020) makes RIS spectacularly effective by reusing candidates: each pixel stores its current pick in a tiny reservoir (the chosen light, plus the running total of scores seen), and combines its reservoir with last frame's (via motion vectors, Chapter 31) and with its neighbors'. Every pixel effectively considers thousands of candidates while evaluating one shadow ray. Recent games use it for direct lighting from thousands of shadowed lights, and its descendants for indirect light too.

In plain words · a reservoir

How do you pick one item from a stream, in proportion to each item's weight, without storing the stream? Keep one chosen item and the running total of weights. When a new item with weight w arrives, add w to the total, and replace the chosen item with the new one with probability w ÷ total. At the end, each item has been kept with probability exactly its weight ÷ the total. That's weighted reservoir sampling, and since two reservoirs can be merged the same way (treat the other reservoir's choice as one item carrying its whole total), pixels can pool their candidates cheaply.

Interactive · one light sample per pixel, four ways

A floor seen from above, lit by 120 colored lights hanging just over it. Left of the divider, every pixel evaluates just one light (as if it could afford one shadow ray); right of it is the reference, which evaluates all 120. Drag the divider to compare. Uniform pick chooses blindly, so most pixels land on a far-away light and the pools of color drown in speckle. RIS scores 32 random candidates by their estimated contribution and keeps one in proportion to its score: color returns, but a pixel only finds the light right above it when that light happens to be among its 32 candidates, so it stays grainy. Merging reservoirs with five random neighbors, twice over (ReSTIR's spatial pass), fixes that: if any nearby pixel found a good light, it shares it. Every pixel now draws on over a thousand candidates, the pools come through, and each pixel still evaluates a single light. ReSTIR adds the temporal pass: each frame, a pixel also merges its own reservoir from the frame before, so good lights found once are kept and refined rather than thrown away. Switch to it and watch it settle toward the reference within a second. (The camera here never moves; in a game, motion vectors say where last frame's reservoir is.) Denoise runs a small à-trous filter (Chapter 36) over the result. It helps every mode, but it can only smooth what's there: uniform picking stays a mess, while ReSTIR's output, already close, comes out closest of all. Click the floor to inspect a pixel: thin lines are the candidates it scored (brighter for higher scores), dashed lines the neighbors it borrowed from, and the gold line the one light it kept.

The remaining noise is removed by a denoiser (Chapter 36) and by accumulating over frames (Chapter 31). The result: thousands of shadowed lights for a fixed cost per pixel, independent of how many lights there are.

Part 5 · Your turn

Culling by hand

Write the test

The heart of every culling scheme is a test between a light's sphere (here a circle) and a cell's box. This playground counts lights per tile with a deliberately crude test: a circle "touches" a tile if the circle's center is inside it. Rewrite touches to be correct, and watch the counts grow to the true values. Then try a cheaper, looser test (treat the circle as a square) and see how many extra lights it lists.

const TILE = 30;   // pixels

// Does a circle (cx, cy, r) touch the box from (x0, y0) to (x1, y1)?
function touches(cx, cy, r, x0, y0, x1, y1) {
  // too strict: only lights whose center is inside the box
  return cx >= x0 && cx < x1 && cy >= y0 && cy < y1;
  // correct: find the box's closest point to the center, and compare its distance with r
}

Recap

What we have so far

Lighting cost is pixels × lights; culling lists, for each region of the screen, only the lights that can reach it.
Tiled shading (tiled deferred, Forward+) lists lights per screen tile, trimmed by the tile's depth range; depth discontinuities inflate the lists.
Clustered shading slices each tile exponentially in depth; pixels look up their cluster by screen position and depth. It works for forward, deferred, transparency and volumes.
Shadows for many lights are rationed in an atlas, or, with ray tracing, made stochastic.
Light trees, RIS and ReSTIR pick one light per pixel in proportion to its contribution, reusing candidates across neighbors and frames with reservoirs.

Chapter 33 gathers the screen-space effects that run after the lights: ambient occlusion done properly, reflections, indirect light and contact shadows.

Exercises

Try it yourself

The correct test. Finish touches in the playground.
Hint
const px = Math.max(x0, Math.min(cx, x1)), py = Math.max(y0, Math.min(cy, y1)); return (px - cx) ** 2 + (py - cy) ** 2 < r * r; The same clamp-then-measure test, in three dimensions, is what the cluster culling shader runs.
Lights per cluster. In the hero, set 4,096 lights and look at "lights per pixel". Where are the lists longest, and why?
Hint
Far away, where each cluster is large and many lights' spheres overlap it. Exponential slicing keeps far clusters bigger in the world but similar on screen, so their lists grow; a cap on list length (here 256) or a limit on light range keeps the worst case bounded.
Merge two reservoirs. Pixel A's reservoir chose light 12 from a total weight of 3.0; pixel B's chose light 40 from a total of 1.0. What is the chance the merged reservoir keeps light 40?
Hint
Treat B's choice as one item of weight 1.0 joining A's total of 3.0: it replaces A's choice with probability 1.0 ÷ (3.0 + 1.0) = 25%. (Full ReSTIR also re-scores the candidate from the receiving pixel's point of view, since a light that's bright for B may be dim for A.)