“The visibility skeleton: a powerful and efficient multi-purpose global visibility tool” by Durand, Drettakis and Puech

Many problems in computer graphics and computer vision require accurate global visibility information. Previous approaches have typically been complicated to implement and numerically unstable, and often too expensive in storage or computation. The Visibility Skeleton is a new powerful utility which can efficiently and accurately answer visibility queries for the entire scene. The Visibility Skeleton is a multi-purpose tool, which can solve numerous different problems. A simple construction algorithm is presented which only requires the use of well known computer graphics algorithmic components such as ray-casting and line/plane intersections. We provide an exhaustive catalogue of visual events which completely encode all possible visibility changes of a polygonal scene into a graph structure. The nodes of the graph are extremal stabbing lines, and the arcs are critical line swaths. Our implementation demonstrates the construction of the Visibility Skeleton for scenes of over a thousand polygons. We also show its use to compute exact visible boundaries of a vertex with respect to any polygon in the scene, the computation of global or on-the-fly discontinuity meshes by considering any scene polygon as a source, as well as the extraction of the exact blocker list between any polygon pair. The algorithm is shown to be manageable for the scenes tested, both in storage and in computation time. To address the potential complexity problems for large scenes, on-demand or lazy construction is presented, its implementation showing encouraging first results.

1. James Arvo and David B. Kirk. Fast ray tracing by ray classification. In Maureen C. Stone, editor, Computer Graphics (SIGGRAPH ’87 Proceedings), volume 21, pages 55-64, July 1987.
2. Daniel R. Baum, Holly E. Rushmeier, and James M. Winget. Improving radiosity solutions through the use of analytically determined tbrm-factors. Computer Graphics, 23(3):325-334, July 1989. Proceedings SIGGRAPH ’89 in Boston, USA.
3. Daniel R. Baum, John R. Wallace, Michael F. Cohen, and Donald P. Greenberg. The back-buffer algorithm : an extension of the radiosity method to dynamic environments. The Visual Computer, 2:298-306, 1986.
4. Michael F. Cohen and Donald P. Greenberg. The hemi-cube : A radiosity solution for complex environments. Computer Graphics, 19(3):31-40, July 1985. Proceedings SIGGRAPH ’85 in San Francisco (USA).
5. George Drettakis and Eugene Fiume. A fast shadow algorithm for area light sources using back projection. In Andrew Glassner, editor, SIGGRAPtt 94 Conference P1vceedings (Orlando, FL), Annual Conference Series, pages 223-230. ACM SIGGRAPH, July 1994.
6. George Drettakis and Francois Sillion. Accurate visibility and meshing calculations for hierarchical radiosity. In X. Pueyo and R Shr6der, editors, Rendering Techniques ’96, pages 269-279. Springer Verlag, June 1996. Proc. 7th EG Workshop on Rendering in Porto.
7. Fr6do Durand, George Drettakis, and Claude Puech. The 3d visibility complex, a new approach to the problems of accurate visibility. In X. Pueyo and R Shr6der, editors, Rendering Techniques ’96, pages 245-257. Springer Verlag, June 1996. Proc. 7th EG Workshop on Rendering in Porto.
8. David W. George, Frangois Sillion, and Donald R Greenberg. Radiosity redistribution for dynamic environments. IEEE Computer Graphics and Applications, 10(4), July 1990.
9. Ziv Gigus, John Canny, and Raimund Seidel. Efficiently computing and representing aspect graphs of polyhedral objects. IEEE Trans. on Pat. Matching & Mach. Intelligence, 13(6), June 1991.
10. Ziv Gigus and Jitendra Malik. Computing the aspect graph for the line drawings of polyhedral objects. IEEE Trans. on Pat. Matching & Mach. Intelligence, 12(2), February 1990.
11. Eric A. Haines. Shaft culling for efficient ray-traced radiosity. In Brunet and Jansen, editors, Photorealistic Rendering in Comp. Graphics, pages 122-138. Springer Verlag, 1993. Proc. 2nd EG Workshop on Rendering (Barcelona, 1991).
12. Pat Hanrahan, David Saltzman, and Larry Aupperle. A rapid hierarchical radiosity algorithm. Computer Graphics, 25(4):197-206, August 1991. SIG- GRAPH ’91 Las Vegas.
13. Stephen Hardt and Seth Teller. High-fidelity radiosity rendering at interactive rates. In X. Pueyo and R Shr6der, editors, Rendering Techniques ’96. Springer Verlag, June 1996. Proc. 7th EG Workshop on Rendering in Porto.
14. Paul Heckbert. Discontinuity meshing for radiosity. Third Emvgraphics Workshop on Rendering, pages 203-226, May 1992.
15. Michael Mc Kenna and Joseph O’Rourke. Arrangements of lines in space: A data structure with applications. In P~vc. 4th Annu. ACM Sympos. Comput. Geom., pages 371-380, 1988.
16. Dani Lischinski, Brian Smits, and Donald R Greenberg. Bounds and error estimates for radiosity. In Andrew S. Glassner, editor, SIGGRAPH 94 Conference P1vceedings (Orlando, FL), Annual Conference Series, pages 67-74. ACM SIG- GRAPH, July 1994.
17. Dani Lischinski, Filippo Tampieri, and Donald R Greenberg. Discontinuity meshing for accurate radiosity. IEEE Computer Graphics and Applications, 12(6):25-39, November 1992.
18. Dani Lischinski, Filippo Tampieri, and Donald R Greenberg. Combining hierarchical radiosity and discontinuity meshing. In Jim Kajiya, editor, SIGGRAPtt 93 Conference P1vceedings (Anaheim, CA), Annual Conference Series, pages 199- 208. ACM SIGGRAPH, August 1993.
19. Rachel Orti, St6phane Rivibre, Fr6do Durand, and Claude Puech. Radiosity for dynamic scenes in flatland with the visibility complex. In Jarek Rossignac and Frangois Sillion, editors, Computer Graphics Forum (P1vc. of Emvgraphics ’96), volume 16, pages 237-249, Poitiers, France, September 1996.
20. M. Pellegrini. Stabbing and ray shooting in 3-dimensional space. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 177-186, 1990.
21. H. Plantinga and C. R. Dyer. Visibility, occlusion, and the aspect graph. Internat. J. Comput. Vision, 5(2):137-160, 1990.
22. M. Pocchiola and G. Vegter. The visibility complex. 1996. special issue devoted to ACM-SoCG’93.
23. Erin Shaw. Hierarchical radiosity for dynamic environments. Master’s thesis, Comell University, Ithaca, NY, August 1994.
24. A. James Stewart and Sherif Ghali. Fast computation of shadow boundaries using spatial coherence and backprojections. In Andrew Glassner, editor, SIG- GRAPH 94 Conference P1vceedings (Orlando, FL), Annual Conference Series, pages 231-238. ACM SIGGRAPH, July 1994.
25. Filippo Tampieri. Discontinuity Meshing for Radiosity Image Synthesis. PhD thesis, Department of Computer Science, Comell University, Ithaca, New York, 1993. PhD Thesis.
26. Seth J. Teller. Computing the antipenumbra of an area light source. Computer Graphics, 26(4):139-148, July 1992. Proc. SIGGRAPH ’92 in Chicago.
27. Seth J. Teller and Patrick M. Hanrahan. Global visibility algorithms for illumination computations. In J. Kajiya, editor, SIGGRAPH 93 Conf. P1vc. (Anaheim), Annual Conf. Series, pages 239-246. ACM SIGGRAPH, August 1993.
28. Seth J. Teller and Michael E. Hohmeyer. Computing the lines piercing tour lines. Technical report, CS Dpt. UC Berkeley, 1991.
29. John R. Wallace, Kells A. Elmquist, and Eric A. Haines. A ray tracing algorithm for progressive radiosity. Computer Graphics, 23(3):315-324, July 1989. Proceedings SIGGRAPH ’89 in Boston.