張振寰

（湖北孝感美珈職業(yè)學院 湖北 孝感 432017）

0 引言

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

1 碰撞檢測技術(shù)概述

1.1 碰撞檢測的實現(xiàn)流程

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

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

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

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

1.2 碰撞檢測算法概述

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

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

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

2 基于WebGL的碰撞檢測技術(shù)實現(xiàn)

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

WebGL 創(chuàng)建部分狀態(tài)機的代碼如下：

//創(chuàng)建一個默認立方體狀態(tài)機

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

//創(chuàng)建一個默認球形狀態(tài)機

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

//創(chuàng)建一個地形狀態(tài)機

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

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

//狀態(tài)機的材質(zhì)設置

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

//狀態(tài)機的坐標原點設置

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

//狀態(tài)機的縮放比設置

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

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

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

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

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

3 基于WebGL的碰撞檢測優(yōu)化策略

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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