Skip to Main content Skip to Navigation
New interface
Conference papers

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 - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:14:45 PM
Last modification on : Friday, February 4, 2022 - 3:23:16 AM
Long-term archiving on: : Thursday, November 18, 2010 - 3:05:28 AM


Files produced by the author(s)


  • HAL Id : inria-00510094, version 1



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⟩



Record views


Files downloads