三維空間中的碰撞檢測技術研究

鐘淑平

（長江工程職業技術學院 湖北 武漢 430212）

0 引言

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

1 碰撞檢測技術的包圍盒算法概述

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

1.1 AABB 算法

AABB 包圍盒主要是通過構建規則長方體網格對三維模型進行逼近，即構建能夠包裹住待檢測模型的最小長方體。在公式中可以通過三維空間坐標上的六個坐標值進行描繪，稱為最大值、最小值表示法。公式如下：

式中xmin、xmax、ymin、ymax、zmin、zmax 表示三維模型在坐標空間中頂點投影的最大值和最小值。

此外，還可以通過中心－半徑表示法和長度表示法進行描繪，公式如下：

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

AABB 包圍盒結構簡單、算法易于實現，且執行效率較高[5]。針對外觀較為規則的模型來說，AABB 包圍盒的空間利用率非常高，一般性的相交檢測都能夠實現。但AABB包圍盒的算法設計并未考慮到方向問題，因此三維物體動態平移、旋轉的情況下，會大大降低算法的檢測精度，同時該算法也不適用于不規則形態模型的精確檢測。

1.2 OBB 算法

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

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

OBB 包圍盒相較于AABB 包圍盒，對于任意方向變化的模型檢測效果更好，且算法開銷適中，在提高檢測質量的同時還能很好的兼顧執行效率。缺點與AABB 包圍盒一樣，采用規則的長方幾何體構造，對邊界復雜的模型包裹緊密度較差，無法實現細節化的碰撞檢測。

1.3 k-DOPs 包圍盒

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

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

2 層次包圍盒的構建

上述三種包圍盒算法在檢測的精度與執行效率等方面各有優勢，因此可以通過層次包圍盒的構建，以實現這些算法優勢的有效融合。

2.1 層次包圍盒的構建思路和檢測流程的設計

層次包圍盒的主要構建思路是通過對三維模型的細化和分割，以實現對其更加精確的檢測，并采用層次式樹狀結構對模型細化的完整過程進行管理，依據不同層級上的檢測需求選擇適當的包圍盒算法實現檢測[8]。檢測流程設計如圖1所示：

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

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

2.2 層次包圍盒的構建

層次包圍盒的構建包括三個關鍵因素，即樹結構的選擇、構造方式的選擇和包圍盒算法的選擇[9]。

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

（2）BVH 樹按照樹的構造層級劃分包括三種構造方式：從根節點劃分、從葉節點合并、層級漸進插入。

從根節點劃分構造方式，首先對待檢測模型構造一個完整包圍盒，將其信息存儲在根節點中，再將其逐層進行子樹劃分，產生的子節點中會包含若干圖元信息，并以節點為單位構造包圍盒，然后繼續分割子節點，直到包含單一圖元信息的葉節點。該構造方式的核心是子樹的劃分，可以采用超平面分割法，通過平面對模型進行左右對稱式分割。

從葉節點合并構造方式，先分割待檢測模型的基本圖元，構建葉節點，每個基本圖元對應一個葉節點，并構造相應的包圍盒，逐層向上對相鄰的節點進行兩兩合并，直至根節點對應完整模型的包圍盒信息。相較于從根節點劃分的構造方式，該方法實現過程相對復雜，但構造的BVH樹結構更為優化。

層級漸進插入方式是一種動態構造方式，初始狀態下先構建一個只包含根節點的空樹，動態構建包圍盒的過程中不斷將新產生的節點插入到根節點下。在插入新的節點之前，需要先將節點包圍盒與根節點包圍盒進行比對，當節點包圍盒體積大于根節點包圍盒時，則尤其替換根節點；反之則插入根節點的下層。當BVH 樹包含兩個層級以上，需要通過遞歸將新的節點逐層向下比對，并插入到適當位置。

（3）包圍盒算法的選擇

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

3 基于混合算法的層次包圍盒構建

基于混合算法層次包圍盒——BVH 樹的構建結構如圖2所示：

圖2 基于混合層次包圍盒的BVH 樹結構

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

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

4 結論

隨著虛擬仿真技術在各行各業的廣泛應用，用戶對三維場景的交互體驗要求越來越高，需求也日趨復雜。在此背景前提下，本研究對三維場景交互實現的關鍵技術——碰撞檢測技術的核心算法設計進行了深入研究和探討，詳細分析了AABB、OBB、k-DOPs 三種包圍盒算法的設計思路與實現過程，結合三種包圍盒算法的優缺點，提出了基于混合包圍盒算法構建BVH 層次樹的碰撞檢測策略，一方面能夠有效提高碰撞檢測技術的精度，另一方面能夠確保在精確檢測環節中算法的執行效率和響應速度。