一種三維碰撞檢測并行算法的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、隨著計(jì)算機(jī)軟硬件以及網(wǎng)絡(luò)等技術(shù)的日益成熟，人們迫切希望能對(duì)現(xiàn)實(shí)世界進(jìn)行真實(shí)的模擬，以解決實(shí)際問題。而碰撞檢測問題是計(jì)算機(jī)動(dòng)畫，物理仿真，計(jì)算幾何，機(jī)器人學(xué)，計(jì)算機(jī)游戲等領(lǐng)域的重要課題。在虛擬環(huán)境中，碰撞檢測可以為物體之間的交互建立良好的基礎(chǔ)。因此，如何在很高的實(shí)時(shí)交互要求下完成對(duì)大量復(fù)雜物體的相交測試是碰撞檢測研究的首要目標(biāo)。
　　 分析和比較了當(dāng)前幾種常用碰撞檢測算法的優(yōu)勢(shì)和不足，有效地結(jié)合軸對(duì)齊包圍盒（Aligned Axi

2、s Bounding Box，AABB）算法和二叉空間剖分（Binary Space Partitioning，BSP）算法進(jìn)行碰撞檢測。根據(jù)兩種碰撞檢測算法自身的特點(diǎn)，把BSP算法應(yīng)用于碰撞初步檢測階段，把AABB算法應(yīng)用于詳細(xì)碰撞檢測階段，并優(yōu)化AABB的更新算法，減少計(jì)算量，從而提高碰撞檢測效率；給出了一種新的分治策略，在多處理器機(jī)器上利用多進(jìn)程和多線程技術(shù)，根據(jù)虛擬環(huán)境中的復(fù)雜度，把碰撞檢測問題分而治之分配給不同的線程并行處理；

3、通過主從進(jìn)程模式來進(jìn)行通信控制。算法充分地利用了硬件資源，從而大大地提高了碰撞檢測效率，也增強(qiáng)了虛擬環(huán)境的真實(shí)性和可靠性。
　　 在總體安全監(jiān)測與評(píng)估平臺(tái)上的三維實(shí)時(shí)顯示與報(bào)警模塊中，結(jié)合基于BSP和AABB的三維碰撞檢測并行算法設(shè)計(jì)了相關(guān)的測試案例，并與基本碰撞檢測算法、串行碰撞檢測算法進(jìn)行對(duì)比，從理論時(shí)間復(fù)雜度和實(shí)際運(yùn)行時(shí)間兩方面進(jìn)行了性能測試。測試結(jié)果表明，使用基于BSP和AABB的三維并行碰撞檢測時(shí)，系統(tǒng)幀率明顯增加，系