三角網(wǎng)格模型的求交算法研究與實(shí)現(xiàn).pdf

1、本論文主要研究了三角網(wǎng)格模型求交算法。三角面片的剔除很大程度上影響了求交算法的效率，而這類剔除工作是基于碰撞檢測來實(shí)現(xiàn)的。碰撞檢測的目的就是檢測多個(gè)模型在空間位置上是否部分或完全重合，這樣就可以在模型進(jìn)行求交之前剔除大量不相交的三角面片。雖然碰撞檢測技術(shù)已經(jīng)比較成熟，有很多經(jīng)典的研究成果，但隨著計(jì)算機(jī)圖形學(xué)的快速發(fā)展，三角網(wǎng)格模型的復(fù)雜度不斷提升，導(dǎo)致求交算法需要處理的三角面片數(shù)量也成倍增加。為了滿足人們對(duì)場景真實(shí)性、交互實(shí)時(shí)性的更高需

2、求，尋求一種快速準(zhǔn)確的碰撞檢測算法成為當(dāng)前需要迫切解決的問題。
　　 本文在研究和分析了大量碰撞檢測算法的基礎(chǔ)上，總結(jié)了目前主流碰撞檢測算法各自的優(yōu)缺點(diǎn)。這些算法包括空間剖分法、AABB層次包圍盒樹方法和OBB層次包圍盒樹算法，對(duì)如何將這些算法進(jìn)行適當(dāng)?shù)慕Y(jié)合和改進(jìn)，以提高碰撞檢測過程的效率并應(yīng)用于模型間的求交計(jì)算進(jìn)行了一定的探索性研究。
　　 空間剖分算法需要判斷每個(gè)三角面片所占的空間小立方體，這樣可以一步定位兩個(gè)模型的

3、相交情況，但效率不高，尤其是模型復(fù)雜度較高時(shí)，問題就更加突出。OBB層次包圍盒樹方法可以用比較快的速度剔除大量不相交的三角面片，但定位可能相交的三角面片這一操作卻是一個(gè)層層迭代的過程，從這個(gè)角度來說就會(huì)降低一定的效率。針對(duì)兩個(gè)算法各自的問題，本文對(duì)其進(jìn)行了改進(jìn)：只對(duì)一個(gè)求交模型建立包圍盒并進(jìn)行剖分，進(jìn)一步確定組成模型的三角面片所占的空間小立方體，進(jìn)行第一次的剔除。然后再對(duì)剩余的模型用OBB層次包圍盒樹進(jìn)行剔除操作，最后對(duì)剩下的三角面片進(jìn)

4、行求交。改進(jìn)后的算法在一定程度上提高了求交前期三角面片間的碰撞檢測效率，并能剔除較多的三角面片，為下一步的求交工作減輕負(fù)擔(dān)。
　　 AABB層次包圍盒樹方法相對(duì)OBB層次包圍盒，包圍盒緊密性比較差，可能會(huì)導(dǎo)致大量冗余的包圍盒需要進(jìn)行相交測試，但這種方法構(gòu)造簡單、操作簡便。本文結(jié)合了AABB層次包圍盒和OBB層次包圍盒的優(yōu)點(diǎn)，提出一種新的求交算法。每次求交操作都直接作用于模型的包圍盒，求出包圍盒的相交部分，然后將相交包圍盒以外的三

5、角面片全部剔除。對(duì)剩余的三角面片重建包圍盒再次進(jìn)行求交剔除操作，當(dāng)剩余的模型三角面片達(dá)到某個(gè)設(shè)定的閾值之后包圍盒求交停止進(jìn)行。通過這一操作，能夠剔除較多數(shù)量的三角面片，一定程度上減少了進(jìn)入下一階段求交的三角面片數(shù)。然后再利用OBB層次包圍盒對(duì)剩余的三角面片進(jìn)行進(jìn)一步的剔除，最后對(duì)剩余的三角面片進(jìn)行兩兩求交。
　　 最后，我們使用VC++與OpenGL實(shí)現(xiàn)了上述的兩個(gè)改進(jìn)的算法，實(shí)驗(yàn)表明，兩種算法應(yīng)用于三角網(wǎng)格模型間的求交計(jì)算，求