Walking in the visibility complex with applications to visibility polygons and dynamic visibility

Stéphane Rivière 1
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, Inria Grenoble - Rhône-Alpes
Abstract : The visibility complex is a data structure that encodes all visibility relations between objects of a scene in the plane. However, in some applications only a subset of these informations is relevant at a time, in particular visibility informations about rays issued from (resp. going to) a given object O. We first consider the set of faces of the complex representing rays issued from a given object. We define an order on these faces and show, once the visibility complex is computed, how to visit all of them with no additional data structure in optimal time O(kf ), where kf is the number of faces visited. Then we show howto use this walk to perform a topological sweep of the vertices incident to these faces in optimal time O(kv), where kv is the number of these vertices, still with no additional data structure. We next consider the set of faces of the complex representing rays issued from the “blue sky” and passing through a line segment s which is outside the convex hull of the scene. We show that the previous algorithms can be adapted simply in this new context, and we use these walks for two applications. First, we show how to compute the visibility polygon of a line segment s = (p, q) outside the convex hull of the scene in O(vis(s)+tv(p)+tv(q)) time, where vis(s) is the size of the visibility polygon and tv(p) (resp. tv(q)) is the time to compute the view around p (resp. q). Second, we show how to maintain the view around a point moving from p to q. Once the view around p is computed, the algorithm has a total running time O(max(v(p), v(p, q))), where v(p) is the size of the view around p and v(p, q) the number of changes of visibility along (p, q). This algorithm is an alternative to those we have described in [Riv97b].
Type de document :
Communication dans un congrès
9th Canadian Conference on Computational Geometry (CCCG97), 1997, Kingston, Canada. 1997
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00510109
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:16:13
Dernière modification le : mercredi 11 avril 2018 - 01:55:22
Document(s) archivé(s) le : jeudi 18 novembre 2010 - 03:06:31

Fichiers

cccg97.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00510109, version 1

Collections

INRIA | UGA | IMAG

Citation

Stéphane Rivière. Walking in the visibility complex with applications to visibility polygons and dynamic visibility. 9th Canadian Conference on Computational Geometry (CCCG97), 1997, Kingston, Canada. 1997. 〈inria-00510109〉

Partager

Métriques

Consultations de la notice

191

Téléchargements de fichiers

149