skip to main content
article

Guided visibility sampling

Published: 01 July 2006 Publication History

Abstract

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.

Supplementary Material

JPG File (p494-wonka-high.jpg)
JPG File (p494-wonka-low.jpg)
High Resolution (p494-wonka-high.mov)
Low Resolution (p494-wonka-low.mov)

References

[1]
Aila, T., and Miettinen, V. 2004. dPVS: An occlusion culling system for massive dynamic environments. IEEE Computer Graphics & Applications 24, 2.
[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.
[3]
Andujar, C., Saona, C., and Navazo, I. 2000. Lod visibility culling and occluder synthesis. Computer Aided Design 32, 13, 773 783.
[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.
[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.
[6]
Bittner, J. 2003. Hierarchical Techniques for Visibility Computations. PhD thesis, Czech Technical University in Prague.
[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.
[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.
[9]
Duguet, F., and Drettakis, G. 2002. Robust epsilon visibility. In Proc. ACM SIGGRAPH 2002, 567--575.
[10]
Durand, F., Drettakis, G., Thollot, J., and Puech, C. 2000. Conservative visibility preprocessing using extended projections. In Proc. ACM SIGGRAPH 2000, 239--248.
[11]
Durand, F. 1999. 3D Visibility: Analytical Study and Applications. PhD thesis, Universite Joseph Fourier, Grenoble, France.
[12]
Gotsman, C., Sudarsky, O., and Fayman, J. 1999. Optimized occlusion culling using five-dimensional subdivision. Computers and Graphics 5, 23, 645--654.
[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.
[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.
[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.
[16]
Levoy, M., and Hanrahan, P. 1996. Light field rendering. In Proc. ACM SIGGRAPH 96, 31--42.
[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.
[18]
Mcdermott, D., and Gelsey, A. 1987. Terrain analysis for tactical situation assessment. In Proceedings Spatial Reasoning and Multi-Sensor Fusion, 420--429.
[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.
[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.
[21]
Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM Philadelphia.
[22]
Nirenstein, S., and Blake, E. 2004. Hardware accelerated visibility preprocessing using adaptive sampling. In Rendering Techniques 2004, 207--216.
[23]
Nirenstein, S., Blake, E., and Gain, J. 2002. Exact from-region visibility culling. In Rendering Techniques 2002, 191--202.
[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.
[25]
Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. ACM Trans. on Graphics 24, 3, 1176--1185.
[26]
Sbert, M. 1993. An integral geometry method for fast form factor computation. Computer Graphics Forum 12, 3, C409-C420.
[27]
Schaufler, G., Dorsey, J., Decoret, X., and Sillion, F. 2000. Conservative volumetric visibility with occluder fusion. In Proc. ACM SIGGRAPH 2000, 229--238.
[28]
Shade, J., Gortler, S., Wei He, L., and Szeliski, R. 1998. Layered depth images. In Proc. ACM SIGGRAPH 98, 231--242.
[29]
Stuerzlinger, W. 1999. Imaging all visible surfaces. In Proc. Graphics Interface 1999, 115--122.
[30]
Teller, S. J., and Séquin, C. H. 1991. Visibility preprocessing for interactive walkthroughs. Computer Graphics (Proc. ACM SIGGRAPH 91) 25, 61--69.
[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.
[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.
[33]
Wilson, A., and Manocha, D. 2003. Simplifying complex environments using incremental textured depth meshes. ACM Transactions on Graphics 22, 3, 678--688.
[34]
Wonka, P., Wimmer, M., and Schmalstieg, D. 2000. Visibility preprocessing with occluder fusion for urban walkthroughs. In Rendering Techniques 2000. 71--82.
[35]
Wonka, P., Wimmer, M., and Sillion, F. 2001. Instant visibility. Computer Graphics Forum 20, 3, 411--421.
[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.

Cited By

View all
  • (2024)Efficient and Robust From-Point VisibilityIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.329113830:8(5313-5327)Online publication date: 1-Aug-2024
  • (2023)PVLI: potentially visible layered image for real-time ray tracingThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-023-03007-539:8(3359-3372)Online publication date: 28-Jul-2023
  • (2022)Probabilistic Occlusion Culling using Confidence Maps for High-Quality Rendering of Large Particle DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.311478828:1(573-582)Online publication date: 1-Jan-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 25, Issue 3
July 2006
742 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1141911
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2006
Published in TOG Volume 25, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. PVS
  2. occlusion culling
  3. visibility
  4. visibility sampling

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)2
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Efficient and Robust From-Point VisibilityIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.329113830:8(5313-5327)Online publication date: 1-Aug-2024
  • (2023)PVLI: potentially visible layered image for real-time ray tracingThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-023-03007-539:8(3359-3372)Online publication date: 28-Jul-2023
  • (2022)Probabilistic Occlusion Culling using Confidence Maps for High-Quality Rendering of Large Particle DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.311478828:1(573-582)Online publication date: 1-Jan-2022
  • (2021)Guided Visibility Sampling++Proceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34512664:1(1-16)Online publication date: 28-Apr-2021
  • (2017)Non-redundant rendering for efficient multi-view scene discretizationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-016-1300-633:12(1555-1569)Online publication date: 1-Dec-2017
  • (2012)Procedural Virtual WorldsVirtual Worlds and Metaverse Platforms10.4018/978-1-60960-854-5.ch002(16-32)Online publication date: 2012
  • (2012)Aggressive region-based visibility computation using importance samplingProceedings of the 11th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry10.1145/2407516.2407551(119-126)Online publication date: 2-Dec-2012
  • (2012)Bridging the gap between visual exploration and agent-based pedestrian simulation in a virtual environmentProceedings of the 18th ACM symposium on Virtual reality software and technology10.1145/2407336.2407339(9-16)Online publication date: 10-Dec-2012
  • (2012)Pseudo-Coloring Occlusion CullingAsiaSim 201210.1007/978-3-642-34387-2_37(323-331)Online publication date: 2012
  • (2011)Crepuscular Rays for Tumor Accessibility PlanningIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2011.18417:12(2163-2172)Online publication date: 1-Dec-2011
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media