Path tracing

Simulating light to achieve photorealistic rendering

Path tracing is a class of rendering techniques that aims to simulate light in order to produce a true-to-life rendering of a scene. It does so by tracing paths taken by light particles (so-called photons). Photons are emitted by light sources, such as a light bulb, a torch or even the sun. The brighter a light, the more photons it emits. These photons travel in straight paths from the light. When a photon makes contact with a surface, it bounces in a random direction and continues on a straight path until it finds the next surface. Eventually, the photon may reach the lens of a camera or an eye. When it does, the photon is registered by this observer. Combining this process for all photons in a given scene, results in an image formed over the area of the lens of the observer. Path tracing simulates this technique by tracing the paths taken by photons throughout the scene. Therefore, light and objects look exactly the same as they would in real-life!

Simulating photon paths

Simulating all photons emitted by all lights in a given scene consumes a lot of time. Furthermore, many of these photons may never even reach the observer in the first place. We would be wasting a lot of computing power on light that does not contribute to the final image. Therefore, in the path tracing approach, we don't trace photons from the lights to the camera, but from the camera to the lights! Photon paths are fully reversible, therefore, we might just as well start at the camera. We shoot photons from the camera, into the scene. When a photon hits a surface, it bounces in a random direction until a light emitting surface is found. When it hits the light area, the path terminates and we have found a photon path that contributes to the final image.

By reversing photon paths, we only need to spend computing power on photons that actually contribute towards the final image. In this manner, a lot of computing power is saved and images can be rendered much faster! However, using this approach, we don't even come close to achieving real-time performance.

Noise

As we described earlier, a photon is shot from the camera into the scene and bounces around until it finds a light emitting surface. However, this photon might just as well never find such a light emitting surface. This may be case when the photon leaves the scene, for example, when it goes up into the sky. In this case, the photon will never find a light source. This means that the corresponding position on the area of the lens will be black! It turns out that this is the case for many, many photons that are shot from the camera. Therefore, when we render an image using a single photon per pixel, we will have an image that has a lot of noise in it, as shown below.

In order to counter this, we can not shoot a single photon per pixel, but shoot two, or maybe even four. Because each photon bounces into random directions when it finds a surface, some of these photons may reach a light source and some might not. By averaging over the results of these photon paths, we produce an image that is photo-realistic. We gather photon samples at each pixel, which results in a noise-less output image! Therefore, the path tracing algorithm falls in a class of algorithms known as Monte-Carlo algorithms. We essentially produce an estimate of all light that hits the camera using multiple photon samples per pixel. However, increasing the number of photons per pixels linearly increases the amount of computation time required to produce an image! As such, doubling the amount of photon samples per pixel, results in cutting the FPS in half. More advanced techniques are required to produce good looking images in real-time.

Variance Reduction

While it is possible to reduce noise by simply taking more samples per pixel, we can also try to reduce noise by taking guesses at which photon paths may result in a lot of light energy. These paths contribute heavily towards the final image and should therefore be favored over paths that do not return a lot of light energy. We can use information about the environment, such as the position and geometry of the light sources and the properties of the materials that the photons bounce of, in order to determine better paths for the photons. This process reduces the amount of variance in the final output image and is therefore known as variance reduction.

Variance reduction is not a single technique, but a class of approaches which each affect variance. In our path tracing engine, we apply direct illumination sampling, importance sampling, multiple importance sampling and resampled importance sampling. Combining these approaches results in a far better image!

Direct Illumination Sampling

Using direct illumination sampling, at each photon bounce, we trace a ray to a random nearby light source. We can evaluate the illumination at this bounce point and add it to the energy carried by the photon. In this way, we drastically reduce the amount of noise in each frame, because we can determine the direct illumination very accurately with just one photon per pixel.

Multiple Importance Sampling

To account for directly sampling the lights, we can no longer add any energy to the photon when a light emmitting surface is reached through random bouncing. If we would, all lights will become twice as bright! However, to make sure computation time of this traced photon path is not wasted, we can weight the light received via the random bounce and the light received via the direct sampling. In this way, we can reduce noise even further.

Grid Acceleration Structure

Instead of checking each photon path against each object in the scene, we use a grid acceleration structure. This grid is perfectly suited for a Minecraft-style game. The whole world is divided up in blocks anyway! Using this structure, we only need to check the path against the blocks it actually passes through. A block may be empty or filled with a material (such as grass or dirt). When it is filled, we know that the photon hits that block and should bounce in a new direction.