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

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

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

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