Robust Construction of the Three-Dimensional Flow Complex - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Robust Construction of the Three-Dimensional Flow Complex

Frédéric Cazals
Sylvain Pion

Résumé

The Delaunay triangulation and its dual the Voronoi diagram are ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and the Morse theory of distance functions. In particular, in the generic setting, algorithms have been proposed to compute the flow complex - the stable and unstable manifolds associated to the critical points of the distance function to a point set. As algorithms ignoring degenerate cases and numerical issues are bound to fail on general inputs, this paper develops the first complete and robust algorithm to compute the flow complex. First, we present complete algorithms for the flow operator, unraveling a delicate interplay between the degenerate cases of Delaunay and those which are flow specific. Second, we sketch how the flow operator unifies the construction of stable and unstable manifolds. Third, we discuss numerical issues related to predicates on cascaded constructions. Finally, we report experimental results with CGAL's filtered kernel, showing that the construction of the flow complex incurs a small overhead w.r.t. the Delaunay triangulation when moderate cascading occurs. These observations provide important insights on the relevance of the flow complex for (surface) reconstruction and medial axis approximation, and should foster flow complex based algorithms. In a broader perspective and to the best of our knowledge, this paper is the first one reporting on the effective implementation of a geometric algorithm featuring cascading.
Fichier principal
Vignette du fichier
socgfinal.pdf (427.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00344962 , version 1 (08-12-2008)

Identifiants

  • HAL Id : inria-00344962 , version 1

Citer

Frédéric Cazals, Aditya Parameswaran, Sylvain Pion. Robust Construction of the Three-Dimensional Flow Complex. ACM Symposium on Computational Geometry (SCG), Jun 2008, Washington, United States. ⟨inria-00344962⟩

Collections

INRIA INRIA2
238 Consultations
261 Téléchargements

Partager

Gmail Facebook X LinkedIn More