在我們進行電腦圖學的各種高階應用之前，如compatible參數化、morph或骨架建立。我們常常需要對三維模型進行一個基礎分析，藉由分析了解模型的幾何特徵，分塊特徵，動畫特徵等等。有了這些特徵我們對於模型內的資訊或是模型間的對應就能夠了解，而這些模型內的資訊及模型間的對應在處理一個三維模型扮演著關鍵的角色。

　　本論文利用模型的突出型態、模型的幾何特徵與使用者要求的特徵來達成近似人類視覺化的切割。本論文演算法主要先建立起模型突出端點的資訊，以建立三維模型主要且基本的拓樸架構。接著由各種不同的幾何特徵﹙如曲率，表面距離﹚描述出局部變化的各種數值以建立起較為精準的切割，我們利用這些局部的幾何資訊計算出符合使用者特徵點之間最佳的切割位置，讓每個切塊有著最大的區分性。由上述演算法，我們希望模型切割的最後結果能夠將模型切割為有意義的區塊，使我們能夠更精準的描述整個模型。

　In computer graphics, mesh decomposition is a fundamental problem and it can benefit many applications including texture mapping, surface parameterization, morphing, shape matching/retrieval and modeling by parts, animation compression. In this thesis, we propose a novel algorithm called controllable mesh decomposition and also present its application to skeleton extraction of models/animation. The proposed method is based on Reeb-graph data structure to represent topology information for a given 3D model. Before reconstructing this topological data structure, we automatically compute salient features called protrusion degree on models using geodesic distance. Then, we build a constrained Reeb-graph where each leaf node only contains one salient feature. Sometimes, user would like the mesh decomposition to be controllable, i.e., user can give some hints. For this reason, the proposed scheme allows several user-specified points on models and we present a coloring scheme to paint each possible segmented part of models. With the combination of both a constrained Reeb-graph and a coloring scheme, the proposed scheme automatically partitions models into several meaningful parts. However, due to discrete property of mesh models, the cutting boundary may be not ideally smooth. We can further smooth boundary using a minimum-cut-maximum-flow and a snake algorithm. Finally, we experimentally evaluate the proposed method against a variety of 3D models. Furthermore, we also demonstrate its usefulness to skeleton extraction. With a good extracted skeleton, we can animate 3D models by mean of modifying the skeletons.

[1] S. C. Cheng, “Region-growing approach to colour segmentation using 3-D clustering and relaxation labeling,” IEE Proc.-Vis. Image Signal Process., Vol. 150, N0. 4, pp. 270-276, August 2003.

[2] Sheng-Yao Cho and Bing-Yu Chen. “Constructing Scalable 3D Animated Model by Deformation Sensitive Simplification.” Proceedings of 2004 Workshop on Computer Graphics, National Tsing Hua University, Hsinchu, Taiwan, 2004.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein “Introduction to Algorithms” Second Edition.

[4] Thomas Funkhouser, Michael Kazhdan, Philip Shilane, Patrick Min, William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David Dobkin ,”Modeling by Example” ACM Transactions on Graphics (SIGGRAPH 2004), Los Angeles, CA, August 2004.

[5] Lavoué Guillaume., Dupont F., Baskurt A. “Constant Curvature Region Decomposition of 3D-Meshes by a Mixed Approach Vertex-Triangle”, Journal of WSCG Vol.12, No.1-3, ISSN 1213-, WSCG’2004, February 2-6, 2004.

[6] Michael Garland, Andrew Willmott, Paul S. Heckbert, “Hierarchical Face Clustering on Polygonal Surfaces” Proceedings of the 2001 Symposium on Interactive 3D Graphics Pages 49-58, 2001.

[7] Natasha Gelfand and Leonidas J. Guibas “Shape Segmentation Using Local Slippage Analysis” Symposium on Geometry Processing, 2004

[8] D.D.Hoffman and M.Singh, “Salience of Visual Parts,” Cognition, vol. 63, pp. 29-78, 1997.

[9] Yi-Ping Hung, Yu-Pao Tsai, Chih-Chuan Lai “A Bayesian Approach to Video Object Segmentation via Merging 3D Watershed Volumes.” ICPR (1): 496-499, 2002.

[10] Huang Jiangbing, Menq ChiaHsiang. “Automatic data segmentation for geometric feature extraction from unorganized 3-D coordinate points” [J]. IEEE Transactions on Robotics and Automation, 17(3): 268～279 , 2001 .

[11] M. Kass, A. Witkin, and D. Terzopoulos “Snakes: Active Contour Models” 1998.

[12] Sagi Katz, Ayellet Tal “Hierarchical mesh decomposition using fuzzy clustering and cuts.” ACM Trans. Graph. 22(3): 954-961 , 2003 .

[13] Longin Jan Latecki, Rolf Lakämper “Shape Similarity Measure Based on Correspondence of Visual Parts.” IEEE Trans. Pattern Anal. Mach. Intell. 22(10): 1185-1190, 2000.

[14] Y. Lee and S. Lee, "Geometric snakes for triangular meshes," Computer Graphics Forum (Eurographics 2002), vol. 21, no. 3, 2002.

[15] Y. Lee, S. Lee, A. Shamir, D. Cohen-Or, and H.-P. Seidel, “Intelligent Mesh Scissoring Using 3D Snakes,” In Proc. of Pacific Graphics 2004, accepted for publication, Seoul, Korea, October 2004.

[16] Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jrome Maillot. “Least squares conformal maps for automatic texture atlas generation.” ACM Transactions on Graphics (SIGGRAPH) 2002.

[17] X.T. Li, T.W. Woon, T.S. Tan and Z.Y. Huang “Decomposing Polygon Meshes for Interactive Applications” The 2001 ACM Symposium on Interactive 3D Graphics, March 19-21, North Carolina, USA, pp.35--42, pp. 243. 2001.

[18] Hsueh-Yi Sean Lin, Hong-Yuan Mark Liao, and Ja-Chen Lin “Visual Salience-Guided Mesh Decomposition” Proc. IEEE Int. Workshop on Multimedia Signal Processing, Siena, Italy, Sept. 29-Oct. 1, 2004.

[19] R. Liu and H. Zhang, "Segmentation of 3D Meshes through Spectral Clustering," Pacific Graphics 2004.

[20] Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L. “Topology matching for fully automatic similarity estimation of 3D shapes.” In: Proc. SIGGRAPH. (2001) 203—212 , 2001.

[21] A. Mangan, and R. Whitaker, “Partitioning 3D Surface Meshes using Watershed Segmentation” , IEEE Transactions on Visualization and Computer Graphics, 5, 4:308-321, 1999.

[22] M. Meyer, M. Desbrun, P. Schröder and A. H. Barr. “Discrete differential-geometry operators for triangulated 2-manifolds.” In Visualization and Mathematics III, H.-C. Hege and K. Polthier eds., pp. 35–57, 2003.

[23] David L. Page, Andreas Koschan, Mongi A. Abidi “Perception-based 3D Triangle Mesh Segmentation Using Fast Marching Watersheds.” CVPR (2) : 27-32, 2003.

[24] Sandeep Pulla, Anshuman Razdany, Gerald Farinz “Improved Curvature Estimation for Watershed Segmentation of 3-Dimensional Meshes” April 30, 2001.

[25] Anshuman Razdan, MyungSoo Bae “A hybrid approach to feature segmentation of triangle meshes” Computer-Aided Design 35(9): 783-789, 2003.

[26] P. Sander, Z. Wood, S. Gortler, J. Snyder, H. Hoppe. ”Multi-chart geometry images.” Eurographics Symposium on Geometry Processing 2003, 146-155.

[27] Pedro V. Sander, John Snyder, Steven J. Gortler, Hugues Hoppe “Texture mapping progressive meshes.” SIGGRAPH 409-416 , 2001.

[28] Ariel Shamir and Valerio Pascucci. “Temporal and spatial level of details for dynamic meshes.” In Proceedings of the ACM symposium on Virtual reality software and technology, pages 77--84. ACM Press, 2001 .

[29] Ariel Shamir , “A Formulation of Boundary Mesh Segmentation” , Proceedings of the second International Symposium on 3DPVT , 2004 .

[30] Jonathan Richard Shewchuk, “Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator” First Workshop on Applied Computational Geometry (Philadelphia, Pennsylvania), pages 124-133, ACM, May 1996

[31] Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, Dani Lischinski “Bounded-distortion Piecewise Mesh Parameterization” 2002.
[32] Kenong Wu, Martin D. Levine ”3D Part Segmentation Using Simulated Electrical Charge Distributions.” IEEE Trans. Pattern Anal. Mach. Intell. 19(11): 1223-1235 , 1997.
[33] Emanoil Zuckerberger, Ayellet Tal, Shymon Shlafman “Polyhedral surface decomposition with applications” Computers & Graphics 26(5): 733-743 , 2002.