透過程序方式有效且快速的自動產生出生動的3D電腦動畫，一直以來是該領域中研究人員所追尋的目標。以中國舞獅在梅花樁上的運動為例，用傳統的動畫製作方式，要能在短時間內產生出符合雙人舞獅演員協同運動的限制，並在佈滿不規則梅花樁的場景中搜尋一條可行走的路徑，是相當費時費力的。我們提出了一套動畫產生系統，讓雙人舞獅演員在隨機產生梅花樁的虛擬環境中，透過協同運動的計畫器，搜尋出可行走的路徑。我們的路徑規劃演算法是依據最佳化優先搜尋演算法的精神來建置，最後並以程序的方式自動模擬出行走過程的3D電腦動畫。這些動畫包含梅花樁上常見的表演動作，如跳躍和轉身等。我們的實驗結果顯示，擬真的舞獅跳梅花樁動畫，可以用互動的方式由協同運動計畫器自動產生。

群體運動在現今的電玩、動畫或電影中，有十分重要的應用；透過群體性的運動，可以表現出故事背景設定的張力。在群體運動的模擬中，除了個體本身的運動行為模擬外，重要的是如何呈現出群體運動的整體效果。過去文獻中多數的群體運動模擬系統，要能在群體運動中呈現出特定形狀的效果，多需花費大量的時間反覆調整個體的模擬結果；個體本身的運動行為模型，則多採用虛擬力場的方式，被動的影響個體的運動，較缺乏直觀設定行為模型的方式。本論文的目標是建立一套人群模擬系統，此系統包括兩個部份：第一個部份是使用者可根據個人偏好設定群體運動理想中的外觀形狀，使此系統在模擬前能根據所輸入的環境資訊，利用運動計畫的方式，自動產生形體形變的路徑，以做為維持群體外形的參考目標。第二部份則是改進人群模擬時個體與群體的行為模型。我們利用模糊數學的特性，來表示行為模型以語意表達時的不確定性，使個體的行為能表現出貼近使用者所需求的結果。我們提出了三種類型的模糊行為模型與對應的原生動作，用以表現個體與群體的運動行為。根據我們實做出來的系統及實驗顯示，透過這樣的系統，我們可以利用程序化的方式為電腦動畫師產生具有特定群體外觀的群體模擬，減少其在製作相關動畫所需要的時間與技術成本，同時也提供了直觀的方式建立人群的行為模型，增加行為的豐富性。 / The effects of crowd behavior are becoming indispensable in computer games and computer animation. In crowd simulation, beside the issue of simulating the motion for individual agents, the more important one is how to simulate a specific behavior of a crowd based on the motion of individuals. In order for a crowd to conform to a specific shape, most simulation systems reported in the literature require the users to spend a great amount of time in tuning the behavior parameters of each individual, governed by virtual forces computed according to inter-agent relations. In this thesis, we aim to build a system of crowd simulation consisting two parts: a path planner for a flexible shape and a motion controller with fuzzy logic. The path planner can search for a feasible path for a region of flexible shape allowing the user to set his preference on the shape of the crowd. The local motion controller for each agent is based on fuzzy logic rules that can be used to present the uncertainty of linguistic behavior models. We have proposed three types of fuzzy behavior models and their corresponding primitive actions. Our experiments show that, with this simulation system, we allow a computer animator to use an intuitive way to create specific appearance and richer.

讓數位演員能夠在虛擬場景中自主的規劃路徑並且移動，一直是一個富有挑戰性的問題。近年來已有相當多與此相關的研究，數位演員已能夠在高低起伏的分層地形中做路徑的規劃。我們的目標是除了能處理更一般化的場景外，對於場景中障礙物的定義，也會隨著數位演員的能力而有所不同。本研究為數位演員所擴充的新的能力包含了翻越過障礙物的能力以及搬移障礙物的能力。在以往藉由搬移障礙物而抵達目的地的研究中，都是以先決定欲搬移障礙物的順序，再為數位演員以本身擁有的運動能力規劃出一條合理且無碰撞的路徑。而本研究的特色則是將搬移障礙物這項能力與數位演員其他的運動能力一併考量，將各種運動能力以一致的觀點來規劃數位演員的行走路徑。我們將以數個模擬的例子說明此運動計畫器的有效性。 / Enabling a digital actor to move autonomously in a virtual environment is a challenging problem that has attracted much research attention in recent years. Many researches have been also to generate the motion of a digital actor in an uneven layered environment. In this thesis, we have extended our previous work to enable the digital actor to have the ability of jumping over a barrier and the ability of manipulating obstacles in order to make room for passing. Most previous work in generating manipulation plans for obstacles must first decide the order of manipulation and then manipulate obstacles in accordance with the sequence. In this thesis, we design a motion planner that can take all motion abilities of the digital actor into account in generating a collision-free path in a layered environment cluttered with various types of obstacles. This planer takes a unified view to consider all types of motions including manipulating objects that could change the system configuration. The experimental results will be demonstrated with several simulation examples to show the effectiveness of the system

在3D遊戲中，讓虛擬角色能夠在場景中自主的和使用者進行即時互動，一直是一個非常有挑戰性的問題。過去在此方面的相關研究雖然為數不少，但大多數的研究不是用效能來換取角色動作的規劃品質，就是屈就於效能而決定犧牲品質，能妥善的在兩者之間取得平衡的系統並不常見。本論文所提出的系統，便是一個能在兩者之間取得不錯平衡的角色動作規劃器。我們的規劃器會根據使用者的操作命令來預測角色未來可行的行動空間，並搭配時間預算的概念，將這些預測結果儲存在一種稱為可行動作樹的資料結構，從這些預測結果中搜尋出最符合使用者操作要求的角色動作。我們利用這個規劃器實作了兩種不同的應用，並測試了它們的效能。我們相信這個運動模組能實用在一般如遊戲的即時動畫環境中，提昇動畫角色的互動性與動畫品質。 / Allowing a virtual character to interact with the user autonomously in a 3D game has been a challenging problem for long. There has been much research in this direction but most of them have to trade interactivity of control with the quality of the generated motions or the other way. It is rare to see a system that can find a good balance between these two factors. In this thesis, we propose an interactive system consisting of a motion planner aiming to find a good balance between these two factors. Our planner attempts to predict the feasible motion space in the near future according to user commands. We use the concept of time-budgeted computing to maintain a data structure called Feasible Motion Tree representing the feasible motion space. This tree is maintained in an incremental fashion and is used to select the most appropriate motion clip when the current motion clip comes to the end. We have used this motion planning module to implement two different applications and verify its efficacy and efficiency. We believe that this motion planning module can be used in a real-time virtual environment, such as a game, for the improvement of the interactivity and the quality of motion control.

在本論文中，我們設計了一個以運動計畫演算法為基礎的自動導覽系統，讓使用者能透過計畫程式的輔助輕鬆地瀏覽虛擬場景。這系統包括一個我們稱之為智慧型觀察者的照相機模組，而這個模組便是本論文的研究焦點。其包含了三個主要功能：第一、追蹤導覽員（目標物），在任何時刻都要看到移動中的導覽員；第二、當使用者對照相機（觀察者）的路徑不滿意時，可以線上進行即時修改，而系統能保證其不與障礙物碰撞；第三、允許設定慣用動作(Idiom)，以豐富導覽活動。我們實作了這個自動導覽系統，並且根據二維以及三維空間的特性，提出有效率的搜尋演算法，以解決智慧型觀察者追蹤目標物的問題，並讓搜尋的時間能符合線上計算的需求。另外針對線上即時修改路徑和設定慣用動作的部分，我們也提出了線上累進的搜尋方法以及內插權重參數的方式，並以實驗證明了這些設計的有效性。我們相信此類智慧型觀察者的研究，能有效地應用在自動導覽系統或其他應用中，提供使用者以方便的介面瀏覽虛擬環境。 / In this thesis, we have designed an automatic tour-guiding system based on motion planning algorithms to assist users in navigating a virtual environment. This system includes a camera module that was called intelligent observer, which is the focus of this thesis. This module includes three main functions as follows. First, the camera must be able to track the moving tour guide (target) at any time. Second, when a user is not satisfied with the camera’s (observer’s) path, he/she can choose to modify the path on-the-fly without letting the camera collide with the environmental obstacles. Third, it incorporates Cinematographic idioms to enrich tour activities. We have proposed and implemented efficient search algorithms in this system to solve the motion-tracking problem according to the characteristics of the 2D and 3D workspaces. Our experiments show that the performance of this planning system is satisfactory for our on-line application. Moreover, for the parts of modifying paths on-line and

在3D虛擬環境中，使用者透過對化身的控制進行場景瀏覽等各種活動。所謂智慧型化身之控制，是指在化身控制系統中，融入一些人工智慧的方法，協助使用者更有效率的控制化身的運動。本論文對此議題的研究範疇包含兩部分：改進第一人稱控制化身的智慧型介面及將智慧型控制的概念延伸到第三人稱的控制方式上。在以第一人稱控制化身的部分，我們在一個具備虛擬力場輔助的控制系統上，加入適性化的機制，以產生能適應使用者操控習慣的虛擬力場。另外，在一個使用街圖運動計畫法輔助控制的智慧型介面上，我們以虛擬鏈結的觀念改善該方法可能造成使用者繞路的不自然現象。在第三人稱的化身控制上，我們以「組態-時間」街圖的新觀念設計運動計畫演算法，並加上讓運動計畫與控制播放兩個程序協調並行的機制，使系統能在符合即時性的效能下，自動為化身搭配能夠適時閃避障礙物的上半身肢體運動。我們相信此類智慧型控制介面，可增加化身在虛擬環境中控制的便利性，並提高化身在動作呈現上的擬真度。 / In a 3D virtual environment, a user takes part in various activities such as walk-through a scene by controlling the avatar representing the user. Intelligent avatar control means a control mechanism using AI techniques to improve user naviga-tion efficiency. This thesis reports research on two aspects of intelligent avatar control: we attempt to improve the efficiency of the first-person intelligent ava-tar control interfaces and extend the intelligent interface concept to a third-person control mechanism. First, we improve a force-field based intelligent interface by adopting an adaptive mechanism that can generate a tailored force field according to user control behavior. In addition, in a motion-planning based assisting mechanism, we have introduced the concept of virtual link to improve the quality of the generated avatar path. Second, we use the concept of C-T space roadmap to design a new motion planning algorithm to generate collision-free motion for a third-person-controlled avatar. We have designed a mechanism to allow motion generation and execution to happen in parallel and collision-free motions for the upper body of the avatar can be generated in real time. We be-lieve that this type of intelligent control interface can enhance the efficiency of avatar interface control and improve the realism of the generated avatar motions.