“Adaptive global visibility sampling” by Bittner, Mattausch, Wonka, Havran and Wimmer

In this paper we propose a global visibility algorithm which computes from-region visibility for all view cells simultaneously in a progressive manner. We cast rays to sample visibility interactions and use the information carried by a ray for all view cells it intersects. The main contribution of the paper is a set of adaptive sampling strategies based on ray mutations that exploit the spatial coherence of visibility. Our method achieves more than an order of magnitude speedup compared to per-view cell sampling. This provides a practical solution to visibility preprocessing and also enables a new type of interactive visibility analysis application, where it is possible to quickly inspect and modify a coarse global visibility solution that is constantly refined.

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. In Computer Graphics (1990 Symposium on Interactive 3D Graphics) 24, 2, 41–50. Google ScholarDigital Library
2. Bittner, J., Wonka, P., and Wimmer, M. 2001. Visibility preprocessing for urban scenes using line space subdivision. In Proc. of Pacific Graphics ’01, 276–284. Google ScholarDigital Library
3. Bittner, J. 2003. Hierarchical Techniques for Visibility Computations. PhD thesis, Czech Technical University in Prague.Google Scholar
4. 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 (Eurographics ’98) 17, 3, 243–254.Google Scholar
5. Cohen-Or, D., Chrysanthou, Y. L., Silva, C. T., and Durand, F. 2003. A survey of visibility for walkthrough applications. IEEE Trans. On Visualization and Computer Graphics 9, 3, 412–431. Google ScholarDigital Library
6. Duguet, F., and Drettakis, G. 2002. Robust epsilon visibility. ACM Transactions on Graphics 21, 3, 567–575. Google ScholarDigital Library
7. Durand, F., Drettakis, G., Thollot, J., and Puech, C. 2000. Conservative visibility preprocessing using extended projections. In Proc. of SIGGRAPH ’00, 239–248. Google ScholarDigital Library
8. Dutré, P., Bala, K., and Bekaert, P. 2003. Advanced Global Illumination. AK Peters. Google ScholarDigital Library
9. Goldberg, D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. Google ScholarDigital Library
10. Gotsman, C., Sudarsky, O., and Fayman, J. A. 1999. Optimized occlusion culling using five-dimensional subdivision. Computers and Graphics 23, 5, 645–654.Google ScholarCross Ref
11. Hastings, A., 2007. Occlusion systems. Insomniac Games Tech Presentation. http://www.insomniacgames.com/tech/articles/1107/occlusion.php.Google Scholar
12. Haumont, D., Mäkinen, O., and Nirenstein, S. 2005. A low dimensional framework for exact polygon-to-polygon occlusion queries. In Rendering Techniques ’05, 211–222. Google ScholarDigital Library
13. Koltun, V., Chrysanthou, Y., and Cohen-Or, C.-O. 2001. Hardware-accelerated from-region visibility using a dual ray space. In Rendering Techniques ’01, 205–216. Google ScholarDigital Library
14. Laine, S. 2005. A general algorithm for output-sensitive visibility preprocessing. In Proc. of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 31–40. Google ScholarDigital Library
15. Lepage, G. 1980. Vegas: An adaptive multidimensional integration program. Tech. Rep. CLNS-80/447, Cornell University.Google Scholar
16. Levoy, M., and Hanrahan, P. 1996. Light field rendering. In Proc. of SIGGRAPH ’96, 31–42. Google ScholarDigital Library
17. Leyvand, T., Sorkine, O., and Cohen-Or, D. 2003. Ray space factorization for from-region visibility. ACM Transactions on Graphics 22, 3, 595–604. Google ScholarDigital Library
18. Mattausch, O., Bittner, J., and Wimmer, M. 2006. Adaptive visibility-driven view cell construction. In Rendering Techniques ’06, 195–206. Google ScholarDigital Library
19. Mattausch, O., Bittner, J., and Wimmer, M. 2008. CHC++: Coherent hierarchical culling revisited. Computer Graphics Forum (Eurographics ’08) 27, 3 (Apr.), 221–230.Google Scholar
20. Nirenstein, S., and Blake, E. 2004. Hardware accelerated visibility preprocessing using adaptive sampling. In Rendering Techniques ’04, 207–216. Google ScholarDigital Library
21. Nirenstein, S., Blake, E., and Gain, J. 2002. Exact from-region visibility culling. In Rendering Techniques ’02, 191–202. Google ScholarDigital Library
22. Pito, R. 1999. A solution to the next best view problem for automated surface acquisition. IEEE Trans. Pattern Anal. Mach. Intell. 21, 10, 1016–1030. Google ScholarDigital Library
23. Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multilevel ray tracing algorithm. ACM Transactions on Graphics 24, 3, 1176–1185. Google ScholarDigital Library
24. Schaufler, G., Dorsey, J., Decoret, X., and Sillion, F. 2000. Conservative volumetric visibility with occluder fusion. In Proc. of SIGGRAPH ’00, 229–238. Google ScholarDigital Library
25. Shirley, P., Slusallek, P., Wald, I., Mark, B., Stoll, G., and Manocha, D. 2006. SIGGRAPH 2006 course 4, State of the art in interactive ray tracing.Google Scholar
26. Teller, S. J., and Séquin, C. H. 1991. Visibility preprocessing for interactive walkthroughs. In Computer Graphics (Proc. of SIGGRAPH ’91), 61–69. Google ScholarDigital Library
27. Thompson, S. K., and Seber, G. A. F. 1996. Adaptive Sampling. Wiley.Google Scholar
28. van de Panne, M., and Stewart, A. J. 1999. Effective compression techniques for precomputed visibility. In Rendering Techniques ’99, 305–316. Google ScholarDigital Library
29. Veach, E., and Guibas, L. J. 1997. Metropolis light transport. In Proc. of SIGGRAPH ’97, 65–76. Google ScholarDigital Library
30. Wilson, A., and Manocha, D. 2003. Simplifying complex environments using incremental textured depth meshes. ACM Transactions on Graphics 22, 3, 678–688. Google ScholarDigital Library
31. Wonka, P., Wimmer, M., and Schmalstieg, D. 2000. Visibility preprocessing with occluder fusion for urban walkthroughs. In Rendering Techniques ’00, 71–82. Google ScholarDigital Library
32. Wonka, P., Wimmer, M., Zhou, K., Maierhofer, S., Hesina, G., and Reshetov, A. 2006. Guided visibility sampling. ACM Transactions on Graphics 25, 3, 494–502. Google ScholarDigital Library