Conservative visibility preprocessing using extended projections

ABSTRACT

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.

REFERENCES

• ACW+99: Daniel Aliaga , Jon Cohen , Andrew Wilson , Eric Baker , Hansong Zhang , Carl Erikson , Kenny Hoff , Tom Hudson , Wolfgang Stuerzlinger , Rui Bastos , Mary Whitton , Fred Brooks , Dinesh Manocha, MMR: an interactive massive model rendering system using geometric and image-based acceleration, Proceedings of the 1999 symposium on Interactive 3D graphics, p.199-206, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300554]
• ARB90: John M. Airey , John H. Rohlf , Frederick P. Brooks, Jr., Towards image realism with interactive update rates in complex virtual building environments, Proceedings of the 1990 symposium on Interactive 3D graphics, p.41-50, February 1990, Snowbird, Utah, United States
• CG85: Michael F. Cohen , Donald P. Greenberg, The hemi-cube: a radiosity solution for complex environments, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.31-40, Jul. 1985
• CH97: Deborah A. Carlson , Jessica K. Hodgins, Simulation levels of detail for real-time animation, Proceedings of the conference on Graphics interface '97, p.1-8, May 1997, Kelowna, British Columbia, Canada
• Cla76: James H. Clark, Hierarchical geometric models for visible surface algorithms, Communications of the ACM, v.19 n.10, p.547-554, Oct. 1976 [doi>10.1145/360349.360354]
• COFHZ98: 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.
• COZ98: D. Cohen-Or and E. Zadicario. Visibility streaming for network-based walkthroughs. In Graphics Interface, 1998.
• CT96: Satyan Coorg , Seth Teller, Temporally coherent conservative visibility, Selected papers from the 12th annual symposium on Computational Geometry, p.105-124, February 1999, Philadelphia, Pennsylvania, United States
• CT97: Satyan Coorg , Seth Teller, Real-time occlusion culling for models with large occluders, Proceedings of the 1997 symposium on Interactive 3D graphics, p.83-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253312]
• Dur99: Fr6do Durand. 3D Visibility, analysis and applications. PhD thesis, U. Joseph Fourier, Grenoble, 1999. http://www-imagis.imag, fr.
• FS93: Thomas A. Funkhouser , Carlo H. Séquin, Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.247-254, September 1993 [doi>10.1145/166117.166149]
• Fun95: Thomas A. Funkhouser, RING: a client-server system for multi-user virtual environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.85-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199418]
• Fun96: Thomas A. Funkhouser, Database management for interactive display of large architectural models, Proceedings of the conference on Graphics interface '96, p.1-8, May 1996, Toronto, Ontario, Canada
• GKM93: Ned Greene , Michael Kass , Gavin Miller, Hierarchical Z-buffer visibility, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.231-238, September 1993 [doi>10.1145/166117.166147]
• HMC+97: T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France [doi>10.1145/262839.262847]
• Jon71: C.B. Jones. A new approach to the 'hidden line' problem. The Computer Journal, 14(3):232-237, August 1971.
• LG95: David Luebke , Chris Georges, Portals and mirrors: simple, fast evaluation of potentially visible sets, Proceedings of the 1995 symposium on Interactive 3D graphics, p.105-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199422]
• LT99: Fei-Ah Law , Tiow-Seng Tan, Preprocessing occlusion for real-time selective refinement, Proceedings of the 1999 symposium on Interactive 3D graphics, p.47-53, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300528]
• Max91: Nelson Max, Unified sun and sky illumination for shadows under trees, CVGIP: Graphical Models and Image Processing, v.53 n.3, p.223-230, May 1991 [doi>10.1016/1049-9652(91)90044-K]
• PD90: Harry Plantinga , Charles R. Dyer, Visibility, occlusion, and the aspect graph, International Journal of Computer Vision, v.5 n.2, p.137-160, Nov. 1990 [doi>10.1007/BF00054919]
• RH94: John Rohlf , James Helman, IRIS performer: a high performance multiprocessing toolkit for real-time 3D graphics, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.381-394, July 1994 [doi>10.1145/192161.192262]
• SC96: O. Sudarsky and C.Gotsman. Output-sensitive visibility algorithms for dynamic scenes with applications to virtual reality. In Proc. Eurographics Conf., 1996.
• SDDS00: Gernot Schaufler , Julie Dorsey , Xavier Decoret , François X. Sillion, Conservative volumetric visibility with occluder fusion, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.229-238, July 2000 [doi>10.1145/344779.344886]
• SLSD96: Jonathan Shade , Dani Lischinski , David H. Salesin , Tony DeRose , John Snyder, Hierarchical image caching for accelerated walkthroughs of complex environments, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.75-82, August 1996 [doi>10.1145/237170.237209]
• SS98: Cyril Soler , François X. Sillion, Fast calculation of soft shadow textures using convolution, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.321-332, July 1998 [doi>10.1145/280814.280927]
• Ste97: A. James Stewart, Hierarchical Visibility in Terrains, Proceedings of the Eurographics Workshop on Rendering Techniques '97, p.217-228, June 16-18, 1997
• Tel92: Seth Jared Teller, Visibility computations in densely occluded polyhedral environments, University of California at Berkeley, Berkeley, CA, 1992
• TH93: Seth Teller , Pat Hanrahan, Global visibility algorithms for illumination computations, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.239-246, September 1993 [doi>10.1145/166117.166148]
• TS91: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.61-70, July 1991
• vdPS99: M. van de Panne and J. Stewart. Effective compression techniques for precomputed visibility. In Eurographics Workshop on Rendering, 1999.
• WBP98: Y. Wang, H. Bao, and Q. Peng. Accelerated walkthroughs of virtual environments based on visibility processing and simplification. In Proc. Eurographics Conf., 1998.
• WS99: P. Wonka and D. Schmalstieg. Occluder shadows for fast walkthroughs of urban environments. In Proc. Eurographics Conf., 1999.
• ZMHH97: Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997 [doi>10.1145/258734.258781]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
PVS, occlusion culling, visibility determination