This is pretty interesting to read, but does anyone have any good links that describe what shadow volumes are and why this solution was clever at the time? Is it still clever, or has some new method taken its place?
It's very clever, and leads to pixel-perfect shadows. the other main technique used to do real time shadows, shadow mapping, writes them to a buffer, so if you have a larger buffer you get better shadows, and with a smaller buffer you get worse, more aliased shadows (there are techniques to make this harder to notice, though).
Shadow volumes is also typically slower, and puts (more) restrictions on your geometry than shadow mapping, so my experience is that most engines use shadow mapping.
Though, I think I remember one of the rendering engineers saying that shadow volumes is much easier to implement for small engines, and that he's disappointed it isn't more widely used, but I might just be thinking of some other less robust method of stencil-buffer shadowing.
Searching shadow mapping and shadow volumes in Google looks like it leads to good links if you're interested in learning more.
Shadow maps are faster and compounding shadows is much easier. What you do is render the subset of the scene that you want casting shadows from the point of view of each light source that you want casting shadows, and then render the entire scene once for each light, using the shadow map to kill fragments that aren't illuminated. Back in the late 90's and 2000, you could potentially have one, maybe two shadow maps. The downside is resolution, but you can play tricks with the projection matrix to bias the pixellation artifacts into more distant areas.
Pre-computed shadow volumes were awesome for static lights, where you didn't have to pay the geometry compute overhead every frame, and shadow maps were awesome for things like flashlights and moving lights, since they allowed moving the shadow compute complexity to the GPU. When the Riva TNT2 came out, and you could multi-texture, shadow map performance doubled.
Lighting is hard! If you have 2 shadow-map shadow casters, and one shadow volume, you're rendering the scene at least 5 times and the shadow volume twice, using the geometry processor to kill front or back sides from the point of view (can't pre-compute this).
(I've been working on this stuff since the 90's. SGI was doing this stuff years before games, but it just wasn't well known because nobody could afford those damn things, it took cheap 3D commodity hardware to make this work really fun, well, minus the whole thing about it sucking to work in the games industry.)
Raytraced shadows are starting to become feasible.
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.[2] Sim Dietrich presented this technique at both GDC in March 1999, and at Creativity in late 1999.[3][4] A few months later, William Bilodeau and Michael Songy filed a US patent application for the technique the same year, US 6384822 , entitled "Method for rendering shadows using a shadow volume and a stencil buffer" issued in 2002. John Carmack of id Software independently discovered the algorithm in 2000 during the development of Doom 3.[5] Since he advertised the technique to the larger public, it is often referred to as Carmack's Reverse.
Math was excluded, as was computer code as a specific usage of mathematical logic.
But slowly patents on computer code made its way into patents, initially as code controlling mechanical or chemical processes.
Looks like some sort of volumetric ray marching approach acceleratred by a signed distance field. Does anyone know what it is?
Also small nitpick: you don't filter the shadow map, but the resulting shadow response.
Secondly, this ray can be extended in any direction; it doesn't matter.
In the shadow volume rendering algorithm, they were originally casting that ray from the visible point on an object (corresponding to a pixel) back toward the eye. Carmack realized that you can cast it away from the eye. But that ray can obviously go in any direction. The eye has nothing to do with whether the point is in a shadow. Of course the algorithm breaks sometimes if the ray is cast toward the eye, and stops at the eye, since it hasn't gone to infinity. So if the eye is in shadow, then the ray has failed to emerge from that shadow, and count that.
I suspect that a much cleaner solution would be to cast the ray toward the light source! Then we only have to consider the silhouette polygons/surfaces, basically: the light-source-side "caps" of the shadow volume. We don't even need the shadow volume as such; we don't need the sides (because they are parallel to any ray we cast toward the light source) and we don't need any caps on it on the opposite side, away from the light source.
The down side, however, is that casting rays not in the eye direction means considering objects that are not in the visible scene. Your database of objects for the frame has to include anything that can potentially be between the light source and the visible point. The beauty of the shadow volumes algorithm is that it can work with viewport-clipped data. (And that is why you want to cast that shadow volume intersecting ray away from the eye: because stuff behind the eye is clippped!)
Another way to do this is to count the area from a point (sum of dot products of consecutive shape vertices). If its positive - inside. If its negative - outside?
These approaches require traversing the whole shape though, whereas the ray-intersecting approach works with clipped pieces (that are not necessarily even connected to form a complete shape). You don't even know which pieces belong to which volumes, necessarily.
Imagine a ray coming out from your eye, if that ray first hits a shadow volume and then an object then that point of that object is inside shadow. If ray never hits the volume or passes through volume