基于Vega的碰撞檢測算法研究

霍光　李中英

摘要：虛擬環境下的碰撞檢測問題是當今計算機圖形學研究的熱點之一。針對復雜場景實時漫游過程中的碰撞檢測本文提出了一種將分割過濾法與包圍盒技術相融合的碰撞檢測方法，在Vega平臺下，應用本算法成功實現了桌面級非沉浸式虛擬漫游系統，在檢測精度和檢測速度上都取得了滿意的效果。

關鍵詞：分割過濾 實時漫游

引言

在虛擬環境中，為了模擬真實世界，讓用戶獲得高度的沉浸感，就必須為用戶提供具有關鍵交互作用的虛擬環境。虛擬現實系統一個最重要功能，就是能快速進行虛擬世界中物體間的碰撞檢測。精確的碰撞檢測對提高虛擬環境的真實性、增強虛擬環境的沉浸感起著至關重要的作用，而虛擬環境自身的復雜性和實時性對碰撞檢測提出了更高的要求[1]。

1為觀察者建立碰撞檢測模型

漫游者在漫游過程中會與地面、障礙物發生碰撞。雖然Vega 有對地面碰撞檢測的定義，但對于自定義的運動模型根本起不到實質的作用，因此本文采用基于視線的BUMP算法進行碰撞檢測。

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

（2）包圍球

包圍球被定義為包含該對象的最小的球體，計算給定對象E的包圍球，首先需分別確定被包圍幾何對象中各個頂點的x，y，z坐標均值以確定包圍球的球心c，再由球心與三個最大值坐標所確定的點間的距離計算半徑r，包圍球的計算時間略多于AABB，但存儲一個包圍球只需兩個浮點數。

包圍球的緊密性在所有包圍盒中是比較差的，它除了對在三個坐標軸上分布得比較均勻的幾何體外，幾乎都會留下很大的空隙。但包圍球有一個比較優秀的特性，就是對于旋轉運動來說，包圍球不需要做任何更新，因而當對象進行頻繁的旋轉運動時，采用包圍球可能的到較好的結果。

3包圍盒的改進

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

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

（1）降維

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

（2）收縮

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

?誗 減少了包圍盒的數量；

?誗 縮小包圍盒的范圍；

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

（3）選建

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

4 碰撞檢測優化方法

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

此方法的目的是為了在系統進行碰撞檢測時，較少實體比較的次數。在漫游的過程中，只需根據視點所在位置的坐標，就可以確定視點所在的網格，然后，再與該網格內的物體進行碰撞檢測即可。從而大大的較少了碰撞檢測的計算量，提高了碰撞檢測的速度。對于包含有大量地物的模型，效果尤為明顯。

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

5 實驗結果

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

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

參考文獻

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

[2] 陳華斌 王彤，虛擬建筑環境實時漫游系統的設計和實現，西南交通大學學報，2001

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

[4] 支劍鋒 韓長紅，虛擬景區中層次碰撞檢測方法的研究，電腦知識與技術，2011