三維空間中的碰撞檢測(cè)技術(shù)研究

鐘淑平

（長(zhǎng)江工程職業(yè)技術(shù)學(xué)院 湖北 武漢 430212）

0 引言

碰撞檢測(cè)是三維場(chǎng)景中交互事件觸發(fā)最主要的方式，通過(guò)碰撞檢測(cè)技術(shù)可以為三維場(chǎng)景中的虛擬物體添加物理模擬屬性，使虛擬物體具有實(shí)體，當(dāng)實(shí)體之間發(fā)生碰撞被檢測(cè)到以后，就可以動(dòng)態(tài)觸發(fā)交互事件。三維場(chǎng)景最初的應(yīng)用主要是在游戲和娛樂(lè)領(lǐng)域，場(chǎng)景結(jié)構(gòu)較為簡(jiǎn)單，對(duì)碰撞檢測(cè)的精度和響應(yīng)時(shí)延等需求也較低，3D 開發(fā)引擎的內(nèi)置組件就可以滿足一般性的碰撞檢測(cè)需求[1]。而隨著三維技術(shù)的快速發(fā)展和應(yīng)用普及，在很多的專業(yè)領(lǐng)域也需要應(yīng)用三維交互技術(shù)，例如工業(yè)流程的模擬作業(yè)、醫(yī)療器械設(shè)備的模擬操作等，這些三維場(chǎng)景對(duì)交互的響應(yīng)時(shí)延和精準(zhǔn)度都具有很高的要求，而原有的碰撞檢測(cè)技術(shù)只能實(shí)現(xiàn)簡(jiǎn)單場(chǎng)景下規(guī)則模型的邊界檢測(cè)，無(wú)法滿足更高精度的檢測(cè)，為了提高檢測(cè)精度，算法設(shè)計(jì)過(guò)于復(fù)雜又難以保證檢測(cè)的響應(yīng)[2]。因此，本研究嘗試采用混合分層式包圍盒算法改進(jìn)策略，以提高復(fù)雜場(chǎng)景下的碰撞檢測(cè)精度和實(shí)時(shí)性。

1 碰撞檢測(cè)技術(shù)的包圍盒算法概述

碰撞檢測(cè)技術(shù)的算法有很多，其中包圍盒是應(yīng)用最為廣泛的一類算法[3]。包圍盒算法是典型的基于幾何體空間檢測(cè)的算法，其核心思路是通過(guò)構(gòu)建規(guī)則幾何體網(wǎng)格對(duì)三維模型進(jìn)行包裹，通過(guò)檢測(cè)幾何體網(wǎng)格之間的相交情況來(lái)判斷是否產(chǎn)生碰撞。主流的包圍盒檢測(cè)算法包括：軸對(duì)齊包圍盒（Axis-aligned Bounding Box,AABB）、方向包圍盒（Oriented Bounding Box,OBB）、k-DOPs包圍盒等算法[4]。

1.1 AABB 算法

AABB 包圍盒主要是通過(guò)構(gòu)建規(guī)則長(zhǎng)方體網(wǎng)格對(duì)三維模型進(jìn)行逼近，即構(gòu)建能夠包裹住待檢測(cè)模型的最小長(zhǎng)方體。在公式中可以通過(guò)三維空間坐標(biāo)上的六個(gè)坐標(biāo)值進(jìn)行描繪，稱為最大值、最小值表示法。公式如下：

式中xmin、xmax、ymin、ymax、zmin、zmax 表示三維模型在坐標(biāo)空間中頂點(diǎn)投影的最大值和最小值。

此外，還可以通過(guò)中心－半徑表示法和長(zhǎng)度表示法進(jìn)行描繪，公式如下：

式中xc、yc、zc表示三維模型在坐標(biāo)空間中的中心坐標(biāo)投影；rx、ry、rz表示三維模型在坐標(biāo)空間中的投影半徑，可由式（4）獲??；WX、Wy、Wz表示三維模型在坐標(biāo)空間中的投影長(zhǎng)度，可由式（5）獲取。

AABB 包圍盒結(jié)構(gòu)簡(jiǎn)單、算法易于實(shí)現(xiàn)，且執(zhí)行效率較高[5]。針對(duì)外觀較為規(guī)則的模型來(lái)說(shuō)，AABB 包圍盒的空間利用率非常高，一般性的相交檢測(cè)都能夠?qū)崿F(xiàn)。但AABB包圍盒的算法設(shè)計(jì)并未考慮到方向問(wèn)題，因此三維物體動(dòng)態(tài)平移、旋轉(zhuǎn)的情況下，會(huì)大大降低算法的檢測(cè)精度，同時(shí)該算法也不適用于不規(guī)則形態(tài)模型的精確檢測(cè)。

1.2 OBB 算法

OBB 包圍盒可以理解為帶有方向的AABB 包圍盒，采用OBB 算法構(gòu)建的包圍盒可以適配任意旋轉(zhuǎn)角度的三維模型檢測(cè)。OBB 包圍盒的構(gòu)建，可以由式（6）表示：

式中O 表示包圍盒的中心點(diǎn)坐標(biāo)；r1、r2、r3表示包圍盒三個(gè)軸向上的半徑；v1、v2、v3表示正交向量，用于來(lái)描繪包圍盒的方向，可由協(xié)方差公式獲取[6]。首先假設(shè)待檢測(cè)的三維模型的所有面片均為三角形面片，其中單個(gè)三角形面片j 的頂點(diǎn)坐標(biāo)可以表示為Aj（Ajx，Ajy，Ajz）、Bj（Bjx，Bjy，Bjz）、Cj（Cjx，Cjy，Cjz），三角形面片總數(shù)為n，中心點(diǎn)O 的公式表示如下：

OBB 包圍盒相較于AABB 包圍盒，對(duì)于任意方向變化的模型檢測(cè)效果更好，且算法開銷適中，在提高檢測(cè)質(zhì)量的同時(shí)還能很好的兼顧執(zhí)行效率。缺點(diǎn)與AABB 包圍盒一樣，采用規(guī)則的長(zhǎng)方幾何體構(gòu)造，對(duì)邊界復(fù)雜的模型包裹緊密度較差，無(wú)法實(shí)現(xiàn)細(xì)節(jié)化的碰撞檢測(cè)。

1.3 k-DOPs 包圍盒

k-DOPs 包圍盒是一種多面不規(guī)則幾何體包圍盒，也稱為離散型包圍盒[7]。k-DOPs 包圍盒所有面的法線向量由方向集合k決定，k的值越大，包圍盒的面數(shù)構(gòu)建越復(fù)雜，對(duì)模型的逼近度也就越高，而AABB 與OBB 包圍盒也是屬于k-DOPs 的一個(gè)特例6-DOPs。構(gòu)建k-DOPs 包圍盒的算法設(shè)計(jì)與OBB 包圍盒相類似，但首先需要基于固定方向k 集合進(jìn)行三維空間的分離，構(gòu)成半空間，再選擇k/2 個(gè)方向進(jìn)行法向量的中心點(diǎn)和協(xié)方差計(jì)算。這是因?yàn)榱硗鈑/2 方向的法向量選取的是基于共線的相反向量，構(gòu)建的半空間只需對(duì)稱過(guò)去即可構(gòu)成完整的包圍盒。計(jì)算法線向量的協(xié)方差是一個(gè)三階對(duì)稱式矩陣，其公式如下：

k-DOPs 包圍盒檢測(cè)精度的高低取決于k值的大小，k值越大，精度越高、算法開銷越大、執(zhí)行效率也就越低。

2 層次包圍盒的構(gòu)建

上述三種包圍盒算法在檢測(cè)的精度與執(zhí)行效率等方面各有優(yōu)勢(shì)，因此可以通過(guò)層次包圍盒的構(gòu)建，以實(shí)現(xiàn)這些算法優(yōu)勢(shì)的有效融合。

2.1 層次包圍盒的構(gòu)建思路和檢測(cè)流程的設(shè)計(jì)

層次包圍盒的主要構(gòu)建思路是通過(guò)對(duì)三維模型的細(xì)化和分割，以實(shí)現(xiàn)對(duì)其更加精確的檢測(cè)，并采用層次式樹狀結(jié)構(gòu)對(duì)模型細(xì)化的完整過(guò)程進(jìn)行管理，依據(jù)不同層級(jí)上的檢測(cè)需求選擇適當(dāng)?shù)陌鼑兴惴▽?shí)現(xiàn)檢測(cè)[8]。檢測(cè)流程設(shè)計(jì)如圖1所示：

圖1 基于層次包圍盒的算法檢測(cè)流程

層次包圍盒首先通過(guò)遞歸將待檢測(cè)模型進(jìn)行圖元分割，并將其結(jié)構(gòu)信息以BVH 節(jié)點(diǎn)樹進(jìn)行存儲(chǔ)，根節(jié)點(diǎn)表示模型本身，中間節(jié)點(diǎn)表示模型分割后的局部信息，葉節(jié)點(diǎn)表示分割模型的最小單位——圖元的信息。檢測(cè)流程首先對(duì)根節(jié)點(diǎn)進(jìn)行檢測(cè)，當(dāng)根節(jié)點(diǎn)未與其他包圍盒發(fā)生相交，則可以直接判定模型未發(fā)生碰撞；當(dāng)根節(jié)點(diǎn)檢測(cè)到相交，則按照節(jié)點(diǎn)樹的層次結(jié)構(gòu)逐層遞歸遍歷所有的內(nèi)部節(jié)點(diǎn)，直到鎖定相交節(jié)點(diǎn)，并通過(guò)該節(jié)點(diǎn)上的圖元信息獲知模型碰撞的具體位置。

2.2 層次包圍盒的構(gòu)建

層次包圍盒的構(gòu)建包括三個(gè)關(guān)鍵因素，即樹結(jié)構(gòu)的選擇、構(gòu)造方式的選擇和包圍盒算法的選擇[9]。

（1）樹結(jié)構(gòu)的選擇是指樹的節(jié)點(diǎn)結(jié)構(gòu)選擇，樹的節(jié)點(diǎn)結(jié)構(gòu)主要分為二叉樹、三叉樹、四叉樹和八叉樹[10]。樹的橫向節(jié)點(diǎn)分叉值越大，縱向深度節(jié)點(diǎn)就會(huì)減少，層次間的迭代次數(shù)也會(huì)減少，可以節(jié)省更多的內(nèi)存空間，同時(shí)檢測(cè)精度也會(huì)更準(zhǔn)確，但在模型的相交檢測(cè)過(guò)程中，會(huì)成倍增加相交的節(jié)點(diǎn)數(shù)，檢測(cè)流程的判斷次數(shù)也會(huì)成倍增長(zhǎng)，算法開銷較大，因此樹結(jié)構(gòu)的選擇還需要結(jié)合具體的三維場(chǎng)景需求進(jìn)行。

（2）BVH 樹按照樹的構(gòu)造層級(jí)劃分包括三種構(gòu)造方式：從根節(jié)點(diǎn)劃分、從葉節(jié)點(diǎn)合并、層級(jí)漸進(jìn)插入。

從根節(jié)點(diǎn)劃分構(gòu)造方式，首先對(duì)待檢測(cè)模型構(gòu)造一個(gè)完整包圍盒，將其信息存儲(chǔ)在根節(jié)點(diǎn)中，再將其逐層進(jìn)行子樹劃分，產(chǎn)生的子節(jié)點(diǎn)中會(huì)包含若干圖元信息，并以節(jié)點(diǎn)為單位構(gòu)造包圍盒，然后繼續(xù)分割子節(jié)點(diǎn)，直到包含單一圖元信息的葉節(jié)點(diǎn)。該構(gòu)造方式的核心是子樹的劃分，可以采用超平面分割法，通過(guò)平面對(duì)模型進(jìn)行左右對(duì)稱式分割。

從葉節(jié)點(diǎn)合并構(gòu)造方式，先分割待檢測(cè)模型的基本圖元，構(gòu)建葉節(jié)點(diǎn)，每個(gè)基本圖元對(duì)應(yīng)一個(gè)葉節(jié)點(diǎn)，并構(gòu)造相應(yīng)的包圍盒，逐層向上對(duì)相鄰的節(jié)點(diǎn)進(jìn)行兩兩合并，直至根節(jié)點(diǎn)對(duì)應(yīng)完整模型的包圍盒信息。相較于從根節(jié)點(diǎn)劃分的構(gòu)造方式，該方法實(shí)現(xiàn)過(guò)程相對(duì)復(fù)雜，但構(gòu)造的BVH樹結(jié)構(gòu)更為優(yōu)化。

層級(jí)漸進(jìn)插入方式是一種動(dòng)態(tài)構(gòu)造方式，初始狀態(tài)下先構(gòu)建一個(gè)只包含根節(jié)點(diǎn)的空樹，動(dòng)態(tài)構(gòu)建包圍盒的過(guò)程中不斷將新產(chǎn)生的節(jié)點(diǎn)插入到根節(jié)點(diǎn)下。在插入新的節(jié)點(diǎn)之前，需要先將節(jié)點(diǎn)包圍盒與根節(jié)點(diǎn)包圍盒進(jìn)行比對(duì)，當(dāng)節(jié)點(diǎn)包圍盒體積大于根節(jié)點(diǎn)包圍盒時(shí)，則尤其替換根節(jié)點(diǎn)；反之則插入根節(jié)點(diǎn)的下層。當(dāng)BVH 樹包含兩個(gè)層級(jí)以上，需要通過(guò)遞歸將新的節(jié)點(diǎn)逐層向下比對(duì)，并插入到適當(dāng)位置。

（3）包圍盒算法的選擇

常用的包圍盒算法中，AABB 軸對(duì)齊包圍盒結(jié)構(gòu)最為簡(jiǎn)單、測(cè)試難度小、執(zhí)行效率高，但動(dòng)態(tài)檢測(cè)效果差，模型包裹緊密度差；OBB 方向包圍盒增加了法向量屬性，能夠更好地逼近模型，但檢測(cè)效果依然存在較大誤差，且算法復(fù)雜度要高于AABB 包圍盒；k-DOPs 包圍盒的構(gòu)造最為復(fù)雜，緊密度最高，但在物體運(yùn)動(dòng)過(guò)程中，算法更新較慢，執(zhí)行效率較低。綜合這三種算法的自身特點(diǎn)，考慮在BVH樹的根節(jié)點(diǎn)層級(jí)可以選擇AABB 算法，用于實(shí)現(xiàn)待檢測(cè)物體的快速檢測(cè)，通過(guò)粗糙檢測(cè)首先判斷物體是否存在相交，如果存在，再做進(jìn)一步的精確檢測(cè)；在BVH 樹的中間可以選擇緊密性更好的OBB 算法，以判斷是物體的哪個(gè)局部發(fā)生相交；鎖定局部區(qū)域后，在BVH 樹的底部葉節(jié)點(diǎn)處采用k-DOPs 算法對(duì)物體的基本圖元依次進(jìn)行相交檢測(cè)，以最終確定模型的相交部位。這種基于混合算法的層次包圍盒構(gòu)建策略，能夠大大提高碰撞檢測(cè)的精準(zhǔn)度，同時(shí)還能保證檢測(cè)效率。

3 基于混合算法的層次包圍盒構(gòu)建

基于混合算法層次包圍盒——BVH 樹的構(gòu)建結(jié)構(gòu)如圖2所示：

圖2 基于混合層次包圍盒的BVH 樹結(jié)構(gòu)

由上圖可知，BVH 樹構(gòu)建采用二叉樹結(jié)構(gòu)，自頂向下從根節(jié)點(diǎn)開始進(jìn)行模型分割，頂層根節(jié)點(diǎn)選擇AABB 包圍盒，中間節(jié)點(diǎn)選擇OBB 包圍盒，底部葉節(jié)點(diǎn)選擇k-DOPs包圍盒。

首先是根節(jié)點(diǎn)層級(jí)對(duì)模型整體進(jìn)行包圍盒的構(gòu)造，通過(guò)模型頂點(diǎn)的最大值與最小值采集，確定模型的中心點(diǎn)與半徑，即可依據(jù)公式2.2 構(gòu)造AABB 包圍盒。再以AABB 包圍盒的最長(zhǎng)邊為分割軸對(duì)模型進(jìn)行左右子集的分割，若最長(zhǎng)邊分割難以實(shí)現(xiàn)，遞歸調(diào)用最短軸分割法，以包圍盒最短軸為分割軸進(jìn)行分割。其次分割后圖元子集作為中間節(jié)點(diǎn)，采用OBB 算法構(gòu)建子集包圍盒，圖元子集作為模型的局部區(qū)域，采用帶有方向包圍盒，能夠具有更好的緊密性。針對(duì)OBB 包圍盒的分割，可以采用平面分割法進(jìn)行分割，即在包圍盒中確定一個(gè)平面作為超平面，依據(jù)圖元子集相對(duì)于平面的位置進(jìn)行二叉樹的子集劃分。如果存在基本圖元橫跨平面的現(xiàn)象，則以圖元的質(zhì)心與平面的相對(duì)位置為依據(jù)進(jìn)行劃分。最后當(dāng)劃分的子集僅包含單一圖元時(shí)，表示為BVH 樹的葉節(jié)點(diǎn)層，葉節(jié)點(diǎn)采用k-DOPs 算法構(gòu)建包圍盒，對(duì)基本圖元實(shí)現(xiàn)緊密包裹，且不再進(jìn)行分割。該層級(jí)主要用于實(shí)現(xiàn)精確級(jí)別的碰撞檢測(cè)，因此除了基于包圍盒的相交檢測(cè)，還增加了基于圖元的檢測(cè)步驟?；緢D元大都以三角形面片為主，判斷三角形面片是否相交，可以通過(guò)點(diǎn)與點(diǎn)、線段與線段、點(diǎn)與三角形面的相交測(cè)試等方式來(lái)確定。

4 結(jié)論

隨著虛擬仿真技術(shù)在各行各業(yè)的廣泛應(yīng)用，用戶對(duì)三維場(chǎng)景的交互體驗(yàn)要求越來(lái)越高，需求也日趨復(fù)雜。在此背景前提下，本研究對(duì)三維場(chǎng)景交互實(shí)現(xiàn)的關(guān)鍵技術(shù)——碰撞檢測(cè)技術(shù)的核心算法設(shè)計(jì)進(jìn)行了深入研究和探討，詳細(xì)分析了AABB、OBB、k-DOPs 三種包圍盒算法的設(shè)計(jì)思路與實(shí)現(xiàn)過(guò)程，結(jié)合三種包圍盒算法的優(yōu)缺點(diǎn)，提出了基于混合包圍盒算法構(gòu)建BVH 層次樹的碰撞檢測(cè)策略，一方面能夠有效提高碰撞檢測(cè)技術(shù)的精度，另一方面能夠確保在精確檢測(cè)環(huán)節(jié)中算法的執(zhí)行效率和響應(yīng)速度。