周守東

摘要：虛擬仿真滅火培訓(xùn)系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)基于虛擬現(xiàn)實(shí)技術(shù)，而碰撞檢測(cè)是虛擬現(xiàn)實(shí)得以實(shí)現(xiàn)的關(guān)鍵技術(shù)之一。模擬系統(tǒng)設(shè)計(jì)對(duì)AABB包圍盒碰撞檢測(cè)算法進(jìn)行改進(jìn)，提出基于Virtools網(wǎng)格的包圍盒算法。實(shí)驗(yàn)表明，改進(jìn)后的包圍盒算法減少了碰撞檢測(cè)的誤差，提高了模擬系統(tǒng)人機(jī)交互的沉浸感。

關(guān)鍵詞：虛擬仿真系

；Virtools；碰撞檢測(cè)；虛擬現(xiàn)實(shí)技術(shù)

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）14-0174-03

1概述

虛擬現(xiàn)實(shí)技術(shù)是一門(mén)富有挑戰(zhàn)性的交叉技術(shù)前沿學(xué)科和研究領(lǐng)域。是它多種技術(shù)集合，包括計(jì)算機(jī)圖形學(xué)、實(shí)時(shí)三維技術(shù)、廣角立體顯示技術(shù)、動(dòng)作捕捉技術(shù)，以及力反饋、網(wǎng)絡(luò)技術(shù)、語(yǔ)音技術(shù)等。使用者通過(guò)各種設(shè)備與計(jì)算機(jī)生成的虛擬空間完成各種交互行為，從而實(shí)現(xiàn)仿真交互。虛擬仿真模擬滅火系統(tǒng)是典型的虛擬現(xiàn)實(shí)系統(tǒng)，基于虛擬現(xiàn)實(shí)技術(shù)模擬滅火培訓(xùn)全過(guò)程；模擬火災(zāi)場(chǎng)景，構(gòu)建真實(shí)感強(qiáng)的虛擬場(chǎng)景。在虛擬現(xiàn)實(shí)場(chǎng)景漫游中經(jīng)常要觸發(fā)的一個(gè)動(dòng)作就是要進(jìn)行碰撞檢測(cè)，碰撞檢測(cè)對(duì)增強(qiáng)虛擬場(chǎng)景漫游的臨場(chǎng)感起到了至關(guān)重要的作用。碰撞檢測(cè)是虛擬現(xiàn)實(shí)領(lǐng)域重要的研究課題。碰撞檢測(cè)做得好了不易被人注意到，但是做得差了卻很容易讓人發(fā)現(xiàn)，人物經(jīng)常被卡住不能前進(jìn)或者人物穿越了障礙。很多研究人員對(duì)此開(kāi)展了系統(tǒng)研究，獲得了不少比較成熟的算法，如層次包圍盒算法中的AABB算法，OBB算法，還有k-DOP算法等。這些算法的主要關(guān)鍵點(diǎn)就是用形狀簡(jiǎn)單的盒子圍住待測(cè)對(duì)像，以包圍盒與其他圖形的相交性來(lái)檢測(cè)。這些算法雖然方便快捷，但針對(duì)復(fù)雜圖形的物體誤差較大。隨著虛擬現(xiàn)實(shí)技術(shù)的普及和推廣，體驗(yàn)者對(duì)虛擬仿真的要求也從新奇逐步升級(jí)為注重仿真度的體驗(yàn)。用戶(hù)需求對(duì)虛擬仿真的模擬技術(shù)提出了舒適度及真實(shí)度的更高要求，虛擬仿真技術(shù)中采用的碰撞檢測(cè)算法對(duì)于虛擬仿真產(chǎn)品的體驗(yàn)感有相當(dāng)重要的影響，本文主要針對(duì)仿真模型采用的碰撞檢測(cè)算法是在傳統(tǒng)AABB包圍盒算法的基礎(chǔ)上進(jìn)行優(yōu)化，對(duì)其不足進(jìn)行改進(jìn)。

2碰撞事件處理算法分析

2.1基于球形包圍檢測(cè)法的碰撞檢測(cè)

在虛擬場(chǎng)景中，為需要檢測(cè)的物體用一個(gè)不可見(jiàn)的球體進(jìn)行包圍，即用球體來(lái)替代不規(guī)則物體進(jìn)行碰撞檢測(cè)。當(dāng)檢測(cè)到有包圍器發(fā)生碰撞時(shí)，采取相應(yīng)措施，以避免碰撞。其實(shí)現(xiàn)思路如圖1所示。

包圍球碰撞檢測(cè)算法是虛擬仿真碰撞檢測(cè)最常用的一種基礎(chǔ)算法。算法使用球體作為基礎(chǔ)包容體，將碰撞檢測(cè)體進(jìn)行包圍，以包圍球的碰撞檢測(cè)替代三維模型的碰撞檢測(cè)。包圍球碰撞檢測(cè)算法極大減少了碰撞檢測(cè)的復(fù)雜度，以最小的系統(tǒng)資源滿(mǎn)足了實(shí)時(shí)碰撞的響應(yīng)速度，但對(duì)應(yīng)的缺點(diǎn)是碰撞檢測(cè)精度不夠精確，誤差冗余較大，經(jīng)常會(huì)導(dǎo)致用戶(hù)的誤操作，用戶(hù)體驗(yàn)度較差。

為了提高基礎(chǔ)包圍球算法的精度，在基礎(chǔ)包圍球算法的基礎(chǔ)上進(jìn)行優(yōu)化，提出了球體樹(shù)解決方案。球體樹(shù)算法實(shí)際上是依據(jù)三維物體層次結(jié)構(gòu)構(gòu)造一個(gè)由基礎(chǔ)包圍球構(gòu)成的集合。具體實(shí)現(xiàn)方法為：首先分析三維模型的層次結(jié)構(gòu)，根據(jù)其層次結(jié)構(gòu)對(duì)模型進(jìn)行拆分；其次對(duì)拆分出的三維模型逐個(gè)進(jìn)行碰撞檢測(cè)球體的包圍和綁定；最后依據(jù)包圍球數(shù)組的碰撞檢測(cè)結(jié)果，判斷是否發(fā)生碰撞檢測(cè)及碰撞部位。

球體樹(shù)算法解決了包圍球算法的碰撞檢測(cè)精度問(wèn)題，缺點(diǎn)是對(duì)三維模型的分析和拆分較為復(fù)雜，球體樹(shù)內(nèi)部碰撞檢測(cè)判斷設(shè)定繁瑣，不利于技術(shù)的普及和推廣。

2.2基于AABB檢測(cè)法的碰撞檢測(cè)

包圍球雖然簡(jiǎn)單，但用球體來(lái)包容一個(gè)三維物體，通過(guò)上述分析我們可以發(fā)現(xiàn)其中存在很多問(wèn)題。盒子包圍法即是對(duì)作為碰撞檢測(cè)對(duì)象的球改成長(zhǎng)方體，降低了碰撞檢測(cè)的計(jì)算維度，同時(shí)也會(huì)在布局上緊湊很多。

目前，盒子包圍碰撞檢測(cè)的算法主要有兩種，分別是AABB（axis-aligned bounding box）盒包圍算法和OBB（Orient Bounding Biox）盒包圍算法。

AABB（axis-aligned bounding box）盒子，即軸對(duì)齊包圍盒，主要用于比較規(guī)則的物體進(jìn)行碰撞檢測(cè)。算法利用長(zhǎng)方體對(duì)三維模型進(jìn)行包圍，立方體的每一條邊都平行于一個(gè)坐標(biāo)平面且與坐標(biāo)系的軸垂直，如圖2所示。

與包圍球相同，針對(duì)復(fù)雜的三維模型，同樣可以構(gòu)建由包圍盒組成的AABB盒子樹(shù)。由于AABB盒子是一種降低維度的檢測(cè)計(jì)算，所以與包圍球檢測(cè)算法不同的是，AABB盒子樹(shù)之間的碰撞檢測(cè)更為優(yōu)化。對(duì)于兩個(gè)AABB盒子的碰撞檢測(cè)，我們僅需要在兩個(gè)維度上對(duì)坐標(biāo)投影進(jìn)行檢測(cè)便可以判斷兩者之間是否有碰撞發(fā)生，如果投影重疊表示有碰撞發(fā)生，反之則沒(méi)有發(fā)生碰撞，如圖3所示。

AABB盒子雖然簡(jiǎn)單，但是當(dāng)物體傾斜時(shí)，檢測(cè)盒就會(huì)隨之變大，一方面增加了系統(tǒng)檢測(cè)消耗，同時(shí)碰撞檢測(cè)精度也隨之下降；當(dāng)物體發(fā)生旋轉(zhuǎn)時(shí)，對(duì)AABB盒子要進(jìn)行重新的計(jì)算賦值，這時(shí)候就必須對(duì)物體的整個(gè)檢測(cè)系統(tǒng)重新進(jìn)行定義，增加了系統(tǒng)負(fù)擔(dān)。

OBB（Oriem Bounding Box）盒子，即是帶有方向的包圍盒，它是在AABB盒子的基礎(chǔ)上增加了方向，使包圍盒能有解決任意方向的碰撞檢測(cè)，主要是對(duì)AABB盒子在檢測(cè)旋轉(zhuǎn)后的模型與其他模型之間的缺點(diǎn)進(jìn)行強(qiáng)化。

3系統(tǒng)中的碰撞檢測(cè)設(shè)計(jì)

3.1設(shè)計(jì)模型及其包圍盒

決定碰撞檢測(cè)效率及質(zhì)量的因素，除算法外，還有一個(gè)很重要的因素就是場(chǎng)景管理。碰撞檢測(cè)對(duì)系統(tǒng)資源的需求，主要取決于場(chǎng)景中需要監(jiān)聽(tīng)并解算碰撞的包圍盒的數(shù)量，即參與碰撞檢測(cè)的三維模型的數(shù)量。高效的場(chǎng)景管理，可以極大的減少當(dāng)前運(yùn)行場(chǎng)景中三維模型的數(shù)量，從而很大程度上提高系統(tǒng)運(yùn)行速度及效率。

在場(chǎng)景管理?xiàng)l件相同的情況下，如場(chǎng)景中參與碰撞檢測(cè)的盒體數(shù)量為n，最原始的算法則是需要每幀對(duì)每個(gè)監(jiān)聽(tīng)盒體進(jìn)行逐個(gè)比較，即n（n-1）/2次，效率很低。針對(duì)碰撞檢測(cè)再加上時(shí)間就更麻煩，于是采取算法簡(jiǎn)化策略，優(yōu)化監(jiān)聽(tīng)對(duì)比效率，優(yōu)化簡(jiǎn)略代碼如下：

3.2基于網(wǎng)格檢測(cè)的優(yōu)化

基于包圍盒的碰撞檢測(cè)技術(shù)在虛擬世界中應(yīng)用的很廣泛，在Virtools里還提供了另外一種獨(dú)特的碰撞檢測(cè)的方法：通過(guò)Grid實(shí)現(xiàn)基于網(wǎng)格的碰撞檢測(cè)。在本項(xiàng)目中最終采用AABB碰撞檢測(cè)來(lái)完成常規(guī)碰撞檢測(cè)，利用網(wǎng)格碰撞檢測(cè)控制整個(gè)場(chǎng)景的大范圍，防止角色漫游出邊界導(dǎo)致系統(tǒng)運(yùn)行出現(xiàn)錯(cuò)誤。

具體實(shí)現(xiàn)：場(chǎng)景中從俯視圖將場(chǎng)景投射到一個(gè)二維區(qū)域，將這個(gè)二維區(qū)域用網(wǎng)格加以細(xì)分和定義，使其作為一個(gè)不可見(jiàn)的三維體，賦予碰撞檢測(cè)屬性。這種碰撞檢測(cè)方法一般采用滑動(dòng)的方法將角色控制在二維區(qū)域范圍內(nèi)。這種方法的優(yōu)點(diǎn)是比較簡(jiǎn)單，但碰撞檢測(cè)的精度不高，而且對(duì)高度不同的地形，要根據(jù)地形的高度同步進(jìn)行調(diào)整。

在投射的二維區(qū)域表面創(chuàng)建Virtools檢測(cè)網(wǎng)格，通過(guò)顏色來(lái)定義整個(gè)場(chǎng)景的邊界和碰撞檢測(cè)范圍，通過(guò)腳本和LayerSlider BB行為交互模塊完成對(duì)角色漫游范圍的控制。在VT中首先將地面賦予Floor屬性，然后通過(guò)Character Keep On Floor BB來(lái)實(shí)現(xiàn)角色跟隨地面高度的變化。

3.3仿真結(jié)果分析

建立測(cè)試場(chǎng)景，對(duì)優(yōu)化后的算法進(jìn)行效率及成果驗(yàn)證。為便于分析，在測(cè)試場(chǎng)景中制作AB兩組三維模型對(duì)象，A組模型對(duì)象適配于包圍盒，B組模型對(duì)象為AABB碰撞檢測(cè)存在缺點(diǎn)的狹長(zhǎng)體。實(shí)驗(yàn)設(shè)定一個(gè)用于碰撞檢測(cè)的剛體小球在測(cè)試框內(nèi)隨機(jī)出現(xiàn)，分別記錄單位時(shí)間段系統(tǒng)檢測(cè)到的交叉碰撞次數(shù)。具體實(shí)驗(yàn)中，單位時(shí)間段分別取值8s、10s及15s。實(shí)驗(yàn)結(jié)果如表1所示。其中上面三行為AABB碰撞檢測(cè)算法成果數(shù)據(jù)，下面三行為優(yōu)化后的Grid+AABB動(dòng)態(tài)檢測(cè)算法。

通過(guò)分析可以得出：三維模型對(duì)象在采用Grid分割后濾除了對(duì)象誤差區(qū)域的碰撞，提高了碰撞檢測(cè)的正確率。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，尤其是針對(duì)原始AABB誤差率較高的狹長(zhǎng)形三維模型對(duì)象有著較大的優(yōu)勢(shì)。

4結(jié)束語(yǔ)

碰撞檢測(cè)技術(shù)是計(jì)算機(jī)虛擬仿真技術(shù)中的核心技術(shù)之一。碰撞檢測(cè)的精度很大程度上決定了虛擬仿真最終產(chǎn)品的數(shù)據(jù)真實(shí)性及用戶(hù)體驗(yàn)滿(mǎn)意度。本文針對(duì)仿真滅火系統(tǒng)中設(shè)計(jì)到的碰撞檢測(cè)算法問(wèn)題，以成熟的AABB包圍盒碰撞檢測(cè)算法為基礎(chǔ)，針對(duì)AABB碰撞檢測(cè)算法在虛擬滅火碰撞檢測(cè)中存在的問(wèn)題進(jìn)行優(yōu)化設(shè)計(jì)。提出了在Virtools中基于Grid的AABB碰撞檢測(cè)算法改進(jìn)方案，經(jīng)過(guò)實(shí)際案例測(cè)試，表明該方案不僅提高了系統(tǒng)運(yùn)行效率，同時(shí)對(duì)軟件的碰撞檢測(cè)也有了較大的提高。