---
created_at: '2014-12-02T04:23:40.000Z'
title: John Carmack on shadow volumes (2000)
url: http://fabiensanglard.net/doom3_documentation/CarmackOnShadowVolumes.txt
author: p7g5
points: 102
story_text: ''
comment_text: 
num_comments: 40
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1417494220
_tags:
- story
- author_p7g5
- story_8685701
objectID: '8685701'

---
[Source](http://fabiensanglard.net/doom3_documentation/CarmackOnShadowVolumes.txt "Permalink to ")

John Carmack on shadow volumes... I recieved this in email from John on May 23rd, 2000. \- Mark Kilgard I solved this in a way that is so elegant you just won't believe it. Here is a description that I posted to a private mailing list: \---------------------------------------------------------- I first implemented stencil shadow volumes over two years ago in the post-Q2 research period. They looked great until you flew the viewpoint into one of the volumes, and depending on the exact test you used, either most of the screen went into negative shadow, or most of the shadows disappeared. The classic shadow volume works that stencil shadows are derived from usually suggest "inverting the test when the view is inside a shadow volume". That is not a robust solution, because a non-zero near clip plane will give situations where the plane is not cleanly on one side or the other of the view point. It is also non-trivial to make the "inside a shadow volume" determination, especially after silhouette optimizations. The conventional wisdom has been that you will need to clip the shadow volumes to the view plane and cap with triangles, treating the shadow volumes as if they were polyhedrons. I implemented the easy cases of this, choosing to project the silhouette points to either the far plane of the light's effect or the view plane. For the clear-cut cases, this worked fine, allowing you to walk in front of a shadowed object, or look directly at it with the light behind it. Intermediate cases, where some of the vertexes should project onto the light plane and some should project onto the view plane could also be handled, but the cost of all the testing was starting to pile up. Unfortunately, there are cases when an occluding triangle projects a shadow volume that will clip to something other than a triangular prism. There are cases where real, honest volume clipping must take place. Anything that requires finding convex hulls in realtime is starting to sound like a Bad Idea. I sweated over this for a while, with the code getting grosser and grosser, but then I had an idea for a different direction. It should be possible to let the shadow volumes get clipped off at the view plane like they always do, then find the clipped off areas in image space and correct them. The way to find if a volume has been clipped off is to render the shadow volume with depth testing disabled, incrementing for the front faces and decrementing for the back faces. If the stencil buffer ends up with the original value, the shadow volume is well formed in front of the view volume. My first attempt to utilize this involved a whole bunch of passes to determine if it was well formed and combine it with the standard volume stencil operations. It was an interesting experiment with masking and anding in the stencil buffer to perform two operations, but it turned out that, while it worked for simple shapes, complex shapes needed more information from the volume clipping than just "well formed" or not. The next iteration involved attempting to "preload" the standard stencil shadow algorithm by the number of clipped away planes. I first drew the shadow volumes with depth test disabled, incrementing for back sides and decrementing for front sides. This finishes with a positive value in the stencil buffer for each plane that is clipped away at the view plane. The normal depth tested shadow volume is drawn next, with the change polarity reversed, decrementing for back sides and incrementing for front sides. The areas not equal to the initial clear value are in shadow. That works all the time. Later, I realized something else. The algorithm was now basically: Draw back sides, incrementing both with depth pass and depth fail. Draw front sides, decrementing both with depth pass and depth fail. Draw back sides, decrementing with depth pass and doing nothing with depth fail. Draw front sides, incrementing both with depth and doing nothing with depth fail. Rearrange the passes and you get: Draw back sides, incrementing both with depth pass and depth fail. Draw back sides, decrementing with depth pass and doing nothing with depth fail. Draw front sides, decrementing both with depth pass and depth fail. Draw front sides, incrementing both with depth and doing nothing with depth fail. It is then obvious that they partially cancel each out and can be combined into: Draw back sides, doing nothing with depth pass and incrementing with depth fail. Draw front sides, doing nothing with depth pass and decrementing with depth fail. I was shocked. I went from feeling pretty clever with my unbalanced preloading algorithm (which I would only apply on surfaces that were likely to intersect the view plane) to just feeling dumb that I had never seen the trivial solution before. Thinking about operating on depth test fails is a bit non-intuitive, but if you work it through a couple times, what is going on makes pretty good sense. Shadows done this way have none of the "fragile" feel that geometric algorithms tend to give. You can use them for major occluders in the world and noclip fly right through them without any problems at all. Stencil shadows still aren't cheap by any means. It can cost 3x the triangle count of the source model (although <2x with some optimizations is reasonable) per shadowing light, and it can have pathological fill rate utilization in some cases, like a light shining out horizontally through a jail cell door. Still, they are quick operations even if there are a lot of them. The vertexes are just bare xyz points without texcoords or color, and the fill rate is only to the depth/stencil buffer. There are lots of subtleties to actually using this, like making sure your shadow volumes are capped on both ends if they need to be (you can often optimize away the caps based on culling information), making sure that none of the shadow volumes get clipped off by your far clipping plane (which would unbalance the count), and all the normal picky silhouette optimization issues. Depth buffer based shadows still sound like they have a lot of advantages: Not much in the way of coding subtleties required. The performance is more level (fixed fill rate overhead) and theoretically somewhat faster (only one extra drawing of the surface into the shadow buffer) in most cases. They avoid the silhouette finding work that still needs to be done with the shadow volumes (a per-face dot product and some copying), and don't require any connectivity information. Unfortunately, the quality just isn't good enough unless you use extremely high resolution shadow maps (or possibly many offset passes with a lower resolution map, although the bias issues become complex), and you need to tweak the biases and ranges in many scenes. For comparison, Pixar will commonly use 2k or 4k shadow maps, focused in on a very narrow field of view (they assume projections outside the map are NOT in shadow, which works for movie sets but not for architectural walkthroughs), along with 16 jittered samples of the shadow map for each pixel and occasional hand tweaking of the bias. I still want to research the options for cropping and skewing shadow depth buffer projection planes, but I am now positive that the stencil shadow architecture works out. John Carmack 

