Dynamic visibility in polygonal scenes with the visibility complex

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 : This paper proposes methods for efficient maintaining of the view around a point (i.e., the visibility polygon) in static and dynamic polygonal scenes in the plane. The algorithms presented use the visibility complex, that we have adapted for polygonal scenes (composed of disjoint simple polygons) to take advantage of the spatial and temporal coherence. The first algorithm shows how to maintain the view around a moving point in O(log2 v) time at each visibility change (v: current size of the view), improving the O(log2 n) time bound (n: number of polygon vertices) of [GS96], and is well-suited for small consecutive moves. The second algo- rithm maintains the view around a point moving along a known trajectory: After a preprocessing in O(v log v) time, the view is updated in O(log v) time at each change of visibil- ity. Finally, we show how to maintain the visibility complex for a dynamic scene (i.e., a scene in which the polygon ver- tices are moving) and how to maintain the view around a moving point in a dynamic scene.
Type de document :
Communication dans un congrès
13th Annual ACM Symposium on Computational Geometry, 1997, Nice, France. 1997
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00510094
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:14:45
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : jeudi 18 novembre 2010 - 03:05:28

Fichiers

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

Identifiants

  • HAL Id : inria-00510094, version 1

Collections

INRIA | UGA | IMAG

Citation

Stéphane Rivière. Dynamic visibility in polygonal scenes with the visibility complex. 13th Annual ACM Symposium on Computational Geometry, 1997, Nice, France. 1997. 〈inria-00510094〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

89