|
Casting Shadows - In Densely Occluded Areas With Detail Objects by (03 March 1999) |
Return to The Archives |
Introduction
 |
|
One of the most difficult tasks in 3D programming is casting real-time dynamic shadows for an arbitrary number of light sources in
complex scenes. So far, there are no real generic solutions for this problem that allow interactive frame rates. In this document I
present an algorithm that comes close to a good and generic solution. The algorithm can be applied to both hardware- and software
rendering. Consider the following scene: A set of rooms, consisting of roughly 100 large polygons. In this room there are several detail objects, like a vase on a table, a few torches on the walls, and a beach ball on the floor. The rooms are interconnected by doors and windows, so that from each room several other rooms are visible. The torches are point light sources. The polygon count of the detail objects is roughly 500 polygons per object. In this scene, the walls will cast shadows because of the lights in the scene. Besides that, the detail objects will cast shadows on the walls, the floors and the ceilings. There are several brute-force approaches possible to render this scene. A selection: Shadow Volume Generation When at least a single point light source is present in the scene, every polygon that faces this light source becomes illuminated. Then, each polygon in the scene that is facing the light source causes a shadow volume to be generated, and all the other illuminated polygons are clipped against this volume. The portions of the polygons that are in the shadow volume are shadowed, the other portions remain illuminated. With 100 polygons, this means a lot of volumes, and a lot of polygon clipping. The detail objects in the scene make this algorithm impossible to do in real time, especially when there's more than just a single light source. Stencil Buffer Shadowing Each light source renders the scene as seen from it's own position, and fills a z-buffer. Then the scene is rendered from the viewpoint of the camera. During this stage, the 3D position for each pixel that is about to be drawn is projected onto the generated stencil buffers to determine whether the pixel is behind another pixel from the viewpoint of the light source. This technique is fast for a single lightsource, since the scene can be rendered from the viewpoint of the lightsource using only z-buffer filling. For multiple lightsources, memory requirements increase quickly. Stencil buffers are only supported by some of the currently available hardware accelerators. On the other accelerators, this technique is impossible. Finally, the shadows produced this way tend to look blocky, because of the resolution of the stencil buffer. |
|
A New Approach: "Let There Be Light"
|
|
The shadow volume approach that I described above makes it quite hard to stop tracing shadows at an early stage. That is because it
assumes that most polygons are lit: Shadows are projected on top of the illuminated polygons, or they replace (parts of) the original
polygons. That's why we might consider starting at the other end: Shadowed polygons. Instead of applying shadow to illuminated
polygons, we could then apply light to initially dark polygons. That's more natural too: If you walk into your bedroom at midnight and
turn on the light, you are not casting shadows into the dark corners, you are casting light to the floor, assuming your light is on the
ceiling. Applying this to a rendering engine: A torch casts beams of light. As soon as all of this light is obscured, tracing of the beams
can be halted. That means that if the beam encounters a floor, tracing could stop there, reducing the amount of processing to 1% in
our sample scene. When, on the other hand, the light is only partially obscured by the first polygon encountered, the beam is split into new convex volumes by subtracting the volume between the encountered polygon and the light source from the original beam. Then the resulting beams are processed. The algorithm should thus start with the nearest polygon, test it against the lightbeam, adjust the lightbeam, and if anything is left, proceed with the other polygons. |
|
The Cost Of Detail
|
|
The first problem with this algorithm arises when a detail object is encountered. There are some optimizations possible that I will
discuss later in this document, but there is also a generic approach possible for detail objects. When a light beam encounters a detail object, rather than processing this object per polygon, it can simply be drawn on the lightmap. When the beam encounters polygons after drawing a silhouette of the detail object on the lightmap, this silhouette is then correctly projected on the larger scenery polygons. This approach has some disadvantages though: First, detail objects can not be 'self-shadowing' this way, as all polygons of the detail object will be shaded using the lightmap as it was before the beam encountered the object. Or, to get some more speed, the object can be illuminated with fake phong shading or gouraud shading. Another problem could be caused by objects that are too close to each other. In that case, two things could go wrong: The second object could receive no shadow at all from the first object, or it could receive a shadow where it shouldn't. A third problem is the potential 'blocky shadow' problem that also happens when the stencil buffer approach is used. So, why is this approach still better than the stencil buffer technique or the shadow volume technique? Well, because for large occluders, you get perfect and sharp shadows. Detail objects cast less perfect shadows, but that's less a problem than with the large occluders, since the shadow of a detail object is somewhat fuzzy anyway. |
|
Optimization Opportunities
|
|
This hybrid approach for shadow casting in complex 3D scenes can be made even faster by applying some simple optimizations: Use Simplified Versions Of Detail Objects The shadows cast by detail objects can also be drawn on the lightmap using a simplified version of the detail object. Typically, if you are using LOD in the renderer already, the shadow might be generated using a LOD that's slightly simpler than the LOD used to draw the object. This way, the shadow is constructed from an even less detailed source mesh when the object gets further away from the camera. Smooth The Projected Silhouette To reduce the blockyness of the silhouette as it is projected on larger occluders, you might want to smooth it prior to drawing it on the lightmap. If the lightmaps are projected using bilinear filtering, this will reduce the blockyness to a very acceptable level. Detect Convex Portions Of Detail Objects The silhouette of a convex detail object is also convex, so you might use this knowledge to drastically reduce the number of polygons you need to draw on the lightmap. A winged edge structure can be useful to quickly determine the (convex) silhouette of a collection of polygons. |
|
Hardware and Software Rendering Considerations
|
|
So far, I have assumed that it is perfectly normal to have a directed beam of light to which the polygons and detail objects can be
tested. In reality, this is not always the case. The torches in the initial example are point light sources, and therefore they cast light in
all directions. This means that the initial volume is not bounded by any planes. This also means that the volume can not be used to
project a lightmap on the polygons that are in the volume. This problem can be solved by generating a number of beams, starting at the
point light source, but that increases the number of tests dramatically. So, in general, this algorithm performs best for light sources
that cast a single, narrow beam. It would work perfectly, for example, for a scene with a window through which the sun shines: The
start volume (in this case not neccessarily starting at a point light source) is easy to define and easy to modify. This algorithm works good for multiple light sources, but one has to keep in mind that the lightmaps need to be projected on top of existing textures. This means that software rendering, while still possible, suffers from great amounts of overdraw. This especially becomes a problem when multiple lights illuminate a relatively large visible region. Hardware accelerators will suffer much less from this problem, as current accelerators can fill (and mix colors) at great speeds. Hardware accelerators on the other hand do have a problem when the lightmap is frequently altered by detail objects. Since this happens only once for every object that is encountered, this should not cause too much delay. For scenes with large amounts of detail objects however, rendering could slow down only because of bandwidth problems. Software rendering does not suffer from this. |
|
Conclusion
|
|
I have presented here an algorithm that makes shadow (or rather, light) casting from multiple sources possible in a relatively complex
scene with detail objects. The most important advantage of the presented approach is that beam tracing can be terminated when the
light is fully absorbed by an occluder, as opposed to the approaches that process shadow rather than light. This means that
conventional visibility determination techniques, like portal tracing, can be used to speed up the rendering of light beams. It also means
that in some cases light sources that have no effect on the visible scene can be omitted in the rendering process completely.
Ultimately, this results in scenes with potentially unlimited light sources, where rendering speed is dependant of the number of visible
light sources and generated lightmaps. Jacco Bikker, a.k.a. "THE PHANTOM" |
|
Article Series:
|