“Ray space factorization for from-region visibility” by Leyvand, Sorkine-Hornung and Cohen-Or

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.

1. AIREY, J. M., ROHLF, J. H., AND BROOKS, JR., F. P. 1990. Towards image realism with interactive update rates in complex virtual building environments. Computer Graphics (1990 Symposium on Interactive 3D Graphics) 24, 2 (Mar.), 41–50. Google Scholar
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.Google Scholar
3. BITTNER, J., HAVRAN, V., AND SLAVIK, P. 1998. Hierarchical visibility culling with occlusion trees. In Proceedings of Computer Graphics International ’98, 207–219. Google Scholar
4. BITTNER, J., WONKA, P., AND WIMMER, M. 2001. Visibility preprocessing for urban scenes using line space subdivision. 9th Pacific Conference on Computer Graphics and Applications (October), 276–284. Google Scholar
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.Google ScholarCross Ref
6. COORG, S., AND TELLER, S. 1996. Temporally coherent conservative visibility. In Proc. 12th Annu. ACM Sympos. Comput. Geom., 78–87. Google Scholar
7. DURAND, F., DRETTAKIS, G., THOLLOT, J., AND PUECH, C. 2000. Conservative visibility preprocessing using extended projections. Proceedings of ACM SIGGRAPH 2000 (July), 239–248. Google ScholarDigital Library
8. DURAND, F. 1999. 3D Visibility: Analytical study and Applications. PhD thesis, Universite Joseph Fourier, Grenoble, France.Google Scholar
9. FUNKHOUSER, T. A., SÉQUIN, C. H., AND TELLER, S. J. 1992. Management of large amounts of data in interactive building walkthroughs. 1992 Symposium on Interactive 3D Graphics 25, 2 (March), 11–20. Google Scholar
10. GORTLER, S. J., GRZESZCZUK, R., SZELISKI, R., AND COHEN, M. F. 1996. The lumigraph. In Proceedings of ACM SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 43–54. Google Scholar
11. GOTSMAN, C., SUDARSKY, O., AND FAYMAN, J. 1999. Optimized occlusion culling. Computer & Graphics 23, 5, 645–654.Google ScholarCross Ref
12. GREENE, N., KASS, M., AND MILLER, G. 1993. Hierarchical z-buffer visibility. Proceedings of ACM SIGGRAPH 93, 231–240. Google Scholar
13. HUDSON, T., MANOCHA, D., COHEN, J., LIN, M., HOFF, K., AND ZHANG, H. 1997. Accelerated occlusion culling using shadow frustra. In Proc. 13th Annu. ACM Sympos. Comput. Geom., 1–10. Google Scholar
14. KLOSOWSKI, J., AND SILVA, C. 2001. Efficient conservative visibility culling using the prioritized-layered projection algorithm. IEEE Transactions on Visualization and Computer Graphics 7, 4. Google ScholarDigital Library
15. KOLTUN, V., CHRYSANTHOU, Y., AND COHEN-OR, D. 2000. Virtual occluders: An efficient intermediate PVS representation. Rendering Techniques 2000: 11th Eurographics Workshop on Rendering (June), 59–70. Google Scholar
16. KOLTUN, V., COHEN-OR, D., AND CHRYSANTHOU, Y. 2001. Hardware-accelerated from-region visibility using a dual ray space. Rendering Techniques 2001: 12th Eurographics Workshop on Rendering (June). Google Scholar
17. LEVOY, M., AND HANRAHAN, P. M. 1996. Light field rendering. In Proceedings of ACM SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 31–42. Google Scholar
18. MEISTERS, G. H. 1975. Polygons have ears. American Mathematical Monthly, 82, 648–751.Google ScholarCross Ref
19. NIRENSTEIN, S., BLAKE, E., AND GAIN, J. 2002. Exact from-region visibility culling. In Rendering Techniques 2002 (Proceedings of the 13th EUROGRAPHICS Workshop on Rendering, 199–210. Google Scholar
20. SAONA-VAZQUEZ, C., NAVAZO, I., AND BRUNET, P. 1999. The visibility octree: A data structure for 3D navigation. Computer & Graphics 23, 5.Google ScholarCross Ref
21. SCHAUFLER, G., DORSEY, J., DECORET, X., AND SILLION, F. X. 2000. Conservative volumetric visibility with occluder fusion. Proceedings of ACM SIGGRAPH 2000 (July), 229–238. Google ScholarDigital Library
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.Google Scholar
23. STANEKER, D., BARTZ, D., AND MEISSNER, M. 2002. Using occupancy maps for better occlusion query efficiency (Poster). In Eurographics Workshop on Rendering.Google Scholar
24. TELLER, S. J., AND SEQUIN, C. H. 1991. Visibility preprocessing for interactive walkthroughs. Computer Graphics (Proceedings of ACM SIGGRAPH 91) 25, 4, 61–69. Google Scholar
25. TELLER, S. J. 1992. Visibility Computations in Densely Occluded Environments. PhD thesis, University of California, Berkeley. Google Scholar
26. TELLER, S. J. 1992. Computing the antipenumbra of an area light source. Computer Graphics (Proceedings of ACM SIGGRAPH 92) 26, 2. Google Scholar
27. VIENNA. Available at http://www.cg.tuwien.ac.at/research/vr/urbanmodels/Google Scholar
28. WONKA, P., AND SCHMALSTIEG, D. 1999. Occluder shadows for fast walkthroughs of urban environments. In Computer Graphics Forum, vol. 18, 51–60.Google ScholarCross Ref
29. WONKA, P., WIMMER, M., AND SCHMALSTIEG, D. 2000. Visibility preprocessing with occluder fusion for urban walkthroughs. Rendering Techniques 2000: 11th Eurographics Workshop on Rendering, 71–82. Google Scholar
30. WONKA, P., WIMMER, M., AND SILLION, F. X. 2001. Instant visibility. In Computer Graphics Forum (Proc. of Eurographics ’01), vol. 20(3).Google Scholar
31. ZHANG, H., MANOCHA, D., HUDSON, T., AND HOFF III, K. E. 1997. Visibility culling using hierarchical occlusion maps. In Proceedings of ACM SIGGRAPH 97, 77–88. Google ScholarDigital Library