Dynamic visibility in polygonal scenes with the visibility complex - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1997

Dynamic visibility in polygonal scenes with the visibility complex

Résumé

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.
Fichier principal
Vignette du fichier
acmcg97.pdf (88.89 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00510094 , version 1 (17-08-2010)

Identifiants

  • HAL Id : inria-00510094 , version 1

Citer

Stéphane Rivière. Dynamic visibility in polygonal scenes with the visibility complex. 13th Annual ACM Symposium on Computational Geometry, 1997, Nice, France. ⟨inria-00510094⟩
62 Consultations
180 Téléchargements

Partager

Gmail Facebook X LinkedIn More