來源:http://www.vbgamedev.com/AI/pz.htm
碰撞檢測技術——凸包的建立
-ZH1110
實時碰撞檢測是機器人、動畫仿真、虛擬現(xiàn)實等領域中一個非常關鍵的問題，其基本任務是確定兩個或多個物體彼此之間是否發(fā)生接觸或穿透。
多面體尤其是凸體良好的空間結(jié)構特性如空間連貫性可被利用來優(yōu)化碰撞檢測的效率。因此，基于多面體，尤其是基于凸體的碰撞檢測算法一直是碰撞檢測算法中的一個研究重點
一般的AABB,OBB樹由于包圍較松散，會產(chǎn)生較多的節(jié)點，我們選擇研究凸包包圍體,其包圍物體緊密,但相互之間的求交計算更復雜
1．包圍球的球心求法
設物體頂點坐標所含最大最小值分別為：xmax,xmin,ymax,ymin,zmax,zmin,則球心坐標為：
2．包圍球半徑的求法
2.凸包 凸包概念:點集Q的凸包(convex hull)是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內(nèi)。下圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。
平面凸包的求法：
凸包最常用的凸包算法是Graham掃描法和Jarvis步進法。
對于一個有三個或以上點的點集Q，過程如下：
計算點集最右邊的點為凸包的頂點的起點，如上圖的P3點。
Do
For i = 0 To 總頂點數(shù)
計算有向向量P3->Pi
If 其余頂點全部在有向向量P3->Pi的左側(cè)或右側(cè)，則Pi點為凸包的下一頂點
Pi點加入凸包列表
GoTo 1
End If
Next
Exit Do
1:
Loop
此過程執(zhí)行后，點按極角自動順時針或逆時針排序，只需要按任意兩點的次序就可以了。而左側(cè)或右側(cè)的判斷可以用前述的矢量點積性質(zhì)實現(xiàn)。
文件下載