複雜環境之碰撞偵測

Abstract

複雜環境之碰撞偵測 學生 : 羅金仁 指導教授 : 莊榮宏 博士 國立交通大學資訊工程研究所 摘 要 兩個以上的物體在空間中移動時會發生兩兩接觸的情形。當這種狀況發生 在模擬真實世界 的系統中時，系統必需能夠偵測出來並且修正這兩個物 體的移動方向以防止一個物體的表 面刺穿另一個物體。當系統中物體的 表面不規則時，偵測碰撞、計算碰撞點及碰撞時間會 變得非常困難而且 計算耗時。本篇論文中考慮的對象是任意形狀的三角網點鋼體。當其作 任意方向、任意角度的移動及轉動時希望能提供一個有效的偵測碰撞並找 出碰撞點及碰撞 時間的方法。作法上我們將利用不同的觀點設計三個過 濾器來當作計算真正碰撞點、碰撞 時間的前置處理。透過這些過濾器能 很快濾除不必要的計算來增快速度。通過這三個過濾 器的物體表面代表 極可能發生碰撞的面。對於這些面我們提出一個方法將其拿來作精細的 運算以找出物體間真正的接觸點及接觸時間。經過模擬系統實測的結果發 現過濾器過濾效 果與預期結果接近，執行速度亦佳。計算真正碰撞點與 碰撞時間卻是執行速度的瓶頸所在 。我們亦將提出一個加速計算的方法 。 Collision Detection for Complex Environments Student : Chin-Ran Lo Advisor : Dr. Jung-Hong Chuang Institute of Computer Science and Information Engineering National Chiao-Tung University ABSTRACT When more than two objects move in 3D space, one may collide with another. In a virtual reality or visual simulation system, this system has to detect the collision and modify the movement of the objects in order to prevent them from interpenetration. When the objects in this system are not regular, collision detection is a time-consuming process. In this thesis, we consider the collision detection for rigid objects represented in trianglular meshes whose moving direction and rotation angle need not to be known in advance. We propose three filters to filter out pairs of objects and triangles that are impossible to collide and, as a result, leaves only triangles that are likely to collide with each other. We also propose a method to compute the exact colliding time and point between two sets of moving triangular modeles. The proposed filtering processes perform very well in practical models with little computing time. Computing the exact colliding time and point is, however, time comsuming. Methods that speed up the process are also described.