Centroidal Voronoi Tesselation of Line Segments and Graphs

Lin Lu 1, 2 Bruno Lévy 2 Wenping Wang 1
2 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Centroidal Voronoi Tesselation (CVT) of points has many applications in geometry processing, including re-meshing and segmentation to name but a few. In this paper, we propose a new extension of CVT, generalized to graphs. Given a graph and a 3D polygonal surface, our method optimizes the placement of the vertices of the graph in such a way that the graph segments best approximate the shape of the surface. We formulate the computation of CVT for graphs as a continuous variational problem, and present a simple approximated method to solve this problem. Our method is robust in the sense that it is independent of degeneracies in the input mesh, such as skinny triangles, T-junctions, small gaps or multiple connected components. We present some applications, to skeleton fitting and to shape segmentation.
Type de document :
Rapport
[Research Report] 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00600255
Contributeur : Bruno Levy <>
Soumis le : mardi 14 juin 2011 - 14:08:40
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 22:27:08

Fichier

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

Identifiants

  • HAL Id : inria-00600255, version 1

Collections

Citation

Lin Lu, Bruno Lévy, Wenping Wang. Centroidal Voronoi Tesselation of Line Segments and Graphs. [Research Report] 2009. 〈inria-00600255〉

Partager

Métriques

Consultations de la notice

244

Téléchargements de fichiers

337