“Conservative visibility preprocessing using extended projections” by Durand, Drettakis, Thollot and Puech

Visualization of very complex scenes can be significantly accelerated using occlusion culling. In this paper we present a visibility preprocessing method which efficiently computes potentially visible geometry for volumetric viewing cells. We introduce novel extended projection operators, which permits efficient and conservative occlusion culling with respect to all viewpoints within a cell, and takes into account the combined occlusion effect of multiple occluders. We use extended projection of occluders onto a set of projection planes to create extended occlusion maps; we show how to efficiently test occludees against these occlusion maps to determine occlusion with respect to the entire cell. We also present an improved projection operator for certain specific but important configurations. An important advantage of our approach is that we can re-project extended projections onto a series of projection planes (via an occlusion sweep), and accumulate occlusion information from multiple blockers. This new approach allows the creation of effective occlusion maps for previously hard-to-treat scenes such as leaves of trees in a forest. Graphics hardware is used to accelerate both the extended projection and reprojection operations. We present a complete implementation demonstrating significant speedup with respect to view-frustum culling only, without the computational overhead of on-line occlusion culling.

1. D. Aliaga, J. Cohen, A. Wilson, Eric Baker, H. Zhang, C. Erikson, K. Hoff, T. Hudson, W. Smerzlinger, R. Bastos, M. Whitton, F. Brooks, and D. Manocha. MMR: An interactive massive model rendering system using geometric and image-based acceleration. In ACM Syrup. on Interactive 3D Graphics, 1999.
2. J. Airey, J. Rohlf, and F. Brooks, Jr. Towards image realism with interactive update rates in complex virtual building environments. In ACM Syrup. on Interactive 3D Graphics, 1990.
3. M. Cohen and D. Greenberg. The hemicube: A radiosity solution for complex environments. In Computer Graphics (Proc. Siggraph), 1985.
4. D.A. Carlson and J. K. Hodgins. Simulation levels of detail for realtime animation. In Graphics Interface, 1997.
5. J.H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM, October 1976.
6. D. Cohen-Or, G. Fibich, D. Halperin, and E. Zadicario. Conservative visibility and strong occlusion for visibility partitionning of densely occluded scenes. In Eurographics, 1998.
7. D. Cohen-Or and E. Zadicario. Visibility streaming for network-based walkthroughs. In Graphics Interface, 1998.
8. S. Coorg and S. Teller. Temporally coherent conservative visibility. In ACM Symp. On Computational Geometry, 1996.
9. S. Coorg and S. Teller. Real-time occlusion culling for models with large occluders. In ACM Symp. on Interactive 3D Graphics, 1997.
10. Fr6do Durand. 3D Visibility, analysis and applications. PhD thesis, U. Joseph Fourier, Grenoble, 1999. http://www-imagis.imag, fr.
11. T. Funkhouser and C. S6quin. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. In Computer Graphics (Proc. Siggraph), 1993.
12. T. Funkhouser. RING – A client-server system for multi-user virtual environments. ACM Symp. on Interactive 3D Graphics, 1995.
13. T. Funkhouser. Database management for interactive display of large architectural models. In Graphics Interface, 1996.
14. N. Greene, M. Kass, and G. Miller. Hierarchical Z-buffer visibility. In Computer Graphics, (Proc. Siggraph), 1993.
15. T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang. Accelerated occlusion culling using shadow frusta. InACMSymp. on Computational Geometry, 1997.
16. C.B. Jones. A new approach to the ‘hidden line’ problem. The Computer Journal, 14(3):232-237, August 1971.
17. D. Luebke and C. Georges. Portals and mirrors: Simple, fast evaluation of potentially visible sets. In ACM Symp. on Interactive 3D Graphics, 1995.
18. F. Law and T. Tan. Preprocessing occlusion for real-time selective refinement. In ACM Symp. on Interactive 3D Graphics, 1999.
19. Max. Unified sun and sky illumination for shadows under trees. Comp. Vision, Graphics, and Image Processing. Graphical Models and Image Processing, 53(3):223-230, May 1991.
20. H. Plantinga and C. R. Dyer. Visibility, occlusion, and the aspect graph. Int. J. of Computer Vision, 5(2), 1990.
21. J. Rohlf and J. Helman. IRIS performer: A high performance multiprocessing toolkit for real-Time 3D graphics. In Computer Graphics (Proc. Siggraph), 1994.
22. O. Sudarsky and C.Gotsman. Output-sensitive visibility algorithms for dynamic scenes with applications to virtual reality. In Proc. Eurographics Conf., 1996.
23. G. Schaufler, J. Dorsey, X. Decoret, and F. Sillion. Conservative volumetric visibility with occluder fusion. In Computer Graphics (Proc. Siggraph), 2000.
24. J. Shade, D. Lischinski, D. Salesin, and T. DeRose. Hierarchical image caching for accelerated walkthroughs of complex environments. In Computer Graphics (Proc. Siggraph), 1996.
25. C. Soler and F. Sillion. Fast calculation of soft shadow textures using convolution. In Computer Graphics, (Proc. Siggraph), 1998.
26. A. James Stewart. Hierarchical visibility in terrains. Eurographics Workshop on Rendering 1997, June 1997.
27. S.J. Teller. Visibility Computations in Densely Occluded Polyhedral Environments. PhD thesis, UC Berkeley, 1992.
28. S. Teller and P. Hanrahan. Global visibility algorithms for illumination computations. In Computer Graphics (Proc. Siggraph), 1993.
29. S. Teller and C. S6quin. Visibility preprocessing for interactive walkthroughs. In Computer Graphics (Proc. Siggraph), 1991.
30. M. van de Panne and J. Stewart. Effective compression techniques for precomputed visibility. In Eurographics Workshop on Rendering, 1999.
31. Y. Wang, H. Bao, and Q. Peng. Accelerated walkthroughs of virtual environments based on visibility processing and simplification. In Proc. Eurographics Conf., 1998.
32. P. Wonka and D. Schmalstieg. Occluder shadows for fast walkthroughs of urban environments. In Proc. Eurographics Conf., 1999.
33. H. Zhang, D. Manocha, T. Hudson, and K. E. Hoff III. Visibility culling using hierarchical occlusion maps. In Computer Graphics (proc. Siggraph), 1997.