基于Vega的碰撞檢測(cè)算法研究

霍光　李中英

摘要：虛擬環(huán)境下的碰撞檢測(cè)問題是當(dāng)今計(jì)算機(jī)圖形學(xué)研究的熱點(diǎn)之一。針對(duì)復(fù)雜場(chǎng)景實(shí)時(shí)漫游過程中的碰撞檢測(cè)本文提出了一種將分割過濾法與包圍盒技術(shù)相融合的碰撞檢測(cè)方法，在Vega平臺(tái)下，應(yīng)用本算法成功實(shí)現(xiàn)了桌面級(jí)非沉浸式虛擬漫游系統(tǒng)，在檢測(cè)精度和檢測(cè)速度上都取得了滿意的效果。

關(guān)鍵詞：分割過濾 實(shí)時(shí)漫游

引言

在虛擬環(huán)境中，為了模擬真實(shí)世界，讓用戶獲得高度的沉浸感，就必須為用戶提供具有關(guān)鍵交互作用的虛擬環(huán)境。虛擬現(xiàn)實(shí)系統(tǒng)一個(gè)最重要功能，就是能快速進(jìn)行虛擬世界中物體間的碰撞檢測(cè)。精確的碰撞檢測(cè)對(duì)提高虛擬環(huán)境的真實(shí)性、增強(qiáng)虛擬環(huán)境的沉浸感起著至關(guān)重要的作用，而虛擬環(huán)境自身的復(fù)雜性和實(shí)時(shí)性對(duì)碰撞檢測(cè)提出了更高的要求[1]。

1為觀察者建立碰撞檢測(cè)模型

漫游者在漫游過程中會(huì)與地面、障礙物發(fā)生碰撞。雖然Vega 有對(duì)地面碰撞檢測(cè)的定義，但對(duì)于自定義的運(yùn)動(dòng)模型根本起不到實(shí)質(zhì)的作用，因此本文采用基于視線的BUMP算法進(jìn)行碰撞檢測(cè)。

該方法使用6段線段，包括x,y的正負(fù)方向和由相交矢量的位置和方向定義的z軸正負(fù)方向。線段長度分別由相對(duì)于x,y,z軸線段的3個(gè)屬性VGIS-_BUMP_WIDTH、VGIS_BUMP_LENGTH和VGIS_BUMP_HEIGHT控制。通常情況下，該方法比其它方法代價(jià)更高，但是卻更為靈活適用。這是因?yàn)樵谠摲椒ㄖ杏?段線段而不是3段線段，其線段不僅有長度，還有方向。但缺點(diǎn)是在碰撞實(shí)體選擇時(shí)，往往不知道視線應(yīng)與哪一個(gè)多邊形求交，如果每次都要對(duì)整個(gè)場(chǎng)景中所有表面多邊形全部都遍歷一遍，勢(shì)必產(chǎn)生巨大運(yùn)算量，造成無謂的浪費(fèi)。因此，在實(shí)現(xiàn)基于視線的碰撞檢測(cè)算法時(shí)，可以考慮借助包圍盒來簡化碰撞的模型，以提高碰撞檢測(cè)的效率。

（2）包圍球

包圍球被定義為包含該對(duì)象的最小的球體，計(jì)算給定對(duì)象E的包圍球，首先需分別確定被包圍幾何對(duì)象中各個(gè)頂點(diǎn)的x，y，z坐標(biāo)均值以確定包圍球的球心c，再由球心與三個(gè)最大值坐標(biāo)所確定的點(diǎn)間的距離計(jì)算半徑r，包圍球的計(jì)算時(shí)間略多于AABB，但存儲(chǔ)一個(gè)包圍球只需兩個(gè)浮點(diǎn)數(shù)。

包圍球的緊密性在所有包圍盒中是比較差的，它除了對(duì)在三個(gè)坐標(biāo)軸上分布得比較均勻的幾何體外，幾乎都會(huì)留下很大的空隙。但包圍球有一個(gè)比較優(yōu)秀的特性，就是對(duì)于旋轉(zhuǎn)運(yùn)動(dòng)來說，包圍球不需要做任何更新，因而當(dāng)對(duì)象進(jìn)行頻繁的旋轉(zhuǎn)運(yùn)動(dòng)時(shí)，采用包圍球可能的到較好的結(jié)果。

3包圍盒的改進(jìn)

前面提到的幾種現(xiàn)在比較常用的碰撞檢測(cè)方法都各有其有缺點(diǎn)。比如：包圍球的緊密性較差，但是它的相交測(cè)試十分簡單；與之相反，方向包圍盒緊密性較好，可是相交測(cè)試相對(duì)困難。

本系統(tǒng)是一個(gè)基于視點(diǎn)的漫游系統(tǒng)，因此，對(duì)碰撞效果的真實(shí)感要求相對(duì)要高一點(diǎn)，而影響碰撞檢測(cè)精度的直接因素就是對(duì)相交檢測(cè)對(duì)象所建立的包圍盒的精度。因此本文選用的包圍盒是一種簡化的OBB。這種簡化包圍盒具有近似OBB的緊密度，同時(shí)，也為后面的碰撞檢測(cè)提供了一種相對(duì)簡單的檢測(cè)模型。具體簡化過程如下：

（1）降維

由于建模的場(chǎng)景是校園，所以大多數(shù)的樓體的基面都是與地面平行的，這就為OBB中最佳方向的計(jì)算提供了一個(gè)約束條件。即最佳方向只可能是與地面水平或垂直的。這樣一來，就可以把三維的OBB計(jì)算簡化為（對(duì)建筑物的垂直投影的）二維計(jì)算。得到二維的最小包圍矩形后，對(duì)每條邊進(jìn)行垂直提拉就可以恢復(fù)到三維的包圍盒了。

（2）收縮

由于本系統(tǒng)所選用的漫游模式是步行，碰撞檢測(cè)的高度不會(huì)超過3米，因此在建立包圍盒時(shí)沒必要把高過3米的物體或物體的某一部分包含在內(nèi)。例如：像房屋的屋檐、大樹的樹冠這類物體一般都是只對(duì)其下部的樓體、樹干建立包圍盒即可。這樣做的優(yōu)點(diǎn)是：

?誗 減少了包圍盒的數(shù)量；

?誗 縮小包圍盒的范圍；

?誗 提高包圍盒的緊密度。

（3）選建

對(duì)于像馬路沿、臺(tái)階這種有一定高度的實(shí)體不建立包圍盒。因?yàn)檫@類物體雖然也有碰撞，但它們是可以跨域的，碰撞瞬間的現(xiàn)象主要表現(xiàn)為漫游者視點(diǎn)高度的增加或減少，而不像樓房那樣碰撞后無法前進(jìn)，所以只要是高度小于跨越高度（zoffset）物體，都不對(duì)其建立包圍盒，而是通過修改其視點(diǎn)高度來實(shí)現(xiàn)其碰撞的效果。

4 碰撞檢測(cè)優(yōu)化方法

對(duì)于范圍較大的場(chǎng)景，且場(chǎng)景中景物繁多的情況，在漫游的過程中實(shí)時(shí)的對(duì)場(chǎng)景中的每一個(gè)物體都進(jìn)行碰撞檢測(cè)，無疑將給系統(tǒng)帶來巨大的計(jì)算開銷，降低系統(tǒng)的性能。為此，人們提出了空間分解法[2]和層級(jí)包圍盒法[3]。本文采用的分割過濾法也屬于空間分解法一種，因此原理也是通過濾去不需要的數(shù)據(jù)，以減少不必要的計(jì)算。所謂分割過濾法就是將漫游場(chǎng)景分割成規(guī)則網(wǎng)格，以此將場(chǎng)景中的物體分割成小的群組。并對(duì)規(guī)則網(wǎng)格建立對(duì)應(yīng)的平面索引表。如圖2所示：

此方法的目的是為了在系統(tǒng)進(jìn)行碰撞檢測(cè)時(shí)，較少實(shí)體比較的次數(shù)。在漫游的過程中，只需根據(jù)視點(diǎn)所在位置的坐標(biāo)，就可以確定視點(diǎn)所在的網(wǎng)格，然后，再與該網(wǎng)格內(nèi)的物體進(jìn)行碰撞檢測(cè)即可。從而大大的較少了碰撞檢測(cè)的計(jì)算量，提高了碰撞檢測(cè)的速度。對(duì)于包含有大量地物的模型，效果尤為明顯。

場(chǎng)景平面索引表中的地物數(shù)據(jù)可能有重復(fù)的現(xiàn)象，這是由于有些地物橫跨兩個(gè)或兩個(gè)以上的地形塊，如圖3所示，A只屬于地形塊1，對(duì)應(yīng)平面索引表的一行。C，D也是如此它們也只屬于地形塊2，不同的只是在一行中有兩條記錄而已。而B則不同，它橫跨4個(gè)地形塊（5,6,9,10），如果只在地形塊5中為其建立一條記錄，那么當(dāng)視點(diǎn)漫游到6,9,10中并與B發(fā)生碰撞時(shí)，由于沒有B的記錄，B也不會(huì)被列入檢測(cè)的范圍，進(jìn)而被檢測(cè)所遺漏。為了避免遺漏現(xiàn)象的出現(xiàn)，本文在平面索引表5,6,9,10四行中，都建立B的記錄，這樣無論在這四塊中的哪一塊碰到B，系統(tǒng)都能檢測(cè)到。

5 實(shí)驗(yàn)結(jié)果

本算法是將整個(gè)場(chǎng)景分割為若干個(gè)小空間，對(duì)每個(gè)小空間的對(duì)象用一個(gè)較為簡單的形體（包圍盒）進(jìn)行描述，再對(duì)該包圍盒進(jìn)行宏觀檢測(cè)，檢測(cè)方法簡單、精確，檢測(cè)速度快，能夠滿足大范圍場(chǎng)景中實(shí)時(shí)交互的要求。

當(dāng)然，BUMP檢測(cè)方法也有它的局限性，如它的視線方向始終是保持水平的，就象人行走在起伏的路面上，人的視線基本保持水平一樣，因此，它可以較好的模擬人的行走。

參考文獻(xiàn)

[1] Kamat V.A survey of techniques for simulation of dynamic collsion detection and response[J], Computer&Graphics,1993,17(4):379-385

[2] 陳華斌 王彤，虛擬建筑環(huán)境實(shí)時(shí)漫游系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)，西南交通大學(xué)學(xué)報(bào)，2001

[3] 胡艷 陳蒙蒙， 一種基于等距線的碰撞檢測(cè)算法，電子科技，2009

[4] 支劍鋒 韓長紅，虛擬景區(qū)中層次碰撞檢測(cè)方法的研究，電腦知識(shí)與技術(shù)，2011