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

  • ©Jiří Bittner, Oliver Mattausch, Peter Wonka, Vlastimil Havran, and Michael Wimmer




    Adaptive global visibility sampling



    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

ACM Digital Library Publication: