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

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

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