---------------------------------------------------- Charles Bloom cbloom@oddworld.com www.cbloom.com Thorough Analysis of Light + Shadow techniques. cbloom 8-21-01 ---------------------------------------------------------------------------- I won't go into detail about the decision of how bright a point should be one you've decided that it's lit by a given light. The goal here is to find a light + shadow method (henceforth just "shadow") which is not necessarily physically correct, but looks good and is free from bad anomalies. The anomalies I'm talking about are shadows cast through walls, Z-fighting, holes in shadows, gross resolution differences, etc. Let me stress again, that I don't want a perfect solution, just something that's actually useable. Very delicate or difficult to use solutions are also not valid. ---------------------------------------------------------------------------- So, before getting into specific techniques, there are a bunch of global issues. 1. There are several cases. You have static & dynamic geometry, and static & dynamic lights, resulting in four combinations. It's okay to special-case all of these. Obviously static lights with static geometry is a good opportunity for optimization, and it's acceptable to not cast shadows from dynamic lights at all. 2. There's the issue of whether you're adding light or subtracting shadows. I've talked about this a lot before, so I won't do it extensively again. This trade-off exists with all techniques. In general adding light makes better results, but is more expensive. Subtracting shadow (usually done with a multiply in practice) is the current defacto shadowing technique. 3. Selecting which objects cast shadows from which lights. This is a general problem. There are various heuristics which select only the "strongest" light(s) to cast shadows from. These work reasonably well, but they *only* work for dynamic objects. Here, I assume that all dynamic lights are compact and disjoint. This doesn't work for static objects, because they may be placed such that they must match seamlessly. For example, a doorframe and a wall might be separate objects. They must select the same shadow casters and lights, or the seam will be exaggerated. Actually, this problem continues to dynamic objects - if the door itself is dynamic, it's selection can't differ too much from the static objects or it will stand out badly. ---------------------------------------------------------------------------- Ok, so let's look at our tools : 1. Shadow maps. Works for dynamic onto anything. The problem with static geometry casting shadow maps is the question of when the shadow starts; that decision must be made with a simple primitive, which just doesn't work with casters that are spatially large. 2. Shadow buffers. Works for anything onto anything. The basic idea is that from each shadow-casting light, you create a depth buffer from the POV of the light looking at the shadow-casters. You then do depth-test between this buffer and the receiving geometry to tell if it's in shadow. The casting geometry cannot have that large of a Z range, or you get bad precision problems. This technique can be very GPU-heavy , requiring lots of rendertarget work and pixel shaders. 3. Stencils from shadow volumes. Works for anything onto anything. Can have very high fill-rate cost. Finding the shadow volume from dynamic geometry can be very CPU-heavy. 4. Light maps. Works for static onto static. Large memory cost. Very efficient at run time. 5. Vertex shadows. Works for static onto static. Similar to light maps. Very efficient at run time. Won't be mentioned again; any technique that applies to light maps could use vertex-light values instead. 6. Polygons. Works for static onto static. The hard-edged version of lightmaps. Find shadow volumes and make "shadow polygons" where they intersect the world. Very efficient at run time. ---------------------------------------------------------------------------- Finally, let's summarize a few tricks that can be applied to many of these to speed them up : 1. Only casting from a few lights. If you can make a fixed decision (only one light in this room casts shadows) then you are relatively safe (except for the anomaly when you transition rooms). If there are many lights, you could choose to cast from the strongest few (or one). If you do this, you must have a way to transition smoothly when the identity of the strongest light changes. To do this you must be able to slide or fade out your shadows. 2. Not casting shadows in the distance. Distant dynamic stuff need not cast. Stuff that's not visible (and whose shadow isn't visible) also need not cast. It's nice if you can fade out shadows that drop out in the distance, but it's not totally necessary. 3. Assigning areas of affect. Each shadow-casting light can store an area of affect. This is the volume where that light's zero-bounce illumiation lies. Only casters in this area need consider that light. Also, you only need to cast onto surfaces which border this area. Use of this technique can hide many anomalies. This assignment could be done by hand or automatically. Another way to do area of effect is dynamically, via a beam-tree. You gather polygons from the POV of the light, accepting only the closest visible fragments. Now let's look at some possible solutions. There's a good technique when looking for anomalies : imagine replacing any piece of static geometry with a piece of dynamic geometry. The lighting of the scene must not be changed in a severe way. It's okay to change slightly, but severe changes will show up as anomalies. ---------------------------------------------------------------------------- 1. Light-maps with projected shadows. This is a common suggestion and is being used frequently at the moment. In this technique, static geometry is lit by static lights with shadows cast by static casters. Static lights create shadow maps (or buffers) to cast shadows from dynamic geometry onto static geometry. There are a few options which aren't really important : dynamic geometry can cast onto other dynamic or not, and dynamic lights can cast shadows from dynamic geometry or not. Only a handful of selected "important" lights cast shadows, and this decision can be made dynamically. I would suggest that dynamic lights probably shouldn't cast from dynamic geometry since they won't cast from static geometry, and consistency is key. So, the carried torch with beautiful shadows is out. Also, static geometry casting shadows onto dynamic actors is out. The biggest anomalies with this technique are the standard problems with shadow maps projecting through walls, and anomalies due to the grossly different resolutions of light-maps and shadow-maps. This resolution problem means that a statue of the player and the player himself will look severely different. Also, you must be very careful about the rounding in the light map. Any lightmap texel which is partially shadowed must be considered fully shadowed. The reason for this is that if you don't do this, then you can put a dynamic object fully behind a static object, and yet it would appear to be outside the shadow of the static object. Imagine a small crow-bar placed behind the corder of a wall. Where the shadow of the crow-bar is, the shadow of the wall must also be. Anomalies the other way around (due to the light map having too much shadow) are not as bad. The shadows in the shadow maps and the light maps must both be completely black. The light map must not contain any ambient. You multiply together the shadow map and the light map, and then add ambient. This way, if you have a wall which is partly made from static and partly from dynamic geometry, you get a shadow of continuous darkness. The edges of the shadow are not continuous, however, due to the resolution difference. This can be fixed only by using very high-resolution lightmaps. The dynamic door in the static door frame will stand out sharply. This can be minimized by using a per-pixel lighting computation for the dynamic objects which is nearly identical to the light map. Another possibility here is to store the light map only in black and white, as a pre-computed shadow map. The actual lighting could then be done for all geometry at run-time in the same way. Shadows would only be cast onto static geometry, via pre-computed shadow map (lightmap) and projected shadow map from dynamic geometry. You definitely must use one of the "area of effect" techniques to find the right target geometry for the shadow maps (unless you use the exact same lights for shadows in the light-map as you do for the run-time shadows, which is certainly possible). Note that "adding light" is not a magic bullet for this technique. The problem is that in order to add light, you must store a separate light map >for each light source<. This is possible, and could even be efficient with clever packing, but it's bad enough to make it not workable. So, to summarize, some common permutations : A. Just light-map the scene; cast shadow maps willy-nilly. Your light-maps need to over-estimate shadows; the shadows need to be black; higher resolution is better, obviously. Only static lights cast shadows. Light-maps contain all the static on static shadows; static doesn't cast on dynamic. Dynamic casts onto static geometry (from static lights) via shadow maps, which can transition and fade out. Shadow maps should be black, and the final texture op is : (LightMap * ShadowMap + Ambient) * Texture Advantages : very fast, well known common technique. Light-map lighting can be pre-computed with very nice algorithms; light-map shadows can be softened. Disadvantages : high memory use for light-maps; static geometry and dynamic geometry is lit and casts shadows very differently (causes "pop out" of dynamic objects). If you don't over-esimate your shadows and always darken, then you'll have places where a static object doesn't cast a shadow, but a dynamic object in the same location does cast a shadow. To prevent this, you must make all objects which block light always cast a fully dark shadow, even when there is another light that illuminates the target location. This is exactly the opposite of what's physical : if a point is shadowed from one light and lit from another, you must make that point shadowed in the light map, otherwise a dynamic object will cast shadows where the static didn't. To make this not horrible, you must select only a few lights as shadow-casting. Of course, this problem is minimized by an area-of-affect technique. If you do AOA, then these rules only need to be followed within the AOA of a light; eg. a light need not cast shadows outside of its AOA. The AOA used for light-map computation must be the same as the AOA used at run time. B. "shadow light-maps". This is a hybrid technique; your light-maps are black and white, containing only shadows. You should have nice big chunks of white and black, so with variable resolution maps, you should be able to compress your light maps a lot and crank up the resolution where it's needed. You do per-pixel lighting of everything at run-time, which gives you more uniformity of appearance; the texel op is : (LightMap * ShadowMap * Light + Ambient) * Texture Notez : when you make your light map, it's always okay to have more shadows. You can cast soft, weak, shadows from the "non-shadowing" static lights into your light maps and then not cast from those lights at run-time. Anomalies only arise when the dynamic shadows affect things that the static did not. C. Optimized Area-Of-Affect. AOA volumes for lights should be computed during the light map construction phase, since they must be identical then and at run time. Each light can construct a volume and store it, along with a list of the faces which border that volume. Now, only those faces need be lit by that light, and only those faces need accept shadows from that light. At run time, you generate shadow maps from that light and cast them onto the faces in the AOA list. This is extremely fast at run time; the list of faces is just a model; you just render it with the shadow map. This solves all the problems with projection through walls. Only shadow-casting lights need this AOA work. The volume of light in the AOA can be approximate; it's only used for selecting which dynamic objects cast onto the target face list of that light. The big problem arises here if your scene is not densely occluded. In that case, you have lots of complicated AOA's which overlap. In a simple Doom/Quake-like level, this is not a problem, but with arbitrary geometry, it's a disaster. Note that this AOA stuff only works for light sources that have a specific position; this doesn't work for directional lights because the same spot could be affected by the same light even thought it's D. One specific way that light maps + projected shadows can work is with a single casting light. You must then separate your lightmaps into light from the casting light and non-casting lights. The "shadow lightmap" should be black where shadows lie. You then create your image like this : ( Shadow LM * Projected Shadow + Non-Casting LM ) * Diffuse The result is that there are no project-through-walls anomalies or anything like that, since all the walls also cast shadows from the same source. The non-casting LM should contain the ambient light. This will also work with multiple casting lights as long as each area of space is only affected by one light, and you do transitions, and those areas of affect are the same for static and dynamic geometry. Static geometry still won't cast onto dynamic at all, and you have all the anomalies with the dynamic lights looking very different than the static background. ---------------------------------------------------------------------------- 2. Stencil everything onto everything. Stencil shadows work for casting everything onto everything (static/dynamic onto static/dynamic) because there's no issue with when the onset of the shadow is (actually, there is a precision issue, but we'll come back to that). Because you cast everything onto everything, there's no issue of anomalies due to shadows going through walls, etc. (again, actually, there still are issues, but the wall will also make a shadow, so the anomaly isn't that onerous). One big problem is that it's too expensive to cast from lots of lights, so you must select just a few lights. It's also hard to spatially localize these lights, because as noted before you can't just make different light selections for adjacent objects. Also, selecting lights is easier if you can do some fading out to make the transitions. Fading out is expensive with stencils. The standard stencil technique is to draw all the shadow volumes to the stencil buffer, then draw one polygon over that to darken where the stencil is set. If you do this, all your shadows have the same darkness. To do shadows of varying darkness, you have to do a separate full-screen polygon for each darkness level, multiplying your fill-rate cost by a lot. All of these stencil issues are somewhat eased by taking advantage of some big static optimizations. First, you discard shadowing from dynamic lights. Second, static shadows (static lights casting from static objects) can just be polygons; dark polygons work perfectly because they have hard edges, just like the stencil shadows. Finally, static shadows casting onto dynamic objects can have pre-computed shadow volumes, and only need to activate and apply to dynamic objects; let me re-iterate this : for each static light-static object pair, you can precompute the shadow volume and clip it to be very small; only the size of its actual area of effect; you can then ignore it completely unless a dynamic object intersects it. The only tricky thing remaining is to cast the shadows from dynamic objects in front of static lights. This can be done via selection of a single shadow-casting light for each dynamic object, perhaps with fade out (or with out), and no shadow-casting in the distance. The expensive CPU work to find the shadow volume for a dynamic object is still needed, but this can be done on a lower-LOD version (and can be cached out for non-moving objects). In order to cast from a lower-LOD version, you probably want to avoid self-shadowing. To do that, you must render the background first, and then render in the shadows from dynamic objects, and then render the characters. It's somewhat expensive to avoid double-darkening. To do that, you must render the static geometry in all white with the shadow polygons in black. You then render in the stencil shadows from the dynamic objects in black. Then you render in the dynamic objects (in white), and render in the stencil shadows from static onto the dynamics. Finally, you render everything again, doing this op : FB = (FB * light + ambient) * texture If you want to avoid all this work, it's acceptable to double-darken where dynamic shadows overlap onto static shadows. It's not acceptable to double-darken where static stencil shadows overlap onto static polygonal shadows; the reason that's not acceptable is that the double-darkening will flicker on and off when dynamic objects move in and out of the shadow volume. ---------------------------------------------------------------------------- 3. Shadow buffers ? It seems to me that shadow buffers don't solve anything. They don't work for static to static shadow casting because of the bad precision problems, and very high expense. So, you have to do something like light-maps for the static to static shadows. The result is that we've just got a shadow-mapping technique that can do self-shadowing. Self-shadowing is nifty, 4. None. Circular blobs under the feet, for example, work pretty well. ----------------------------------------------------------------------------