“Interactive shadow generation in complex environments”

  • ©Naga Govindaraju, Sung-Eui Yoon, Avneesh Sud, and Dinesh Manocha




    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

ACM Digital Library Publication:

Overview Page: