Photon mapping
Encyclopedia
In computer graphics
, photon mapping is a two-pass global illumination
algorithm developed by Henrik Wann Jensen
that solves the rendering equation
. Rays from the light source and rays from the camera are traced independently until some termination criterion is met, then they are connected in a second step to produce a radiance
value. It is used to realistically simulate the interaction of light
with different objects. Specifically, it is capable of simulating the refraction of light through a transparent substance such as glass or water, diffuse interreflection between illuminated objects, the subsurface scattering
of light in translucent materials, and some of the effects caused by particulate matter such as smoke or water vapor. It can also be extended to more accurate simulations of light such as spectral rendering
.
Unlike path tracing
, bidirectional path tracing and Metropolis light transport
, photon mapping is a "biased" rendering algorithm, which means that averaging many renders using this method does not converge to a correct solution to the rendering equation
. However, since it is a consistent method, a correct solution can be achieved by increasing the number of photons.
or reflected
causes patterns called caustics
, usually visible as concentrated patches of light on nearby surfaces. For example, as light rays pass through a wine glass sitting on a table, they are refracted and patterns of light are visible on the table. Photon mapping can trace the paths of individual photons to model where these concentrated patches of light will appear.
(BRDF), and thus light from one object striking another is a natural result of the method. Diffuse interreflection was first modeled using radiosity
solutions. Photon mapping differs though in that it separates the light transport from the nature of the geometry in the scene. Color bleed
is an example of diffuse interreflection.
is the effect evident when light enters a material and is scattered before being absorbed or reflected in a different direction. Subsurface scattering can accurately be modeled using photon mapping. This was the original way Jensen implemented it; however, the method becomes slow for highly scattering materials, and bidirectional surface scattering reflectance distribution functions (BSSRDFs) are more efficient in these situations.
called Russian roulette is used to choose one of these actions. If the photon is absorbed, no new direction is given, and tracing for that photon ends. If the photon reflects, the surface's bidirectional reflectance distribution function
is used to determine a new direction. Finally, if the photon is transmitting, a different function for its direction is given depending upon the nature of the transmission.
Once the photon map is constructed (or during construction), it is typically arranged in a manner that is optimal for the k-nearest neighbor algorithm
, as photon look-up time depends on the spatial distribution of the photons. Jensen advocates the usage of kd-tree
s. The photon map is then stored on disk or in memory for later usage.
At this point, the rendering equation
is used to calculate the surface radiance leaving the point of intersection in the direction of the ray that struck it. To facilitate efficiency, the equation is decomposed into four separate factors: direct illumination, specular reflection, caustics, and soft indirect illumination.
For an accurate estimate of direct illumination, a ray is traced from the point of intersection to each light source. As long as a ray does not intersect another object, the light source is used to calculate the direct illumination. For an approximate estimate of indirect illumination, the photon map is used to calculate the radiance contribution.
Specular reflection can be, in most cases, calculated using ray tracing procedures (as it handles reflections well).
The contribution to the surface radiance from caustics is calculated using the caustics photon map directly. The number of photons in this map must be sufficiently large, as the map is the only source for caustics information in the scene.
For soft indirect illumination, radiance is calculated using the photon map directly. This contribution, however, does not need to be as accurate as the caustics contribution and thus uses the global photon map.
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....
, photon mapping is a two-pass 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 developed by Henrik Wann Jensen
Henrik Wann Jensen
Henrik Wann Jensen is a Danish computer graphics researcher. He is best known for developing the photon mapping technique as the subject of his PhD thesis, but has also done important research in simulating subsurface scattering and the sky....
that solves 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...
. Rays from the light source and rays from the camera are traced independently until some termination criterion is met, then they are connected in a second step to produce a radiance
Radiance
Radiance and spectral radiance are radiometric measures that describe the amount of radiation such as light or radiant heat that passes through or is emitted from a particular area, and falls within a given solid angle in a specified direction. They are used to characterize both emission from...
value. It is used to realistically simulate the interaction 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...
with different objects. Specifically, it is capable of simulating the refraction of light through a transparent substance such as glass or water, diffuse interreflection between illuminated objects, the subsurface scattering
Subsurface scattering
Subsurface scattering is a mechanism of light transport in which light penetrates the surface of a translucent object, is scattered by interacting with the material, and exits the surface at a different point...
of light in translucent materials, and some of the effects caused by particulate matter such as smoke or water vapor. It can also be extended to more accurate simulations of light such as spectral rendering
Spectral rendering
In computer graphics, spectral rendering is where a scene's light transport is modeled with real wavelengths. This process is typically a lot slower than traditional rendering, which renders the scene in its red, green, and blue components and then overlays the images...
.
Unlike path tracing
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...
, bidirectional path tracing and 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...
, photon mapping is a "biased" rendering algorithm, which means that averaging many renders using this method does not converge to a correct solution to 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...
. However, since it is a consistent method, a correct solution can be achieved by increasing the number of photons.
Caustics
Light refractedRefraction
Refraction is the change in direction of a wave due to a change in its speed. It is essentially a surface phenomenon . The phenomenon is mainly in governance to the law of conservation of energy. The proper explanation would be that due to change of medium, the phase velocity of the wave is changed...
or reflected
Specular reflection
Specular reflection is the mirror-like reflection of light from a surface, in which light from a single incoming direction is reflected into a single outgoing direction...
causes patterns called 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...
, usually visible as concentrated patches of light on nearby surfaces. For example, as light rays pass through a wine glass sitting on a table, they are refracted and patterns of light are visible on the table. Photon mapping can trace the paths of individual photons to model where these concentrated patches of light will appear.
Diffuse interreflection
Diffuse interreflection is apparent when light from one diffuse object is reflected onto another. Photon mapping is particularly adept at handling this effect because the algorithm reflects photons from one surface to another based on that surface's bidirectional reflectance distribution functionBidirectional reflectance distribution function
The bidirectional reflectance distribution function is a four-dimensional function that defines how light is reflected at an opaque surface...
(BRDF), and thus light from one object striking another is a natural result of the method. Diffuse interreflection was first modeled using radiosity
Radiosity
Radiosity is a global illumination algorithm used in 3D computer graphics rendering. Radiosity is an application of the finite element method to solving the rendering equation for scenes with purely diffuse surfaces...
solutions. Photon mapping differs though in that it separates the light transport from the nature of the geometry in the scene. Color bleed
Color bleeding (computer graphics)
In computer graphics and 3D rendering, color bleeding is the phenomenon in which objects or surfaces are colored by reflection of colored light from nearby surfaces....
is an example of diffuse interreflection.
Subsurface scattering
Subsurface scatteringSubsurface scattering
Subsurface scattering is a mechanism of light transport in which light penetrates the surface of a translucent object, is scattered by interacting with the material, and exits the surface at a different point...
is the effect evident when light enters a material and is scattered before being absorbed or reflected in a different direction. Subsurface scattering can accurately be modeled using photon mapping. This was the original way Jensen implemented it; however, the method becomes slow for highly scattering materials, and bidirectional surface scattering reflectance distribution functions (BSSRDFs) are more efficient in these situations.
Construction of the photon map (1st pass)
With photon mapping, light packets called photons are sent out into the scene from the light sources. Whenever a photon intersects with a surface, the intersection point and incoming direction are stored in a cache called the photon map. Typically, two photon maps are created for a scene: one especially for caustics and a global one for other light. After intersecting the surface, a probability for either reflecting, absorbing, or transmitting/refracting is given by the material. A Monte Carlo methodMonte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
called Russian roulette is used to choose one of these actions. If the photon is absorbed, no new direction is given, and tracing for that photon ends. If the photon reflects, the surface's bidirectional reflectance distribution function
Bidirectional reflectance distribution function
The bidirectional reflectance distribution function is a four-dimensional function that defines how light is reflected at an opaque surface...
is used to determine a new direction. Finally, if the photon is transmitting, a different function for its direction is given depending upon the nature of the transmission.
Once the photon map is constructed (or during construction), it is typically arranged in a manner that is optimal for the k-nearest neighbor algorithm
K-nearest neighbor algorithm
In pattern recognition, the k-nearest neighbor algorithm is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until...
, as photon look-up time depends on the spatial distribution of the photons. Jensen advocates the usage of kd-tree
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
s. The photon map is then stored on disk or in memory for later usage.
Rendering (2nd pass)
In this step of the algorithm, the photon map created in the first pass is used to estimate the radiance of every pixel of the output image. For each pixel, the scene is ray traced until the closest surface of intersection is found.At this point, 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...
is used to calculate the surface radiance leaving the point of intersection in the direction of the ray that struck it. To facilitate efficiency, the equation is decomposed into four separate factors: direct illumination, specular reflection, caustics, and soft indirect illumination.
For an accurate estimate of direct illumination, a ray is traced from the point of intersection to each light source. As long as a ray does not intersect another object, the light source is used to calculate the direct illumination. For an approximate estimate of indirect illumination, the photon map is used to calculate the radiance contribution.
Specular reflection can be, in most cases, calculated using ray tracing procedures (as it handles reflections well).
The contribution to the surface radiance from caustics is calculated using the caustics photon map directly. The number of photons in this map must be sufficiently large, as the map is the only source for caustics information in the scene.
For soft indirect illumination, radiance is calculated using the photon map directly. This contribution, however, does not need to be as accurate as the caustics contribution and thus uses the global photon map.
Calculating radiance using the photon map
In order to calculate surface radiance at an intersection point, one of the cached photon maps is used. The steps are:- Gather the N nearest photons using the nearest neighbor search function on the photon map.
- Let S be the sphere that contains these N photons.
- For each photon, divide the amount of flux (real photons) that the photon represents by the area of S and multiply by the BRDF applied to that photon.
- The sum of those results for each photon represents total surface radiance returned by the surface intersection in the direction of the ray that struck it.
Optimizations
- To avoid emitting unneeded photons, the initial direction of the outgoing photons is often constrained. Instead of simply sending out photons in random directions, they are sent in the direction of a known object that is a desired photon manipulator to either focus or diffuse the light. There are many other refinements that can be made to the algorithm: for example, choosing the number of photons to send, and where and in what pattern to send them. It would seem that emitting more photons in a specific direction would cause a higher density of photons to be stored in the photon map around the position where the photons hit, and thus measuring this density would give an inaccurate value for irradianceIrradianceIrradiance is the power of electromagnetic radiation per unit area incident on a surface. Radiant emittance or radiant exitance is the power per unit area radiated by a surface. The SI units for all of these quantities are watts per square meter , while the cgs units are ergs per square centimeter...
. This is true; however, the algorithm used to compute radianceRadianceRadiance and spectral radiance are radiometric measures that describe the amount of radiation such as light or radiant heat that passes through or is emitted from a particular area, and falls within a given solid angle in a specified direction. They are used to characterize both emission from...
does not depend on irradiance estimates.
- For soft indirect illumination, if the surface is Lambertian, then a technique known as irradiance caching may be used to interpolate values from previous calculations.
- To avoid unnecessary collision testing in direct illumination, shadow photons can be used. During the photon mapping process, when a photon strikes a surface, in addition to the usual operations performed, a shadow photon is emitted in the same direction the original photon came from that goes all the way through the object. The next object it collides with causes a shadow photon to be stored in the photon map. Then during the direct illumination calculation, instead of sending out a ray from the surface to the light that tests collisions with objects, the photon map is queried for shadow photons. If none are present, then the object has a clear line of sight to the light source and additional calculations can be avoided.
- To optimize image quality, particularly of caustics, Jensen recommends use of a cone filter. Essentially, the filter gives weight to photons' contributions to radiance depending on how far they are from ray-surface intersections. This can produce sharper images.
- Image space photon mapping achieves real-time performance by computing the first and last scattering using a GPU rasterizer.
Variations
- Although photon mapping was designed to work primarily with ray tracers, it can also be extended for use with scanline renderersScanline renderingScanline 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...
.
External links
- Global Illumination using Photon Maps
- Realistic Image Synthesis Using Photon Mapping ISBN 1-56881-147-0
- Photon mapping introduction from Worcester Polytechnic InstituteWorcester Polytechnic InstituteWorcester Polytechnic Institute is a private university located in Worcester, Massachusetts, in the United States.Founded in 1865 in Worcester, WPI was one of the United States' first engineering and technology universities...
- Bias in Rendering
- Siggraph Paper