在三維電腦圖學的&;#63924;域中，角色動作&;#64008;為就是一段頁框(frame)期間中使用&;#63898;
續內插的運算結果，而這些角色是被大&;#63870;的多邊型所包覆，要控制這些多邊形實
為&;#63847;&;#63968;，所以&;#63845;產生&;#63930;為角色設&;#63991;骨架的方法，透過角色人物的關節、骨頭與其
週遭的多邊形彼此建&;#63991;起關&;#63895;性，使用這些關節以及骨頭&;#63789;調整人物動作並且設
&;#63991;關鍵頁框(keyframe)，最後再搭配內插方法，即可讓這個角色做出動作。上述方
法的優點是可以讓該人物主角透過骨架事先已與多邊形定義好的關&;#63895;性，在需要
即時運算的場景中使用該動作檔時，可以即時地產生與場景互動的運算，而&;#63847;需
要事先針對此場景進&;#64008;費時的處&;#63972;。因此在三維電腦圖學技術中，&;#63845;發展出&;#63930;一
個被名為動作重置(motion retargetting)的方法。本研究&;#63851;考&;#63930;演化式演算法
(evolutionary algorithms)提出階層式演化方法，搭配交配的機制讓&;#63864;個親代的骨架
交配產生新的巨集骨架(meta skeleton)，此巨集骨架會同時包含親代雙方的關節以
及骨頭，再針對此巨集骨架產生突變以及適應值篩選，之後讓被篩選後產生的骨
架對應到親代的骨架，以產生無接縫動作傳遞(motion transition)的結果，本&;#63809;文可
應用於三維電腦遊戲及動畫，減少動畫製作過程中依賴美工人員之程&;#64001;，並增加
角色動作之高重覆使用性。

In this thesis, we present an efficient approach to performing motion retargetting
on a new creature’s skeleton that is generated by taking hierarchical evolution. A meta
skeleton is created by means of crossing over two source skeletons. We use mutation to
reproduce the next-generation skeleton, in order to perform motion transition in a
seamless and smooth manner we operate survivor step to analysis motion data. In
addition to the skeleton construction of a new creature by using hierarchical evolution,
motion analysis is a required process to preserve the original motion attributes of source
objects. Spacetime constraints is taken into account in the proposed system in order to
prevent from unexpected artifacts. The proposed technique can effectively produce a
new virtual creature’s skeleton with plausible motion data, and are applicable to work
for 3D computer games and animations.

中文摘要 …………………………………………………………….…….i
Abstract ………………………………………………………………....…ii
致謝 …………………………………………………………………...….iii
目錄 ………………………………………………………………………iv
圖目錄 ……………………………………………………………………vi
表目錄 ……………………………………………………………………ix
第一章 緒論 …………………………………………………………...…1
1.1 研究動機 ……………………………………………………………..1
1.2 研究範圍與構想 …………………………………………..…………2
1.3 章節安排 ………………………………………………….………….4
第二章 相關研究 ………………………………………...………………5
2.1 動作重置 ……………………………………………………...…6
2.1.1 網格形變對應方法 …………………………………….…7
2.1.2 骨架為基礎對應方法 ………………………………….…7
2.1.2.1 時空方法 ………………………………………..….8
2.1.2.2 動作分析方法 …………………...………………..10
2.1.2.3 對應於不同骨架結構 …………………………….15
2.2 演化式演算法 ……………………………………………….…18
2.2.1 基因演算法 ………………………………………...……18
2.2.2 基因規劃 …………………………………………….…..19
2.2.3 階層式演化法 ……………………………………...……20
第三章 演算法 ………………………………………………………….22
3.1 簡介 ………………………………………………………...…..22
3.2 動作重置 ……………………………………………………….22
3.2.1 骨架對應性 ……………………………………….……..23
3.2.2 骨架初始化 ……………………………………………...23
3.2.3 動作傳遞 ………………………………………………...24
3.3 階層式演算法 …………………………………………...……..26
3.3.1 選取親代 ………………………………………………...27
3.3.2 交配 ……………………………………………………...28
3.3.3 突變 ……………………………………………………...31
3.3.4 適應值 …………………………………………………...44
3.3.4.1 時空 ……………………………………………….45
3.3.4.1(a) 目標函數 …………………………………..45
3.3.4.1(b) 限制令 ……………………………………..47
3.3.4.2 反向運動學 ……………………………………….48
第四章 實驗結果與討論 ...……………………………………………..49
4.1 權重值 ………………………………………………………….50
4.2 突變數目 ……………………………………………………….51
4.3 時空控制參數 ………………………………………………….52
4.4 親代雙方與子代的轉動軌跡比較 …………………………….55
4.5 動作重置的時間花費 ………………………………………….61
第五章 結論與未來工作 ……………………………...………………..65
5.1 結論 …………………………………………………………….65
5.2 未來工作 ……………………………………………………….65
參考文獻 ………………………………………………………………...67

1. R. S. Wright, Benjamin Lipchak, OpenGL SuperBible 3/e, SAMS, 2004.
2. I. V. Kerlow, The Art of 3D Computer Animation and Effects, 3rd Edition, John Wiley &
Sons, Inc, 2004.
3. Daniel Sanchez-Crespo Dalmau and Daniel Sanchez-Crespom, Core Techniques and
Algorithms in Game Programming, New Riders Publish, 2003.
4. David H. Eberly, 3D Game Engine Design, Academic Press, 2001.
5. Pamela K. Levangie and Cynthia C. Norkin, Joint Structure and Function: A
Comprehensive Analysis, 4th Edition, ISBN: 0803611919, 2000.
6. Michael Girard and A. A. Maciejewski, “Computational modeling for the computer
animation of legged figures,” Proceedings of the 12th annual conference on computer
graphics and interactive techniques, pp. 263-270, 1985.
7. Jehee, Lee and Sung Yong, Shin, “A hierarchical approach to interactive motion editing
for human-like figures,” Proceedings of the 26th annual conference on Computer graphics
and interactive techniques, pp. 39–48, 1999.
8. Alberto, Menache, Understanding Motion Capture for Computer Animation and Video
Games, Academic Press, ISBN 0124906303, 2000.
9. Pitotech, available through http://www.pitotech.com.tw/c/2-product07.htm.
10. Axis 3D, available through http://www.axis3d.com.tw/content.jsp?cat=new&id=66.
11. Michael Gleicher, Hyun Joon Shin, Lucas Kovar, and Andrew Jepsen, “Snap-together
motion: Assembling run-time animations,” ACM Transactions on Graphics, Vol. 22, Issue
3, pp. 702-702, 2003.
12. Golam Ashraf and Kok Cheong Wong, “Generating consistent motion transition via
decoupled framespace interpolation,” Computer Graphics Forum (Proceedings of
Eurographics 2000 Conference), pp. 447–456, 2000.
13. Kwang-Jin Choi and Hyeong-Seok Ko, “On-line motion retargetting,” The Journal of
Visualization and Computer Animation, Vol. 11, No. 5, pp. 223-235, 2000.
14. Michael Gleicher, “Retargetting motion to new characters,” Proceedings of the 25th annual
conference on computer graphics and interactive techniques, pp. 33-42, 1998.
15. Alexander Savenko and Gordon Clapworthy, “Using motion analysis techniques for
motion retargetting,” Proceedings of Information Visualization, IEEE Computer Society
Press, pp. 110-115, 2002.
16. Ming-Kai Hsieh, Bing-Yu Chen, and Ming Ouhyoung, “Motion retargetting and transition
in different articulated figures,” Proceedings of 2005 International Conference on
Computer Aided Design and Computer Graphics, pp. 457-462, 2005.
17. Seyoon Tak, Hyeong-Seok Ko, “An interactive physically-based motion retargeting filter,”
ACM Transactions on Graphics, Vol. 24, Issue 1, pp. 98-117, 2005.
18. Robert W. Sumner and Jovan Popović, “Deformation transfer for triangle meshes,” ACM
Transactions on Graphics, Vol. 23, No. 3, pp. 399-405, 2004.
19. Michael Gleicher and Peter Litwinowicz, “Constraint-based motion adaptation,” The
Journal of Visualization and Computer Animation, Vol. 9, No. 2, pp. 65-94, 1998.
20. Witkin and Kass, “Spacetime constraints,” Proceedings of the 15th annual conference on
Computer graphics and interactive techniques, pp. 159–168, 1988.
21. Shih-Pin Chao, Chin-Yi Chiu, Jui-Hsiang Chao, Shin-Nine Yang, and Tsang-Ken,
“Motion Retrieval and Its Application to Motion Synthesis,” IEEE ICDCS
2004/Proceedings of The 6th International Workshop on Multimedia Network Systemsand Applications, Tokyo, Japan, pp. 254-259, 2004.
22. Yan Li, Tianshu Wang, and Heung-Yeung Shum, “Motion Texture: A Two-Level
Statistical Model for Character Motion Synthesis,” Proceedings of the 29th annual
conference on Computer graphics and interactive techniques, pp. 465-472, 2002.
23. Katherine Pullen and Christoph Bregler , “Motion Capture Assisted Animation: Texturing
and Synthesis,” ACM Transactions on Graphics, Vol. 21, Issue 3, pp. 501-508, 2002.
24. Armin Bruderlin and Lance Williams, “Motion Signal Processing,” Proceedings of the
22nd annual conference on Computer graphics and interactive techniques, pp. 97 – 104,
1995.
25. Lucas Kovar, Michael Gleicher, and Fr`ed`eric Pighin, “Motion graphs,” Proceedings of
the 29th annual conference on Computer graphics and interactive techniques, pp. 473–482,
2002.
26. James McCann, Nancy S. Pollard, and Siddhartha S. Srinivasa, “Physics-based motion
retiming,” In 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation,
pp. 205-214, 2006.
27. Michael F. Cohen, “Interactive spacetime control for animation,” Proceedings of the 19th
annual conference on computer graphics and interactive techniques, pp. 293-302, 1992.
28. Charles Rose, Brain Guenter, Bobby Bodenheimer, and Michael F. Cohen, “Efficient
generation of motion transitions using spacetime constraints,” International Conference on
Computer Graphics and Interactive Techniques, pp. 147-154, 1996.
29. Michael Gleicher, “Motion editing with spacetime constraint,” Proceedings of the 1997
symposium on interactive 3D graphics, pp. 139-ff, 1997.
30. Zoran Popovi´c and Andrew Witkin, “Physically based motion transformation,”
Proceedings of the 26th annual conference on computer graphics and interactivetechniques, pp. 11–20, 1999.
31. Ronan Boulic and Daniel Thalmann, “Combined direct and inverse kinematic control for
articulated figures motion editing,” Computer Graphics Forum, Vol. 11, No. 4, pp.
189-202, 1992.
32. Lionel Reveret, Laurent Favreau, Christine Depraz, Marie-Paule Cani, “Morphable model
of quadrupeds skeletons for animating 3D animals,” Proceedings of the 2005 ACM
SIGGRAPH/Eurographics symposium on Computer animation, pp. 135-142, 2005.
33. John H. Holland and Judith S. Reitman, “Cognitive systems based on adaptive
algorithms,” In 1997 ACM SIGART Bulletin, pp. 49-49, 1997.
34. C□ndida Ferreira, “Gene expression programming: A New adaptive algorithm for solving
problems,” Complex Systems, Vol. 13, Issue 2, pp. 87-129, 2001.
35. K.Sims, “Evolving virtual creatures,” Computer Graphics (Siggraph '94 Proceedings), pp.
15-22, 1994.
36. John R. Koza, “Genetic programming”, MIT Press, 1992.
37. L. Gritz, J.K. Hahn, “Genetic programming for articulated figure motion”, The Journal of
Visualization and Computer Animation, Vol. 6, Issue 3 , pp. 129-142, 1995.
38. L. Gritz, J.K. Hahn, “Genetic Programming evolution of controllers for 3-D character
animation”, Genetic Programming 1997: Proceedings of the 2nd Annual Conference, pp.
139-146, 1997.
39. Lindsay I Smith, “A tutorial on principal components analysis,” 2002.
40. FLTK, http://www.fltk.org/