Advisor: Prof. Chin-Shyurng Fahn

TEL: 02-2733-3141 # 7425

Location: RB307-3

Designer: Yu-Ta Lin

任意運動中的多面體物件之近似與精確碰撞偵測

 

  本論文提出在電腦系統所模擬的三度空間圖形環境中之物件間的碰撞偵測演算法。在此環境中,所有物件係由凸多邊形所構成之凸或凹多面體,它們能進行任意平移或且旋轉的運動。我們的演算法可直接使用於這些多面體,且在實際的應用上,必須有兩種不同的解決方法,即為離散時間與連續時間的碰撞偵測,其中前者能夠於固定的時間點偵測碰撞事件之發生位置,而後者能夠於一個時間的區格內決定碰撞事件之近似發生時間與位置。首先,我們使用"空間劃分"(space cell)的方法來局部搜尋物件與物件間之碰撞事件,它是將三度空間分割為較小之隔間(cell),然後,針對運動物件所處的隔間中做物件與物件間的碰撞偵測,以減少物件間之偵測次數。接著,一個"方位—仰角映射"(azimuth-elevation map)的方法被提出來,它係藉由事先將物件的頂點以球體座標值做排序,來快速 地選擇在物件重疊區域中之多邊形。其後,利用外接箱體(bounding box)的方式,提出一個"分割並解決"(divide-and-conquer)的方法,以降低需要做多邊形交錯測試之多邊形的數量。為了處理離散時間與連續時間之碰撞偵測,我們提出了兩個多邊形交錯測試的方法,它們皆使用階層的實現方式以精簡不必要之計算。所有的實驗係在Pentium Pro-180配備64M RAM之個人電腦上,使用微軟Visual C/C++4.0編譯器於微軟Windows NT 4.0作業系統下完成。如文中之實驗所示,空間劃分的方法之時間複雜度係隨物件之數量呈現近似線性地增長。當外接球體(bounding sphere)能簡潔地包住物件所佔用之空間時,則方位—仰角映射的方法將較所有多邊形皆對重疊區域做測試的方法為快,而分割並解決的方法也能夠節省大量的計算時間。最後,我們驗證了所提出之連續時間的碰撞偵測演算法,並將它和離散時間的碰撞偵測演算法做比較,以瞭解它所需要的計算量。截至目前為止,本論文所提出的方法之實驗結果令人鼓舞。