Predicates for line transversals to lines and line segments in three-dimensional space

Olivier Devillers 1 Marc Glisse 2 Sylvain Lazard 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
2 GIPSA-GPIG - GPIG
GIPSA-DIS - Département Images et Signal
3 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are ransversals to some edges of the polyhedra. In this paper we investigate predicates about visibility events arising in this context. Namely, we consider the predicates for counting the number of line transversals to lines and segments in 3D and the predicate for determining whether a line of sight is intersected by a triangle. We also consider a predicate that order these visibility events in the rotating plane-sweep algorithm of Brönnimann et al. (2007) We present a new approach for solving these predicates and show that the degree of the resulting procedures are significantly smaller than the naive approach based on Plücker coordinates. All the degrees are considered here in the Cartesian coordinates of the points defining the lines and segments. Precisely, we present a procedure of degree 12 (resp. 15) for determining the number of transversals to four (resp. five or more) segments. We present procedures of degree 15 for the occlusion predicate and of degree 36 for the ordering predicate. In comparison, the degree of the standard procedure based on the Plücker coordinates for solving these predicates range from 36 to 168 [Everett et al. 2006].
Type de document :
Communication dans un congrès
Monique Teillaud. 24th Annual Symposium on Computational Geometry (SoCG 2008), Jun 2008, College Park, Maryland, United States. ACM, pp.174-181, 2008, 〈10.1145/1377676.1377704〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00336256
Contributeur : Olivier Devillers <>
Soumis le : lundi 3 novembre 2008 - 13:03:38
Dernière modification le : samedi 28 juillet 2018 - 01:14:49
Document(s) archivé(s) le : mardi 9 octobre 2012 - 14:50:57

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Olivier Devillers, Marc Glisse, Sylvain Lazard. Predicates for line transversals to lines and line segments in three-dimensional space. Monique Teillaud. 24th Annual Symposium on Computational Geometry (SoCG 2008), Jun 2008, College Park, Maryland, United States. ACM, pp.174-181, 2008, 〈10.1145/1377676.1377704〉. 〈inria-00336256〉

Partager

Métriques

Consultations de la notice

545

Téléchargements de fichiers

194