陳騫

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

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

中圖分類號(hào)：TP391 ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

2 算法實(shí)現(xiàn)

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

2.1 預(yù)檢測(cè)階段

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

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

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

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

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

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

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

接著，遍歷體素空間中每一個(gè)體素，如果體素中同時(shí)存放有兩個(gè)模型的三角形序號(hào)，則為碰撞體素。

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

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

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

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

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

2.3 三角形的精確求交

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