This chapter links to the course’s interactive demos and uses MathJax for its formulas. Read it through the course website (or download the file and open it in a browser); a Canvas inline preview will reach neither the demos nor the math. All chapters.

Ray Tracing and Global Illumination

Arthur Appel cast rays from the eye to shade and shadow solids in 1968, at IBM, twelve years before Whitted's recursive ray tracer. Appel, Some Techniques for Shading Machine Renderings of Solids, AFIPS 1968

The rasterizer of the earlier chapters asks, for each triangle, which pixels it covers. Ray tracing asks the opposite question, for each pixel, which surface it sees, by following a ray from the eye through the pixel into the scene. The reversal costs a search per pixel and buys everything the rasterizer cannot do directly: exact shadows, mirrors, glass, and, once the rays are allowed to bounce at random, the whole of global illumination. This chapter builds the machine from its parts. It casts a camera ray through the illumination demo’s sphere and solves the quadratic by hand, intersects a triangle two ways and a box, sends a ray into an instanced ellipsoid, traces Whitted’s reflection and refraction tree with Snell’s law and the Fresnel factor worked, renders a small scene with that recursion, and then softens it: an area light sampled for a penumbra and a thin lens for depth of field, both rendered. A bounding-volume hierarchy turns a scene of seventy thousand triangles from impossible to routine. The second half replaces the fixed tree by random sampling: a four-sample Monte Carlo estimate, the measured \(1/\sqrt{N}\) convergence, the two ways to sample a lighting integral and the combination that survives both failures, and a Cornell box path-traced at 8 and 512 samples per pixel next to the same scene lit directly, the difference being the indirect light a local model omits. Fog and the shader stages of a hardware ray tracer close the chapter.

1 · Rays, and the ray through a pixel

The camera of the viewing chapter gives the ray through a pixel. With the eye at \(\mathbf{e}\), the camera basis \(\mathbf{u}, \mathbf{v}, \mathbf{w}\) (right, up, and backward), a vertical field of view \(\phi\) and a square image of \(S\) pixels, the pixel \((p_x, p_y)\) has normalized coordinates \(s_x = 2(p_x + \tfrac12)/S - 1\), \(s_y = 1 - 2(p_y + \tfrac12)/S\) in \([-1, 1]\), and its ray is \[ \mathbf{d} = \mathrm{normalize}\bigl(s_x \tan\tfrac{\phi}{2}\,\mathbf{u} + s_y \tan\tfrac{\phi}{2}\,\mathbf{v} - \mathbf{w}\bigr), \qquad \mathbf{o} = \mathbf{e}. \] This is the projection matrix run backward: instead of mapping a point to a pixel, it maps a pixel to the line of points that project there. No matrix is needed, and no perspective divide: the perspective is in the fan of directions. The interaction chapter builds the same ray from the inverse of the projection and view matrices, and the two agree to four digits on the pixel below.

2 · Intersections: sphere, triangle, box

node -e "
import('./lib/core/xform.js').then(x=>{
const e=[3,3,6], d=x.normalize([-0.372,-0.370,-0.852]);
const b=x.dot(e,d), c=x.dot(e,e)-1.44, disc=b*b-c; const t=-b-Math.sqrt(disc);
console.log({b:+b.toFixed(4), c:+c.toFixed(2), disc:+disc.toFixed(4), t:+t.toFixed(4), hit:e.map((v,i)=>+(v+t*d[i]).toFixed(3))});})"

{ b: -7.3336, c: 52.56, disc: 1.2224, t: 6.228, hit: [ 0.685, 0.697, 0.697 ] }

A ray tracer’s inner loop is these three routines. Everything else in a scene is either triangles (meshes), or is tested through a box around it (Section 6), or is reached by transforming the ray (next).

3 · Instancing: rays into object space

A scene of a thousand identical chairs stores one chair and a thousand matrices, as the scene-graph chapter describes. A ray tracer never transforms the chair; it transforms the ray. With the object’s world matrix \(M\), the ray is pulled into object space by \(M^{-1}\), intersected with the stored geometry there, and the hit distance and normal are carried back.

Instancing also makes the bounding-volume hierarchy of Section 6 two-level: a top-level tree over the instances’ world-space boxes, and one bottom-level tree per distinct object in its own space, built once and shared. Hardware ray tracing exposes exactly this structure.

4 · Whitted ray tracing: shadows, mirrors, glass

Appel cast rays in 1968 to find visible surfaces and shadows. Whitted’s 1980 algorithm made the hit point itself a source of rays: at each hit, shade with the local model of the illumination chapter, but first send a shadow ray toward each light and use the light only if nothing blocks it; then, for a reflective surface, send a reflection ray in the mirror direction and add what it sees; for a transparent one, send a refraction ray bent by Snell’s law and add that too. Each secondary ray is traced by the same routine, so the image is a recursion, a tree of rays per pixel, cut off at a maximum depth.

What the picture has that the rasterizer lacks: shadows that are exact by construction (a shadow ray either hits something or does not), reflections of things off-screen, and refraction that shows the scene through the sphere. What it lacks is everything soft: the shadows have hard edges because the light is a point, the mirror is perfect because there is one reflection ray, the floor under the spheres is not tinted by them because a diffuse hit sends no further rays. Those are the limits of following one ray per event, and the rest of the chapter removes them by sending many.

5 · Distributed rays: soft shadows, depth of field, motion blur

Cook, Porter and Carpenter (1984) noticed that every hard edge in a Whitted image comes from replacing an integral by a single sample: a point light instead of an area, a pinhole instead of a lens, an instant instead of a shutter interval, a mirror direction instead of a glossy lobe. Their distributed ray tracing sends several rays per event, each at a random position in the integral’s domain, and averages. It is the Monte Carlo of Section 7 before the name, and it produces the effects that make an image look photographed.

A thin lens gives depth of field. Instead of one ray from the eye, choose a point on a disk of radius \(a\) (the aperture) around it, and aim at where the pinhole ray crosses the focal plane at distance \(f\): points on that plane are seen the same by every lens sample and stay sharp; points at another distance \(z\) spread over a circle of confusion of diameter \(2a\,|z - f|/z\) measured on the focal plane.

Motion blur is the same trick on the time axis: give each ray a random time within the shutter interval and place the moving objects where they are at that time. Glossy reflection samples directions around the mirror direction weighted by the BRDF lobe of the light-transport chapter. All four effects cost the same: \(N\) times the rays for a noise that falls as \(1/\sqrt N\), and the rays of different effects can share the same sample (one ray with a lens position, a light position and a time), so the cost does not multiply.

6 · Acceleration: the bounding-volume hierarchy

Every ray of every kind must find its nearest hit, and the naive way tests every object. For the bunny of the meshes chapter at \(1920\times1080\) with three rays per pixel (primary, shadow, reflection), that is \(2{,}073{,}600 \times 3 \times 69{,}451 \approx 4.3\times10^{11}\) triangle tests for one frame. The fix is to test boxes before triangles, hierarchically.

The median split is the simplest builder. Production builders minimize the surface area heuristic: the expected cost of a node is the probability of a ray entering each child, which is proportional to the child’s surface area, times the child’s primitive count, and the split plane is chosen to minimize that sum over a few candidate positions. It produces trees that a ray traverses two to three times faster than median trees on real scenes. Alternatives partition space rather than objects: a uniform grid (cheap to build, poor when objects cluster) or a k-d tree (splits space by axis-aligned planes; excellent traversal, harder to update). Production tracers use BVHs, and the acceleration structure is why ray tracing scales to scenes of billions of triangles while the rasterizer must touch each triangle every frame.

7 · Monte Carlo integration and importance sampling

Soft shadows, glossy reflections, and light bouncing between diffuse surfaces are all integrals: over the area of a light, over a lobe of directions, over the whole hemisphere above a point. The rendering equation of the light-transport chapter is that integral in its general form. It has no closed form for any scene of interest, and the way to evaluate it is to sample it.

The \(1/\sqrt N\) law is the economics of every renderer in this chapter. Halving the noise costs four times the samples; going from a preview to a clean frame is not a few more samples but a few hundred times more. It is also why the noise is honest: an unbiased estimator’s error is random, with no systematic darkening or brightening, and it averages away. The one lever that changes the constant is \(p\), and a lighting integral offers two natural choices.

Next-event estimation is the name for adding a light sample at every bounce of a path, and MIS is what reconciles it with the path’s own bounce direction hitting the light by chance. The chapter’s Cornell box uses both.

8 · Path tracing and the Cornell box

Path tracing (Kajiya, 1986) applies the estimator to the rendering equation recursively. At a hit point, estimate the direct light by sampling a point on each light and sending a shadow ray; then estimate the indirect light by choosing one random bounce direction, tracing it, and weighting what it returns by the BRDF and cosine over the density. Each pixel’s value is the average over many such paths. Because the bounce is a single random direction, the path does not branch; it is a random walk from the eye that ends when it escapes the scene or, to keep it finite without bias, when Russian roulette terminates it.

Read the three panels against the local model. Direct light only is the illumination chapter with area-light shadows: the ceiling is black (the light faces down), the shadows are black, the walls are their own color and nothing else. At 8 samples the path tracer already has every effect, buried in noise; at 512 the noise has fallen by \(\sqrt{64} = 8\) and the effects are legible: the ceiling is lit from below, the shadows are soft and filled, the spheres pick up red on the left and green on the right. Nothing in the algorithm names any of these effects. They are what the integral contains.

Production path tracers add what the chapter’s does not: importance sampling of glossy BRDFs, next-event estimation with many lights chosen by their expected contribution, the bidirectional and Metropolis variants of Section 10 for hard paths (caustics through glass), and denoisers that trade the last factor of ten in samples for a learned filter. Every one of them is the same estimator with a better \(p\).

9 · Light in a medium

Everything so far assumed that light travels unchanged between surfaces. Fog, smoke, clouds, milk and skin do not allow that: light is absorbed and scattered along the way, and a ray’s radiance changes with every unit of distance it travels through the participating medium.

Ray marching evaluates that integral by stepping along the ray, as the worked example did, and a volumetric path tracer instead samples a scattering distance from \(T\) (\(d = -\ln\xi/\sigma_t\) for a uniform \(\xi\)) and continues the random walk from there, which is unbiased and handles multiple scattering. Subsurface scattering in skin and marble is the same physics with a surface entry and exit, and is the reason those materials look soft. Real-time engines approximate a homogeneous fog by the transmittance alone, applied per pixel from the depth buffer, plus a few marched samples for light shafts.

10 · Radiosity, photon maps, bidirectional paths, and hardware rays

Radiosity (Goral, Torrance, Greenberg and Battaile, 1984) solved the diffuse case before path tracing was practical: divide the scene into patches, compute a form factor for every pair (the fraction of light leaving one that arrives at the other, a geometric integral), and solve the resulting linear system for each patch’s brightness. It is view-independent, so the solution can be baked into vertex colors or lightmaps and walked through in real time, which is what every game’s precomputed lighting still is. Its cost grows as the square of the patch count and it handles only diffuse surfaces.

Photon mapping (Jensen, 1996) traces paths from the lights instead of the eye, stores the hits in a spatial map, and estimates radiance at a point from the density of nearby photons. It handles caustics, which eye-first path tracing finds only by luck, at the price of a blurred, biased estimate. Bidirectional path tracing (Veach and Guibas, 1994; Lafortune and Willems, 1993) traces one path from the eye and one from the light and connects every vertex of one to every vertex of the other with shadow rays, weighting all the resulting paths by MIS; it finds light through a keyhole or under a lampshade that the eye path alone would almost never reach. Metropolis light transport (Veach and Guibas, 1997) goes further and, having found one such path, explores its neighbors by small mutations, so that the hard paths are sampled in proportion to how much light they carry.

Denoising is the practical companion of all of them: a filter, today a trained network, that takes an image at a few samples per pixel together with its depth, normal and albedo buffers and produces one that looks converged, trading the last order of magnitude of samples for a small bias in the fine detail. Every production renderer ships one.

Real-time ray tracing arrived in hardware in 2018: GPUs with dedicated units for box and triangle tests traverse two-level BVHs at billions of rays per second, enough for one or a few samples per pixel per frame. The programming model is five shader stages: a ray generation shader (one per pixel, the camera of Section 1), an intersection shader for primitives that are not triangles (the sphere of Section 2), an any-hit shader called at every candidate hit (alpha-tested leaves, shadow rays that can stop at the first hit), a closest-hit shader (the shading of Section 4, which may recurse), and a miss shader (the sky). The acceleration structure is built by the driver from the triangles and the instance matrices of Section 3. Games use the stages for shadows, reflections and one bounce of indirect light, run a denoiser over the noisy result, and rasterize everything else. The hybrid is the current state of the field: the rasterizer for visibility, rays for the effects it cannot do, and the estimator of Section 7 underneath both.

11 · Exercises

node -e "import('./lib/core/xform.js').then(x=>{
const A=[0,0,0],B=[2,0,0],C=[0,2,0],o=[0.2,1.5,1],d=[0,0,-1];
const e1=x.sub(B,A),e2=x.sub(C,A),p=x.cross(d,e2),det=x.dot(e1,p),s=x.sub(o,A);
const u=x.dot(s,p)/det,q=x.cross(s,e1),v=x.dot(d,q)/det,t=x.dot(e2,q)/det;
console.log({det,u,v,t,inside:u>=0&&v>=0&&u+v<=1});})"