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

Frédo Durand 1 George Drettakis 1, * Claude Puech 1
* Auteur correspondant
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, 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.
Type de document :
Communication dans un congrès
ACMSIGGRAPH 97, 1997, Los angeles, United States. 12 p, 1997
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00510107
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:15:49
Dernière modification le : mercredi 11 avril 2018 - 01:53:49
Document(s) archivé(s) le : mardi 23 octobre 2012 - 12:25:50

Identifiants

  • HAL Id : inria-00510107, version 1

Collections

INRIA | UGA | IMAG

Citation

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, 1997. 〈inria-00510107〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

344