The Full Wiki

Path tracing: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

A simple scene showing the soft phenomena simulated with path tracing.

Path tracing is a computer graphics rendering technique that attempts to simulate the physical behaviour of light as closely as possible. It is a generalisation of conventional ray tracing, tracing rays 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 is the simplest, most physically-accurate and slowest rendering method. It naturally simulates many effects that have to be specifically added to other methods (ray tracing or scanline rendering), such as soft shadows, depth of field, motion blur, caustics, ambient occlusion, and indirect lighting. Implementation of a renderer including these effects is correspondingly simpler.

Due to its accuracy and unbiased nature, path tracing is used to generate reference images when testing the quality of other rendering algorithms. In order to get high quality images from path tracing, a very large number of rays need to be traced lest the image have lots of visible artefacts in the form of noise.

Contents

History

A more complete history is given here.

The rendering equation and its use in computer graphics was presented by James Kajiya in 1986.[1] This presentation contained what was probably the first description of the path tracing algorithm. Later that year, Lafortune suggested many refinements, including bidirectional path tracing.[2]

Metropolis light transport, 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.

More recently, computers 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 algorithm running on a GPU in 2002.[3] In 2009, Vladimir Koylazov demonstrated the first commercial implementation of a path tracer running on a GPU, and other implementations have followed.[4] This was aided by the maturing of GPGPU programming toolkits such as CUDA and OpenCL.

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, 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, which is the equation that path tracing algorithms try to solve.

Path tracing is not simply ray tracing with infinite recursion 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 cost = DotProduct(newRay.direction, r.normalWhereObjWasHit);

   Color BRDF = m.reflectance/PI;
   float scale = 1.0*PI;
   Color reflected = TracePath(newRay,depth+1);

   // return emittance + ( BRDF * scale * cost * reflected );
   return emittance + ( BRDF * scale * 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 give a more accurate description[5]:

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 pixels of an image. 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 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.[citation needed] Noise is particularly a problem for animations, giving them a normally-unwanted "film-grain" quality of random speckling.

Metropolis light transport 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.

Scattering distribution functions

Scattering distribution functions

The reflective properties (amount, direction and colour) of surfaces are modelled using BRDFs. The equivalent for transmitted light (light that goes through the object) are BTDFs. 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.

Notes

  1. ^  Kajiya, J T, The rendering equation, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, ACM, 1986
  2. ^  Lafortune, E, Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering, (PhD thesis), 1996
  3. ^  Purcell, T J; Buck, I; Mark, W; and Hanrahan, P, "Ray Tracing on Programmable Graphics Hardware", Proc. SIGGRAPH 2002, 703 - 712. See also Purcell, T, Ray tracing on a stream processor (PhD thesis), 2004
  4. ^  Vray demo; Other examples include Octane Render, Arion, and Luxrender.
  5. ^  Veach, E., and Guibas, L. J. Metropolis light transport. In SIGGRAPH’97 (August 1997), pp. 65–76.
  1. This "Introduction to Global Illumination" has some good example images, demonstrating the image noise, caustics and indirect lighting properties of images rendered with path tracing methods. It also discusses possible performance improvements in some detail.
  2. SmallPt is an educational path tracer by Kevin Beason. It uses 99 lines of C++ (including scene description). This page has a good set of examples of noise resulting from this technique.
Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message