Centroidal Voronoi Tesselation of Line Segments and Graphs

Lin Lu (1, 2) , Bruno Lévy (2) , Wenping Wang (1)

1 CSE - Department of Computer Science and Engineering [HKUST]
2 ALICE - Geometry and Lighting

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.

Mots clés: geometry processing; Lloyd relaxation; centroidal Voronoi diagram; triangular mesh; numerical geometry

Domaines: Géométrie algorithmique [cs.CG]

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