Editing Shadow volume (section)

== Stencil buffer implementations ==

After Crow, in 1991 [[Tim Heidmann]] showed how to use the [[stencil buffer]] 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 ''[[Shadow volume#Optimization|optimization]]'' 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 [[Z-buffering|depth]] and color buffers.
# Use [[back-face culling]].
# 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).

According to [[Euler characteristic]], all lit surfaces will correspond to a 0 in the stencil buffer, where the numbers of front and back surfaces of all closed manifolds (shadow volumes) 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]]. 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]]. (If they used [[arithmetic overflow]] instead, the problem would be insignificant.)

Depth pass testing is also known as '''z-pass''' testing, as the [[depth buffer]] 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.<ref>{{cite web|last=Yen |first=Hun |url=http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/the-theory-of-stencil-shadow-volumes-r1873 |title=The Theory of Stencil Shadow Volumes |publisher=GameDev.net |date=2002-12-03 |accessdate=2010-09-12}}</ref> [[Sim Dietrich]] presented this technique at both [[Game Developers Conference|GDC]] in March 1999, and at Creativity in late 1999.<ref>{{cite web|url=http://www.gamedev.net/topic/181647-stencil-shadows-patented--wtf/ |title=Stencil Shadows Patented!? WTF! - GameDev.net |date=2004-07-29 |accessdate=2012-03-28}}</ref><ref>{{cite web|url=http://techreport.com/discussions.x/7113 |title=Creative patents Carmack's reverse |publisher=The Tech Report |date=2004-07-29 |archive-url=https://web.archive.org/web/20100131044756/http://techreport.com/discussions.x/7113 |accessdate=2010-09-12|archive-date=2010-01-31 }}</ref> A few months later, William Bilodeau and Michael Songy filed a [[software patent|US patent application]] for the technique the same year entitled "Method for rendering shadows using a shadow volume and a stencil buffer".<ref>{{Cite patent|country=US|number=6384822|pubdate=2002-05-07|title=Method for rendering shadows using a shadow volume and a stencil buffer|assign1=[[Creative Technology Ltd.]]|inventor1-last=Bilodeau|inventor1-first=William|inventor2-last=Songy|inventor2-first=Michael}}</ref> [[John D. Carmack|John Carmack]] of [[id Software]] independently discovered the algorithm in 2000 during the development of ''[[Doom 3]]''.<ref>{{cite web|last=Kilgard |first=Mark |title=John Carmack on shadow volumes... |url=http://developer.nvidia.com/attach/6832 |work=Practical and Robust Shadow Volumes page of NVIDIA Developer Zone |publisher=NVIDIA |accessdate=18 October 2012 |author2=John Carmack |archiveurl=https://web.archive.org/web/20090127020935/http://developer.nvidia.com/attach/6832 |archivedate=January 27, 2009 |location=archive.org }}</ref>

=== Exclusive-or ===
Either of the above types may be approximated with an [[Exclusive disjunction|exclusive-or]] 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.