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

陳騫

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

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

中圖分類號：TP391 ? ? ? ? 文獻標識碼：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 引言

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

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

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

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

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

2 算法實現

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

2.1 預檢測階段

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 三角形的精確求交

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