臺灣博碩士論文加值系統

在傳統2D動畫製作中，角色的姿勢稍微改變，便須繪製出許多張類似的圖片，相當繁瑣且耗時。有鑑於此，本研究主要目的即是發展出一套能夠簡易操作且具互動式的動畫製作程式，使用者可輕易讓圖片中角色變形，並且同時獲得一系列的角色動作畫面，由此便能節省動畫的製作時間。方法是將角色圖形以網格包覆，產生適當的節點代表此圖形結構，再使用無網格法為基礎的物理模擬演算法，配合能量最佳化進行角色的特徵約束，達到較為真實的動作變形。本研究所設計的程式，簡化原本複雜的動畫製作，讓一般使用者較容易使用；使用者得以即時互動方式，透過簡單的操作步驟來編輯2D角色形狀的姿勢，最後將結果輸出為動畫影片。

In traditional 2D animation production, animators must generate lots of similar images just for little changes of character’s posture, which is bothersome and time consuming. The aim of the current study is to develop an easily manipulated and interactive animation program. People using this program can effortlessly make the character deform and obtain sequences of images simultaneously, so that the production time can be saved. It starts by covering the image of character with a mesh, getting a set of nodes corresponding to the structure of character, applying a physical simulation algorithm based on the mesh-free method and using optimization solver to obtain realistic deformations. We have developed a program to simplify the animation production process, which supply an easier way to general users. Users who utilize this program can edit poses of 2D characters by simple steps and output results to animation video in real time.

謝誌 i
摘要 ii
ABSTRACT iii
目錄 iv
圖目錄 vii
表目錄 ix
第一章 緒論 1
1.1 前言 1
1.2 研究動機 2
1.3 研究目的 2
1.4 研究限制 3
1.5 論文結構 3
第二章 相關研究 4
2.1 基於網格之模擬變形技術 4
2.1.1 有限元素法(Finite Element Method) 4
2.1.2 其他相關技術應用 6
2.2 無網格之物理模擬技術 7
2.2.1 無網格法 8
2.2.2 無網格法在電腦動畫領域之應用 9
2.3 網格化理論 10
2.3.1 Delaunay Triangulation (DT) 和Constrained Delaunay Triangulation (CDT) 11
2.3.2 Conforming Constrained Delaunay Triangulation (CCDT) 14
第三章 系統架構 17
3.1 近似位移函數之推導 18
3.2 Partition of Unity性質檢驗 22
3.3 權重函數的形式 25
3.4 變形場最佳化 27
3.4.1 約束操作點 28
3.4.2 計算最小應變 29
3.4.3 維持多邊形總面積 31
第四章 實作結果與討論 33
4.1 實作環境 33
4.2 實作結果 34
4.3 約束條件與參數討論 38
4.4 系統執行時間分析 43
第五章 結論與未來展望 46
5.1 結論 46
5.2 未來展望 46
參考文獻 48

[1]T. W. Sederberg and S. R. Parry, "Free-form deformation of solid geometric models," SIGGRAPH Comput. Graph., vol. 20, pp. 151-160, 1986.
[2]M. Alexa, D. Cohen-Or, and D. Levin, "As-rigid-as-possible shape interpolation," presented at the Proceedings of the 27th annual conference on Computer graphics and interactive techniques, New Orleans, USA, pp. 157-164, 2000.
[3]O. Sorkine, D. Cohen-Or, Y. Lipman, M. Alexa, C. Rossi, and H.-P. Seidel, "Laplacian surface editing," presented at the Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, Nice, France, pp. 175-184, 2004.
[4]L. Shi, Y. Yu, N. Bell, and W.-W. Feng, "A fast multigrid algorithm for mesh deformation," ACM Trans. Graph., vol. 25, pp. 1108-1117, 2006.
[5]Y. Weng, W. Xu, Y. Wu, K. Zhou, and B. Guo, "2D shape deformation using nonlinear least squares optimization," Vis. Comput., vol. 22, pp. 653-660, 2006.
[6]C. Welman, "Inverse kinematics and geometric constraints for articulated figure manipulation," Master of Science Thesis, School of Computing Science, Simon Fraser University, 1993.
[7]R. W. Sumner, M. Zwicker, C. Gotsman, and J. Popovic, "Mesh-based inverse kinematics," ACM Trans. Graph., vol. 24, pp. 488-495, 2005.
[8]X. Shi, K. Zhou, Y. Tong, M. Desbrun, H. Bao, and B. Guo, "Mesh puppetry: Cascading optimization of mesh deformation with inverse kinematics," ACM Trans. Graph., vol. 26, p. 81, 2007.
[9]T. Boubekeur, O. Sorkine, and C. Schlick, "Simod: Making freeform deformation size-insensitive," in IEEE/Eurographics Symposium on Point-Based Graphics 2007, 2007.
[10]D. L. James and C. D. Twigg, "Skinning mesh animations," ACM Trans. Graph., vol. 24, pp. 399-407, 2005.
[11]K. G. Der, R. W. Sumner, and J. Popovic, "Inverse kinematics for reduced deformable models," ACM Trans. Graph., vol. 25, pp. 1174-1179, 2006.
[12]R. W. Sumner, J. Schmid, and M. Pauly, "Embedded deformation for shape manipulation," ACM Trans. Graph., vol. 26, p. 80, 2007.
[13]B. Adams, M. Ovsjanikov, M. Wand, H.-P. Seidel, and L. J. Guibas, "Meshless modeling of deformable shapes and their motion," presented at the Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Dublin, Ireland, pp. 77-86, 2008.
[14]B. Adams, M. Wicke, M. Ovsjanikov, M. Wand, H. P. Seidel, and L. J. Guibas, "Meshless shape and motion design for multiple deformable objects," Computer Graphics Forum, vol. 29, pp. 43-59, 2010.
[15]M. S. Floater, G. Kos, and M. Reimers, "Mean value coordinates in 3D," Comput. Aided Geom. Des., vol. 22, pp. 623-631, 2005.
[16]T. P. Fries and H. G. Matthies, Classification and overview of meshfree methods. Brunswick: Technical University Braunschweig, 2004.
[17]M. Desbrun and M. P. Gascuel, "Smoothed particles: a new paradigm for animating highly deformable bodies," presented at the Proceedings of the Eurographics workshop on Computer animation and simulation '96, Poitiers, France, pp. 61-76, 1996.
[18]J. J. Monaghan, "Smoothed particle hydrodynamics," Annual Review of Astronomy and Astrophysics, vol. 30, pp. 543-574, 1992.
[19]M. Muller, R. Keiser, A. Nealen, M. Pauly, M. Gross, and M. Alexa, "Point based animation of elastic, plastic and melting objects," presented at the Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, Grenoble, France, pp. 141-151, 2004.
[20]P. Lancaster and K. Salkauskas, "Surfaces generated by moving least squares methods," Mathematics of Computation, vol. 37, pp. 141-158, 1981.
[21]L. P. Chew, "Constrained Delaunay triangulations," presented at the Proceedings of the third annual symposium on Computational geometry, Waterloo, Ontario, Canada, pp. 215-222, 1987.
[22]J. R. Shewchuk, "Delaunay refinement algorithms for triangular mesh generation," Computational Geometry, vol. 22, pp. 21-74, 2002.
[23]Y. C. Chang, "Combine the computer graphics programming and the triangle mesh generator in finite element code," Master of Science Thesis, Mechanical Engineering, National Cheng Kung University, 2004.
[24]T. Belytschko, Y. Y. Lu, and L. Gu, "Element-free Galerkin methods," International Journal for Numerical Methods in Engineering, vol. 37, pp. 229-256, 1994.
[25]Y. Krongauz and T. Belytschko, "Enforcement of essential boundary conditions in meshless approximations using finite elements," Computer Methods in Applied Mechanics and Engineering, vol. 131, pp. 133-145, 1996.
[26]Free Software Foundation. GSL - GNU scientific library. Available: http://www.gnu.org/software/gsl/
[27]B. Spitzak. Fast light toolkit. Available: http://fltk.org/