基于兩層體素模型的碰撞檢測算法

陳騫

摘要：碰撞檢測是布爾運算中的關(guān)鍵步驟。針對現(xiàn)有的大尺度三角網(wǎng)格模型的布爾運算時間效率不足的問題，提出一種基于兩層體素模型的碰撞檢測算法，以求提高兩個靜置模型在布爾運算場景中碰撞檢測的速度。在算法中，首先利用AABB包圍盒算法確定模型的相交區(qū)域，然后在相交區(qū)域內(nèi)構(gòu)建起兩級體素模型，檢測出發(fā)生碰撞的體素后，將體素中所對應(yīng)的三角面兩兩進行求交測試，最終以兩個三角網(wǎng)格模型的交線集合作為碰撞檢測算法的結(jié)果。經(jīng)過多組表面復(fù)雜的模型測試，比VTK中的算法時間效率平均提高了90%。

關(guān)鍵詞： 碰撞檢測; 體素模型; 體素化; 布爾運算; AABB包圍盒

中圖分類號：TP391 ? ? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2020）17-0010-04

Abstract： Collision detection is a key step in the process of Boolean operations. To solve the problem of insufficient Boolean operation time efficiency of large-scale triangular mesh model， a collision detection algorithm based on a two-layer voxel model is proposed to improve the efficiency of Boolean operation. The algorithm has three stages， first use the axis-aligned bounding box determine the area of the voxel model， and then construct a two-level voxel model within the intersection area. After detecting the colliding voxel， the corresponding triangles in the voxel are carried out in pairs. For the intersection test， the intersection set of two triangular mesh models is finally used as the result of the collision detection algorithm. After multiple sets of complex triangular mesh tests， the time of this algorithm is increased by 80% on average compared to VTK.

Key words： collision detection; voxel model; voxelization; boolean operation; AABB box

1 引言

三角網(wǎng)格模型的布爾運算是計算機圖形學(xué)領(lǐng)域的一個經(jīng)典問題。布爾運算在3D打印、動畫仿真、虛擬現(xiàn)實、地理信息系統(tǒng)等領(lǐng)域中有著重要的應(yīng)用[1-3]。通過布爾運算可以對現(xiàn)有的三維幾何模型進行交并差等操作得到新的模型。本文以3D打印領(lǐng)域中通用的文件格式STL模型作為算法的輸入結(jié)果。STL模型是一種用三角網(wǎng)格表達模型邊界信息的文件格式。該文件格式以三角面的三個頂點的空間位置和三角面的單位法向量為元素，所有元素的集合即是一個完整的三角網(wǎng)格模型。

現(xiàn)有的常見碰撞檢測算法主要分為兩種類型，層次包圍盒樹法和空間剖分法[4]。層次包圍盒樹法是通過使用一個形狀簡單的包圍盒代替模型中被包圍住的局部信息，如果發(fā)現(xiàn)兩個包圍盒的模型沒有發(fā)生碰撞則可以直接結(jié)束檢測，如果發(fā)生了碰撞，則繼續(xù)查找包圍盒樹的子節(jié)點，逐步篩選過濾掉沒有發(fā)生碰撞的部分[5]。常見的包圍盒有軸對齊包圍盒（Axis Aligned Bounding Box，AABB）、有向包圍盒（Oriented Bounding Box，OBB）、包圍球（Sphere）[6]和K-DOP包圍盒（K-Discrete Oriented Polytope）等。

空間剖分的方法是將物體模型所在的空間分割成多個空間，并以此將空間中的模型分割成多個更小的群組，在當(dāng)前的更小的空間內(nèi)對模型進行相交測試。目前具有代表性的兩種空間分割的方法是BSP樹和八叉樹。BSP樹是二叉樹結(jié)構(gòu)，通過不斷地加入分割平面對模型進行分割為前后兩部分作為樹的兩個子節(jié)點，八叉樹是將當(dāng)前的空間八等分，并將每一個空間作為樹的子節(jié)點。在相交測試中，從根節(jié)點開始，遍歷空間樹的每一個節(jié)點如果相交就繼續(xù)遍歷，如果不相交就放棄該子樹，最后葉子結(jié)點進行三角面片的相交測試。

上述的兩種傳統(tǒng)的碰撞檢測算法在大尺度的STL布爾運算的場景中有著不足之處：包圍盒樹和BSP樹是二叉樹，當(dāng)發(fā)生碰撞的是某一個很小的三角面片時，會有著搜索樹的深度過深，也就是說在最壞情況下效率低的問題?？臻g剖分中往往需要將與剖分面發(fā)生碰撞的三角形也進行剖分計算，這樣就導(dǎo)致了許多不必要的冗余計算。

在模型數(shù)據(jù)量龐大的情況下，傳統(tǒng)的碰撞檢測算法的首先要構(gòu)建包圍盒樹或是空間剖分樹的結(jié)構(gòu)，這就要耗去大量的時間，樹的深度為O（logN），[N]是三角形的數(shù)量，并且在兩個模型的檢測階段需要對樹的每一層的節(jié)點深度遍歷去檢測。然而在實際情況中發(fā)生相交的三角面片對只占模型的很少的一部分，所以傳統(tǒng)的碰撞檢測算法計算上存在大量冗余，于是本文利用體素模型碰撞檢測速度快的優(yōu)勢對碰撞檢測算法進行優(yōu)化，以求達到時間上的高效性。

2 算法實現(xiàn)

本文提出的基于兩級體素模型的算法主要分為三個階段：預(yù)檢測階段、體素化和體素模型求交階段、三角形的精確相交檢測階段。在算法的預(yù)檢測階段，在模型的讀取過程中構(gòu)建模型的AABB包圍盒，如果兩個包圍盒沒有發(fā)生碰撞，則算法結(jié)束，如果發(fā)生碰撞，則求解兩個包圍盒的相交區(qū)域。接著是體素化階段，將上一階段得到的相交區(qū)域作為體素化空間，對模型進行體素化，構(gòu)建起兩層體素模型，接著對體素模型求交得到兩個體素模型的碰撞體素。最后是三角形的精確相交檢測階段，對每個碰撞體素中的兩個模型的三角形兩兩之間進行快速求交檢測，并將求得的交線作為算法的最終結(jié)果。

2.1 預(yù)檢測階段

在預(yù)檢測階段，本文采用構(gòu)建AABB包圍盒的方法來確定兩個物體的可能相交的區(qū)域，并且這個步驟在模型數(shù)據(jù)的讀取期間就可以完成。這一步的目的是初步篩除部分三角形減少了后續(xù)計算的數(shù)據(jù)量，并且可以確立出體素空間的邊界。對于一個AABB包圍盒，我們用一個左下角的點和一個右上角的點來定義，這兩個點的坐標(biāo)值分別（xmin，ymin，zmin）和（xmax，ymax，zmax），在模型的讀取期間不斷地更新這6個值，即可完成兩個模型AABB包圍盒的構(gòu)建。然后通過判斷兩個包圍盒的在各個軸的投影是否有重疊來判斷兩個包圍盒是否發(fā)生相交，如果都沒有發(fā)生相交則算法結(jié)束，兩個模型沒有發(fā)生碰撞，如果發(fā)生相交，則對兩個包圍盒求交集，通過對兩個包圍盒的投影求交可以快速地構(gòu)建待體素化區(qū)域S。

在式（2）中 S表示求解的待體素化區(qū)域，p是在S區(qū)域中的點，A、B代表兩個模型的包圍盒，Ux為A、B的包圍盒在X軸上投影的交集，Uy為A、B的包圍盒在Y軸上投影的交集，Uz為A，B的包圍盒在Z軸上投影的交集。

接著，篩除不與體素空間相交的三角形。將兩個模型中與體素空間發(fā)生相交的三角形序號分別保存進兩個新的數(shù)組中。這里以兩個三角網(wǎng)格模型為例，一個是兔子模型，一個是四面體桁架模型。如圖1所示，是兩個模型讀取完成時，對其AABB包圍盒的構(gòu)建。如圖2所示，是兩個模型求交后的體素空間以及保留的兩個模型的三角網(wǎng)格信息。

2.2 體素化和體素模型求交階段

在體素化階段，首先要以區(qū)域S為體素空間進行網(wǎng)格劃分建立第一級體素模型。由于體素空間是長方體，如果以正方體為體素，那么邊界情況就需要特殊處理，所以為了能夠統(tǒng)一化處理，將每一個體素劃分為近似正方體的長方體。比較區(qū)域S在各個軸上的投影，找到投影距離最小的軸，劃分等分區(qū)間，以這個區(qū)間長度為基準(zhǔn)，對其他兩個軸進行劃分。下面以X軸投影最小為例，將X軸劃分為dimx個等分區(qū)間，通過式（3）可以求解出其他軸上的劃分：

建立起一級體素空間后，則將在其中的三角面進行體素化。體素化的過程就是在與當(dāng)前三角形發(fā)生相交的每一個體素中記錄下三角形的ID號。模型的體素化方法有許多種，如截平面法，三角面取特征點法，空間距離法和網(wǎng)格線求交法等[8]。根據(jù)場景的不同，算法的適用性也不同。布爾運算中碰撞檢測的目的是快速的地找出相交三角面對，并且精確地計算與三角形發(fā)生相交的體素會占用不必要的時間，所以這里采用一種精細體素化延遲的方法。這種方法將體素化的步驟拆分為兩步：粗體素化和細體素化。在粗體素化中以三角形的包圍盒代替三角形去體素化。完成粗體素化后，對兩個體素模型進行求交運算，對發(fā)生碰撞的體素與其記錄的三角形精確運算，即細體素化，將沒有發(fā)生相交的三角形篩除。

首先是粗體素化的過程，在這一步驟中，遍歷模型與體素空間發(fā)生相交的三角形數(shù)組中的每一個三角形。對每一個三角形的包圍盒的兩個頂點（xmin，ymin，zmin）、（xmax，ymax，zmax），如果兩點都在體素空間中，則將其映射到體素空間的坐標(biāo)（Xmin，Ymin，Zmin）、（Xmax，Ymax，Zmax）。對每一個在其范圍內(nèi)的體素遍歷，將當(dāng)前三角形的ID號插入進體素的表中。同樣的，如果三角形的包圍盒只有一個點在體素空間內(nèi)，則先用三角形的包圍盒與體素空間求交，將求交后的包圍盒放入體素空間中進行體素化。

接著，遍歷體素空間中每一個體素，如果體素中同時存放有兩個模型的三角形序號，則為碰撞體素。

然后是細體素化的過程，目的是篩除碰撞體素中沒有與體素相交的三角形，這里采用歐式距離法判斷三角形是否與體素相交[9]。遍歷碰撞體素中的三角形，求解碰撞體素中心點C（x0，y0，z0）到三角形平面的距離D，判斷其是否大于體素包絡(luò)球的半徑R，如果大于，則從碰撞體素中刪除這個三角形的序號。

至此，完成了第一級的體素模型的建立。

大尺度的三角網(wǎng)格模型會出現(xiàn)某個局部的三角面數(shù)量密集的情況，所以當(dāng)一個碰撞體素中兩個模型的三角形數(shù)量過多時，會導(dǎo)致算法效率的降低。這里通過建立第二級體素模型來解決這個問題。

第二級體素模型是對第一級體素模型中的碰撞的體素更加精細的劃分。當(dāng)在第一級體素模型的體素中兩個模型的三角形數(shù)量均超過某一數(shù)量N時，以當(dāng)前體素作為新的體素空間，以它的表中存放的兩個模型的三角形序號作為輸入的三角形，建立新的體素模型。由于更進一步的劃分會導(dǎo)致更多的內(nèi)存占用，而且因為三角網(wǎng)格模型在局部上往往三角形的大小相近，所以通過對當(dāng)前第一體素內(nèi)的三角形進行采樣作為劃分依據(jù)。采樣依據(jù)是提取每個模型的前N個三角形的包圍盒，取其最短軸的平均值作為新的體素空間的劃分依據(jù)，從而完成對新體素空間的劃分。之后通過與第一級體素構(gòu)建相同的方法對其進行體素化，將三角形分配進各個體素中，再對體素模型進行求交得到相交的體素。

如圖3所示是在上文例子中的兩個模型，在完成體素化求解碰撞體素后的結(jié)果。

2.3 三角形的精確求交

在以上文的檢測步驟中，主要目的是快速地篩除不可能發(fā)生碰撞的三角形對，從而縮小兩個模型之間的三角形求交運算規(guī)模，提升時間效率。而在這一步驟中，逐個遍歷兩層體素模型中的碰撞體素，通過三角形與三角形求交算法直接獲取交線的線段。