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