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

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

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

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