AndrewBromage/SamplingAndRendering

PseudoCode: Sampling and Rendering, Part 1

by AndrewBromage for The Monad.Reader IssueX
31.07.2005

Abstract

A hands-on introduction to the theory of rendering.

The Nature of Light

This year is the 100th anniversary of five landmark papers published in the German journal Annalen der Physik by a then-unknown patent examiner named Albert Einstein. In one of those papers, the title of which is usually translated On a Heuristic Point of View Concerning the Production and Transformation of Light, Einstein suggested that, from a thermodynamic point of view, light could be described as if it consists of independent packets (or quanta) of energy.

Nowadays, these quanta are called photons. It turns out that there are an awful lot of them involved in vision and photography. A standard international candle¹ emits over 5e16 photons every second. A typical stage light, of the sort used in cinematography, emits several orders of magnitude more than that, and in a more tightly focussed beam.

Photons, after they leave a light source, get absorbed and sometimes re-emitted by whatever they come in contact with. Eventually, a few of them enter the pupil of someone's eye or the aperture of a camera, both of which usually have quite small areas. Even so, in a brightly-lit room, as many as 2.0e12 photons might be entering your eye in any given millisecond.

Clearly, a full physical simulation of this is beyond current computing technology. Still, you can get some pretty good results by using fewer individual photons. The Photon Soup 2 project managed to trace 382 billion photons over the course of several months using a large number of distributed clients.

The results look pretty impressive, but the speed is a bit of a problem. Let's suppose you're in the movie business. A typical animated feature film is anywhere from 70 to 85 minutes long. At 24 frames per second, allowing a year of processing time, you only have about five minutes to compute a single frame. Clearly there has to be a better way.

Sampling

Rendering is the process of taking a continuous representation of some three-dimensional scene and turning it into a two-dimensional array of samples, known as pixels. It is very important to understand that pixels are point samples, and not squares (or rectangles). This point was most stronly emphasised by Alvy Ray Smith in a technical memo which is well worth reading if you're at all interested in this sort of thing.

The take-home lesson is that rendering is sampling. How to represent a continuous signal with a periodic set of samples (also known as analog-to-digital conversion, or A/D conversion for short) is part of the field of Digital Signal Processing (or DSP for short). DSP has given us many useful theorems and techniques which help with understanding the problem of rendering, the most relevant of which we will briefly discuss.

The adjoint of a photon

Cornell box, local illumination only, soft shadows:

Stratified light sampling:

Final gathering only:

test.3.png

1 Assuming that it is emitting power in all directions.