DOMAIN CONNECTED GRAPH: THE ESSENTIAL SKELETON OF A 3D SHAPE FOR ANIMATION

Abstract

Extracting skeleton from 3D objects is always an issue. Skeleton is not only a brief description of a 3D shape, it can also be used in many applications such as 3D object retrieval and articulated character animation. An ideal extraction method should be able to work on arbitrary shapes (concave, convex, or donut-like), be robust and efficient to compute, and above all, be able to generate visually satisfactory skeleton. We propose a novel approach based on Domain Connected Graph (DCG) to meet all the above criteria. Instead of using medial axis transform (MAT), our DCG based method automatically generates a set of significant points inside a 3D object which are domain points, and a skeleton is generated by connecting these domain points based on the topologic information of the boundary. To locate the domain points, a repulsion force model (1/rn , r =distance to boundary) is used to simulate the internal energy field contributed from the boundary shape. The constructed skeleton of DCG is a concise, stable and meaningful representation of a general 3D object, and can avoid the noise-sensitive problem encountered in MAT. Furthermore, there is no restriction on the types of 3D models, a problem often faced by the Radial Basis Function based approaches. Currently, the skeleton generated from a typical 3D model with 1000 to 10000 polygons takes less than 5 minutes on a Pentium IV 2.4 GHz PC.