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

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

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

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

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

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