Path tracing is a computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

 rendering

Rendering (computer graphics)

Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...

 technique that attempts to simulate the physical behaviour of light

Light

Light or visible light is electromagnetic radiation that is visible to the human eye, and is responsible for the sense of sight. Visible light has wavelength in a range from about 380 nanometres to about 740 nm, with a frequency range of about 405 THz to 790 THz...

 as closely as possible. It is a generalisation of conventional ray tracing, tracing rays

Ray (optics)

In optics, a ray is an idealized narrow beam of light. Rays are used to model the propagation of light through an optical system, by dividing the real light field up into discrete rays that can be computationally propagated through the system by the techniques of ray tracing. This allows even very...

 from the virtual camera through several bounces on or through objects. The image quality provided by path tracing is usually superior to that of images produced using conventional rendering methods at the cost of much greater computation requirements.

Path tracing naturally simulates many effects that have to be specifically added to other methods (conventional ray tracing or scanline rendering

Scanline rendering

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

), such as soft shadows, depth of field

Depth of field

In optics, particularly as it relates to film and photography, depth of field is the distance between the nearest and farthest objects in a scene that appear acceptably sharp in an image...

, motion blur

Motion blur

Motion blur is the apparent streaking of rapidly moving objects in a still image or a sequence of images such as a movie or animation. It results when the image being recorded changes during the recording of a single frame, either due to rapid movement or long exposure.- Photography :When a camera...

, caustics

Caustic (optics)

In optics, a caustic or caustic network is the envelope of light rays reflected or refracted by a curved surface or object, or the projection of that envelope of rays on another surface. The caustic is a curve or surface to which each of the light rays is tangent, defining a boundary of an...

, ambient occlusion

Ambient occlusion

Ambient occlusion is a shading method used in 3D computer graphics which helps add realism to local reflection models by taking into account attenuation of light due to occlusion...

, and indirect lighting. Implementation of a renderer including these effects is correspondingly simpler.

Due to its accuracy and unbiased

Unbiased rendering

In computer graphics, unbiased rendering refers to a rendering technique that does not introduce any systematic error, or bias, into the radiance approximation. Because of this, they are often used to generate the reference image to which other rendering techniques are compared...

 nature, path tracing is used to generate reference images when testing the quality of other rendering algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s. In order to get high quality images from path tracing, a large number of rays must be traced to avoid visible artifacts in the form of noise

Image noise

Image noise is random variation of brightness or color information in images, and is usually an aspect of electronic noise. It can be produced by the sensor and circuitry of a scanner or digital camera...

.

History

The rendering equation

Rendering equation

In computer graphics, the rendering equation is an integral equation in which the equilibrium radiance leaving a point is given as the sum of emitted plus reflected radiance under a geometric optics approximation. It was simultaneously introduced into computer graphics by David Immel et al. and...

 and its use in computer graphics was presented by James Kajiya in 1986. This presentation contained what was probably the first description of the path tracing algorithm. A decade later, Lafortune suggested many refinements, including bidirectional path tracing.

Metropolis light transport

Metropolis light transport

The Metropolis light transport is a SIGGRAPH 1997 paper by Eric Veach and Leonidas J. Guibas, describing an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three...

, a method of perturbing previously found paths in order to increase performance for difficult scenes, was introduced in 1997 by Eric Veach and Leonidas J. Guibas

Leonidas J. Guibas

Leonidas John Guibas is a professor of computer science at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth at Stanford, where he received his Ph.D. in 1976...

.

More recently, CPUs and GPUs have become powerful enough to render images more quickly, causing more widespread interest in path tracing algorithms. Tim Purcell first presented a global illumination

Global illumination

Global illumination is a general name for a group of algorithms used in 3D computer graphics that are meant to add more realistic lighting to 3D scenes...

 algorithm running on a GPU in 2002. In February 2009 Austin Robison of Nvidia

NVIDIA

Nvidia is an American global technology company based in Santa Clara, California. Nvidia is best known for its graphics processors . Nvidia and chief rival AMD Graphics Techonologies have dominated the high performance GPU market, pushing other manufacturers to smaller, niche roles...

 demonstrated the first commercial implementation of a path tracer running on a GPU , and other implementations have followed, such as that of Vladimir Koylazov in August 2009. This was aided by the maturing of GPGPU

GPGPU

General-purpose computing on graphics processing units is the technique of using a GPU, which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the CPU...

 programming toolkits such as CUDA

CUDA

CUDA or Compute Unified Device Architecture is a parallel computing architecture developed by Nvidia. CUDA is the computing engine in Nvidia graphics processing units that is accessible to software developers through variants of industry standard programming languages...

 and OpenCL

OpenCL

OpenCL is a framework for writing programs that execute across heterogeneous platforms consisting of CPUs, GPUs, and other processors. OpenCL includes a language for writing kernels , plus APIs that are used to define and then control the platforms...

 and GPU ray tracing SDKs such as OptiX

OptiX

NVIDIA OptiX is a real time ray tracing engine for CUDA-based video cards such as the GeForce, Quadro, and Tesla series....

.

Description

In the real world, many small amounts of light are emitted from light sources, and travel in straight lines (rays) from object to object, changing colour and intensity

Intensity (physics)

In physics, intensity is a measure of the energy flux, averaged over the period of the wave. The word "intensity" here is not synonymous with "strength", "amplitude", or "level", as it sometimes is in colloquial speech...

, until they are absorbed (possibly by an eye or camera). This process is simulated by path tracing, except that the paths are traced backwards, from the camera to the light. The inefficiency arises in the random nature of the bounces from many surfaces, as it is usually quite unlikely that a path will intersect a light. As a result, most traced paths do not contribute to the final image.

This behaviour is described mathematically by the rendering equation

Rendering equation

In computer graphics, the rendering equation is an integral equation in which the equilibrium radiance leaving a point is given as the sum of emitted plus reflected radiance under a geometric optics approximation. It was simultaneously introduced into computer graphics by David Immel et al. and...

, which is the equation that path tracing algorithms try to solve.

Path tracing is not simply ray tracing with infinite recursion

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

 depth. In conventional ray tracing, lights are sampled directly when a diffuse surface is hit by a ray. In path tracing, a new ray is randomly generated within the hemisphere of the object and then traced until it hits a light — possibly never. This type of path can hit many diffuse surfaces before interacting with a light.

A simple path tracing pseudocode might look something like this:


Color TracePath(Ray r,depth) {
if(depth

MaxDepth)
return Black; // bounced enough times

r.FindNearestObject;
if(r.hitSomething

false)
return Black; // nothing was hit

Material m = r.thingHit->material;
Color emittance = m.emittance;

// pick a random direction from here and keep going
Ray newRay;
newRay.origin = r.pointWhereObjWasHit;
newRay.direction = RandomUnitVectorInHemisphereOf(r.normalWhereObjWasHit);
float cos_omega = DotProduct(newRay.direction, r.normalWhereObjWasHit);

Color BDRF = m.reflectance*cos_omega;
Color reflected = TracePath(newRay,depth+1);

return emittance + ( BDRF * cos_omega * reflected );
}


In the above example if every surface of a closed space emitted and reflected (0.5,0.5,0.5) then every pixel in the image would be white.

Bidirectional path tracing

In order to accelerate the convergence of images, bidirectional algorithms trace paths in both directions. In the forward direction, rays are traced from light sources until they are too faint to be seen or strike the camera. In the reverse direction (the usual one), rays are traced from the camera until they strike a light or too many bounces ("depth") have occurred. This approach normally results in an image that converges much more quickly than using only one direction.

Veach and Guibas

Leonidas J. Guibas

Leonidas John Guibas is a professor of computer science at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth at Stanford, where he received his Ph.D. in 1976...

 give a more accurate description:

These methods generate one subpath starting at a light source and another
starting at the lens, then they consider all the paths obtained
by joining every prefix of one subpath to every suffix
of the other. This leads to a family of different importance
sampling techniques for paths, which are then combined to
minimize variance.

Performance

A path tracer continuously samples pixel

Pixel

In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....

s of an image

Image

An image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...

. The image starts to become recognisable after only a few samples per pixel, perhaps 100. However, for the image to "converge" and reduce noise to acceptable levels usually takes around 5000 samples for most images, and many more for pathological

Pathological (mathematics)

In mathematics, a pathological phenomenon is one whose properties are considered atypically bad or counterintuitive; the opposite is well-behaved....

 cases. This can take hours or days depending on scene complexity and hardware and software performance. Newer GPU implementations are promising from 1-10 million samples per second on modern hardware, producing acceptably noise-free images in seconds or minutes. Noise is particularly a problem for animations, giving them a normally-unwanted "film-grain" quality of random speckling.

Metropolis light transport

Metropolis light transport

The Metropolis light transport is a SIGGRAPH 1997 paper by Eric Veach and Leonidas J. Guibas, describing an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three...

 obtains more important samples first, by slightly modifying previously-traced successful paths. This can result in a lower-noise image with fewer samples.

Renderer performance is quite difficult to measure fairly. One approach is to measure "Samples per second", or the number of paths that can be traced and added to the image each second. This varies considerably between scenes and also depends on the "path depth", or how many times a ray is allowed to bounce before it is abandoned. It also depends heavily on the hardware used. Finally, one renderer may generate many low quality samples, while another may converge faster using fewer high-quality samples.

Scattering distribution functions

The reflective properties (amount, direction and colour) of surfaces are modelled using BRDF

Bidirectional reflectance distribution function

The bidirectional reflectance distribution function is a four-dimensional function that defines how light is reflected at an opaque surface...

s. The equivalent for transmitted light (light that goes through the object) are BTDF

Bidirectional scattering distribution function

The definition of the BSDF is not well standardized. The term was probably introduced in 1991 by Paul Heckbert. Most often it is used to name the general mathematical function which describes the way in which the light is scattered by a surface...

s. A path tracer can take full advantage of complex, carefully modelled or measured distribution functions, which controls the appearance ("material", "texture" or "shading" in computer graphics terms) of an object.