Adaptive global visibility sampling

ABSTRACT

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.

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: 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
• 3: Bittner, J. 2003. Hierarchical Techniques for Visibility Computations. PhD thesis, Czech Technical University in Prague.
• 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.
• 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.
• 6: Florent Duguet , George Drettakis, Robust epsilon visibility, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 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: Philip Dutre , Kavita Bala , Philippe Bekaert, Advanced Global Illumination, A. K. Peters, Ltd., Natick, MA, 2002
• 9: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 10: Gotsman, C., Sudarsky, O., and Fayman, J. A. 1999. Optimized occlusion culling using five-dimensional subdivision. Computers and Graphics 23, 5, 645--654.
• 11: Hastings, A., 2007. Occlusion systems. Insomniac Games Tech Presentation. http://www.insomniacgames.com/tech/articles/1107/occlusion.php.
• 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.
• 13: 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
• 14: Samuli Laine, A general algorithm for output-sensitive visibility preprocessing, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053433]
• 15: Lepage, G. 1980. Vegas: An adaptive multidimensional integration program. Tech. Rep. CLNS-80/447, Cornell University.
• 16: 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]
• 17: Tommer Leyvand , Olga Sorkine , Daniel Cohen-Or, Ray space factorization for from-region visibility, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: Mattausch, O., Bittner, J., and Wimmer, M. 2006. Adaptive visibility-driven view cell construction. In Rendering Techniques '06, 195--206.
• 19: Mattausch, O., Bittner, J., and Wimmer, M. 2008. CHC++: Coherent hierarchical culling revisited. Computer Graphics Forum (Eurographics '08) 27, 3 (Apr.), 221--230.
• 20: Nirenstein, S., and Blake, E. 2004. Hardware accelerated visibility preprocessing using adaptive sampling. In Rendering Techniques '04, 207--216.
• 21: 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
• 22: Richard Pito, A Solution to the Next Best View Problem for Automated Surface Acquisition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.10, p.1016-1030, October 1999 [doi>10.1109/34.799908]
• 23: Alexander Reshetov , Alexei Soupikov , Jim Hurley, Multi-level ray tracing algorithm, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 24: 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]
• 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.
• 26: 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
• 27: Thompson, S. K., and Seber, G. A. F. 1996. Adaptive Sampling. Wiley.
• 28: van de Panne, M., and Stewart, A. J. 1999. Effective compression techniques for precomputed visibility. In Rendering Techniques '99, 305--316.
• 29: Eric Veach , Leonidas J. Guibas, Metropolis light transport, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.65-76, August 1997 [doi>10.1145/258734.258775]
• 30: Andrew Wilson , Dinesh Manocha, Simplifying complex environments using incremental textured depth meshes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 31: 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
• 32: Peter Wonka , Michael Wimmer , Kaichi Zhou , Stefan Maierhofer , Gerd Hesina , Alexander Reshetov, Guided visibility sampling, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006

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:
from-region visibility, visibility preprocessing