Resolution-matched shadow maps

ABSTRACT

This article presents resolution-matched shadow maps (RMSM), a modified adaptive shadow map (ASM) algorithm, that is practical for interactive rendering of dynamic scenes. Adaptive shadow maps, which build a quadtree of shadow samples to match the projected resolution of each shadow texel in eye space, offer a robust solution to projective and perspective aliasing in shadow maps. However, their use for interactive dynamic scenes is plagued by an expensive iterative edge-finding algorithm that takes a highly variable amount of time per frame and is not guaranteed to converge to a correct solution. This article introduces a simplified algorithm that is up to ten times faster than ASMs, has more predictable performance, and delivers more accurate shadows. Our main contribution is the observation that it is more efficient to forgo the iterative refinement analysis in favor of generating all shadow texels requested by the pixels in the eye-space image. The practicality of this approach is based on the insight that, for surfaces continuously visible from the eye, adjacent eye-space pixels map to adjacent shadow texels in quadtree shadow space. This means that the number of contiguous regions of shadow texels (which can be efficiently generated with a rasterizer) is proportional to the number of continuously visible surfaces in the scene. Moreover, these regions can be coalesced to further reduce the number of render passes required to shadow an image. The secondary contribution of this paper is demonstrating the design and use of data-parallel algorithms inseparably mixed with traditional graphics programming to implement a novel interactive rendering algorithm. For the scenes described in this paper, we achieve 60--80 frames per second on static scenes and 20--60 frames per second on dynamic scenes for 512² and 1024² images with a maximum effective shadow resolution of 32,768² texels.

REFERENCES

• 1: Aila, T. and Laine, S. 2004. Alias-free shadow maps. In 15th Eurographics Workshop on Rendering (Rendering Techniques'04). 161--166.
• 2: Jukka Arvo, Tiled Shadow Maps, Proceedings of the Computer Graphics International, p.240-247, June 16-19, 2004 [doi>10.1109/CGI.2004.97]
• 3: Chan, E. and Durand, F. 2004. An efficient hybrid shadow rendering algorithm. In 15th Eurographics Workshop on Rendering (Rendering Techniques'04). 185--196.
• 4: Chong, H. Y. and Gortler, S. J. 2004. A lixel for every pixel. In 15th Eurographics Workshop on Rendering (Rendering Techniques'04). 167--172.
• 5: Franklin C. Crow, Shadow algorithms for computer graphics, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.242-248, July 20-22, 1977, San Jose, California
• 6: William Donnelly , Andrew Lauritzen, Variance shadow maps, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111440]
• 7: Randima Fernando , Sebastian Fernandez , Kavita Bala , Donald P. Greenberg, Adaptive shadow maps, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.387-390, August 2001 [doi>10.1145/383259.383302]
• 8: Forsyth, T. 2004. Practical shadows. In Game Developers Conference. http://www.eelpi.gotdns.org/papers/papers.html.
• 9: Markus Giegl , Michael Wimmer, Queried virtual shadow maps, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230112]
• 10: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 11: Ned Greene , Paul S. Heckbert, Creating raster Omnimax images from multiple perspective views using the elliptical weighted average filter, IEEE Computer Graphics and Applications, v.6 n.6, p.21-27, June 1986 [doi>10.1109/MCG.1986.276738]
• 12: Harris, M., Sengupta, S., and Owens, J. D. Parallel prefix sum (scan) with CUDA. In Nguyen Ed. GPU Gems 3, Chap. 31. Addison Wesley, 851--876.
• 13: Hasenfratz, J.-M., Lapierre, M., Holzschuch, N., and Sillion, F. 2003. A survey of real-time soft shadows algorithms. Comput. Graph. For. 22, 4, 753--774.
• 14: Horn, D. 2005. Stream reduction operations for GPGPU applications. In GPU Gems 2, M. Pharr, Ed. Addison Wesley, Chapter 36, 573--589.
• 15: Gregory S. Johnson , Juhyun Lee , Christopher A. Burns , William R. Mark, The irregular Z-buffer: Hardware acceleration for irregular data structures, ACM Transactions on Graphics (TOG), v.24 n.4, p.1462-1482, October 2005 [doi>10.1145/1095878.1095889]
• 16: Aaron Lefohn , Shubhabrata Sengupta , Joe Kniss , Robert Strzodka , John D. Owens, Dynamic adaptive shadow maps on graphics hardware, ACM SIGGRAPH 2005 Sketches, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1187112.1187126]
• 17: Aaron E. Lefohn , Shubhabrata Sengupta , Joe Kniss , Robert Strzodka , John D. Owens, Glift: Generic, efficient, random-access GPU data structures, ACM Transactions on Graphics (TOG), v.25 n.1, p.60-99, January 2006 [doi>10.1145/1122501.1122505]
• 18: Lloyd, B., Tuft, D., Yoon, S., and Manocha, D. 2006. Warping and partitioning for low error shadow maps. In Proceedings of the Eurographics Symposium on Rendering. Eurographics Association, 215--226.
• 19: Lloyd, B., Yoon, S., Tuft, D., and Manocha, D. 2005. Subdivided shadow maps. Tech. rep. TR05-024, University of North Carolina at Chapel Hill.
• 20: Martin, T. and Tan, T.-S. 2004. Anti-aliasing and continuity with trapezoidal shadow maps. In Eurographics Symposium on Rendering. 153--160.
• 21: Joel McCormack , Ronald Perry , Keith I. Farkas , Norman P. Jouppi, Feline: fast elliptical lines for anisotropic texture mapping, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.243-250, July 1999 [doi>10.1145/311535.311562]
• 22: Fabio Pellacini , Kiril Vidimče , Aaron Lefohn , Alex Mohr , Mark Leone , John Warren, Lpics: a hybrid hardware-accelerated relighting engine for computer cinematography, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 23: William T. Reeves , David H. Salesin , Robert L. Cook, Rendering antialiased shadows with depth maps, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.283-291, August 1987
• 24: Alexander Reshetov , Alexei Soupikov , Jim Hurley, Multi-level ray tracing algorithm, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 25: Segal, M. and Akeley, K. 2004. The OpenGL Graphics System: A Specification (Version 2.0---Oct.).
• 26: Pradeep Sen, Silhouette maps for improved texture magnification, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058139]
• 27: Pradeep Sen , Mike Cammarano , Pat Hanrahan, Shadow silhouette maps, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 28: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 29: Sengupta, S., Lefohn, A. E., and Owens, J. D. 2006. A work-efficient step-efficient prefix sum algorithm. In Proceedings of the Workshop on Edge Computing Using New Commodity Architectures. D--26---27.
• 30: Marc Stamminger , George Drettakis, Perspective shadow maps, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 31: Thrane, N. and Simonsen, L. O. 2005. A comparison of acceleration structures for GPU assisted ray tracing. M.S. thesis, University of Aarhus.
• 32: Wald, I., Purcell, T. J., Schmittler, J., Benthin, C., and Slusallek, P. 2003. Realtime ray tracing and its use for interactive global illumination. In Eurographics (State of the Art Reports). 85--122.
• 33: Lance Williams, Casting curved shadows on curved surfaces, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.270-274, August 23-25, 1978
• 34: Wimmer, M., Scherzer, D., and Purgathofer, W. 2004. Light space perspective shadow maps. In Eurographics Symposium on Rendering. 143--151.
• 35: Andrew Woo , Pierre Poulin , Alain Fournier, A Survey of Shadow Algorithms, IEEE Computer Graphics and Applications, v.10 n.6, p.13-32, November 1990 [doi>10.1109/38.62693]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Design, Performance

Keywords:
GPGPU, GPU, Shadows, adaptive shadow maps, graphics hardware, scan, shadow maps