“Guided visibility sampling” by Wonka, Wimmer, Zhou, Maierhofer, Hesina, et al. …

This paper addresses the problem of computing the triangles visible from a region in space. The proposed aggressive visibility solution is based on stochastic ray shooting and can take any triangular model as input. We do not rely on connectivity information, volumetric occluders, or the availability of large occluders, and can therefore process any given input scene. The proposed algorithm is practically memoryless, thereby alleviating the large memory consumption problems prevalent in several previous algorithms. The strategy of our algorithm is to use ray mutations in ray space to cast rays that are likely to sample new triangles. Our algorithm improves the sampling efficiency of previous work by over two orders of magnitude.

1. Aila, T., and Miettinen, V. 2004. dPVS: An occlusion culling system for massive dynamic environments. IEEE Computer Graphics & Applications 24, 2. Google ScholarDigital Library
2. 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), vol. 24, 41–50. Google ScholarDigital Library
3. Andujar, C., Saona, C., and Navazo, I. 2000. Lod visibility culling and occluder synthesis. Computer Aided Design 32, 13, 773 783.Google ScholarCross Ref
4. Bittner, J., Wonka, R, and Wimmer, M. 2001. Visibility preprocessing for urban scenes using line space subdivision. In Proc. of Pacific Graphics 2001, 276–284. Google ScholarDigital Library
5. Bittner, J. 2002. Efficient construction of visibility maps using approximate occlusion sweep. In SCCG ’02: Proceedings of the 18th spring conference on Computer graphics, 167–175. Google ScholarDigital Library
6. Bittner, J. 2003. Hierarchical Techniques for Visibility Computations. PhD thesis, Czech Technical University in Prague.Google Scholar
7. Chhugani, J., Purnomo, B., Krishnan, S., Cohen, J., Venkata-Subramanian, S., and Johnson, D. S. 2005. vLOD: High-fidelity walkthrough of large virtual environments. IEEE Trans. on Visualization and Computer Graphics 11, 1, 35–47. Google ScholarDigital Library
8. 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
9. Duguet, F., and Drettakis, G. 2002. Robust epsilon visibility. In Proc. ACM SIGGRAPH 2002, 567–575. Google ScholarDigital Library
10. Durand, F., Drettakis, G., Thollot, J., and Puech, C. 2000. Conservative visibility preprocessing using extended projections. In Proc. ACM SIGGRAPH 2000, 239–248. Google ScholarDigital Library
11. Durand, F. 1999. 3D Visibility: Analytical Study and Applications. PhD thesis, Universite Joseph Fourier, Grenoble, France.Google Scholar
12. Gotsman, C., Sudarsky, O., and Fayman, J. 1999. Optimized occlusion culling using five-dimensional subdivision. Computers and Graphics 5, 23, 645–654.Google ScholarCross Ref
13. Haumont, D., Mäkinen, O., and Nirenstein, S. 2005. A low dimensional framework for exact polygon-to-polygon occlusion queries. In Proc. Eurographics Symposium on Rendering, 211–222. Google ScholarDigital Library
14. Jeschke, S., Wimmer, M., Schumann, H., and Purgathofer, W. 2005. Automatic impostor placement for guaranteed frame rates and low memory requirements. In Proc. of ACM SIGGRAPH Symp. on Interactive 3D Graphics and Games, 103–110. Google ScholarDigital Library
15. Koltun, V., Chrysanthou, Y., and Cohen-Or, C.-O. 2001. Hardware-accelerated from-region visibility using a dual ray space. In Rendering Techniques 2001, 205–216. Google ScholarDigital Library
16. Levoy, M., and Hanrahan, P. 1996. Light field rendering. In Proc. ACM 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. Mcdermott, D., and Gelsey, A. 1987. Terrain analysis for tactical situation assessment. In Proceedings Spatial Reasoning and Multi-Sensor Fusion, 420–429.Google Scholar
19. Mora, F., Aveneau, L., and Mériaux, M. 2005. Coherent and exact polygon-to-polygon visibility. In Proceedings of Winter School on Computer Graphics 2005, 87–94.Google Scholar
20. Müller, P., Wonka, P., Hägler, S., Ulmer, A., and Gool, L. V. 2006. Procedural modeling of buildings. ACM Transactions on Graphics 25, 3. Google ScholarDigital Library
21. Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM Philadelphia. Google ScholarDigital Library
22. Nirenstein, S., and Blake, E. 2004. Hardware accelerated visibility preprocessing using adaptive sampling. In Rendering Techniques 2004, 207–216. Google ScholarDigital Library
23. Nirenstein, S., Blake, E., and Gain, J. 2002. Exact from-region visibility culling. In Rendering Techniques 2002, 191–202. Google ScholarDigital Library
24. 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
25. Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. ACM Trans. on Graphics 24, 3, 1176–1185. Google ScholarDigital Library
26. Sbert, M. 1993. An integral geometry method for fast form factor computation. Computer Graphics Forum 12, 3, C409-C420.Google ScholarCross Ref
27. Schaufler, G., Dorsey, J., Decoret, X., and Sillion, F. 2000. Conservative volumetric visibility with occluder fusion. In Proc. ACM SIGGRAPH 2000, 229–238. Google ScholarDigital Library
28. Shade, J., Gortler, S., Wei He, L., and Szeliski, R. 1998. Layered depth images. In Proc. ACM SIGGRAPH 98, 231–242. Google ScholarDigital Library
29. Stuerzlinger, W. 1999. Imaging all visible surfaces. In Proc. Graphics Interface 1999, 115–122. Google ScholarDigital Library
30. Teller, S. J., and Séquin, C. H. 1991. Visibility preprocessing for interactive walkthroughs. Computer Graphics (Proc. ACM SIGGRAPH 91) 25, 61–69. Google ScholarDigital Library
31. Wald, I., Purcell, T. J., Schmittler, J., Benthin, C., and Slusallek, P. 2003. Realtime ray tracing and its use for interactive global illumination. In Eurographics State of the Art Reports. Google ScholarDigital Library
32. Wald, I., Dietrich, A., and Slusallek, P. 2004. An interactive out-of-core rendering framework for visualizing massively complex models. In Rendering Techniques 2004, 81–92. Google ScholarDigital Library
33. 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
34. Wonka, P., Wimmer, M., and Schmalstieg, D. 2000. Visibility preprocessing with occluder fusion for urban walkthroughs. In Rendering Techniques 2000. 71–82. Google ScholarDigital Library
35. Wonka, P., Wimmer, M., and Sillion, F. 2001. Instant visibility. Computer Graphics Forum 20, 3, 411–421.Google ScholarCross Ref
36. Woop, S., Schmittler, J., and Slusallek, P. 2005. RPU: a programmable ray processing unit for realtime ray tracing. ACM Transactions on Graphics 24, 3. 434–444. Google ScholarDigital Library