Skip to Main content Skip to Navigation
New interface
Conference papers

The Visibility Skeleton: A Powerful and Multi-Purpose Global Visibility Tool

Frédo Durand 1 George Drettakis 1, * Claude Puech 1 
* Corresponding author
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, Inria Grenoble - Rhône-Alpes
Abstract : 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 contruction is presented, its implementation showing encouraging first results.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:15:49 PM
Last modification on : Friday, February 4, 2022 - 3:23:29 AM
Long-term archiving on: : Tuesday, October 23, 2012 - 12:25:50 PM


  • HAL Id : inria-00510107, version 1



Frédo Durand, George Drettakis, Claude Puech. The Visibility Skeleton: A Powerful and Multi-Purpose Global Visibility Tool. ACMSIGGRAPH 97, 1997, Los angeles, United States. 12 p. ⟨inria-00510107⟩



Record views


Files downloads