Anti-aliasing and Continuity with Trapezoidal Shadow Maps

Tobias Martin (tobiasmartin@t-online.de) and Tiow-Seng Tan (tants@comp.nus.edu.sg)

School of Computing, National University of Singapore

Abstract

This paper proposes a new shadow map technique termed trapezoidal shadow maps to calculate high quality shadows in real-time applications. To address the resolution problem of the standard shadow map approach, our technique approximates the eye’s frustum as seen from the light with a trapezoid to warp it onto a shadow map. Such a trapezoidal approximation, which may first seem straightforward, is carefully designed to achieve the goal of good shadow quality for objects from near to far, and to address the so-called continuity problem that is found in all existing shadow map approaches. The continuity problem occurs mainly when the shadow map quality changes significantly from frame to frame due to the motion of the eye or the light. This results in flickering of shadows. On the whole, our proposed approach is simple to implement without using complex data structures and it maps well to graphics hardware as shown in our experiments with large virtual scenes of hundreds of thousands to over a million of triangles. * This work has a patent filed by our University. However, it is not our intention to derive much monetary rewards from the patent. Most of all, universities are generally non-profit organizations and reputation/recognition (of creating useful techniques) rather than money is utmost important to them; our University is no exception in this case. Do feel free to explore TSM. Should you have further questions or problems about the technique, just drop us an email - we do our best in giving support. If you are interested in using it for commercial products, we would be happy to listen to you, and then work with you to obtain the right to use with little hassle and at most a small token of appreciation of some form from you.

Known Uses of TSM

Attribution : Open source project: West Point Bridge Designer 2nd Edition; see also implementation notes by Eugene Ressler.

Results

We have implemented the proposed trapezoidal shadow maps using GNU C++ and OpenGL under Linux environment on an Intel Pentium 4 1.8GHz CPU with a nVidia GeForce FX5900 ultra graphics controller. We use GL_fragment_program_ARB for polygon offset and for shading inclusive of shadow comparison. The shadow maps are rendered into a pbuffer using GLX_SGIX_pbuffer. Note that our approach uses various geometric yet simple operations such as convex hulls, line operations etc. in 2D. Robustness issues are easy to handle in our 2D cases. The standard shadow maps (SSM), a version of the smallest bounding box approximation (BB), and the perspective shadow maps (PSM) are implemented for purposes of comparison.

For PSM, there are many implementation choices. We devote lots of effort to replicate the description provided in the paper and to tune to the best of our knowledge the algorithm in flavour of our test scene. It remains possible that our implementation may not be as efficient or effective as the original implementation of PSM. For one, we do not perform a read back of the depth buffer to know how much to push a near plane closer to a far plane as this is rather costly in our highly interactive test scene with our current hardware configuration. On the other hand, we do push the near plane towards the far plane as much as possible geometrically (till it touches H as defined in the paper) in order to obtain high shadow map resolutions. Details of our PSM implementation are provided in the webpage http://www.comp.nus.edu.sg/~tants/tsm/psm.html . As there are various implementation options at various steps of PSM, our implementation, though with good care, may not be of the same effectiveness as the original implementation of PSM (see also Kozlov, S. 2004. Perspective Shadow Maps: Care and Feeding. In GPU Gems: Programming Techniques, Tips and Tricks for Real-Time Graphics, edited by Fernando, R., Addison Wesley.)

A. Fantasy World (Figure 1)

Our first experiment is on a fantasy world with over 100K triangles, and uses a shadow map size of 1024x1024. All objects can cast shadows where the only light source is set at a far distance from the scene. See Figure 1(a) for an overview of the scene rendered with SSM. Figure 1(b) to (f) show snapshots of our scene rendered by the various approaches. The objects in the scene include a static tree (as in Figure 1(b) and (c) to test thin triangles casting shadows), three mushrooms (as in Figure 1(c) to test curved surfaces casting shadows), a pergola (as in Figure 1(d) to test beams casting shadows), dynamic objects inclusive of a dragon (as in Figure 1(e)) and a few characters (as in Figure 1(a),(d) and (e) to test shadows of small and large details), and a lotus (as in Figure 1(f) to test shadows of a small but detailed object).

The first part of the accompanying video contains flythroughs of the scene: (1) a quick one using PSM, (2) a complete one using TSM, (3) comparisons among the approaches. All the approaches run smoothly with an average of 28 frames per second without any special occlusion culling and optimization. The light is static for the beginning part and then moves around the scene for the last few seconds.

With SSM, shadows of static objects do not flicker while shadows of dynamic objects often flicker. With BB, the flickering occurs for both static and dynamic objects. The quality of the shadows is not good in general, and the flythrough experience is not acceptable. With PSM, it produces better shadow quality than that of BB for its favorable cases. It, however, converges to the SSM for those unfavorable cases such as when the position of the eye needs to be moved away so that all objects casting shadows into the eye’s frustum are included in the new "virtual" eye's frustum.

With TSM, the animation is smooth with only occasional flickering of shadows. The experience of the flythrough is very pleasant. In the video, the polygon offset used by TSM is visible as a gap between the leg of the pergola and the terrain. This is of the same amount as used in SSM, BB, and PSM. For PSM, this offset is not always sufficient as we still observe surface acne (for example, on the mushrooms) in the video.

(a) (c) (e)
 
(b) (d) (f)

Figure 1: Fantasy World. (a) An overview of the scene rendered with SSM. (b) to (f) are comparisons of shadows generated by BB (left), PSM (center), and TSM (right). (b) The area near the tree with shadows of tree branches. (c) Top view of shadows of tree branches on the terrain and on one of the three mushrooms. (d) Shadows of a character carrying an axe under the pergola, and (e) another character riding on a dragon and carrying a lance. (f) Shadows of the lotus at a near distance and a mushroom farther away.

B. Urban Model (Figure 2)

Our second experiment is on an urban model with approximately 1.4 million triangles from 79 objects of buildings, vehicles etc. (as in Figure 2(a) and (b)) where the only light source is set at a far distance from the scene. We use a shadow map size of 2048x2048 pixels with the eye having a large depth of view to test the quality of shadows of objects from near to far. Such a setting is unfavorable to BB (as mentioned in Section 3), and comparison with BB is thus not necessary and not shown here.

The second part of the accompanying video shows flythroughs of the scene and comparisons between PSM and TSM. See also Figure 2(c) to (f) for comparisons of shadows between PSM and TSM. We observe that both far away and nearby shadows generated by TSM are of better quality than those by PSM. Our program for this scene uses ARB_occlusion_query for a simple occlusion culling in the shadow map generation step. On the average, TSM renders only about 56 objects during the shadow map generation. In contrast, SSM has to render all of the 79 objects, and BB and PSM about 61 and 72 objects on the average, respectively. The frame rates for all approaches are below 10 due to the large number of triangles in the scene while there is no sophisticated optimization in our implementation.

(a) (c) (e)
 
(b) (d) (f)

Figure 2: Urban World. (a) and (b) An overview of the city rendered using TSM. The eye has a large depth of view. (c) to (f) are comparisons of shadows generated by PSM (left) and TSM (right). (c) Shadows of a truck and street lamps from near to far. (d) Shadows of the car port close to the eye position, and a bus and some street lamps at a distance. (e) A zoom from a distant position on the shadows of the car port on the Mercedes. (f) A building with shadows from its roof on the facade, and its porch on the entrance staircases.

Concluding Remarks and Limitation

We propose the novel trapezoidal shadow maps for real-time interactive applications. Our implementation shows that it is practical and maps well to graphics hardware. We note that our approach is only one way to address the resolution and the continuity problem. It is a reasonable heuristic to generate shadow maps of good resolution, but the issues on over- and under-sampling remain for various situations such as in the dueling frusta case where the trapezoidal approximation does not have any particular advantage over other approximations. The possibility to compute an optimal resolution by using only one shadow map remains an open question. Also, the approach addresses the continuity problem due to the motions of the eye and the light but not that of objects per se. Nevertheless, we take comfort in a good overall control of the shadow map resolution and its smooth transition, so that shadows blend well into the scenes without attracting special (undesirable) attention!

Videos

  1. Video for paper (640x480.mp4), low resolution (46.3 MB)
  2. Video for paper (640x480.mov), high resolution - available upon request (157 MB)

Supplementary Videos

  1. Standard Shadow Maps 640x480_low.mp4 (14.9 MB), high resolution video available upon request (52.2 MB)
  2. Bounding Box Approach 640x480_low.mp4 (14.9 MB), high resolution video available upon request (52.2 MB)
  3. Perspective Shadow Maps 640x480_low.mp4 (14.9 MB), high resolution video available upon request (52.2 MB)
  4. Trapezoidal Shadow Maps 640x480_low.mp4 (14.9 MB), high resolution video available upon request (52.2 MB)

Updated on 5 August 2003, 5 October 2003, 18 January 2004, 15 May, 26 June, 12 July, 16 July, 26 August 2004, 15 December 2004, 27 Feb 2008, 19 March 2011, 2 May 2011 © NUS