在三維空間中，一個任意形狀的物體漸漸轉變成另一個不同形狀物體的過程，我們稱之為三維物體形變（3D metamorphosis or 3D morphing）。
在目前的研究中，都必須將物體切割成多個對應區塊，並在各對應區塊內部產生物體的對應關係。如此使用者必須花相當多的時間和精神在
區塊的建立和特徵點的指定上。
本論文的主要目的是讓使用者只需給定兩物體上的特徵對應點，系統將自動產生具相同網格拓樸的新物體網格，進而完成網格形變的過程。
本論文結合Geometry Images[2002]和Interactive Geometry Remeshing[2002]的方式建立物體網格的切割和物體拓樸網格的重建。
尋找合適的切割路徑使網格能順利的映射到一個二維的平面上，在平面上建立物體的對應關係，再根據各物體的幾何資訊和
物體映射過程中的失真度求得新共同網格點的取樣。將分佈在二維平面上的取樣點經由受限制的狄勞尼三角化（constrained Delaunay triangulation）建立共同的拓樸網格，
並根據相同的拓樸網格重建各物體的幾何資訊。此由共同拓樸網格所重建的物體網格具有點的對應關係。
在形變過程中，根據時間變化利用線性內差的方式計算形變中的中間物體，完成物體的形變過程。

The metamorphosis or the 3D morphing is the process of continuously transforming one object into another.
Most previous proposed techniques partition a given mesh into several patches.
User often suffers from assigning partition paths and patch correspondence between objects.
In this thesis, we aim to alleviate such user intervention.
In the proposed morphing scheme, the user is required to specify only correspondence of feature vertices on objects.
According to topological and geometric information, we find a suitable cutting path that cuts the given mesh into a single patch.
We apply mesh parameterization to assign a 2D parametric value to each vertex on the patch,
then adjust 2D parametric value for each feature vertex, and construct vertex correspondence on parametric domain.
Using image processing technique and constrained Delaunay triangulation decides the point distribution and the topology of the new common mesh.
Based on the common mesh and the original mesh geometry, we construct 3D meshes.
In morphing stage,the interpolated mesh is constructed by a traditional linear interpolation between corresponding vertices.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vii
表目錄 x
1 序論 1
1.1 研究動機 1
1.2 研究範圍與目標 2
1.3 章節安排 2
2 相關研究 3
2.1 三維物體形變技術概要 3
2.1.1 體積形變法 3
2.1.2 高度圖形變法 4
2.1.3 多邊形物體形變法 4
2.1.4 不同形變法分析與比較 5
2.2 傳統多邊形形變 6
2.2.1 投影對應法 6
2.2.2 物體表面取樣法 7
2.3 多邊形形變-二維平面對應法 9
2.3.1 區塊重疊法 9
2.3.2 重建網格法 11
2.4 網格重建 16
2.4.1 均勻取樣法 17
2.4.2 非均勻取樣法 17
3 相同拓樸物體切線之形成與物體點對應之建構 21
3.1 網格形變流程簡介 21
3.2 建立物體網格上的切割路徑 23
3.2.1 物體拓樸屬性為零的切割路徑 23
3.2.2 物體拓樸屬性大於零的切割路徑 23
3.3 三維網格的參數化 25
3.4 對應點在參數空間上的調整 28
3.5 重建網格 32
3.5.1 建立取樣圖 33
3.5.2 多物體的取樣方式 37
3.5.3 建立網格資訊 37
3.5.4 三維物體網格最佳化 40
4 實作過程與討論結果 44
4.1 程式架構與實作 44
4.2 前置處理結果 51
4.3 網格形變結果 70
4.4 網格形變技術之比較 79
5 結論 80
5.1 研究總結 80
5.2 未來發展與工作 81

[AMD02] P. Alliez, M. Meyer, and M. Desbrun. Interactive geometry remeshing. ACM
Transactions on Graphics, 21(3):347—354, July 2002.
[COSL98] D. Cohen-Or, A. Solomovici, and D. Levin. Three-dimensional distance field
metamorphosis. ACM Transactions on Graphics, 17(2):116—141, April 1998.
[DG96] D. DeCarlo and J. Gallier. Topological evolution of surfaces. Proc. Graphics
Interface ’96, pages 194—203, 1996.
[DMA02] M. Desbrun, M. Meyer, and P. Alliez. Intrinsic parameterizations of surface
meshes. Computer Graphics Forum, 21(3):209—218, 2002.
[Flo97] M. S. Floater. Parametrization and smooth approximation of surface triangulations.
Comp. Aided Geom, 14:231—250, 1997.
[FM98] K. Fujimura and M. Makarov. Foldover-free image warping. Graphical Models
and Image Processing, 60(2):100—111, March 1998.
[GGH02] X. Gu, S. J. Gortler, and H. Hoppe. Geometry images. ACM Transactions
on Graphics, 21(3):355—361, July 2002.
[GSL+98] A. Gregory, A. State, M. Lin, D. Manocha, and M. Livingston. Feature-based
surface decomposition for correspondence and morphing between polyhedra.
In Computer Animation ’98, June 1998.
[KCP92] J. Kent, W. E. Carlson, and R. E. Parent. Shape transformation for polyhedral
objects. In Computer Graphics (Proceedings of SIGGRAPH 92), volume 26,
pages 47—54, July 1992.
[KPC91] J. Kent, R. Parent, and W. E. Carlson. Establishing correspondences by topological
merging: A new approach to 3-d shape transformation. In Graphics
Interface ’91, pages 271—278, June 1991.
[KSK00] T. Kanai, H. Suzuki, and F. Kimura. Metamorphosis of arbitrary triangular
meshes. IEEE Computer Graphics & Applications, 20(2):62—75, 2000.
[LCLC02] J. L. Lin, J. H. Chuang, C. C. Lin, and Chih-Chun Chen. Consistent mesh
parametrizations using quinary patch subdivision. International Computer
Symposium, 2002.
[LGM95] Lerios, Garfinkle, and L. M. Featurebased volume metamorphosis. Comput
Graph (SIGGRAPH’95), 29:449—464, 1995.
[LV94] F. Lazarus and A. Verroust. Feature-based shape transformation for polyhedral
objects. 1994.
[LV97] F. Lazarus and A. Verroust. Metamorphosis of cylinder-like objects. 1997.
[MKFC01] T. Michikawa, T. Kanai, M. Fujita, and H. Chiyokura. Multiresolution interpolation
meshes. In Pacific Graphics 2001, Proc. 9th Pacific Graphics
International Conference, pages 60—69, October 2001.
[OKT01] R. Ohbuchi, Y. Kokojima, and S. Takahashi. Blending shapes by using subdivision
surfaces. Computers and Graphics, 25:41—58, 2001.
[Ost01] V. Ostromoukhov. A simple and e±cient error-di®usion algorithm. In Proceedings
of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual
Conference Series, pages 567—572, August 2001.
[PSS01] E. Praun, W. Sweldens, and P. Schr¨oder. Consistent mesh parameterizations.
In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings,
Annual Conference Series, pages 179—184, August 2001.
[TKO01] S. Takahashi, Y. Kokojima, and R. Ohbuchi. Explicit control of topological
transitions in morphing shapes of 3d meshes. Proc. 9th Pacific Graphics
International Conference, 2001.
[VRKS01] J. Vorsatz, C. R¨ossl, L. P. Kobbelt, and H. P. Seidel. Feature sensitive remeshing.
Computer Graphics Forum, 20(3):393—401, 2001.