基于K-DOPS的快速碰撞檢測算法研究.pdf

1、碰撞檢測是虛擬現(xiàn)實、動畫仿真、計算機(jī)輔助設(shè)計等領(lǐng)域不可回避的問題之一,其基本任務(wù)是確定兩個或多個物體彼此之間是否發(fā)生接觸或穿透。盡管人們已經(jīng)取得了一系列成果,但是這些算法側(cè)重于考慮碰撞檢測的精確性,很少涉及實時性。隨著計算機(jī)軟硬件及網(wǎng)絡(luò)等技術(shù)的日益成熟,交互實時性、場景真實性要求令碰撞檢測再度成為圖形學(xué)研究的熱點。本文主要研究基于K-DOPS包圍盒方法的碰撞檢測,闡述了K-DOPS包圍盒的原理,提出并證明了一種快速區(qū)間測試法以解決兩個K

2、-DOPS包圍盒間的相交測試問題,通過查找兩個包圍盒在由固定方向集合所定義的方向軸上的范圍區(qū)間是否存在不重疊的情況,來判斷它們是否不相交。通過這種簡單的區(qū)間測試法,兩個包圍盒間的相交測試最多只需要k次比較運算(k為固定方向集合的大小)。在充分開發(fā)和利用虛擬環(huán)境中對象運動的時空相關(guān)性的基礎(chǔ)上,提出了加速對象間碰撞檢測速度的遍歷跟蹤策略。這是一個啟發(fā)式的策略,通過跟蹤上一時間采樣點對包圍盒樹的遍歷過程,確定當(dāng)前時間采樣點的遍歷路徑,從而有效