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