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

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

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

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

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