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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00510094
Contributor : Team Evasion <>
Submitted on : Tuesday, August 17, 2010 - 3:14:45 PM
Last modification on : Wednesday, April 11, 2018 - 1:55:17 AM
Long-term archiving on : Thursday, November 18, 2010 - 3:05:28 AM

Files

acmcg97.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00510094⟩

Share

Metrics

Record views

131

Files downloads

202