Ray space factorization for from-region visibility

ABSTRACT

From-region visibility culling is considered harder than from-point visibility culling, since it is inherently four-dimensional. We present a conservative occlusion culling method based on factorizing the 4D visibility problem into horizontal and vertical components. The visibility of the two components is solved asymmetrically: the horizontal component is based on a parameterization of the ray space, and the visibility of the vertical component is solved by incrementally merging umbrae. The technique is designed so that the horizontal and vertical operations can be efficiently realized together by modern graphics hardware. Similar to image-based from-point methods, we use an occlusion map to encode visibility; however, the image-space occlusion map is in the ray space rather than in the primal space. Our results show that the culling time and the size of the computed potentially visible set depend on the size of the viewcell. For moderate viewcells, conservative occlusion culling of large urban scenes takes less than a second, and the size of the potentially visible set is only about two times larger than the size of the exact visible set.

REFERENCES

• 1: 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
• 2: BITTNER, J., AND PRIKRYL, J. 2001. Exact regional visibility using line space partitioning. Tech. Rep. TR-186-2-01-06, Institute of Computer Graphics, Vienna University of Technology.
• 3: J. Bittner , V. Havran , P. Slavik, Hierarchical Visibility Culling with Occlusion Trees, Proceedings of the Computer Graphics International 1998, p.207, June 22-26, 1998
• 4: Jiri Bittner , Peter Wonka , Michael Wimmer, Visibility Preprocessing for Urban Scenes using Line Space Subdivision, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.276, October 16-18, 2001
• 5: COHEN-OR, D., FIBICH, G., HALPERIN, D., AND ZADICARIO, E. 1998. Conservative visibility and strong occlusion for viewspace partitioning of densely occluded scenes. Computer Graphics Forum 17, 3, 243--254.
• 6: Satyan Coorg , Seth Teller, Temporally coherent conservative visibility (extended abstract), Proceedings of the twelfth annual symposium on Computational geometry, p.78-87, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237242]
• 7: Frédo Durand , George Drettakis , Joëlle Thollot , Claude Puech, Conservative visibility preprocessing using extended projections, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.239-248, July 2000 [doi>10.1145/344779.344891]
• 8: DURAND, F. 1999. 3D Visibility: Analytical study and Applications. PhD thesis, Universite Joseph Fourier, Grenoble, France.
• 9: Thomas A. Funkhouser , Carlo H. Séquin , Seth J. Teller, Management of large amounts of data in interactive building walkthroughs, Proceedings of the 1992 symposium on Interactive 3D graphics, p.11-20, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147158]
• 10: Steven J. Gortler , Radek Grzeszczuk , Richard Szeliski , Michael F. Cohen, The lumigraph, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.43-54, August 1996 [doi>10.1145/237170.237200]
• 11: GOTSMAN, C., SUDARSKY, O., AND FAYMAN, J. 1999. Optimized occlusion culling. Computer & Graphics 23, 5, 645--654.
• 12: 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]
• 13: 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]
• 14: James T. Klosowski , Cláudio T. Silva, Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.4, p.365-379, October 2001 [doi>10.1109/2945.965350]
• 15: Vladlen Koltun , Yiorgos Chrysanthou , Daniel Cohen-Or, Virtual Occluders: An Efficient Intermediate PVS Representation, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.59-70, June 26-28, 2000
• 16: Vladlen Koltun , Yiorgos Chrysanthou , Daniel Cohen-Or, Hardware-Accelerated from-Region Visibility Using a Dual Ray Space, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.205-216, June 25-27, 2001
• 17: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 18: MEISTERS, G. H. 1975. Polygons have ears. American Mathematical Monthly, 82, 648--751.
• 19: S. Nirenstein , E. Blake , J. Gain, Exact from-region visibility culling, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 20: SAONA-VAZQUEZ, C., NAVAZO, I., AND BRUNET, P. 1999. The visibility octree: A data structure for 3D navigation. Computer & Graphics 23, 5.
• 21: 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]
• 22: SCOTT, N., OLSEN, D., AND GANNETT, E. 1998. An overview of the VISUALIZE fx Graphics Accelerator Hardware. The Hewlett-Packard Journal, May, 28--34.
• 23: STANEKER, D., BARTZ, D., AND MEISSNER, M. 2002. Using occupancy maps for better occlusion query efficiency (Poster). In Eurographics Workshop on Rendering.
• 24: 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
• 25: Seth Jared Teller, Visibility computations in densely occluded polyhedral environments, University of California at Berkeley, Berkeley, CA, 1992
• 26: Seth J. Teller, Computing the antipenumbra of an area light source, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.139-148, July 1992
• 27: VIENNA. Available at http://www.cg.tuwien.ac.at/research/vr/urbanmodels/
• 28: WONKA, P., AND SCHMALSTIEG, D. 1999. Occluder shadows for fast walkthroughs of urban environments. In Computer Graphics Forum, vol. 18, 51--60.
• 29: Peter Wonka , Michael Wimmer , Dieter Schmalstieg, Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.71-82, June 26-28, 2000
• 30: WONKA, P., WIMMER, M., AND SILLION, F. X. 2001. Instant visibility. In Computer Graphics Forum (Proc. of Eurographics '01), vol. 20(3).
• 31: 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
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Keywords:
PVS, dual space, hardware acceleration, line parameterization, occlusion culling, visibility