View source for Path tracing

{{for multi|tracing network paths|Traceroute|other uses|Tracing (disambiguation)}}
{{short description|Computer graphics method}}
<!-- Deleted image removed: [[Image:SunroomIndigoRender2007.jpg|right|thumb|300px|Path tracing excels in indoor scenes in which complicated indirect light would confound lesser methods.]] -->
[[File:Path tracing 001.png|right|thumb|350px|An image rendered using path tracing, demonstrating notable features of the technique]]

'''Path tracing''' is a rendering algorithm in [[computer graphics]] that [[Simulation|simulates]] how light interacts with [[Physical object|objects]], [[voxel]]s, and [[Volumetric_path_tracing|participating media]] to generate realistic (''physically plausible'') [[Raster graphics|images]].

This [[Ray_tracing_(graphics)|ray tracing]] technique uses the [[Monte Carlo method]] to accurately model [[global illumination]], simulate different surface characteristics, and capture a wide range of effects observable in a [[camera]] system, such as optical properties of [[lens]]es (e.g., [[depth of field]] and [[bokeh]]) or the impact of [[Shutter (photography)|shutter]] speed (e.g., [[motion blur]] and [[Exposure_value|exposure]]). By incorporating [[Physically_based_rendering|physically accurate materials]] and [[Light_transport_theory|light transport models]], it can produce [[Photorealism|photorealistic]] results but requires significant computational power. Performance is often constrained by [[Video random-access memory|VRAM]]/[[Random-access memory|RAM]] capacity and memory bandwidth, especially in complex scenes, necessitating [[Image noise|denoising]] <!-- Future editors! In this article, "denoising" refers to reducing the visible noise in 2D rendered images (such as the artifacts typically addressed by AI denoising in path tracing) which is conceptually closer to [[Image noise]]. Please avoid linking "denoising" to [[Noise (signal processing)]]. There is no dedicated AI denoising page, but there is [[Noise_reduction#In_images]]. I will be continuously working on this article and I might dedicate a section (or a new page) to the missing topic. If unsure, feel free to talk to: [[User:Czerniawskimc]] --> techniques for practical use. Additionally, the [[Garbage_in,_garbage_out|Garbage In, Garbage Out (GIGO)]] principle applies - inaccurate scene data, poor [[Geometric_modeling|geometry]], low-quality [[Physically_based_rendering#Process|materials]], or incorrect rendering settings can negatively impact the final output, regardless of [[Rendering_(computer_graphics)|rendering]] precision.

Due to its accuracy, [[Unbiased rendering|unbiased]] nature, and algorithmic simplicity, path tracing is commonly used to generate reference images when testing the quality of other rendering [[Algorithm|algorithm]]s. Fundamentally, the algorithm works by [[Monte Carlo integration|integrating]] the light arriving at a point on an object’s surface, where this [[illuminance]] is then modified by a surface reflectance function ([[Bidirectional reflectance distribution function|BRDF]]) to determine how much light contributes to the final image, as seen by the camera. This integration procedure is repeated for every [[pixel]] in the output image, ensuring detailed evaluation of each one. The number of samples per pixel (spp) determines the level of detail and quality of the final render, with more samples generally improving image clarity. Rendering performance is often measured in mega samples per second (Ms/sec), which reflects how many millions of samples can be processed per second, directly impacting rendering speed. Several variants of path tracing, such as [[Path tracing#Bidirectional path tracing|bidirectional path tracing]] and [[Metropolis light transport]], have been developed to improve efficiency in various types of scenes, reducing noise and speeding up convergence.

==History==

{{further|Rendering (computer graphics)#Chronology of algorithms and techniques}}

The [[rendering equation]] and its use in computer graphics was presented by [[James Kajiya]] in 1986.{{Ref|kajiya1986rendering}} Path tracing was introduced then as an algorithm to find a [[Monte Carlo integration|numerical solution]] to the integral of the rendering equation. A decade later, Lafortune suggested many refinements, including bidirectional path tracing.{{Ref|lafortune1996mathematical}}

[[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, [[CPU]]s and [[GPU]]s 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.{{Ref|purcell2002ray}} In February 2009, Austin Robison of [[Nvidia]] demonstrated the first commercial implementation of a path tracer running on a GPU,{{Ref|robisonNVIRT}} and other implementations have followed, such as that of Vladimir Koylazov in August 2009.{{Ref|pathGPUimplementations}} This was aided by the maturing of [[GPGPU]] programming toolkits such as [[CUDA]] and [[OpenCL]] and GPU ray tracing SDKs such as [[OptiX]].

Path tracing has played an important role in the film industry. Earlier films had relied on [[scanline rendering]] to produce CG visual effects and animation. In 1998, [[Blue Sky Studios]] rendered the [[Academy Award]]-winning short film [[Bunny (1998 film)|''Bunny'']] with their proprietary CGI Studio path tracing renderer, featuring soft shadows and indirect illumination effects. [[Sony Pictures Imageworks]]' ''[[Monster House (film)|Monster House]]'' was, in 2006, the first animated feature film to be rendered entirely in a path tracer, using the commercial [[Arnold (software)|Arnold]] renderer. Also, [[Walt Disney Animation Studios]] has been using its own optimized path tracer known as Hyperion ever since the production of ''[[Big Hero 6 (film)|Big Hero 6]]'' in 2014.{{Ref|DisneyHyperion}} [[Pixar Animation Studios]] has also adopted path tracing for its commercial [[RenderMan]] renderer.

==Description==

Kajiya's [[rendering equation]] adheres to three particular principles of optics; the Principle of Global Illumination, the Principle of Equivalence (reflected light is equivalent to emitted light), and the Principle of Direction (reflected light and scattered light have a direction).

In the real world, objects and surfaces are visible due to the fact that they are reflecting light. This reflected light then illuminates other objects in turn. From that simple observation, two principles follow.

'''I.''' For a given indoor scene, every object in the room must contribute illumination to every other object.

'''II.''' Second, there is no distinction to be made between illumination emitted from a light source and illumination reflected from a surface.

Invented in 1984, a rather different method called [[Radiosity (computer graphics)|radiosity]] was faithful to both principles. However, radiosity relates the total illuminance falling on a surface with a uniform [[luminance]] that leaves the surface. This forced all surfaces to be [[Lambertian reflectance|Lambertian]], or "perfectly diffuse". While radiosity received a lot of attention at its introduction, perfectly diffuse surfaces do not exist in the real world. The realization that scattering from a surface depends on both incoming and outgoing directions is the key principle behind the [[bidirectional reflectance distribution function]] (BRDF). This direction dependence was a focus of research resulting in the [[Rendering (computer graphics)#Chronology of important published ideas|publication of important ideas]] throughout the 1990s, since accounting for direction always exacted a price of steep increases in calculation times on desktop computers. Principle III follows.

'''III.''' The illumination coming from surfaces must scatter in a particular direction that is some function of the incoming direction of the arriving illumination, and the outgoing direction being sampled.

Kajiya's equation is a complete summary of these three principles, and path tracing, which approximates a solution to the equation, remains faithful to them in its implementation. There are other principles of optics which are not the focus of Kajiya's equation, and therefore are often difficult or incorrectly simulated by the algorithm. Path tracing is confounded by optical phenomena not contained in the three principles. For example,

* Bright, sharp [[Caustic (optics)|caustics]]; [[radiance]] scales by the density of illuminance in space.
* [[Subsurface scattering]]; a violation of Principle III above.
* [[Chromatic aberration]], [[fluorescence]], [[iridescence]]; light is a spectrum of frequencies.

==Algorithm==

The following [[pseudocode]] is a procedure for performing naive path tracing. The TracePath function calculates a single sample of a pixel, where only the Gathering Path is considered.

<syntaxhighlight lang="c" line="1">
Color TracePath(Ray ray, count depth) {
  if (depth >= MaxDepth) {
    return Black;  // Bounced enough times.
  }

  ray.FindNearestObject();
  if (ray.hitSomething == false) {
    return Black;  // Nothing was hit.
  }

  Material material = ray.thingHit->material;
  Color emittance = material.emittance;

  // Pick a random direction from here and keep going.
  Ray newRay;
  newRay.origin = ray.pointWhereObjWasHit;

  // This is NOT a cosine-weighted distribution!
  newRay.direction = RandomUnitVectorInHemisphereOf(ray.normalWhereObjWasHit);

  // Probability of the newRay
  const float p = 1 / (2 * PI);

  // Compute the BRDF for this ray (assuming Lambertian reflection)
  float cos_theta = DotProduct(newRay.direction, ray.normalWhereObjWasHit);
  Color BRDF = material.reflectance / PI;

  // Recursively trace reflected light sources.
  Color incoming = TracePath(newRay, depth + 1);

  // Apply the Rendering Equation here.
  return emittance + (BRDF * incoming * cos_theta / p);
}

void Render(Image finalImage, count numSamples) {
  foreach (pixel in finalImage) {
    foreach (i in numSamples) {
      Ray r = camera.generateRay(pixel);
      pixel.color += TracePath(r, 0);
    }
    pixel.color /= numSamples;  // Average samples.
  }
}
</syntaxhighlight>

All the samples are then [[Arithmetic mean|averaged]] to obtain the output color. Note this method of always sampling a random ray in the normal's hemisphere only works well for perfectly diffuse surfaces. For other materials, one generally has to use importance sampling, i.e. probabilistically select a new ray according to the BRDF's distribution. For instance, a perfectly specular (mirror) material would not work with the method above, as the probability of the new ray being the correct reflected ray – which is the only ray through which any radiance will be reflected – is zero. In these situations, one must divide the reflectance by the [[probability density function]] of the sampling scheme, as per Monte Carlo integration (in the naive case above, there is no particular sampling scheme, so the PDF turns out to be <math>\frac{1}{2\pi}</math>).

There are other considerations to take into account to ensure conservation of energy. In particular, in the naive case, the reflectance of a diffuse BRDF must not exceed <math>\frac{1}{\pi}</math> or the object will reflect more light than it receives (this however depends on the sampling scheme used, and can be difficult to get right).

==Bidirectional path tracing==

Sampling the integral can be done by either of the following two distinct approaches:
* '''Backwards path tracing''', where paths are generated starting from the camera and bouncing around the scene until they encounter a light source. This is referred to as "backwards" because starting paths from the camera and moving towards the light source is opposite the direction that the light is actually traveling. It still produces the same result because all optical systems are reversible.
* '''Light tracing''' (or '''forwards path tracing'''), where paths are generated starting from the light sources and bouncing around the scene until they encounter the camera.

In both cases, a technique called ''next event estimation'' can be used to reduce variance. This works by directly sampling an important feature (the camera in the case of ''light tracing'', or a light source in the case of ''backwards path tracing'') instead of waiting for a path to hit it by chance. This technique is usually effective, but becomes less useful when specular or near-specular BRDFs are present. For ''backwards path tracing'', this creates high variance for [[Caustic (optics)|caustic]] paths that interact with a diffuse surface, then bounce off a specular surface before hitting a light source. ''Next event estimation'' cannot be used to sample these paths directly from the diffuse surface, because the specular interaction is in the middle. Likewise, it cannot be used to sample paths from the specular surface because there is only one direction that the light can bounce. ''Light tracing'' has a similar issue when paths interact with a specular surface before hitting the camera. Because this situation is significantly more common, and noisy (or completely black) glass objects are very visually disruptive, ''backwards path tracing'' is the only method that is used for unidirectional path tracing in practice.

Bidirectional path tracing provides an algorithm that combines the two approaches and can produce lower variance than either method alone. For each sample, two paths are traced independently: one using from the light source and one from the camera. This produces a set of possible sampling strategies, where every vertex of one path can be connected directly to every vertex of the other. The original ''light tracing'' and ''backwards path tracing'' algorithms are both special cases of these strategies. For ''light tracing'', it is connecting the vertices of the camera path directly to the first vertex of the light path. For ''backwards path tracing'', it is connecting the vertices of the light path to the first vertex of the camera path. In addition, there are several completely new sampling strategies, where intermediate vertices are connected. Weighting all of these sampling strategies using [[Importance sampling#Multiple_and_adaptive_importance_sampling|multiple importance sampling]] creates a new sampler that can converge faster than unidirectional path tracing, even though more work is required for each sample. This works particularly well for caustics or scenes that are lit primarily through indirect lighting.

==Performance==

[[File:Path tracing sampling values.png|thumb|right|Noise decreases as the number of samples per pixel increase. The top left shows 1 sample per pixel, and doubles from left to right each square.]]

A path tracer continuously samples [[pixel]]s of an [[image]]. The image starts to become recognizable 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 (mathematics)|pathological]] cases. Noise is particularly a problem for animations, giving them a normally unwanted "film grain" quality of random speckling.

The central performance bottleneck in path tracing is the complex geometrical calculation of casting a ray. Importance sampling is a technique which is motivated to cast fewer rays through the scene while still converging correctly to outgoing luminance on the surface point. This is done by casting more rays in directions in which the luminance would have been greater anyway. If the density of rays cast in certain directions matches the strength of contributions in those directions, the result is identical, but far fewer rays were actually cast. Importance sampling is used to match ray density to [[Lambert's cosine law]], and also used to match BRDFs.

[[Metropolis light transport]] can result in a lower-noise image with fewer samples. This algorithm was created in order to get faster convergence in scenes in which the light must pass through odd corridors or small holes in order to reach the part of the scene that the camera is viewing. It has also shown promise in correctly rendering pathological situations with caustics. Instead of generating random paths, new sampling paths are created as slight mutations of existing ones. In this sense, the algorithm "remembers" the successful paths from light sources to the camera.

==Scattering distribution functions==
[[Image:Bidirectional scattering distribution function.svg|thumb|right|Scattering distribution functions]]

The reflective properties (amount, direction, and color) of surfaces are modeled using [[bidirectional reflectance distribution function|BRDFs]]. The equivalent for transmitted light (light that goes through the object) are [[bidirectional scattering distribution function|BSDFs]]. A path tracer can take full advantage of complex, carefully modeled or measured distribution functions, which controls the appearance ("material", "texture", or "shading" in computer graphics terms) of an object.

==See also==

* [[Arnold (software)]]
* [[Blender (software)]] – 3D program that integrates '''Cycles''', a path tracing GPU-accelerated rendering engine
* [[Octane Render]]
* [[Pixar RenderMan]]
* [[LuxRender|LuxCoreRenderer]]

== Notes ==

{{Reflist}}
# {{note |kajiya1986rendering}}{{cite conference | last = Kajiya | first = J. T. | citeseerx=10.1.1.63.1402 | title = The rendering equation | book-title = Proceedings of the 13th annual conference on Computer graphics and interactive techniques | publisher = ACM | year = 1986 }}
# {{note |lafortune1996mathematical}}Lafortune, E, [https://web.archive.org/web/20160807210051/http://www.graphics.cornell.edu:80/~eric/thesis/index.html Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering], (PhD thesis), 1996.
# {{note |purcell2002ray}}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, [http://graphics.stanford.edu/papers/tpurcell_thesis/ Ray tracing on a stream processor] (PhD thesis), 2004.
# {{note |robisonNVIRT}}Robison, Austin, [http://realtimerendering.com/downloads/NVIRT-Overview.pdf "Interactive Ray Tracing on the GPU and NVIRT Overview"], slide 37, I3D 2009.
# {{note |pathGPUimplementations}}[https://www.youtube.com/watch?v=eRoSFNRQETg Vray demo]; Other examples include Octane Render, Arion, and Luxrender.
# {{note |DisneyHyperion}}{{cite web|last1=Seymour|first1=Mike|title=Disney’s new Production Renderer ‘Hyperion’ – Yes, Disney!|url=https://www.fxguide.com/featured/disneys-new-production-renderer-hyperion-yes-disney/|website=fxguide|access-date=16 September 2017}}
# {{note |veach1997metropolis}}Veach, E., and Guibas, L. J. [http://graphics.stanford.edu/papers/metro/metro.pdf Metropolis light transport]. In SIGGRAPH’97 (August 1997), pp.&nbsp;65–76.
# [http://www.kevinbeason.com/smallpt/ 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.

{{DEFAULTSORT:Path Tracing}}
{{Computer graphics}}
[[Category:Global illumination algorithms]]