Shadow volume is a technique used in
3D computer graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
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. A shadow volume divides the virtual world in two: areas that are in shadow and areas that are not.
The
stencil buffer
A stencil buffer is an extra data buffer, in addition to the ''color buffer'' and ''Z-buffer'', found on modern graphics hardware. The buffer is per pixel and works on integer values, usually with a depth of one byte per pixel. The Z-buffer and ...
implementation of shadow volumes is generally considered among the most practical general purpose real-time shadowing techniques for use on modern 3D graphics hardware. It has been popularized by the
video game
Video games, also known as computer games, are electronic games that involves interaction with a user interface or input device such as a joystick, controller, keyboard, or motion sensing device to generate visual feedback. This fee ...
''
Doom 3
''Doom 3'' is a 2004 survival horror first-person shooter video game developed by id Software and published by Activision. ''Doom 3'' was originally released for Microsoft Windows on August 3, 2004, adapted for Linux later that year, and ported ...
'', and a particular variation of the technique used in this game has become known as
Carmack's Reverse
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. A shadow volume divi ...
.
Shadow volumes have become a popular tool for real-time shadowing, alongside the more venerable
shadow mapping
Shadow mapping or shadowing projection is a process by which shadows 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 b ...
. The main advantage of shadow volumes is that they are accurate to the pixel (though many implementations have a minor self-shadowing problem along the silhouette edge, see ''
construction
Construction is a general term meaning the art and science to form objects, systems, or organizations,"Construction" def. 1.a. 1.b. and 1.c. ''Oxford English Dictionary'' Second Edition on CD-ROM (v. 4.0) Oxford University Press 2009 and com ...
'' below), whereas the accuracy of a shadow map depends on the texture memory allotted to it as well as the angle at which the shadows are cast (at some angles, the accuracy of a shadow map unavoidably suffers). However, the technique requires the creation of shadow geometry, which can be CPU intensive (depending on the implementation). The advantage of shadow mapping is that it is often faster, because shadow volume polygons are often very large in terms of screen space and require a lot of fill time (especially for convex objects), whereas shadow maps do not have this limitation.
Construction
In order to construct a shadow volume, project a ray from the light source through each vertex in the shadow casting object to some point (generally at infinity). These projections will together form a volume; any point inside that volume is in shadow, everything outside is lit by the light.
For a polygonal model, the volume is usually formed by classifying each face in the model as either facing toward the light source or facing away from the light source. The set of all edges that connect a toward-face to an away-face form the ''silhouette'' with respect to the light source. The edges forming the silhouette are extruded away from the light to construct the faces of the shadow volume. This volume must extend over the range of the entire visible scene; often the dimensions of the shadow volume are extended to infinity to accomplish this (see ''
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
'' below.) To form a closed volume, the front and back end of this extrusion must be covered. These coverings are called "caps". Depending on the method used for the shadow volume, the front end may be covered by the object itself, and the rear end may sometimes be omitted (see ''
depth pass
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. A shadow volume divi ...
'' below).
There is also a problem with the shadow where the faces along the silhouette edge are relatively shallow. In this case, the shadow an object casts on itself will be sharp, revealing its polygonal facets, whereas the usual lighting model will have a gradual change in the lighting along the facet. This leaves a rough shadow artifact near the silhouette edge which is difficult to correct. Increasing the polygonal density will minimize the problem, but not eliminate it. If the front of the shadow volume is capped, the entire shadow volume may be offset slightly away from the light to remove any shadow self-intersections within the offset distance of the silhouette edge (this solution is more commonly used in
shadow mapping
Shadow mapping or shadowing projection is a process by which shadows 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 b ...
).
The basic steps for forming a shadow volume are:
# Find all
silhouette edge In computer graphics, a silhouette edge on a 3D body projected onto a 2D plane (display plane) is the collection of points whose outwards ''surface normal is perpendicular to the view vector''. Due to discontinuities in the surface normal, a silhou ...
s (edges which separate front-facing faces from back-facing faces)
# Extend all silhouette edges in the direction away from the light-source
# Add a ''front-cap'' and/or ''back-cap'' to each surface to form a closed volume (may not be necessary, depending on the implementation used)
Stencil buffer implementations
After Crow, in 1991
Tim Heidmann showed how to use the
stencil buffer
A stencil buffer is an extra data buffer, in addition to the ''color buffer'' and ''Z-buffer'', found on modern graphics hardware. The buffer is per pixel and works on integer values, usually with a depth of one byte per pixel. The Z-buffer and ...
to render shadows with shadow volumes quickly enough for use in real time applications. There are three common variations to this technique, depth pass, depth fail, and exclusive-or, but all of them use the same process:
# Render the scene as if it were completely in shadow.
# For each light source:
## Using the depth information from that scene, construct a mask in the stencil buffer that has holes only where the visible surface is not in shadow.
## Render the scene again as if it were completely lit, using the stencil buffer to mask the shadowed areas. Use additive blending to add this render to the scene.
The difference between these three methods occurs in the generation of the mask in the second step. Some involve two passes, and some only one; some require less precision in the stencil buffer.
Shadow volumes tend to cover large portions of the visible scene, and as a result consume valuable rasterization time (fill time) on 3D graphics hardware. This problem is compounded by the complexity of the shadow casting objects, as each object can cast its own shadow volume of any potential size onscreen. See ''
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
'' below for a discussion of techniques used to combat the fill time problem.
Depth pass
Heidmann proposed that if the front surfaces and back surfaces of the shadows were rendered in separate passes, the number of front faces and back faces in front of an object can be counted using the stencil buffer. If an object's surface is in shadow, there will be more front facing shadow surfaces between it and the eye than back facing shadow surfaces. If their numbers are equal, however, the surface of the object is not in shadow. The generation of the stencil mask works as follows:
# Disable writes to the
depth and color buffers.
# Use
back-face culling
In computer graphics, back-face culling determines whether a polygon of a graphical object is drawn. It is a step in the graphical pipeline that tests whether the points in the polygon appear in clockwise or counter-clockwise order when projected ...
.
# Set the stencil operation to increment on depth pass (only count shadows in front of the object).
# Render the shadow volumes (because of culling, only their front faces are rendered).
# Use front-face culling.
# Set the stencil operation to decrement on depth pass.
# Render the shadow volumes (only their back faces are rendered).
After this is accomplished, all lit surfaces will correspond to a 0 in the stencil buffer, where the numbers of front and back surfaces of all shadow volumes between the eye and that surface are equal.
This approach has problems when the eye itself is inside a shadow volume (for example, when the light source moves behind an object). From this point of view, the eye sees the back face of this shadow volume before anything else, and this adds a −1 bias to the entire stencil buffer, effectively inverting the shadows. This can be remedied by adding a "cap" surface to the front of the shadow volume facing the eye, such as at the front
clipping plane
A clipping path (or "deep etch") is a closed vector path, or shape, used to cut out a 2D image in image editing software. Anything inside the path will be included after the clipping path is applied; anything outside the path will be omitted fro ...
. There is another situation where the eye may be in the shadow of a volume cast by an object behind the camera, which also has to be capped somehow to prevent a similar problem. In most common implementations, because properly capping for depth-pass can be difficult to accomplish, the depth-fail method (see below) may be licensed for these special situations. Alternatively one can give the stencil buffer a +1 bias for every shadow volume the camera is inside, though doing the detection can be slow.
There is another potential problem if the stencil buffer does not have enough bits to accommodate the number of shadows visible between the eye and the object surface, because it uses
saturation arithmetic
Saturation arithmetic is a version of arithmetic in which all operations, such as addition and multiplication, are limited to a fixed range between a minimum and maximum value.
If the result of an operation is greater than the maximum, it is set ...
. (If they used
arithmetic overflow
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th cen ...
instead, the problem would be insignificant.)
Depth pass testing is also known as z-pass testing, as the
depth buffer
A depth buffer, also known as a z-buffer, is a type of data buffer used in computer graphics to represent depth information of objects in 3D space from a particular perspective. Depth buffers are an aid to rendering a scene to ensure that the ...
is often referred to as the z-buffer.
Depth fail
Around the year 2000, several people discovered that Heidmann's method can be made to work for all camera positions by reversing the depth. Instead of counting the shadow surfaces in front of the object's surface, the surfaces behind it can be counted just as easily, with the same end result. This solves the problem of the eye being in shadow, since shadow volumes between the eye and the object are not counted, but introduces the condition that the rear end of the shadow volume must be capped, or shadows will end up missing where the volume points backward to infinity.
# Disable writes to the depth and color buffers.
# Use front-face culling.
# Set the stencil operation to increment on depth fail (only count shadows behind the object).
# Render the shadow volumes.
# Use back-face culling.
# Set the stencil operation to decrement on depth fail.
# Render the shadow volumes.
The depth fail method has the same considerations regarding the stencil buffer's precision as the depth pass method. Also, similar to depth pass, it is sometimes referred to as the z-fail method.
William Bilodeau and Michael Songy discovered this technique in October 1998, and presented the technique at Creativity, a Creative Labs developer's conference, in 1999.
Sim Dietrich
Sim or SIM may refer to:
Computing and technology
*SIM card or Subscriber Identity Module, used by mobile telephones
*HP Systems Insight Manager, a system management tool
* Scientific instrument module in the Apollo command and service module
* ...
presented this technique at both
GDC in March 1999, and at Creativity in late 1999. A few months later, William Bilodeau and Michael Songy filed a
US patent application for the technique the same year entitled "Method for rendering shadows using a shadow volume and a stencil buffer".
John Carmack
John D. Carmack II (born August 20, 1970) is an American computer programmer and video game developer. He co-founded the video game company id Software and was the lead programmer of its 1990s games ''Commander Keen'', ''Wolfenstein 3D'', ''Doo ...
of
id Software
id Software LLC () is an American video game developer based in Richardson, Texas. It was founded on February 1, 1991, by four members of the computer company Softdisk: programmers John Carmack and John Romero, game designer Tom Hall, and ar ...
independently discovered the algorithm in 2000 during the development of ''
Doom 3
''Doom 3'' is a 2004 survival horror first-person shooter video game developed by id Software and published by Activision. ''Doom 3'' was originally released for Microsoft Windows on August 3, 2004, adapted for Linux later that year, and ported ...
''.
Exclusive-or
Either of the above types may be approximated with an
exclusive-or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
variation, which does not deal properly with intersecting shadow volumes, but saves one rendering pass (if not fill time), and only requires a 1-bit stencil buffer. The following steps are for the depth pass version:
# Disable writes to the depth and color buffers.
# Set the stencil operation to XOR on depth pass (flip on any shadow surface).
# Render the shadow volumes.
Optimization
* One method of speeding up the shadow volume geometry calculations is to utilize existing parts of the rendering pipeline to do some of the calculation. For instance, by using
homogeneous coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
, the ''w''-coordinate may be set to zero to extend a point to infinity. This should be accompanied by a
viewing frustum
In 3D computer graphics, the view frustum (also called viewing frustum) is the region of space in the modeled world that may appear on the screen; it is the field of view of a perspective virtual camera system.
The view frustum is typically ...
that has a far clipping plane that extends to infinity in order to accommodate those points, accomplished by using a specialized projection matrix. This technique reduces the accuracy of the depth buffer slightly, but the difference is usually negligible. See 2002 pape
"Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering" C. Everitt and
M. Kilgard, for a detailed implementation.
* Rasterization time of the shadow volumes can be reduced by using an in-hardware scissor test to limit the shadows to a specific onscreen rectangle.
*
NVIDIA
Nvidia CorporationOfficially written as NVIDIA and stylized in its logo as VIDIA with the lowercase "n" the same height as the uppercase "VIDIA"; formerly stylized as VIDIA with a large italicized lowercase "n" on products from the mid 1990s to ...
has implemented a hardware capability called th
''depth bounds test''that is designed to remove parts of shadow volumes that do not affect the visible scene. (This has been available since the
GeForce
GeForce is a brand of graphics processing units (GPUs) designed by Nvidia. As of the GeForce 40 series, there have been eighteen iterations of the design. The first GeForce products were discrete GPUs designed for add-on graphics boards, inten ...
FX 5900 model.) A discussion of this capability and its use with shadow volumes was presented at the
Game Developers Conference
The Game Developers Conference (GDC) is an annual conference for video game developers. The event includes an expo, networking events, and awards shows like the Game Developers Choice Awards and Independent Games Festival, and a variety of tutori ...
in 2005.
* Since the depth-fail method only offers an advantage over depth-pass in the special case where the eye is within a shadow volume, it is preferable to check for this case, and use depth-pass wherever possible. This avoids both the unnecessary back-capping (and the associated rasterization) for cases where depth-fail is unnecessary, as well as the problem of appropriately front-capping for special cases of depth-pass.
* On more recent GPU pipelines,
geometry shader
In computer graphics, a shader is a computer program that calculates the appropriate levels of light, darkness, and color during the rendering of a 3D scene - a process known as ''shading''. Shaders have evolved to perform a variety of speci ...
s can be used to generate the shadow volumes.
* On systems that do not support geometry shaders,
vertex shaders
In computer graphics, a shader is a computer program that calculates the appropriate levels of light, darkness, and color during the rendering of a 3D scene - a process known as ''shading''. Shaders have evolved to perform a variety of speci ...
can also be used to create shadow volumes by selectively extruding vertices that already reside within GPU memory.
See also
*
Silhouette edge In computer graphics, a silhouette edge on a 3D body projected onto a 2D plane (display plane) is the collection of points whose outwards ''surface normal is perpendicular to the view vector''. Due to discontinuities in the surface normal, a silhou ...
*
Shadow mapping
Shadow mapping or shadowing projection is a process by which shadows 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 b ...
, an alternative shadowing algorithm
*
Stencil buffer
A stencil buffer is an extra data buffer, in addition to the ''color buffer'' and ''Z-buffer'', found on modern graphics hardware. The buffer is per pixel and works on integer values, usually with a depth of one byte per pixel. The Z-buffer and ...
*
Depth buffer
A depth buffer, also known as a z-buffer, is a type of data buffer used in computer graphics to represent depth information of objects in 3D space from a particular perspective. Depth buffers are an aid to rendering a scene to ensure that the ...
*
List of software patents
This is a list of software patents, which contains notable patents and patent applications involving computer programs (also known as a software patent). Software patents cover a wide range of topics and there is therefore important debate about ...
References
External links
The Theory of Stencil Shadow VolumesThe Mechanics of Robust Stencil ShadowsAn Introduction to Stencil Shadow VolumesShadow Mapping and Shadow VolumesStenciled Shadow Volumes in OpenGLVolume shadow tutorialat NVIDIA
at NVIDIA
Advanced Stencil Shadow and Penumbral Wedge RenderingRealistic Soft Shadows by Penumbra-Wedges BlendingSoft Textured Shadow VolumeCorrect Z-Pass Stencil Shadow Volumes
Regarding depth-fail patents
*
*
*
{{DEFAULTSORT:Shadow Volume
Shading