“Interactive shadow generation in complex environments”

We present a new algorithm for interactive generation of hard-edged, umbral shadows in complex environments with a moving light source. Our algorithm uses a hybrid approach that combines the image quality of object-precision methods with the efficiencies of image-precision techniques. We present an algorithm for computing a compact potentially visible set (PVS) using levels-of-detail (LODs) and visibility culling. We use the PVSs computed from both the eye and the light in a novel cross-culling algorithm that identifies a reduced set of potential shadow-casters and shadow-receivers. Finally, we use a combination of shadow-polygons and shadow maps to generate shadows. We also present techniques for LOD-selection to minimize possible artifacts arising from the use of LODs. Our algorithm can generate sharp shadow edges and reduces the aliasing in pure shadow map approaches. We have implemented the algorithm on a three-PC system with NVIDIA GeForce 4 cards. We achieve 7–25 frames per second in three complex environments composed of millions of triangles.

1. ANDUJAR, C., SAONA-VAZQUEZ, C., NAVAZO, I., AND BRUNET, P. 2000. Integrating occlusion culling and levels of detail through hardly-visibly sets. In Proceedings of Eurographics.Google Scholar
2. ATHERTON, P., WEILER, K., AND GREENBERG, D. 1978. Polygon shadow generation. In Computer Graphics (SIGGRAPH ’78 Proceedings), vol. 12, 275–281. Google Scholar
3. BAXTER, B., SUD, A., GOVINDARAJU, N., AND MANOCHA, D. 2002. Gigawalk: Interactive walkthrough of complex 3d environments. Proc. of Eurographics Workshop on Rendering. Google Scholar
4. BERGERON, P. 1985. Shadow volumes for non-planar polygons. In Graphics Interface ’85 Proceedings, 417–418.Google Scholar
5. BLINN, J. 1988. Jim blinn’s corner: Me and my (fake) shadow. IEEE Computer Graphics and Applications 8, 1 (Jan.), 82–86. Google ScholarDigital Library
6. BRABEC, S., ANNEN, T., AND SEIDEL, H. 2001. Hardware-accelerated rendering of antialiased shadows. In Proc. of Computer Graphics International. Google Scholar
7. BRABEC, S., ANNEN, T., AND SEIDEL, H. 2002. Shadow mapping for hemispherical and omnidirectional light sources. In Proc. of Computer Graphics International.Google Scholar
8. BROTMAN, L. S., AND BADLER, N. I. 1984. Generating soft shadows with a depth buffer algorithm. IEEE Computer Graphics and Applications 4, 10, 71–81.Google ScholarCross Ref
9. CHIN, N., AND FEINER, S. 1989. Near real-time shadow generation using BSP trees. In Computer Graphics (SIGGRAPH ’89 Proceedings), vol. 23, 99–106. Google Scholar
10. CHRYSANTHOU, Y., AND SLATER, M. 1995. Shadow volume BSP trees for computation of shadows in dynamic scenes. In 1995 Symposium on Interactive 3D Graphics, 45–50. Google Scholar
11. COHEN-OR, D., CHRYSANTHOU, Y., AND SILVA, C. 2001. A survey of visibility for walkthrough applications. SIGGRAPH Course Notes # 30.Google Scholar
12. CROW, F. 1977. Shadow algorithms for computer graphics. vol. 11, 242–248. Google Scholar
13. EL-SANA, J., SOKOLOVSKY, N., AND SILVA, C. 2001. Integrating occlusion culling with view-dependent rendering. Proc. of IEEE Visualization. Google Scholar
14. EVERITT, C., AND KILGARD, M. 2002. Practical and robust stenciled shadow volumes for hardware-accelerated rendering. In SIGGRAPH 2002 Course Notes, vol. 31.Google Scholar
15. FERNANDO, R., FERNANDEZ, S., BALA, K., AND GREENBERG, D. 2001. Adaptive shadow maps. In Proceedings of ACM SIGGRAPH 2001, 387–390. Google Scholar
16. GOVINDARAJU, N., SUD, A., YOON, S., AND MANOCHA, D. 2003. Interactive visibility culling in complex environments with occlusion-switches. Proc. of ACM Symposium on Interactive 3D Graphics. Google Scholar
17. HEIDMANN, T. 1991. Real shadows real time. IRIS Universal, 18.Google Scholar
18. HEIDRICH, W., AND SEIDEL, H. P. 1999. Realistic hardware-accelerated shading and lighting. In Proc. of ACM SIGGRAPH, 171–178. Google Scholar
19. LUEBKE, D., REDDY, M., COHEN, J., VARSHNEY, A., WATSON, B., AND HUEBNER, R. 2002. Level of Detail for 3D Graphics. Morgan-Kaufmann. Google Scholar
20. MCCOOL, M. 2000. Shadow volume reconstruction from depth maps. ACM Trans. on Graphics 19, 1, 1–26. Google ScholarDigital Library
21. PARKER, S., MARTIC, W., SLOAN, P., SHIRLEY, P., SMITS, B., AND HANSEN, C. 1999. Interactive ray tracing. Symposium on Interactive 3D Graphics. Google Scholar
22. REEVES, W., SALESIN, D., AND COOK, R. 1987. Rendering antialiased shadows with depth maps. In Computer Graphics (ACM SIGGRAPH ’87 Proceedings), vol. 21, 283–291. Google Scholar
23. SEGAL, M., KOROBKIN, C., VAN WIDENFELT, R., FORAN, J., AND HAEBERLI, P. 1992. Fast shadows and lighting effects using texture mapping. In Computer Graphics (SIGGRAPH ’92 Proceedings), vol. 26, 249–252. Google Scholar
24. STAMMINGER, M., AND DRETTAKIS, G. 2002. Perspective shadow maps. In Proceedings of ACM SIGGRAPH 2002, 557–562. Google Scholar
25. TADAMURA, K., QIN, X., JIAO, G., AND NAKAMAE, E. 2001. Rendering optimal solar shadows with plural sunlight depth buffers. The Visual Computer 17, 2.Google ScholarCross Ref
26. UDESHI, T., AND HANSEN, C. 1999. Towards interactive photorealistic rendering of indoor scenes: A hybrid approach. In Rendering Techniques ’99, D. Lischinski and G. W. Larson, Eds., 63–76. Google Scholar
27. VARADHAN, G., AND MANOCHA, D. 2002. Out-of-core rendering of massive geometric environments. Proc. of IEEE Visualization. Google Scholar
28. WALD, I., SLUSALLEK, P., AND BENTHIN, C. 2001. Interactive distributed ray-tracing of highly complex models. In Rendering Techniques, 274–285. Google Scholar
29. WANGER, L. 1992. The effect of shadow quality on the perception of spatial relationships in computer generated imagery. In Computer Graphics (1992 Symposium on Interactive 3D Graphics), vol. 25, 39–42. Google Scholar
30. WILLIAMS, L. 1978. Casting curved shadows on curved surfaces. In Computer Graphics (SIGGRAPH ’78 Proceedings), vol. 12, 270–274. Google Scholar
31. WOO, A., POULIN, P., AND FOURNIER, A. 1990. A survey of shadow algorithms. IEEE Computer Graphics and Applications 10, 6 (Nov.), 13–32. Google ScholarDigital Library
32. YOON, S., SALOMON, B., AND MANOCHA, D. 2003. Interactive view-dependent rendering with conservative occlusion culling in complex environments. Tech. Rep. TR03-015, Department of Computer Science, University of North Carolina.Google Scholar