6 ms·

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 i

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?

ginko 12y ago
Shadow mapping[1] has pretty much taken over at this point. This is mainly because of the high overdraw when rendering shadow volumes. You can also filter shadow maps to get soft shadows. This is not really possible with shadow volumes. Raytraced shadows are starting to become feasible. [1]http://en.wikipedia.org/wiki/Shadow_mapping http://en.wikipedia.org/wiki/Shadow_mapping
- codezero 12y ago
  Cool, thanks a bunch for that info.
- kleiba 12y ago
  Let's not forget that he was not the first to come up with this technique. From wikipedia [1]: 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. [1] http://en.wikipedia.org/wiki/Shadow_volume http://en.wikipedia.org/wiki/Shadow_volume
  - digi_owl 12y ago
    Ah, i initially heard about this as a fix for z-fighting.
  - renox 12y ago
    <Sigh>, so many things are independently discovered.. Why do we still have patents??
    - digi_owl 12y ago
      Patents were originally on the specific mechanical system (like the Colt revolver) or chemical composition. 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.
  - kybernetikos 12y ago
    According to an earlier comment, iD used this technique in Doom3. Would Carmack have had to pay patent license fees?
- mirsadm 12y ago
  From my memory the only games which ended up using shadow volumes were Doom 3 and games based on the Doom 3 engine. Shadow maps always seemed like the way forward to me. That is purely based on my own "what looks better" scale. Given that most techniques in 3D programming are hacks to make things look better, I was surprised to see Carmack go down the shadow volumes path. It felt like he'd chosen it based on having nicer code versus an overall nicer looking game. This is all my opinion of course.
  - jgh 12y ago
    I find shadow volumes tend to look better, at least cleaner anyway. Shadow mapping if not properly done can look glitchy and aliased. One surprisingly bad offender was Skyrim.
  - theandrewbailey 12y ago
    I recall seeing both shadow mapping and volumes in Far Cry. Mapping was generally used outdoors in daylight (parallel casted light), and volumes for point lights. F.E.A.R. used volumes extensively also.
- intruder 12y ago
  Not only overdraw but also having to be careful with how you craft the scene. SM pretty much allows for arbitrary scenes. Also small nitpick: you don't filter the shadow map, but the resulting shadow response.
- CyberDildonics 12y ago
  Are there actual production games using ray traced shadows? For non realtime rendering the advantages are soft shadows through lots of rays, rendering in one pass, and no geometry based artifacts. To do them in games though you have to trace against some sort of geometry and that geometry has to be sorted every frame. Simple proxy geo and dynamic bvhs are feasible I'm sure, but it seems to me to be a solution in search of a problem for the time being since all geo to be traced must stay in memory (and for transparency, the opacity textures as well). Now filtering cone sampling of volumes like the Unreal engine is a different story.
- rbdn 12y ago
  I’m wondering what is the technique behind the shadows in this recent Unreal demo: https://www.youtube.com/watch?v=4249b94KtyA https://www.youtube.com/watch?v=4249b94KtyA Looks like some sort of volumetric ray marching approach acceleratred by a signed distance field. Does anyone know what it is?
yoklov 12y ago
Caveat: I'm not a rendering engineer (though I do work in game development), so my knowledge might be a bit out of date or imperfect. 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.
- tsemple 12y ago
  Another reason stencil shadows are difficult in a production environment is that any model that casts a shadow needs to be watertight (i.e. a manifold). Models need to have to full geometry for things like hair, thin fins, and grass.
  - manolus 12y ago
    If a triangular surface has a hole (a cycle of one-triangle-only edges) it's manifold but not watertight.
- oppositelock 12y ago
  Shadow volumes have a number of disadvantages. You have to create geometry for every shadow casting object and for every light source for which it casts a shadow, this is a lot of geometry and a lot of CPU overhead, so you generally used them for static lights and only shadowed moving objects that crossed the light cone. These days CPU doesn't matter as much, but back in 2000 it was a big deal. It was hard to solve the problem in a general way, and you ended up asking your modelers to tag which objects could be shadow casters, which could be shadow receivers, and which lights corresponded to the shadows. 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.)
shultays 12y ago
And for what shadow volumes are: It is basically an imaginary volume that encloses the shadowed area on your world. For example a sphere produces a cone shaped shadow volume behind it when a point light hits it. In computer graphics you can use this geometry to render shadows on object. 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
kazinator 12y ago
There is nothing new about the idea that to determine whether a point is inside a shape (2D or 3D), you can extend a ray from that point to infinity and then count the transitions across object boundaries. If the count is odd, the point is inside, otherwise it is outside. 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!)
- JoeAltmaier 12y ago
  In/out works for shapes in geometry with continuous boundaries. But digital shapes are defined by vertices. If your ray intersects a vertex right as it inflects back (tangent to a corner) a 'crossing' gets counted yet nothing was crossed? 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?
  - kazinator 12y ago
    For a convex polygon, you can determine whether a point is inside or outside by giving each edge an consistent orientation around the path. Then check where the point lies w.r.t. that orientation: is it to the left of the line or to the right? If the polygon is counter-clockwise, say, and the point is to the left of every edge-line, then the point is inside. This extends to 3D convex polyhedra, where you have a consistent orientation of each face. If a point is in the negative half-space of each face, then it is inside. 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.

ginko 12y ago

Shadow mapping[1] has pretty much taken over at this point. This is mainly because of the high overdraw when rendering shadow volumes. You can also filter shadow maps to get soft shadows. This is not really possible with shadow volumes. Raytraced shadows are starting to become feasible. [1]http://en.wikipedia.org/wiki/Shadow_mapping http://en.wikipedia.org/wiki/Shadow_mapping

codezero 12y ago
Cool, thanks a bunch for that info.
kleiba 12y ago
Let's not forget that he was not the first to come up with this technique. From wikipedia [1]: 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. [1] http://en.wikipedia.org/wiki/Shadow_volume http://en.wikipedia.org/wiki/Shadow_volume
- digi_owl 12y ago
  Ah, i initially heard about this as a fix for z-fighting.
- renox 12y ago
  <Sigh>, so many things are independently discovered.. Why do we still have patents??
  - digi_owl 12y ago
    Patents were originally on the specific mechanical system (like the Colt revolver) or chemical composition. 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.
- kybernetikos 12y ago
  According to an earlier comment, iD used this technique in Doom3. Would Carmack have had to pay patent license fees?
mirsadm 12y ago
From my memory the only games which ended up using shadow volumes were Doom 3 and games based on the Doom 3 engine. Shadow maps always seemed like the way forward to me. That is purely based on my own "what looks better" scale. Given that most techniques in 3D programming are hacks to make things look better, I was surprised to see Carmack go down the shadow volumes path. It felt like he'd chosen it based on having nicer code versus an overall nicer looking game. This is all my opinion of course.
- jgh 12y ago
  I find shadow volumes tend to look better, at least cleaner anyway. Shadow mapping if not properly done can look glitchy and aliased. One surprisingly bad offender was Skyrim.
- theandrewbailey 12y ago
  I recall seeing both shadow mapping and volumes in Far Cry. Mapping was generally used outdoors in daylight (parallel casted light), and volumes for point lights. F.E.A.R. used volumes extensively also.
intruder 12y ago
Not only overdraw but also having to be careful with how you craft the scene. SM pretty much allows for arbitrary scenes. Also small nitpick: you don't filter the shadow map, but the resulting shadow response.
CyberDildonics 12y ago
Are there actual production games using ray traced shadows? For non realtime rendering the advantages are soft shadows through lots of rays, rendering in one pass, and no geometry based artifacts. To do them in games though you have to trace against some sort of geometry and that geometry has to be sorted every frame. Simple proxy geo and dynamic bvhs are feasible I'm sure, but it seems to me to be a solution in search of a problem for the time being since all geo to be traced must stay in memory (and for transparency, the opacity textures as well). Now filtering cone sampling of volumes like the Unreal engine is a different story.
rbdn 12y ago
I’m wondering what is the technique behind the shadows in this recent Unreal demo: https://www.youtube.com/watch?v=4249b94KtyA https://www.youtube.com/watch?v=4249b94KtyA Looks like some sort of volumetric ray marching approach acceleratred by a signed distance field. Does anyone know what it is?

yoklov 12y ago

Caveat: I'm not a rendering engineer (though I do work in game development), so my knowledge might be a bit out of date or imperfect. 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.

tsemple 12y ago
Another reason stencil shadows are difficult in a production environment is that any model that casts a shadow needs to be watertight (i.e. a manifold). Models need to have to full geometry for things like hair, thin fins, and grass.
- manolus 12y ago
  If a triangular surface has a hole (a cycle of one-triangle-only edges) it's manifold but not watertight.
oppositelock 12y ago
Shadow volumes have a number of disadvantages. You have to create geometry for every shadow casting object and for every light source for which it casts a shadow, this is a lot of geometry and a lot of CPU overhead, so you generally used them for static lights and only shadowed moving objects that crossed the light cone. These days CPU doesn't matter as much, but back in 2000 it was a big deal. It was hard to solve the problem in a general way, and you ended up asking your modelers to tag which objects could be shadow casters, which could be shadow receivers, and which lights corresponded to the shadows. 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.)

shultays 12y ago

And for what shadow volumes are: It is basically an imaginary volume that encloses the shadowed area on your world. For example a sphere produces a cone shaped shadow volume behind it when a point light hits it. In computer graphics you can use this geometry to render shadows on object. 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

kazinator 12y ago

There is nothing new about the idea that to determine whether a point is inside a shape (2D or 3D), you can extend a ray from that point to infinity and then count the transitions across object boundaries. If the count is odd, the point is inside, otherwise it is outside. 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!)

JoeAltmaier 12y ago
In/out works for shapes in geometry with continuous boundaries. But digital shapes are defined by vertices. If your ray intersects a vertex right as it inflects back (tangent to a corner) a 'crossing' gets counted yet nothing was crossed? 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?
- kazinator 12y ago
  For a convex polygon, you can determine whether a point is inside or outside by giving each edge an consistent orientation around the path. Then check where the point lies w.r.t. that orientation: is it to the left of the line or to the right? If the polygon is counter-clockwise, say, and the point is to the left of every edge-line, then the point is inside. This extends to 3D convex polyhedra, where you have a consistent orientation of each face. If a point is in the negative half-space of each face, then it is inside. 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.