近年來，三維動畫與電腦遊戲中的即時運算技術儼然成為一個重要的研究議題，虛擬角色與虛擬環境的即時互動漸漸被大家所探討；本研究主要針對兩個議題進行探討，分別是動態場景編輯與虛擬角色之互動關係，以及應用於接合不同動作的動作混合技術(motion blending)。透過這兩方面研究去解決多種虛擬角色，經由生殖而演化出下一代虛擬角色，彼此之間在大型場景中的動作表現問題。本研究利用了演化式演算法中的階層式演化方法 (hierarchical evaluation)概念，搭配交配及突變的機制讓兩個親代的角色骨架(skeleton)交配產生子代的骨架後，並透過使用者互動式編輯的模擬環境地圖，計算動作地磚的數量(motion tiles)產生的比例，經由動作重置(motion retargetting)的方法，使兩親代的動作透過巨集骨架的傳遞來產生子代動作，再把製成的子代角色放入之前由使用者編輯的三維虛擬環境中，此外，系統會根據使用者定義在虛擬環境中的路徑設定，自行產生虛擬角色的動作路徑，使虛擬角色可以在環境中移動，並根據環境的動作地磚產生相對應的運動變化，觸發不同的動作片段，在每段動作與動作之間再利用動作混合技術加以串接，使動作變化的過程平滑且順暢。
本論文中開發將虛擬角色的骨架和動作跟不同屬性的地形環境進行即時的互動，解決虛擬角色在虛擬環境即時互動的問題；此技術可應用於三維動畫與電腦遊戲的虛擬角色製作，提高網格模型的骨架和動作的重複使用性，藉以降低美術人員的美工開發成本和製作時間。

In the past few years, 3D animations and computer games have taken good advantage of sophisticated real-time graphics technologies, and interested a lot of researchers in developing diverse methodologies with respect to the issue of virtual characters animating in virtual environments. In this thsis, we classify the above issue into two steps; one is to create a virtual characters to move around a virtual environment that had been authored in advance, and the other is to stitch various parts of the motion data by means of motion blending. Based on the two operations, we are able to create a next-generation virtual characters by mating the two source characters and thus make such a character animating in the virtual environment as well as its parental characters.
In addition, hierarchical evaluation is employed to facilitate the operations of crossing over and mutating in order to construct a target skeleton. In the beginning, users can interactively edit their 3D virtual environments in terms of motion tiles. The parental skeletons are merged by means of the cut-and-paste method to form an intermediate skeleton, namely, the meta-skeleton. Subsequently, we make use of the motion retargeting approach to transfer the analyzed motion data from the parental skeletons to the target skeleton through the meta-skeleton. As a result, the target skeleton with motion data can be placed in the virtual environment and therefore move forward according to each motion tile. Due to the fact that different motion tiles have been assigned different spatial functionalities, the target virtual character is to follow the user-defined path to move forward in specific behaviors, such as flying, walking, and swimming. Therefore, we propose a rapid motion blending technique to assemble each motion clip in a seamlessly manner with a view to smoothly moving the target virtual character forward in the virtual environments.

中文摘要 ………………………………………………………………i
Abstract ………………………………………………………………ii
致謝 ………………………………………………………………………iv
目錄 ………………………………………………………………………vi
圖目錄 ……………………………………………………………………ix
表目錄 …………………………………………………………………x
第一章 緒論 ……………………………………………………………1
1.1 研究動機 ……………………………………………………………1
1.2 研究範圍與構想 ………………………………………….………...…2
1.3 章節安排 ………………………………………………….….……......6
第二章 相關研究 ………………………………………...…….………….9
2.1 虛擬環境與動作生成 …………………………………….…….…9
2.1.1 虛擬環境建置 …..……………………………….……...…10
2.1.2 路徑與虛擬環境設計 ..…………………………….…...…12
2.1.2.1 動作圖形與路徑 ………………………………....…12
2.1.2.2 建構區塊與路徑 ………………..…………….….....15
2.2 動作混合 …….………………………………………………...…16
2.2.1 簡介 …………………………………………….…...…..…17
2.2.2 時間軸扭曲 …………………………………….……..….….....18
2.3 階層式演化法 .…………………………………...…..…….....…20
第三章 虛擬環境與虛擬角色 .………………………………..…...…….23
3.1 簡介 ……………………………………………………….....…..23
3.2 地圖編輯器………………………………………………….…….25
3.3 階層式演算法 …………………………………………...……...27
3.4 環境與動作轉移……………………………………………….…30
3.4.1 動作轉移 ………………………………………………....30
3.4.2 地圖分析與路徑規劃……………………………………...31
3.5 地圖樣板……………………………………………….………...34
第四章 動作合成………. ...……………………………………………...39
4.1 簡介 ……………………………………………………………..39
4.2 動作圖形與路徑 ………………………………………………..40
4.3 時間軸扭曲 ……………………………………………………..41
4.3.1 時間軸扭曲表 ………………………………….………...42
4.3.2 動作混合區段 ……………………………….…………...43
4.4 動作合成技術 …………………………………………………..44
4.4.1 動作混合技術 ……………………………..……………..44
4.4.2 運動參數轉換 ………………………………..…………..46
4.5 系統生成 ………………………………………………………..47
第五章 系統實驗………. ...……………………………………………...49
5.1 實驗流程 ………………………………………………………..49
5.2 實驗結果 ………………………………………….………….…51
5.3 動作混合方法比較 …………………………….…………….…55
5.3.1 相關方法介紹 ……………………………..……………..56
5.3.2 動作混合實驗結果 ……………………...…………….…56
5.4 虛擬環境與動作圖形 …………………………….………….…59
5.5 多樣虛擬角色 ………………………………….…………….…61
第六章 結論與未來工作 ……………………………......……………....65
6.1 結論 ……………………………………………………………..65
6.2 未來工作 …………………………………………………….….66
參考文獻 ………………………………………………………………....67

[1] R. S. Wright, B. 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] D. Sanchez-Crespo Dalmau and D. Sanchez-Crespom, Core Techniques and Algorithms in Game Programming, New Riders Publish, 2003.
[4] D. H. Eberly, 3D Game Engine Design, Academic Press, 2001.
[5] A. Menache, Understanding Motion Capture for Computer Animation and Video Games, Academic Press, ISBN 0124906303, 2000.
[6] Pitotech, available through http://www.pitotech.com.tw/c/2-product07.htm, July, 2008.
[7] Axis 3D, available through http://www.axis3d.com.tw/content.jsp?cat=new&id=66, July, 2008.
[8] Eaudry, available through http://www.eaudrey.com/myth/, July, 2008.
[9] J. P. Williams, S. Q. Hendricks and W. K. Winkler, Introduction: Fantasy Games, Gaming Cultures, and Social Life, Gaming as Culture, Essays on Reality, Identity and Experience in Fantasy Games. McFarland & Company: Oxford University Press. ISBN 0786424362, 2006.
[10] E. Bonny, J. Grubb, R. Redman, S. Williams and S. Winter., 龍與地下城怪物圖鑑II, 第三波, ISBN 957-23-1451-3, 2003.
[11] T. C. Lu, D. S. Mu, and T. H. Yang, "Animation of a Virtual Skeleton-based Characters via Motion Retargetting," In Proc. of ICCE Workshop on Digital Game and Intelligent Toy in Education, 2007.
[12] S. Bandi and D. Thalmann, "A configuration space approach for efficient animation of human figures," In Proc. of IEEE Non Rigid and Articulated Motion Workshop, IEEECS Press, p.38, 1997.
[13] R. Bindiganavale, J. P. Granieri, S. Wei, X. Zhao, and N. I. Badler, "Posture interpolation with collision avoidance," In Proc. of Computer Animation, pp. 13 – 20, 1994.
[14] S. Chenney, “Flow tiles,” In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Modeling and Simulation Design. AK Peters Ltd., pp.233 -242, 2004.
[15] J. Lee, J. Chai, P. S. A. Reitsma, J. K. Hodgins, and N. S. Pollard, “Interactive control of avatars animated with human motion data,” ACM Trans. On Graphics (SIGGRAPH 2002), Vol.21, No. 3, pp.491 – 500, 2002.
[16] K. H. Lee, M. G. Choi and J. Lee, ”Motion patches:building blocks for virtual environments annotated with motion data,” ACM Trans. On Graphics (SIGGRAPH 2006), Vol.25, No.3, pp. 898 – 906, 2006.
[17] Alla Safonova Jessica K. Hodgins,”Construction and optimal search of interpolated motion graphs,” ACM Trans. On Graphics (SIGGRAPH 2007) , Vol.26, No.3, 2007.
[18] L. Kovar, M. Gleicher, F. Pighin, "Motion Graphs" ACM Trans. On Graphics (SIGGRAPH 2002) , Vol.21, No.3, pp. 473 – 482, 2002.
[19] O. Arikan and D. A. Forsyth, “Interactive Motion Generation From Examples”, ACM Trans. On Graphics (SIGGRAPH 2002), Vol.21, No.3, pp.483 - 490, 2002.
[20] L. Ikemoto, O. Arikan, and D. A. Forsyth, “Quick Transitions with Cached Multi-way Blends,” In Proc. of Interactive 3D Graphics and Games (SI3D 2007), pp.145-151, 2007.
[21] L. Ren, A. Patrick, A. A. Efros, J. K. Hodgins, and J. M. Rehg, “A data-driven approach to quantifying natural human motion,” ACM Trans. On Graphics (SIGGRAPH 2005), Vol.24, No.3, pp.1090 - 1097, 2005.
[22] Z. Chen and X. Zhu, “A Motion Blending Approach Based on Unsupervised Clustering,” In Proc. of ICAT Workshops, pp.626 – 631. 2006.
[23] J. S. R. Jang , H. R. Lee, “Hierarchical filtering method for content-based music retrieval via acoustic input,” In Proc. of the ninth ACM international conference on Multimedia, pp.401 – 410, 2001.
[24] E. Keogh, “Exact indexing of dynamic time warping,” In Proc. of the 28th International Conference on Very Large Data Bases (VLDB), pp. 406 – 417, 2002.
[25] A. Witkin, Z. Popovi´c, “Motion warping,” In Proc. of SIGGRAPH 1995, 1995.
[26] A. Majkowska, V. B. Zordan and P. Faloutsos, ”Automatic Splicing for Hand and Body Animations,” In Proc. of SIGGRAPH 2006, pp.309 – 316, 2006.
[27] R. Heck, L. Kovar, and M. Gleicher, “Splicing Upper-Body Actions with Locomotion,” Computer Graphics Forum, Vol.25, No.3, pp. 459 – 466, 2006.
[28] E. Hsu, M. da Silva and J. Popovic, “Guided TimeWarping for Motion Editing,” In Proc. of Eurographics Symposium on Computer Animation, pp. 45 – 52, 2007.
[29] J. R. Koza, “Genetic programming”, MIT Press, 1992.
[30] K. Sims, “Evolving virtual characters,” In Proc. of SIGGRAPH 1994, pp. 15 – 22, 1994.
[31] Warhammeronline, available through http://www.warhammeronline.com, July 2008.
[32] Curtis Distance, available through http://people.revoledu.com/kardi/tutorial/Similarity/BrayCurtisDistance.html, July 2008.
[33] J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley ISBN 0-201-05594-5, 1985.
[34] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, pp. 97-104, ISBN 0-13-790395-2, 2003.
[35] Virtools, available through http://www.axis3d.com.tw/software.php?cat=virtools, July 2008.
[36] P. Davis, B-splines and Geometric design, SIAM News, 1997.
[37] E. Meijering, “A chronology of interpolation: from ancient astronomy to modern signal and image processing,” PROCEEDINGS OF THE IEEE, VOL. 90, NO. 3, pp.319 – 342, 2002.
[38] J. Stoer and R. Bulirsch, Introduction to Numerical Analysis. Springer-Verlag., pp. 93-106, ISBN 0387904204.
[39] FLTK, available through http://www.fltk.org/, July 2008.