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 - Graphisme, Vision et Robotique, 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.
Type de document :
Communication dans un congrès
11th Annual ACM Symposium on Computational Geometry, 1995, Vancouver, Canada. pp.436--437, 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00510135
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:18:45
Dernière modification le : mercredi 11 avril 2018 - 01:55:01

Identifiants

  • HAL Id : inria-00510135, version 1

Collections

Citation

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, 1995. 〈inria-00510135〉

Partager

Métriques

Consultations de la notice

66