Skeleton Extraction by Mesh Contraction

ACM Transactions on Graphics (Proc. of SIGGRAPH 2008)


Extraction of curve-skeletons is a fundamental problem with many applications in computer graphics and visualization. In this paper, we present a simple and robust skeleton extraction method based on mesh contraction. The method works directly on the mesh domain, without pre-sampling the mesh model into a volumetric representation. The method first contracts the mesh geometry into a zero-volume skeletal shape by applying implicit Laplacian smoothing with global positional constraints. The contraction does not alter the mesh connectivity and retains the key features of the original mesh. The contracted mesh is then converted into a 1D curve-skeleton through a connectivity surgery process to remove all the collapsed faces while preserving the shape of the contracted mesh and the original topology. The centeredness of the skeleton is refined by exploiting the induced skeleton-mesh mapping. The contraction process generates valuable information about the object's geometry, in particular, the skeleton-vertex correspondence and the local thickness, which are useful for various applications. We demonstrate its effectiveness in mesh segmentation and skinning animation.


Top row: Neptune, dancer, feline, elephant, and elk. Bottom row: fertility, gargoyle, heptoroid and dancing children. Our method extracts good quality curve-skeletons for complex models, including high-genus models and flat regions (see the elk model).



We would like to thank the anonymous reviewers for their valuable comments, Yu-Shuen Wang for giving a talk at HKUST that inspired this work, Youyi Zheng for his help in implementing the segmentation application, and Carl Jantzen for providing the video voice over. This work was supported in part by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China (Project No: 620107), the National Science Council, Taiwan (NSC-96-2628-E-006-200-MY3), the Landmark Program of the NCKU Top University Project (Contract B0008), the Israeli Ministry of Science, and the Israel Science Foundation.


 author = {Au, Oscar Kin-Chung and Tai, Chiew-Lan and Chu, Hung-Kuo and Cohen-Or, Daniel and Lee, Tong-Yee},
 title = {Skeleton Extraction by Mesh Contraction},
 journal = {ACM Trans. Graph. (Proc. SIGGRAPH)},
 volume = {27},
 number = {3},
 year = {2008},
 pages = {44:1--44:10},
 articleno = {44},
 numpages = {10}