New interface

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

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 : 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].
Document type :
Conference papers
Domain :

Cited literature [6 references]

https://hal.inria.fr/inria-00510109
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:16:13 PM
Last modification on : Friday, February 4, 2022 - 3:21:46 AM
Long-term archiving on: : Thursday, November 18, 2010 - 3:06:31 AM

### Files

cccg97.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00510109, version 1

### 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. ⟨inria-00510109⟩

Record views