歐陽明臺灣大學：資訊工程學研究所Wu, Fu-CheFu-CheWu2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/53822Extracting 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.Table of Contents v Abstract vii 1 Introduction 1 1.1 Skeleton Related Application . . . . . . . . . . 1 1.2 Problem Analysis . . . . . . . . . . . . . . . . . 2 1.3 Proposed Solution . . . . . . . . . . . . . . . . .5 2 Previous Work 7 2.1 Medial Axis Transform Method . . . . . . . . . . . 8 2.2 Generalized Potential Field Method . . . . . . . . 9 2.3 Decomposition Based Method . . . . . . . . . . . . 12 3 Overview of DCG 14 3.1 Basic Concept .. . . . . . . . . . . . . . . . . . 14 3.2 General Procedure . . . . . . . . . . . . . . . . 18 3.3 Overview of Algorithm . . . . . . . . . . . . . . 19 4 Evaluation function 22 4.1 Surface Shrinking . .. . . . . . . . . . . . . . . 22 4.2 Radial Basis Function . .. . . . . . . . . . . . . 24 4.3 Repulsive Force Field . . . . . . . . . . . . . . 26 5 Radial Basis Function Based Approach 31 5.1 Skeletonization Algorithm . . . . . . . . . . . . 31 5.2 Property of Radial Basis Function . . . . . . . . 33 5.3 Results and Problems . . . . . . . . . . . . . . . 36 6 Initial Candidates 39 6.1 Voronoi Diagram . .. . . . . . . . . . . . . . . . 39 6.2 Domain Ball . .. . . . . . . . . . . . . . . . . . 40 7 Prong Feature Detection 44 7.1 Geodesic Distance . . . . . . . . . . . . . . . . 45 7.2 Watershed Algorithm . . .. . . . . . . . . . . . . 45 7.3 Refinement . . . . . . . . . . . . . . . . . . . . 50 8 Connection Construction 52 8.1 Joint Point Detection . . . . . . . . . . . . . . 52 8.2 Neighborhood Relationship . . . . . . .. . . . . . 53 8.3 Snake Algorithm . . . . . . . . . . . . . . . . . 57 9 Sketch Based Animation Editing 61 9.1 Motion Editing . . . . . . . . . . . . . . . . . . 61 9.2 Shape Deformation . . . . . .. . . . . . . . . . . 65 10 Results 73 10.1 Timing Analysis . . . . . . . . . . . . . . . . . 73 10.2 Complexity Analysis . . . . . . . . . . . . . . . 76 10.3 Future Work and Applications . . . . . . . . . . 77 11 Conclusion 88 Bibliography 90en-US骨幹中軸動畫區域連接圖skeletonMATanimationDCGthesis