基于WebGL 三維場景的碰撞檢測技術研究

張振寰

（湖北孝感美珈職業學院 湖北 孝感 432017）

0 引言

3D 繪圖協議（Web Graphics Library，WebGL）是基于Web 應用開發的三維圖形處理技術，以開放式圖形庫（Open Graphics Library，OpenGL）為底層核心庫，提供了基于硬件的圖形渲染加速接口，具有非常高效的圖形處理性能，可以提供基于Web 瀏覽器的三維圖形顯示、三維場景交互等服務[1]。其中三維場景漫游、交互功能需要通過碰撞檢測技術來實現。碰撞檢測技術用于完成虛擬場景對真實世界物理特性的模擬，也就是讓虛擬場景中的物體具有“實體”，用戶可以與這些具有“實體”的物體進行交互，也可以對其進行仿真操作。最初三維場景的應用需求比較簡單，主要集中在游戲和娛樂方面，碰撞檢測主要用于防止三維物體的穿透、重疊以及對用戶的簡單響應[2]，對于碰撞檢測的精度與實時性方面并沒有太高的要求，WebGL 內置的碰撞檢測組件就可以滿足大部分的用戶需求。因此，本研究提出了一種基于WebGL 碰撞檢測狀態機的混合算法改進策略，以滿足三維場景碰撞檢測的高精度、高實時性需求。

1 碰撞檢測技術概述

1.1 碰撞檢測的實現流程

隨著三維場景中模型和材質等素材的不斷精細化、復雜化，碰撞檢測算法很難獨立完成對場景中復雜對象的碰撞檢測，而是需要經過多個階段的整合處理，稱為碰撞檢測的一般實現流程。碰撞檢測的實現流程主要包括3 個處理階段：碰撞檢測預處理階段、碰撞檢測階段、碰撞檢測結果響應階段，見圖1。

其中碰撞檢測的預處理階段，主要用于完成三維場景中模型的動態加載與結構優化處理。三維場景中所有的模型不會在初始運行時就被全部加載，這是為了保障系統的運行效率，節約內存開銷，也就是說瀏覽器視圖會以攝像機的深度設置參數為基準，只對進入攝像機視角范圍內的模型進行加載和渲染，隨著視角在場景中的移動變換，再動態加載新的模型資源[3]，碰撞檢測也只針對加載完成的模型進行檢測。同時預處理階段還需要依據模型的屬性類別進行結構優化，三維場景中的模型可以通過屬性設置區分為動態模型與靜態模型兩種，動態模型是指可以進行一些復雜交互的虛擬物體，例如移動、旋轉、點擊交互等，這類的模型結構較為復雜，對碰撞檢測的準確度和實時性要求也更高；靜態模型是指置于場景中的固定不動的虛擬物體，例如場景中的障礙物、墻體、透明材質的空間邊界等，這類物體往往結構簡單，交互功能單一，只需要具有最基本的碰撞檢測功能即可。

碰撞檢測階段，通過調用各類碰撞檢測算法實現碰撞檢測。目前較為主流的3D 開發引擎大都借助碰撞機組件實現對碰撞算法的封裝與調用，針對碰撞檢測精度要求較低、場景交互單一的應用開發，配置適當的碰撞機組件即可解決一般性的碰撞檢測問題。而針對高要求的復雜場景的碰撞檢測，則需要進行更為復雜的算法設計。復雜算法設計通常包括兩個步驟：第1 步針對靜態模型進行粗糙檢測，常采用的算法有層次包圍盒、空間劃分等算法；第2步針對動態模型進行高精度、實時性檢測，常采用連續碰撞檢測算法或離散碰撞檢測算法。

碰撞檢測結果響應階段，用于輸出碰撞檢測的結果信息以及響應事件的邏輯控制，其中碰撞檢測的結果信息具體包括檢測的時間點、檢測的坐標位置等；響應事件的邏輯控制指的是對碰撞檢測結果進行邏輯判斷，已決定響應的事件類型。

1.2 碰撞檢測算法概述

常用的碰撞檢測算法有很多，但大致可以歸為兩大類：基于空間域和基于時間域的碰撞檢測算法，見圖2。

空間域的算法是基于三維圖像的空間劃分或模型幾何空間的圖元分解實現碰撞檢測的算法，又可分為圖像空間檢測算法與幾何空間檢測算法。圖像空間檢測算法以硬件為輔助，通過GPU 實現對三維圖像的二維投影，在依據二維空間的中投影信息進行圖像是否相交的判斷檢測。幾何空間檢測算法則是利用數學幾何原理進行碰撞檢測的相關計算，是完全基于編程實現的算法，經典的檢測算法主要有空間剖分法和層次包圍樹算法。空間剖分法是將三維空間按照一定規則設定進行區域劃分，然后以區域為單位對區域內或相鄰區域的物體進行檢測。常用的區域劃分方法有均勻網格劃分、8 叉樹劃分和2 叉樹遞歸劃分等。該算法適用于空間分布比較均勻的物體檢測，如局部區域內檢測物體過多，會大大降低計算效率，并存在一定的漏檢現象。層次包圍樹算法是先通過包圍盒技術對不相交物體進行快速剔除，再對物體進行更高精度的相交檢測。其中相交的每個檢測對象將視作一個葉子節點，同屬一個父節點的葉子節點，可以通過父節點的相交檢測來快速判定葉子節點是否相交，并通過遞歸到達根節點。依據包圍盒的構建原理不同，常用的包圍盒檢測算法有固定軸向包圍盒（AABB）、球心包圍盒（Sphere）、可變方向包圍盒（OBB）和離散方向多面體（k-dop）等[4]。

基于時間域的算法是基于模型的運動狀態進行碰撞檢測的算法，可以分為離散碰撞檢測算法和連續碰撞檢測算法。該類算法專門用于檢測實時碰撞，其中離散碰撞檢測算法是將三維物體的運動全過程進行有限的時間分段，表示為[t0，t1]，[t1，t2]，…… [tn-1，tn][5]，然后在每個時間段的邊界點上進行采樣和檢測。如果時間分段過多，可以提高檢測的精度，但會影響檢測性能，如果時間分段少，則會降低檢測精度。連續碰撞檢測算法則是對動態場景進行連續時段設置，表示為[t0，tn]，在連續時段內對運動物體進行連續采樣和檢測，可以完全避免漏檢和運動穿透問題，但運算效率較低。

2 基于WebGL的碰撞檢測技術實現

WebGL 內置了多個碰撞檢測狀態機用于實現不同環境需求下的碰撞檢測，這些狀態機以幾何體算法原理為核心，通過快速生成的規則幾何體對需要檢測的模型區域進行框選，剔除了不需要檢測的區域后，再進行區域內和區域邊界的相交檢測，相交檢測算法主要采用了基于包圍盒檢測的AABB、OBB 等算法[6]。依據幾何體的生成方式不同，狀態機可以分為球形狀態機、網格狀態機、環形狀態機、立方體狀態機、地形狀態機、膠囊狀態機6 種。其中球形、環形、立方體狀態機只能通過規則幾何體進行簡單的區域劃分，檢測精度較低，但計算效率很高，適用于框架類或結構簡單的模型檢測，例如樓體、墻體、足球、籃球等模型；地形狀態機生成類似平面的幾何體，用于實現三維場景的地面檢測，防止物體穿透地面；膠囊狀態機生成的膠囊型幾何體，適用于人體、動物類模型的碰撞檢測；網格狀態機則是依據模型的網格分布動態生成的不規則幾何體，適用于網格結構較為復雜的模型檢測，但運行效率較低。

WebGL 創建部分狀態機的代碼如下：

//創建一個默認立方體狀態機

var box=BABYLON.Mesh.CreateBox("box"，scene);

//創建一個默認球形狀態機

var sphere=BABYLON.Mesh.CreateSphere("sphere"，scene);

//創建一個地形狀態機

var plane=BABYLON.Mesh.CreatePlane("plane"，scene);

WebGL 基于狀態機的屬性設置代碼如下（以立方體狀態機為例）：

//狀態機的材質設置

box.material=new BABYLON.StandardMaterial("material"，scene);

//狀態機的坐標原點設置

box.position=new BABYLON.Vector3(0，0，0);

//狀態機的縮放比設置

box.scaling=new BABYLON.Vector3(1，Math.cos(Math.PI/2)，Math.cos(Math.PI/2));

WebGL 的碰撞檢測狀態機可以滿足大多數的碰撞檢測需求，但在以下3 個方面仍然具有明顯的局限性。

（1）狀態機算法設計較為簡單，為了節省計算開銷，并未引入層級式樹狀管理的概念，更適用于檢測數量不多的小規模的三維場景應用，而在大型場景或模型結構復雜的檢測環境內，由于檢測節點之間沒有建立緊密的邏輯關系，導致每個點都需要進行完整的檢測計算，反而會付出更大的計算代價。

（2）狀態機的空間劃分是粗糙的，通過一些基本的幾何體包圍盒進行空間劃分和檢測，以忽略模型的細節表示為代價換取較為流暢的檢測效果，結果往往是模型之間雖然不能穿透，但會有部分相交，大大影響了檢測精度。

（3）缺少針對動態模型的有效檢測方法，模型運動中邊界檢測的實時性較差，導致穿透現象非常嚴重。

3 基于WebGL的碰撞檢測優化策略

為了有效改進WebGL的碰撞檢測精度和實時檢測性能，在原有的狀態機包圍盒算法基礎上將AABB 與OBB 算法進行混合設計，其主要原理是在包圍盒樹狀結構中，將子葉節點與父節點視作內外兩層，外層采用AABB 包圍盒檢測法，用于快速完成空間劃分，以剔除不需檢測的區域；內層采用OBB 包圍盒檢測法，并加入了時間變量，基于時間區間進行連續采樣，用于實現區域內實時的精確檢測。

AABB 包圍盒在三維空間中是一個各邊都平行于坐標軸的六面立方體，首先遍歷待檢測模型的所有頂點，并獲取其在坐標軸上的最大投影值（maxX，maxY，maxZ）和最小投影值（minX，minY，minZ），然后生成能夠包圍模型的最小立方體。AABB 包圍盒的8 個頂點坐標的取值范圍可以用以下公式表示：

AABB 碰撞檢測就是對立方體包圍盒6 個面的坐標投影進行相交檢測，將待檢測物體的投影最小值與碰撞到的物體投影最大值進行比較，即可得出結論。

由于AABB 包圍盒的方向是固定的，要與坐標軸平行，因此當物體旋轉運動時，AABB 包圍盒的檢測性能將大大下降。因此內層采用OBB 包圍盒檢測法可以有效解決這一問題。

OBB包圍盒是三維空間中可以任意方向的六面立方體，通過中心點（CP）到立方體3 個方向（D1，D2，D3）的半徑（R1，R2，R3）距離來表示，表示公式：

OBB 包圍盒方向的確定，首先要獲取構成模型的所有的三角面圖元的頂點坐標；然后計算出頂點均值以確定立方體的中心點，通過計算頂點的協方差矩陣得到基于中心點實對稱的三階矩陣；最后通過實對稱三階矩陣分別計算特征向量的內積，取內積為零的3 個特征向量用以確定立方體方向。

OBB 包圍盒邊長的確定，遍歷模型上的所有頂點在3個方向軸上的投影距離即可得到包圍盒的邊長值。OBB 包圍盒的數值表示共需要15 個浮點數，包括3 個方向的9個浮點數和6 個邊長值。

OBB 基于分離軸來檢測物體是否相交，兩個待檢測的OBB 包圍盒之間最多可以有15 條分離軸，其中任意一條軸與單個待檢測模型的任意面正交，或者同時與兩個待檢測模型的任意面正交，即可認為它們不相交，否則判定為產生碰撞。

對于內層OBB 檢測，如果涉及的是運動中的物體檢測，可以設定時間區間，并在區間內進行連續檢測，以實現動態模型的實時性檢測。連續碰撞檢測的時間區間設置算法有很多，較為常用的有掃掠法、步進法和光線追蹤法等。WebGL 的第三方庫three.js 提供的射線碰撞檢測組件采用的就是光線追蹤算法，其實現原理是對運動中的物體綁定射線組件，以物體中心點作為視點投射出多條光線，設場景中障礙物若干，所有待檢測的點表示為P，取值范圍[P1，Pn]，當光線與任意P 點產生交點，即認為進入了動態檢測區，并選擇距離最近的P 點，通過距離計算時間區間。射線碰撞檢測組件的調用代碼示例：

var ray = new THREE.Raycaster(originPoint，direction.normalize()，near，far);

其中，originPoint 參數表示射線的起點向量；direction.normalize()表示射線的歸一化方向向量；near 可選參數，默認值為零，表示射線長度不小于0；far 可選參數，默認無窮大，表示射線長度不大于far。

4 結語

本研究針對WebGL 三維場景漫游下碰撞檢測技術的實現展開了深入研究，并在此基礎上對WebGL 原有的包圍盒檢測技術進行了改進與優化，嘗試采用樹狀結構將AABB與OBB 兩種包圍盒算法進行層次式混合，以提高檢測精度，并結合WebGL 第三方庫three.js 的射線檢測方式完善了WebGL 的實時碰撞檢測功能，以便為相關領域的研究應用提供一定的參考價值。