|
|
|
|
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, dec
|
