Shadow mapping
Encyclopedia
Shadow mapping or projective shadowing is a process by which shadow
s are added to 3D computer graphics
. This concept was introduced by Lance Williams
in 1978, in a paper entitled "Casting curved shadows on curved surfaces". Since then, it has been used both in pre-rendered scenes and realtime scenes in many console and PC games.
Shadows are created by testing whether a pixel
is visible from the light source, by comparing it to a z-buffer
or depth image of the light source's view, stored in the form of a texture
.
This technique is less accurate than shadow volume
s, but the shadow map can be a faster alternative depending on how much fill time is required for either technique in a particular application and therefore may be more suitable to real time applications. In addition, shadow maps do not require the use of an additional stencil buffer
, and can be modified to produce shadows with a soft edge. Unlike shadow volumes, however, the accuracy of a shadow map is limited by its resolution.
), an orthographic projection
should be used.
From this rendering, the depth buffer is extracted and saved. Because only the depth information is relevant, it is usual to avoid updating the color buffers and disable all lighting and texture calculations for this rendering, in order to save drawing time. This depth map
is often stored as a texture in graphics memory.
This depth map must be updated any time there are changes to either the light or the objects in the scene, but can be reused in other situations, such as those where only the viewing camera moves. (If there are multiple lights, a separate depth map must be used for each light.)
In many implementations it is practical to render only a subset of the objects in the scene to the shadow map in order to save some of the time it takes to redraw the map. Also, a depth offset which shifts the objects away from the light may be applied to the shadow map rendering in an attempt to resolve stitching
problems where the depth map value is close to the depth of a surface being drawn (i.e., the shadow casting surface) in the next step. Alternatively, culling front faces and only rendering the back of objects to the shadow map is sometimes used for a similar result.
. The location of the object on the screen is determined by the usual coordinate transformation, but a second set of coordinates must be generated to locate the object in light space.
The matrix used to transform the world coordinates into the light's viewing coordinates is the same as the one used to render the shadow map in the first step (under OpenGL
this is the product of the modelview and projection matrices). This will produce a set of homogeneous coordinates
that need a perspective division (see 3D projection
) to become normalized device coordinates, in which each component (x, y, or z) falls between −1 and 1 (if it is visible from the light view). Many implementations (such as OpenGL and Direct3D
) require an additional scale and bias matrix multiplication to map those −1 to 1 values to 0 to 1, which are more usual coordinates for depth map (texture map) lookup. This scaling can be done before the perspective division, and is easily folded into the previous transformation calculation by multiplying that matrix with the following:
If done with a shader
, or other graphics hardware extension, this transformation is usually applied at the vertex level, and the generated value is interpolated between other vertices, and passed to the fragment level.
If the z value is greater than the value stored in the depth map at the appropriate (x,y) location, the object is considered to be behind an occluding object, and should be marked as a failure, to be drawn in shadow by the drawing process. Otherwise it should be drawn lit.
If the (x,y) location falls outside the depth map, the programmer must either decide that the surface should be lit or shadowed by default (usually lit).
In a shader
implementation, this test would be done at the fragment level. Also, care needs to be taken when selecting the type of texture map storage to be used by the hardware: if interpolation cannot be done, the shadow will appear to have a sharp jagged edge (an effect that can be reduced with greater shadow map resolution).
It is possible to modify the depth map test to produce shadows with a soft edge by using a range of values (based on the proximity to the edge of the shadow) rather than simply pass or fail.
The shadow mapping technique can also be modified to draw a texture onto the lit regions, simulating the effect of a projector
. The picture above, captioned "visualization of the depth map projected onto the scene" is an example of such a process.
s are available, the depth map test may be performed by a fragment shader which simply draws the object in shadow or lighted depending on the result, drawing the scene in a single pass (after an initial earlier pass to generate the shadow map).
If shaders are not available, performing the depth map test must usually be implemented by some hardware extension (such as GL_ARB_shadow), which usually do not allow a choice between two lighting models (lighted and shadowed), and necessitate more rendering passes:
The example pictures in this article used the OpenGL
extension GL_ARB_shadow_ambient to accomplish the shadow map process in two passes.
or shadow continuity glitches. A simple way to overcome this limitation is to increase the shadow map size, but due to memory, computational or hardware constraints, it is not always possible. Commonly used techniques for real-time shadow mapping have been developed to circumvent this limitation. These include Cascaded Shadow Maps, Trapezoidal Shadow Maps, Light Space Perspective Shadow maps, or Parallel-Split Shadow maps.
Also notable is that generated shadows, even if aliasing
free, have hard edges, which is not always desirable. In order to emulate real world soft shadows, several solutions have been developed, either by doing several lookups on the shadow map, generating geometry meant to emulate the soft edge or creating non standard depth shadow maps. Notable examples of these are Percentage Closer Filtering, Smoothies, and Variance Shadow maps.
Shadow
A shadow is an area where direct light from a light source cannot reach due to obstruction by an object. It occupies all of the space behind an opaque object with light in front of it. The cross section of a shadow is a two-dimensional silhouette, or reverse projection of the object blocking the...
s are added to 3D computer graphics
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
. This concept was introduced by Lance Williams
Lance Williams
Lance J. Williams is a prominent graphics researcher who made major contributions to texture map prefiltering, shadow rendering algorithms, facial animation, and antialiasing techniques...
in 1978, in a paper entitled "Casting curved shadows on curved surfaces". Since then, it has been used both in pre-rendered scenes and realtime scenes in many console and PC games.
Shadows are created by testing whether a 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....
is visible from the light source, by comparing it to a z-buffer
Z-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
or depth image of the light source's view, stored in the form of a texture
Texture mapping
Texture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
.
Principle of a shadow and a shadow map
If you looked out from a source of light, all of the objects you can see would appear in light. Anything behind those objects, however, would be in shadow. This is the basic principle used to create a shadow map. The light's view is rendered, storing the depth of every surface it sees (the shadow map). Next, the regular scene is rendered comparing the depth of every point drawn (as if it were being seen by the light, rather than the eye) to this depth map.This technique is less accurate than shadow volume
Shadow volume
Shadow volume is a technique used in 3D computer graphics to add shadows to a rendered scene. They were first proposed by Frank Crow in 1977 as the geometry describing the 3D shape of the region occluded from a light source...
s, but the shadow map can be a faster alternative depending on how much fill time is required for either technique in a particular application and therefore may be more suitable to real time applications. In addition, shadow maps do not require the use of an additional stencil buffer
Stencil buffer
A stencil buffer is an extra buffer, in addition to the color buffer and depth buffer found on modern computer graphics hardware. The buffer is per pixel, and works on integer values, usually with a depth of one byte per pixel...
, and can be modified to produce shadows with a soft edge. Unlike shadow volumes, however, the accuracy of a shadow map is limited by its resolution.
Algorithm overview
Rendering a shadowed scene involves two major drawing steps. The first produces the shadow map itself, and the second applies it to the scene. Depending on the implementation (and number of lights), this may require two or more drawing passes.Creating the shadow map
The first step renders the scene from the light's point of view. For a point light source, the view should be a perspective projection as wide as its desired angle of effect (it will be a sort of square spotlight). For directional light (e.g., that from the SunSun
The Sun is the star at the center of the Solar System. It is almost perfectly spherical and consists of hot plasma interwoven with magnetic fields...
), an orthographic projection
Orthographic projection
Orthographic projection is a means of representing a three-dimensional object in two dimensions. It is a form of parallel projection, where all the projection lines are orthogonal to the projection plane, resulting in every plane of the scene appearing in affine transformation on the viewing surface...
should be used.
From this rendering, the depth buffer is extracted and saved. Because only the depth information is relevant, it is usual to avoid updating the color buffers and disable all lighting and texture calculations for this rendering, in order to save drawing time. This depth map
Depth map
In 3D computer graphics a depth map is an image or image channel that contains information relating to the distance of the surfaces of scene objects from a viewpoint. The term is related to and may be analogous to depth buffer, Z-buffer, Z-buffering and Z-depth...
is often stored as a texture in graphics memory.
This depth map must be updated any time there are changes to either the light or the objects in the scene, but can be reused in other situations, such as those where only the viewing camera moves. (If there are multiple lights, a separate depth map must be used for each light.)
In many implementations it is practical to render only a subset of the objects in the scene to the shadow map in order to save some of the time it takes to redraw the map. Also, a depth offset which shifts the objects away from the light may be applied to the shadow map rendering in an attempt to resolve stitching
Z-fighting
Z-fighting is a phenomenon in 3D rendering that occurs when two or more primitives have similar values in the z-buffer. It is particularly prevalent with coplanar polygons, where two faces occupy essentially the same space, with neither in front...
problems where the depth map value is close to the depth of a surface being drawn (i.e., the shadow casting surface) in the next step. Alternatively, culling front faces and only rendering the back of objects to the shadow map is sometimes used for a similar result.
Shading the scene
The second step is to draw the scene from the usual camera viewpoint, applying the shadow map. This process has three major components, the first is to find the coordinates of the object as seen from the light, the second is the test which compares that coordinate against the depth map, and finally, once accomplished, the object must be drawn either in shadow or in light.Light space coordinates
In order to test a point against the depth map, its position in the scene coordinates must be transformed into the equivalent position as seen by the light. This is accomplished by a matrix multiplicationMatrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
. The location of the object on the screen is determined by the usual coordinate transformation, but a second set of coordinates must be generated to locate the object in light space.
The matrix used to transform the world coordinates into the light's viewing coordinates is the same as the one used to render the shadow map in the first step (under OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
this is the product of the modelview and projection matrices). This will produce a set of homogeneous coordinates
Homogeneous coordinates
In mathematics, homogeneous coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcül, are a system of coordinates used in projective geometry much as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points,...
that need a perspective division (see 3D projection
3D projection
3D projection is any method of mapping three-dimensional points to a two-dimensional plane. As most current methods for displaying graphical data are based on planar two-dimensional media, the use of this type of projection is widespread, especially in computer graphics, engineering and drafting.-...
) to become normalized device coordinates, in which each component (x, y, or z) falls between −1 and 1 (if it is visible from the light view). Many implementations (such as OpenGL and Direct3D
Direct3D
Direct3D is part of Microsoft's DirectX application programming interface . Direct3D is available for Microsoft Windows operating systems , and for other platforms through the open source software Wine. It is the base for the graphics API on the Xbox and Xbox 360 console systems...
) require an additional scale and bias matrix multiplication to map those −1 to 1 values to 0 to 1, which are more usual coordinates for depth map (texture map) lookup. This scaling can be done before the perspective division, and is easily folded into the previous transformation calculation by multiplying that matrix with the following:
If done with a shader
Shader
In the field of computer graphics, a shader is a computer program that is used primarily to calculate rendering effects on graphics hardware with a high degree of flexibility...
, or other graphics hardware extension, this transformation is usually applied at the vertex level, and the generated value is interpolated between other vertices, and passed to the fragment level.
Depth map test
Once the light-space coordinates are found, the x and y values usually correspond to a location in the depth map texture, and the z value corresponds to its associated depth, which can now be tested against the depth map.If the z value is greater than the value stored in the depth map at the appropriate (x,y) location, the object is considered to be behind an occluding object, and should be marked as a failure, to be drawn in shadow by the drawing process. Otherwise it should be drawn lit.
If the (x,y) location falls outside the depth map, the programmer must either decide that the surface should be lit or shadowed by default (usually lit).
In a shader
Shader
In the field of computer graphics, a shader is a computer program that is used primarily to calculate rendering effects on graphics hardware with a high degree of flexibility...
implementation, this test would be done at the fragment level. Also, care needs to be taken when selecting the type of texture map storage to be used by the hardware: if interpolation cannot be done, the shadow will appear to have a sharp jagged edge (an effect that can be reduced with greater shadow map resolution).
It is possible to modify the depth map test to produce shadows with a soft edge by using a range of values (based on the proximity to the edge of the shadow) rather than simply pass or fail.
The shadow mapping technique can also be modified to draw a texture onto the lit regions, simulating the effect of a projector
Video projector
A video projector is an image projector that receives a video signal and projects the corresponding image on a projection screen using a lens system. All video projectors use a very bright light to project the image, and most modern ones can correct any curves, blurriness, and other...
. The picture above, captioned "visualization of the depth map projected onto the scene" is an example of such a process.
Drawing the scene
Drawing the scene with shadows can be done in several different ways. If programmable shaderShader
In the field of computer graphics, a shader is a computer program that is used primarily to calculate rendering effects on graphics hardware with a high degree of flexibility...
s are available, the depth map test may be performed by a fragment shader which simply draws the object in shadow or lighted depending on the result, drawing the scene in a single pass (after an initial earlier pass to generate the shadow map).
If shaders are not available, performing the depth map test must usually be implemented by some hardware extension (such as GL_ARB_shadow), which usually do not allow a choice between two lighting models (lighted and shadowed), and necessitate more rendering passes:
- Render the entire scene in shadow. For the most common lighting models (see Phong reflection modelPhong reflection modelThe Phong reflection model is an empirical model of the local illumination of points on a surface...
) this should technically be done using only the ambient component of the light, but this is usually adjusted to also include a dim diffuse light to prevent curved surfaces from appearing flat in shadow. - Enable the depth map test, and render the scene lit. Areas where the depth map test fails will not be overwritten, and remain shadowed.
- An additional pass may be used for each additional light, using additive blending to combine their effect with the lights already drawn. (Each of these passes requires an additional previous pass to generate the associated shadow map.)
The example pictures in this article used the OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
extension GL_ARB_shadow_ambient to accomplish the shadow map process in two passes.
Shadow map real-time implementations
One of the key disadvantages of real time shadow mapping is that the size and depth of the shadow map determines the quality of the final shadows. This is usually visible as aliasingAliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
or shadow continuity glitches. A simple way to overcome this limitation is to increase the shadow map size, but due to memory, computational or hardware constraints, it is not always possible. Commonly used techniques for real-time shadow mapping have been developed to circumvent this limitation. These include Cascaded Shadow Maps, Trapezoidal Shadow Maps, Light Space Perspective Shadow maps, or Parallel-Split Shadow maps.
Also notable is that generated shadows, even if aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
free, have hard edges, which is not always desirable. In order to emulate real world soft shadows, several solutions have been developed, either by doing several lookups on the shadow map, generating geometry meant to emulate the soft edge or creating non standard depth shadow maps. Notable examples of these are Percentage Closer Filtering, Smoothies, and Variance Shadow maps.
Splitting
- PSSM "Parallel Split" http://http.developer.nvidia.com/GPUGems3/gpugems3_ch10.html
- CSM "Cascaded" http://developer.download.nvidia.com/SDK/10.5/opengl/src/cascaded_shadow_maps/doc/cascaded_shadow_maps.pdf
Warping
- LiSPSM "Light Space Perspective" http://www.cg.tuwien.ac.at/~scherzer/files/papers/LispSM_survey.pdf
- TSM "Trapezoid" http://www.comp.nus.edu.sg/~tants/tsm.html
- PSM "Perspective" http://www-sop.inria.fr/reves/Marc.Stamminger/psm/
Smoothing
- PCF "Percentage Closer Filtering" http://http.developer.nvidia.com/GPUGems/gpugems_ch11.html
Filtering
- ESM "Exponential" http://www.thomasannen.com/pub/gi2008esm.pdf
- CSM "Convolution" http://research.edm.uhasselt.be/~tmertens/slides/csm.ppt
- VSM "Variance" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.2569&rep=rep1&type=pdf
- SAVSM "Summed Area Variance" http://http.developer.nvidia.com/GPUGems3/gpugems3_ch08.html
Soft Shadows
- PCSS "Percentage Closer" http://developer.download.nvidia.com/shaderlibrary/docs/shadow_PCSS.pdf
Assorted
- ASM "Adaptive" http://www.cs.cornell.edu/~kb/publications/ASM.pdf
- AVSM "Adaptive Volumetric" http://visual-computing.intel-research.net/art/publications/avsm/
- CSSM "Camera Space" http://free-zg.t-com.hr/cssm/
- DASM "Deep Adaptive"
- DPSM "Dual Paraboloid" http://sites.google.com/site/osmanbrian2/dpsm.pdf
- DSM "Deep" http://graphics.pixar.com/library/DeepShadows/paper.pdf
- FSM "Forward" http://www.cs.unc.edu/~zhangh/technotes/shadow/shadow.ps
- LPSM "Logarithmic" http://gamma.cs.unc.edu/LOGSM/
- MDSM "Multiple Depth" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.3376&rep=rep1&type=pdf
- RMSM "Resolution Matched" http://www.idav.ucdavis.edu/func/return_pdf?pub_id=919
- SDSM "Sample Distribution" http://visual-computing.intel-research.net/art/publications/sdsm/
- SPPSM "Separating Plane Perspective" http://jgt.akpeters.com/papers/Mikkelsen07/sep_math.pdf
- SSSM "Shadow Silhouette" http://graphics.stanford.edu/papers/silmap/silmap.pdf
See also
- Shadow volumeShadow volumeShadow volume is a technique used in 3D computer graphics to add shadows to a rendered scene. They were first proposed by Frank Crow in 1977 as the geometry describing the 3D shape of the region occluded from a light source...
, another shadowing technique - Ray castingRay castingRay casting is the use of ray-surface intersection tests to solve a variety of problems in computer graphics. It enables spatial selections of objects in ascene by providing users a virtual beam as a visual cue extending...
, a slower technique often used in ray tracing - Photon mappingPhoton mappingIn 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...
, a much slower technique capable of very realistic lighting - Radiosity, another very slow but very realistic technique
Further reading
- Smooth Penumbra Transitions with Shadow Maps Willem H. de Boer
- Forward shadow mapping does the shadow test in eye-space rather than light-space to keep texture access more sequential.
- Shadow mapping techniques An overview of different shadow mapping techniques
External links
- Hardware Shadow Mapping, nVidiaNVIDIANvidia 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...
- Shadow Mapping with Today's OpenGL Hardware, nVidia
- Riemer's step-by-step tutorial implementing Shadow Mapping with HLSL and DirectX
- NVIDIA Real-time Shadow Algorithms and Techniques
- Shadow Mapping implementation using Java and OpenGL