基于最近點(diǎn)碰撞檢測(cè)算法的研究.pdf

1、碰撞檢測(cè)(Collision Detection,CD)在虛擬現(xiàn)實(shí)(Virtual Reality,VR)技術(shù)及游戲中起到舉足輕重的作用。它已經(jīng)成為物理仿真、觸覺(jué)渲染、計(jì)算機(jī)動(dòng)畫和計(jì)算機(jī)可視化等領(lǐng)域的研究熱點(diǎn)。精確性和實(shí)時(shí)性是碰撞檢測(cè)兩大特性。精確度高和實(shí)時(shí)好的碰撞檢測(cè)能提高虛擬環(huán)境的真實(shí)感，增強(qiáng)虛擬環(huán)境沉浸感。所以如何提高算法的精度一直是研究的重點(diǎn)。
　　在解決碰撞檢測(cè)初期檢測(cè)問(wèn)題時(shí)，包圍盒方法無(wú)疑是最有效的。它被大量用在游戲引

2、擎里，以便快速地檢測(cè)出游戲?qū)ο笾g產(chǎn)生的碰撞。包圍盒代表一個(gè)規(guī)則的多邊形或者多面體，它近似地描述了虛擬環(huán)境中物體對(duì)象。本文圍繞2D碰撞檢測(cè)算法進(jìn)行研究，具體研究?jī)?nèi)容如下：(1)軸向矩形包圍盒之間的碰撞檢測(cè)算法，(2)基于分離軸定理碰撞檢測(cè)算法。論文主要研究成果包含以下幾個(gè)方面：
　　1)提出了基于軸向矩形包圍盒(Axis-Aligned Bounding Box, AABB)碰撞檢測(cè)改進(jìn)算法。本文以最近頂點(diǎn)對(duì)為基礎(chǔ)，借助點(diǎn)到直線的

3、投影，提出一種改進(jìn)的碰撞檢測(cè)算法。通過(guò)歐式距離來(lái)判斷頂點(diǎn)是否被軸向矩形包圍。如果最近頂點(diǎn)對(duì)中有一個(gè)頂點(diǎn)滿足條件，則說(shuō)明發(fā)生碰撞。如果最近頂點(diǎn)對(duì)都不滿足條件，則說(shuō)明沒(méi)有發(fā)生碰撞。此改進(jìn)算法降低了有效碰撞檢測(cè)時(shí)間，提高了碰撞檢測(cè)速度。
　　2)提出了基于分離軸定理(Separating Axis Theorem, SAT)碰撞檢測(cè)改進(jìn)算法。在研究凸多邊形特性的基礎(chǔ)上，通過(guò)對(duì)分離軸算法優(yōu)缺點(diǎn)的分析，提出以最近頂點(diǎn)所在邊法線做為潛在分離軸

4、，將中心點(diǎn)所在直線作為第一階段判斷條件的改進(jìn)算法。改進(jìn)算法首先通過(guò)第一階段潛在分離軸的判斷。如果被檢測(cè)的兩個(gè)凸多邊形頂點(diǎn)在直線上投影的最大值和最小值沒(méi)有發(fā)生重疊現(xiàn)象時(shí)，就證明沒(méi)有發(fā)生碰撞。否則進(jìn)入第二階段。該改進(jìn)算法最多需要判斷五條潛在分離軸，最少只需第一階段潛在分離軸的判斷。從而解決了隨著凸多邊形邊數(shù)增加潛在分離軸也增加的問(wèn)題。
　　實(shí)驗(yàn)數(shù)據(jù)表明，優(yōu)化后的包圍盒算法在初期碰撞檢測(cè)階段可以很好解決物體間碰撞檢測(cè)的冗余問(wèn)題，對(duì)虛擬環(huán)