skip to main content
article

Resolution-matched shadow maps

Published: 01 October 2007 Publication History

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 5122 and 10242 images with a maximum effective shadow resolution of 32,7682 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]
Arvo, J. 2004. Tiled shadow maps. In Computer Graphics International Conference. 240--247.
[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]
Crow, F. C. 1977. Shadow algorithms for computer graphics. In Computer Graphics Proceedings of SIGGRAPH. 11, 242--248.
[6]
Donnelly, W. and Lauritzen, A. 2006. Variance shadow maps. In Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. ACM, New York, NY, 161--165.
[7]
Fernando, R., Fernandez, S., Bala, K., and Greenberg, D. P. 2001. Adaptive shadow maps. In Proceedings of ACM SIGGRAPH. Computer Graphics Proceedings, Annual Conference Series. 387--390.
[8]
Forsyth, T. 2004. Practical shadows. In Game Developers Conference. http://www.eelpi.gotdns.org/papers/papers.html.
[9]
Giegl, M. and Wimmer, M. 2007. Queried virtual shadow maps. In Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. ACM, New York, NY, 65--72.
[10]
Govindaraju, N. K., Gray, J., Kumar, R., and Manocha, D. 2006. GPUTeraSort: High performance graphics coprocessor sorting for large database management. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 325--336.
[11]
Greene, N. and Heckbert, P. S. 1986. Creating raster omnimax images from multiple perspective views using the elliptical weighted average filter. IEEE Comput. Graph. Appl. 6, 6, 21--27.
[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]
Johnson, G. S., Lee, J., Burns, C. A., and Mark, W. R. 2005. The irregular Z-buffer: Hardware acceleration for irregular data structures. ACM Trans. Graph. 24, 4, 1462--1482.
[16]
Lefohn, A., Sengupta, S., Kniss, J., Strzodka, R., and Owens, J. D. 2005. Dynamic adaptive shadow maps on graphics hardware. In ACM SIGGRAPH Conference Abstracts and Applications.
[17]
Lefohn, A. E., Kniss, J., Strzodka, R., Sengupta, S., and Owens, J. D. 2006. Glift: Generic, efficient, random-access GPU data structures. ACM Trans. Graph. 26, 1, 60--99.
[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]
McCormack, J., Perry, R., Farkas, K. I., and Jouppi, N. P. 1999. Feline: Fast elliptical lines for anisotropic texture mapping. In Proceedings of SIGGRAPH. Computer Graphics Conference Series. 243--250.
[22]
Pellacini, F., Vidimče, K., Lefohn, A., Mohr, A., Leone, M., and Warren, J. 2005. Lpics: A hybrid hardware-accelerated relighting engine for computer cinematography. ACM Trans. Graph. 24, 3, 464--470.
[23]
Reeves, W. T., Salesin, D. H., and Cook, R. L. 1987. Rendering antialiased shadows with depth maps. In Computer Graphics Proceedings of SIGGRAPH. 21, 283--291.
[24]
Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. ACM Trans. Graph. 24, 3, 1176--1185.
[25]
Segal, M. and Akeley, K. 2004. The OpenGL Graphics System: A Specification (Version 2.0---Oct.).
[26]
Sen, P. 2004. Silhouette maps for improved texture magnification. In Graphics Hardware. 65--74.
[27]
Sen, P., Cammarano, M., and Hanrahan, P. 2003. Shadow silhouette maps. ACM Trans. Graph. 22, 3, 521--526.
[28]
Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Proceedings of Graphics Hardware. ACM, 97--106.
[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]
Stamminger, M. and Drettakis, G. 2002. Perspective shadow maps. ACM Trans. Graph. 21, 3, 557--562.
[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]
Williams, L. 1978. Casting curved shadows on curved surfaces. In Computer Graphics Proceedings of SIGGRAPH. 12, 270--274.
[34]
Wimmer, M., Scherzer, D., and Purgathofer, W. 2004. Light space perspective shadow maps. In Eurographics Symposium on Rendering. 143--151.
[35]
Woo, A., Poulin, P., and Fournier, A. 1990. A survey of shadow algorithms. IEEE Comput. Graph. Appl. 10, 6 (Nov.), 13--32.

Cited By

View all
  • (2024)GigaVoxels DP: Starvation-Less Render and Production for Large and Detailed Volumetric Worlds WalkthroughProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753897:3(1-11)Online publication date: 9-Aug-2024
  • (2022)Real-time Modeling of Dynamic Terrain Shadows based on Multilevel Ray CastingProgramming and Computer Software10.1134/S036176882203010048:3(190-198)Online publication date: 30-May-2022
  • (2021)Non-overlapping geometric shadow mapComputers and Graphics10.1016/j.cag.2021.08.013101:C(59-71)Online publication date: 1-Dec-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 26, Issue 4
October 2007
139 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1289603
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2007
Published in TOG Volume 26, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GPGPU
  2. GPU
  3. Shadows
  4. adaptive shadow maps
  5. graphics hardware
  6. scan
  7. shadow maps

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)26
  • Downloads (Last 6 weeks)2
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)GigaVoxels DP: Starvation-Less Render and Production for Large and Detailed Volumetric Worlds WalkthroughProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753897:3(1-11)Online publication date: 9-Aug-2024
  • (2022)Real-time Modeling of Dynamic Terrain Shadows based on Multilevel Ray CastingProgramming and Computer Software10.1134/S036176882203010048:3(190-198)Online publication date: 30-May-2022
  • (2021)Non-overlapping geometric shadow mapComputers and Graphics10.1016/j.cag.2021.08.013101:C(59-71)Online publication date: 1-Dec-2021
  • (2018)Accurate Shadow Generation Analysis in Computer Graphics2018 IEEE 20th International Conference on High Performance Computing and Communications; IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2018.00186(1116-1120)Online publication date: Jun-2018
  • (2017)Euclidean Distance Transform Shadow MappingProceedings of the 43rd Graphics Interface Conference10.5555/3141475.3141510(171-180)Online publication date: 1-Jun-2017
  • (2017)Soft bilateral filtering shadows using multiple image-based algorithmsMultimedia Tools and Applications10.5555/3048787.304886076:2(2591-2608)Online publication date: 1-Jan-2017
  • (2017)Simplification of 3D Graphics for Mobile Devices3D Research10.1007/s13319-016-0111-x8:1(1-29)Online publication date: 1-Mar-2017
  • (2016)Soft bilateral filtering shadows using multiple image-based algorithmsMultimedia Tools and Applications10.1007/s11042-016-3254-076:2(2591-2608)Online publication date: 18-Jan-2016
  • (2016)Analysis of Hard Shadow Anti-aliasingAdvances in Computer Science and Ubiquitous Computing10.1007/978-981-10-3023-9_66(421-429)Online publication date: 23-Nov-2016
  • (2015)Real-time many-light management and shadows with clustered shadingACM SIGGRAPH 2015 Courses10.1145/2776880.2792712(1-398)Online publication date: 30-Jul-2015
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media