在電腦圖學的領域之中，三維多邊形物體的變形是一項實用並且功能強大的技術，它被廣泛地應用至許多的領域，像是科學視覺化和娛樂工業中的特效效果等。
　
　　將欲變形的物體做參數化來建立他們之間的對應關係是變形前的先行必要工作，在眾多的參數化方法中，球體參數化因為可以避免平面參數化中常見的邊界條件和區塊對應的問題，因此球體參數化常被應用至變形的領域之中。然而，球體參數化有個限制，其欲參數化的物體的虧格數必需要是0，也就是物體中不能有洞的存在。本篇論文提出一個新的架構來有效地減化大型模型的虧格數並且能讓任意虧格數的物體能使用球體參數化來進行變形。
　
　　本文首先提出一個快速偵測三維模型的洞的演算法，然後依照所偵測到的洞的邊緣形狀來產生兩個網格模型，在將該網格模型和洞進行對位之後，利用解一個Poisson方程式的方法來將該網格模型和進行變形以符合洞的形狀，之後將它們和洞進行接合來將模型中的洞移除。我們將此縫合後之模型視為正值物件並將移除之洞視為負值物件。將兩變形模型相對應且虧格數都是0的正值物件跟負值物件進形變形之後，對變形所內插產生出的物體進行布林相減運算來得到中繼的變形形狀，來達到任意虧格數模型之間的變形效果。

　Metamorphosis of 3D polyhedral models is a useful and powerful technique in computer graphics. It is widely used in a variety of areas such as scientific visualization and special effects in entertainment industry. Parameterization of models is required to establish correspondence between models in many applications. Among various parameterization methods, spherical parameterization is commonly used for metamorphosis since it avoids several problems such as boundary conditions and correspondence of patches that are usually seen in other parameterizations. However, the drawback of spherical parameterization of 3D polyhedral models is that it can only be applied to Genus-0 (i.e. with no holes) models. In this thesis, we present a new framework to effectively reduce the Genus of 3D models and to enable metamorphosis between 3D polyhedral models with arbitrary Genus using spherical parameterization.
　We first introduce a novel technique to fast identify the holes of the model. Then we build two cap meshes according to the boundary of the detected hole. To eliminate each hole, those cap meshes are warped to fit the shape of the hole by solving a Poisson's equation. The model without holes is treated as a positive object and its holes are treated as negative objects. Both positive and negative objects are Genus-0 and then morphed accordingly. Finally we apply Boolean difference operations on the interpolated meshes to acquire the in-between shapes of the morphing sequence. In this manner, we achieve metamorphosis between models of arbitrary Genus using spherical parameterization.

[1] Ahn, M. , Lee, S. , Mesh Metamorphosis With Topology Transformation, Pacific Graphics, p481-482, 2002.
[2] Alexa, M. , Merging Polyhedral Shapes with Scattered Features, The Visual Computer, vol. 16, no. 1, p26-37, 2000.
[3] Axen, U. , Computing Morse functions On Triangulated Manifolds, Proceedings of the SIAM Symposium on Discrete Algorithms (SODA). 1999.
[4] Colin De Verdi `Ere, ´E. Lazarus, F. , Optimal System of Loops On An Orientable Surface, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, p627-636, 2002.
[5] Chao Hung Lin, Tong Yee Lee. Metamorphosis of 3D Polyhedral Models Using Progressive Connectivity Transformations. IEEE Transactions of Visualization and Computer Graphics. vol. 11, no. 1, p2-12, 2005.
[6] D. Steiner, A. Fischer, Cutting 3D Freeform Objects With Genus-n Into Single Boundary Surfaces Using Topological Graphs, Proceeding of ACM Solid Modeling and Applications, 2002.
[7] D. Steiner, A. Fischer, Finding And Defining The Generators of Genus-n Objects For Constructing Topological and Cut Graphs. The Visual Computer 20(4), p266-278, 2004.
[8] Edmonds J. , R. M. Karp, Theoretical Improvements in Algorithmic Efficiency For Network Flow Problems. Journal of ACM, Volume19, Issue2, p248-264, 1972
[9] Eric W. Weisstein. "Simplicial Complex. "From MathWorld--A Wolfram Web Resource. http://mathworld. wolfram. com/SimplicialComplex. html
[10] Eric W. Weisstein. "Genus. "From MathWorld--A Wolfram Web Resource. http://mathworld. wolfram. com/Genus. html
[11] Erickon, J. Har-Peled, S. Optimally Cutting A Surface Into A Disk. Proceedings of 18th Symposium of Computational Geometry, ACM, June, p244-253, 2002
[12] Ford L. R. Jr, D. R. Fulkerson, Maximal Flow Through a Network, Canadian Journal of Mathematics, p99-404, 1956.
[13] Fujimura K. , M. Makarov, M, Foldover-Free Image Warping. Graphical models and Image Processing, 60(2), p100-111. 1998.
[14] Guskov, I. , Wood, Z. Topological Noise Removal. Graphics Interface, p19-26. 2001.
[15] Gu, X. , Gortlers, S. J. , Hoppe, H. Geometry images. Proceedings of SIGGRAPH, p355-361. 2002.
[16] Gregory, A. , State, A. , Lin, M. , Manocha, D. , Livingston, M. Interactive Surface Decomposition for Polyhedra Morphing. The Visual Computer, vol. 15, no. 9, p453-470. 1999
[17] G. Reeb. Sur les points singuliers d’une forme de pfaff compl`etement int´egrable ou d’une function num´erique. Comptes Rendus Acad. Sciences aris, p847-849, 1946.
[18] Polthier, K. , Preuss, E. Variational Approach To Vector Field Decomposition. Proceeding of Eurographics Workshop on Scientific Visualization, 2000.
[19] R. Zayer, C. Rössl, Z. Karniand H. -P. Seidel, Harmonic Guidance for Surface Deformation, to appear in EUROGRAPHICS, 2005.
[20] Shalfman, S. , Tal, A. , S. Katz, S. Metamorphosis Of Polyhedral Surfaces Using Decomposition. EUROGRAPHICS Conference Proceedings, p219-228, 2002.
[21] Tong-Yee Lee, Chien-Chi Huang. Dynamic and Adaptive Morphing of Three-dimensional Mesh Using Control Maps. IEICE Transactions on Information and Systems, vol. e88-d, no. 3, march, p645-651, 2005.
[22] T. Kanai, H. Suzuki, and F. Kimura, Three-Dimensional Geometric Metamorphosis Based on Harmonic Maps, The Visual Computer, vol. 14, p166-176, 1998.
[23] Tong, Y. , Lombeyda, S. , Hirani, A. , Desbrun, M. Discrete Multiscale Vector Field Decomposition. ACM Transactions on Graphics 22, 3, P445-452. 2003
[24] J. El-Sana, A. Varshney. Controlled Simplification Of Genus For Polygonal Models. Proceedings of IEEE Visualization, P403-412, 1997.
[25] Kanai, T. , Suzuki, H. , AND Kimura, F. Metamorphosis of Arbitrary Triangular Meshes. IEEE Computer Graphics and Applications, vol. 20, no. 2, p62-75. 2000
[26] K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan and V. Pascucci. Loops in Reeb Graphs of 2-Manifolds. Symposium on Computational Geometry. p344-350. 2003
[27] Kartasheva, E. The Algorithm For Automatic Cutting of Three-Dimensional Polyhedron of h-Genus. International Conference of Shape Modeling and Applications. IEEE Computer Society, Aizu, Japan, p26-33. 1999.
[28] Lee, T. -Y. , P. -H. Hung, P. -H. Fast and Intuitive Metamorphosis of 3D Polyhedral Models Using SMCC Mesh Merging Scheme. IEEE Transactions of Visualization and Computer Graphics, vol. 9, no. 1, p85-98. 2003
[29] Lazarus, F. , Pocchiola, M. , Vegter, G. , Verroust, A. Computing A Canonical Polygonal Schema of An Orientable Triangulated Surface. ACM Symposium on Computational Geometry, p80-89, 2001.
[30] Lee, A. , Dobkin, D. , Sweldens, W. , Schröder, P. Multiresolution Mesh Morphing. ACM SIGGRAPH Conference Proceedings, p343-350. 1999
[31] Michikawa, T. , Kanai, T. , Fujita, M. , and Chiyokura, H. . Multiresolution Interpolation Meshes. Pacific Graphics, p60-69, 2001.
[32] Nooruddin, F. , Turk, G. Simplification And Repair Of Polygonal Models Using Volumetric Techniques. Research Report, Georgia Tech, p99-37. 1999
[33] Praun, E. , Sweldens, W. , Schröder, P. , Consistent Mesh Parameterization. ACM SIGGRAPH Conference Proceedings, 179-184, 2001.
[34] Yizhou Yu, Kun Zhou, Dong Xu Xiaohan Shi, Hujun Bao, Baining Guo, Heung-Yeung Shum, Mesh Editing with Poisson-Based Gradient Field Manipulation, ACM Transactions on Graphics, Vol. 23, No. 3, p641-648, 2004.
[35] Zockler, M. , Stalling, D. , Hege, H. -C. Fast and Intuitive Generation of Geometric Shape Transitions. The Visual Computer, vol. 16, no. 5, p241-253. 2000
[36] Z. Wood, H. Hoppe, M. Desbrun, P. Schröder. Removing excess topology from Isosurfaces. ACM Transactions on Graphics, 23(2), p190-208, April 2004.