Centroidal Voronoi Tesselation of Line Segments and Graphs for Variational Skeleton Fitting.

Linda Lu and Bruno Levy and Wenping Wang. ( 2009 )
in: Proc. 29th Gocad Meeting, Nancy

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.

Download / Links

BibTeX Reference

@inproceedings{LuGM2009,
 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. },
 author = { Lu, Linda AND Levy, Bruno AND Wang, Wenping },
 booktitle = { Proc. 29th Gocad Meeting, Nancy },
 title = { Centroidal Voronoi Tesselation of Line Segments and Graphs for Variational Skeleton Fitting. },
 year = { 2009 }
}