Skip to Main content Skip to Navigation
Conference papers

Topologically sweeping the visibility complex of polygonal scenes

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 : In order to do efficient visibility computations in the plane, one must deal with maximal free line segments, that is line segments of maximal length in free space. To that end, [PV93b] introduce, for scene of convex curved objects, a new data structure, the visibility comp~ex, whose elements represent classes of maximal free segments having the same visibilities. In particular the visibility complex contains the visibility graph. We have studied the visibility complex for general polygonal scenes, and have devised an algorithm for topologically sweeping the visibility complex (and so for computing the visibility graph with the same complexity) in optimal time O(n log n + m) and optimal space O(n), where n is the total number of polygon vertices, and m the size of the visibility graph. Since it is a sweep algorithm, it improves the space storage of [GM87] for computing the visibility graph of polygonal scenes. Moreover, we have implemented our algorithm and we have made experimental comparisons with two other sweep algorithms for computing visibility graphs : the algorithm of [OW88] and the algorithm of [PV93a], which both run in time O(m log n). They were tested on scenes composed of line segments. We see that the gain due to the suppression of the logarithmic cost is significant.
Document type :
Conference papers
Complete list of metadata
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:18:45 PM
Last modification on : Friday, February 4, 2022 - 3:18:19 AM


  • HAL Id : inria-00510135, version 1



Stéphane Rivière. Topologically sweeping the visibility complex of polygonal scenes. 11th Annual ACM Symposium on Computational Geometry, 1995, Vancouver, Canada. pp.436--437. ⟨inria-00510135⟩



Record views