“Conservative volumetric visibility with occluder fusion” by Schaufler, Dorsey, Décoret and Sillion

Visibility determination is a key requirement in a wide range of graphics algorithms. This paper introduces a new approach to the computation of volume visibility, the detection of occluded portions of space as seen from a given region. The method is conservative and classifies regions as occluded only when they are guaranteed to be invisible. It operates on a discrete representation of space and uses the opaque interior of objects as occluders. This choice of occluders facilitates their extension into adjacent opaque regions of space, in essence maximizing their size and impact. Our method efficiently detects and represents the regions of space hidden by such occluders. It is the first one to use the property that occluders can also be extended into empty space provided this space is itself occluded from the viewing volume. This proves extremely effective for computing the occlusion by a set of occluders, effectively realizing occluder fusion. An auxiliary data structure represents occlusion in the scene and can then be queried to answer volume visibility questions. We demonstrate the applicability to visibility preprocessing for real-time walkthroughs and to shadow-ray acceleration for extended light sources in ray tracing, with significant acceleration in both cases.

1. Airey, John M., John H. Rohlf and Frederick P. Brooks, Jr., “Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments,” Symposium on Interactive 3D Graphics 1990, pp 41-50.
2. Catmull, Edwin, E., Computer Display of Curved Surface, IEEE Conference on Computer Graphics, Pattern Recognition and Data Structures, May 1975, pp 11-17.
3. Chin, Norman and Steven Feiner, Fast Object-Precision Shadow Generation for Area Light Sources Using BSP Trees, Symposium on Interactive Graphics (1992), pp 21-30.
4. Coorg, Satyan and Seth Teller, Temporally Coherent Conservative Visibility, Proc. Twelfth Annual ACM Symposium on Computational Geometry, Philadelphia, PA, May 24-26, 1996, pp 78-87.
5. Cohen-Or, Daniel and Amit Shaked, Visibility and Dead- Zones in Digital Terrain Maps, EUROGRAPHICS ’95 14 3 (1995) pp 171-180.
6. Cohen-Or, D., G. Fibich, D. Halperin and E. Zadicario, Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes, Computer Graphics Forum, 17 (3) 1998, pp 243-253.
7. Chrysanthou, Y., D. Cohen-Or, and D. Lischinski, Fast Approximate Quantitative Visibility for Complex Scenes, Computer Graphics International ’98, June 1998, pp 220-229.
8. Drettakis George, Fiume Eugene L., A Fast Shadow Algorithm for Area Light Sources Using Backprojection, SIG- GRAPH 94, pp 223-230.
9. Durand, Fredo, George Drettakis and Claude Puech, The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tool, SIGGRAPH 97, pp 89-100.
10. Durand, Fredo, 3D Visibility: Analytical Study and Applications, PhD Dissertation, Universite Joseph Fournier, Grenoble, France.
11. Durand, Fredo, George Drettakis, Joelle Thollot and Claude Puech, Conservative Visibility Preprocessing using Extended Projections, SIGGRAPH 2000.
12. Foley, James, Andries van Dam, Steven Feiner and John Hughes, Computer Graphics: Principles and Practice, Addison-Wesley Publishing Co., ISBN 0-201-12110-7, 1990.
13. Greene, Ned Approximating Visibility with Environment Maps, Graphics Interface ’86, pp 108-114.
14. Greene, Ned, Michael Kass and Gavin Miller, Hierarchical Z-Buffer Visibility, SIGGRAPH 93, pp 231-238.
15. Haines, A. Eric and Donald P. Greenberg, The Light Buffer: A Ray Tracer Shadow Testing Accelerator, IEEE Computer Graphics and Applications, 6 9, 1986, pp 6-16.
16. Haines, A. Eric and John R. Wallace, Shaft Culling for Efficient Ray Cast Radiosity, Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering), Springer-Verlag, New York, 1994, pp 122-138.
17. Hart, David, Philip Dutre and Donald P. Greenberg, Direct Illumination with Lazy Visibility Evaluation, SIGGRAPH 99, pp 147-154.
18. Hudson, Tom, Dinesh Manocha, Jonathan Cohen, Ming Lin, Kenneth E. Hoff III, Hansong Zhang, Occlusion Culling using Shadow Volumes, Proceedings of 13th Symposium on Computational Geometry, Nice, France, June 4-6 1997, pp 1- 10.
19. Murali T.M., and Thomas A. Funkhouser, Consistent Solid and Boundary Representations from Arbitrary Polygonal Data, Symposium on Interactive 3D Graphics), 1997, pp 155-162.
20. Plantinga, Harry. and Charles Dyer, Visibility, Occlusion and the Aspect Graph, International Journal of Computer Vision, 5(2) 1990, pp 137-160.
21. Saona-Vazquez, Carlos, Isabel Navazo and Pere Brunet, The Visibility Octree. A Data Structure for 3D Navigation, TR LSI-99-22-R, Universitat Politecnica de Catalunya, Spain.
22. Samet, Hanan, “Applications of Spatial Data Structures, Addison-Wesley, Reading, MA, ISBN 0-201-50300-X, 1990.
23. Stewart, James and S. Ghali, Fast computation of shadow boundaries using spatial coherence and backprojections, SIGGRAPH 94, pp 231-238.
24. Stewart, James, Hierarchical Visibility in Terrains, Eurographics Rendering Workshop, June 1997, pp 217-228.
25. Tanaka, Toshimitsu, and Tokiichiro Takahashi, Fast Analytic Shading and Shadowing for Area Light Sources, Computer Graphics Forum, Vol. 16, 3, 1997, pp 231-240.
26. Teller, Seth J. and Carlo H. Sequin, Visibility Preprocessing For Interactive Walkthroughs SIGGRAPH 91, pp 61-69.
27. Teller, Seth, Computing the Antipenumbra of an Area Light Source, SIGGRAPH 92, pp 139-148.
28. Teller, Seth, and Pat Hanrahan, Global Visibility Algorithms for Illumination Computation, SIGGRAPH 94, pp 443-450.
29. Ward, Gregory J. and Paul Heckbert, Irradiance Gradients, Third Eurographics Workshop on Rendering, May 1992, pp 85-98.
30. Woo, Andrew and John Amanatides, Voxel Occlusion Testing: A Shadow Determination Accelerator for Ray Tracing, Graphics Interface ’90, pp 213-219.
31. Yagel, Roni, and William Ray, Visibility Computation for Efficient Walkthrough of Complex Environments, PRESENCE, Vol.5, No. 1, Winter 1996, pp 1-16.
32. Zhang, Hansong, Dinesh Manocha, Tom Hudson and Kenneth E. Hoff, Visibility Culling using Hierarchical Occlusion Maps, SIGGRAPH 97, pp 77-88.