基于虛擬現(xiàn)實環(huán)境的建模技術(shù)中碰撞檢測算法的改進.pdf

1、碰撞檢測是計算機動畫、計算機圖形學等領域的重要課題。近幾年來，隨著虛擬現(xiàn)實技術(shù)和分布式仿真技術(shù)的興起，碰撞檢測問題成為一個研究熱點。快速的碰撞檢測對提高虛擬環(huán)境的真實性、增強虛擬環(huán)境的交互性有著至關重要的作用，因此有必要在時間或是空間上進行優(yōu)化以滿足動態(tài)實時性的要求。本文在對各類碰撞檢測算法作出全面了解和透徹分析的基礎上，從以下兩個方面對變形物體的碰撞檢測問題進行研究，提出新的檢測碰撞的思想和方法。
　　 （1）從存儲空間角度入

2、手，對包圍盒樹存儲需求問題進行研究。觀察發(fā)現(xiàn)，AABB包圍盒樹中大約一半的結(jié)點，它們與父結(jié)點之間的空隙只占父結(jié)點空間的10％，因此可以壓縮存儲AABB樹。為此，提出一種優(yōu)化的AABB包圍盒樹算法。算法首先簡化樹中每個結(jié)點存儲的包圍盒信息，減少父結(jié)點和子結(jié)點間冗余數(shù)據(jù)的存儲，然后將樹中所有葉結(jié)點的存儲信息放置到其父結(jié)點里，從AABB樹的存儲結(jié)構(gòu)里刪除葉結(jié)點。實驗表明，結(jié)合包圍盒父結(jié)點和葉結(jié)點的存儲優(yōu)化，既節(jié)省了算法所需的存儲空間，又加快了

3、算法的執(zhí)行速度。
　　 （2）從執(zhí)行時間角度入手，提出了一種改進的相交測試算法。對于改進的AABB包圍盒，從父結(jié)點的包圍盒信息可以得到其子結(jié)點的包圍盒，因此可以將對子結(jié)點包圍盒信息的計算放到父結(jié)點，即在計算父結(jié)點包圍盒信息的時候就把其子結(jié)點的包圍盒計算好，將結(jié)果傳至子包圍盒。這樣，子結(jié)點在做相交測試的時候就不需要再計算自己的包圍盒信息，可以直接進行相交測試，浮點運算次數(shù)減少了一大半。實驗結(jié)果表明，改進的相交測試算法加快了碰撞檢測