基于層次包圍盒與平均單元格的三角網(wǎng)格求交

,

(浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023)

在計(jì)算機(jī)圖形學(xué)、CAD/CAM中,對(duì)于任何的實(shí)體表面，都可以通過(guò)不規(guī)則三角網(wǎng)(TIN)[1]去逼近它,逼近的程度則取決于原始數(shù)據(jù)的分布、密度和三角形的形狀等.而對(duì)于三角網(wǎng)格模型的處理，在虛擬現(xiàn)實(shí)、虛擬設(shè)計(jì)等領(lǐng)域,提出各式各樣的問(wèn)題與方法，如曲面重構(gòu)、模型特征提取[2]和模型編輯造型[3]技術(shù).而如今，隨著對(duì)建模[4-7]要求的不斷提高,模型中三角面片的數(shù)量也是跟著指數(shù)增長(zhǎng).于是三角網(wǎng)格求交速度問(wèn)題便成了最急迫的問(wèn)題，也是最基本的問(wèn)題.Suri等[8]通過(guò)對(duì)層次包圍盒法的分析研究,證明了較于一般的求交算法,此算法可以有效降低空間復(fù)雜度.根據(jù)劃分包圍盒的不同，常見(jiàn)的包圍盒包括:AABB(Axis align bounding box)、方向包圍盒OBB(Oriented bounding box)、包圍球(Sphere)、固定方向凸包包圍盒FDH(Fixed directions hulls)等. Gvan[9]基于AABB結(jié)構(gòu)構(gòu)建層次結(jié)構(gòu)的二叉樹(shù)，有效地剔除了不相交的三角面片.Gottschalk等[10-11]基于OBB結(jié)構(gòu)構(gòu)建層次結(jié)構(gòu)的二叉樹(shù)，有效地剔除了不相交的三角面片.魏迎梅等[12]對(duì)虛擬環(huán)境碰撞檢測(cè)的研究，提出基于FDH的層次包圍盒樹(shù)算法.亦有其他方法，如Lo等[13]使用背景網(wǎng)格篩選出潛在的相交三角面片，然后求交點(diǎn)時(shí)，通過(guò)追蹤相鄰三角面片來(lái)求得相交鏈或者環(huán).或者如蔣錢(qián)平等[14]提出了平均單元格法，采用劃分和索引思想，將空間分割成一個(gè)個(gè)固定的小立方體進(jìn)行處理.Tomas等[15]提出了快速的，內(nèi)存消耗最小的射線與三角形求交算法，具體表現(xiàn)為:將一個(gè)三角形的3條邊看作3條射線分別與另一個(gè)三角形求交計(jì)算.Tomas[16]先將兩個(gè)三角形近似看成兩個(gè)平面，從而簡(jiǎn)化判斷兩者是否相交以及求出相交線，進(jìn)而再判斷該相交線是否為兩個(gè)三角形的公共線.徐智淵等[17]通過(guò)一條射線構(gòu)造一對(duì)相互垂直的平面，然后通過(guò)任意三角形的三個(gè)點(diǎn)與射線所在的平面作距離運(yùn)算，只需定性的判斷正負(fù),便能排除空間中不相交三角形.

上述方法要么算法實(shí)現(xiàn)思路較為簡(jiǎn)單，但是計(jì)算速度并不讓人滿意；要么實(shí)現(xiàn)過(guò)程較為復(fù)雜，提高了速度卻浪費(fèi)了大量?jī)?nèi)存，甚至在某些特殊情況下反而下降.為了高效快速解決求交運(yùn)算，對(duì)于未經(jīng)處理的模型,先構(gòu)造AABB層次包圍盒，粗略地篩選出可能相交的三角形；其次，使用平均單元格法，采用索引的思想，精確地將相交的三角形確定在一部分小單元格內(nèi)；最后，逐次迭代剩余三角形，進(jìn)行求交計(jì)算.

1 碰撞檢測(cè)及求交點(diǎn)計(jì)算

對(duì)于已有的AABB層次包圍盒法，不足在于：1) 隨著層次的增加，空間復(fù)雜度也相應(yīng)增加，當(dāng)達(dá)到一個(gè)臨界值時(shí)，碰撞檢測(cè)的速度非但不會(huì)提高，反而會(huì)降低；2) 對(duì)于樹(shù)的葉節(jié)點(diǎn)來(lái)說(shuō)，在簡(jiǎn)單判斷是否相交之后,只能對(duì)其中含有所有的三角面片進(jìn)行笨拙地兩兩求交.同樣，對(duì)于已有的平均單元格法，其不足在于：1) 單元格的邊長(zhǎng)size設(shè)定隨著模型的不同而不同，且邊長(zhǎng)size的變化，對(duì)模型求交速度影響很大；2) 對(duì)于大模型來(lái)說(shuō)，該算法的內(nèi)存消耗巨大，不適用于大場(chǎng)景.

1.1 改進(jìn)算法

針對(duì)以上提出的不足，此處給出混合算法的示意圖，如圖1所示。

圖1 混合算法Fig.1 Hybrid algorithm

混合算法主要步驟:

1) 對(duì)于未經(jīng)處理的模型,先構(gòu)造AABB層次包圍盒，分層的次數(shù)主要由模型的大小決定，并排除不相交的葉節(jié)點(diǎn)(其中含有大量的三角面片).對(duì)于AABB層次包圍盒，它的優(yōu)勢(shì)在于分別對(duì)兩個(gè)模型建立各自包圍盒，然后使用二叉樹(shù)或者八叉樹(shù)，對(duì)大量的三角面片進(jìn)行粗略的碰撞檢測(cè)，排除絕大部分的顯而易見(jiàn)的無(wú)關(guān)三角面片.

2) 經(jīng)過(guò)AABB層次包圍盒篩選，候選的相交三角面片將被限定在一個(gè)較小的范圍內(nèi),此時(shí)再使用平均單元格法，選取適當(dāng)?shù)倪呴L(zhǎng)size，將必定相交的三角面片限定在部分小立方體內(nèi).對(duì)于平均單元格法，它的優(yōu)勢(shì)是可以快速地將任意一個(gè)三角面片定位在某一個(gè)預(yù)先設(shè)定的小正方體內(nèi)，由于size大小接近三角面片邊長(zhǎng),只需要處理含有來(lái)自兩個(gè)模型三角面片的正方體，即可避免95%以上的不必要三角面片求交.

3) 對(duì)于同一個(gè)小立方體內(nèi)的三角形，使用Ray triangle intersection算法進(jìn)行兩兩求交.即將一個(gè)三角形的三條邊看作三條射線，分別與另一個(gè)三角形求交.

基于此，算法流程圖如圖2所示.

圖2 算法流程圖Fig.2 Algorithm flow chart

1.2 連接相鄰交點(diǎn)得到直線段

對(duì)于任意相交的三角形ABC和EFD，用之前提到的方法，即將1個(gè)三角形的3條邊看作3條射線，分別與另1個(gè)三角形求交，那么相交的情況可以分為2大類(lèi)7種情況，如圖3所示.

圖3 三角形相交的種類(lèi)Fig.3 The kind of intersection of triangles

第1類(lèi)共面

1) 交線為一個(gè)封閉的三角形，如圖3(a)所示.

2) 交線為一個(gè)封閉的四邊形，如圖3(b)所示.

3) 交線為一個(gè)封閉的五邊形，如圖3(c)所示.

4) 交線為一個(gè)封閉的六邊形，如圖3(d)所示.

第2類(lèi)不共面

1) 2個(gè)交點(diǎn).圖3(e)有2個(gè)交點(diǎn)都來(lái)自于一個(gè)三角形的邊；圖3(f)有2個(gè)交點(diǎn)分別來(lái)自兩個(gè)三角形的邊.

2) 3個(gè)交點(diǎn).圖3(g)有2個(gè)交點(diǎn)剛好落在一個(gè)頂點(diǎn)上.

3) 4個(gè)交點(diǎn)，圖3(h)有2對(duì)交點(diǎn)剛好分別落在2個(gè)頂點(diǎn)上;圖3(i)有4個(gè)交點(diǎn)都落在一個(gè)頂點(diǎn)上.

注意兩點(diǎn)：1) 正確性.由于兩個(gè)三角形相交要么產(chǎn)生一個(gè)封閉三角形，要么產(chǎn)生一條線段，因此，求得一組交點(diǎn)便要進(jìn)行標(biāo)記，防止此交點(diǎn)組與另外其他交點(diǎn)作連線；2) 連通性.因?yàn)椴捎玫臄?shù)據(jù)結(jié)構(gòu)為半邊結(jié)構(gòu)，相應(yīng)的交點(diǎn)會(huì)被求解兩次，所以交線段便會(huì)被很好的連接在一起，圖3(j)中POQ按順序連接.

2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在酷睿CPU頻率2.2 GHz，內(nèi)存4 GB的筆記本上進(jìn)行，算法在VS2010環(huán)境下實(shí)現(xiàn).對(duì)以下3個(gè)例子分別運(yùn)用AABB包圍盒、平均單元格和改進(jìn)算法，并且進(jìn)行了反復(fù)實(shí)驗(yàn)統(tǒng)計(jì)與分析，實(shí)驗(yàn)數(shù)據(jù)有3種情況.

1) 給定的模型由2 956個(gè)和8 874個(gè)三角形組成，一幅為模型，一幅為模型的相交線，如圖4所示.

圖4 狗模型與魚(yú)模型相交Fig.4 Intersection of dog model and fish model

2) 給定的模型分別由30 326個(gè)和29 014個(gè)三角形組成，一幅為模型，一幅為模型的相交線，如圖5所示.

圖5 熊模型和桶模型相交Fig.5 Intersection of bear model and bucket model

3) 給定的模型分別由15 142個(gè)和27 100個(gè)三角形組成，一幅為模型，一幅為模型的相交線，如圖6所示.

圖 6 杯子模型和軸承模型相交Fig.6 Intersection of cup model and bearing model

實(shí)驗(yàn)結(jié)果如表1，2所示.

表1 比較算法運(yùn)算速度Table 1 Operation speed of comparison algorithm

表2比較算法對(duì)模型構(gòu)建單元格的個(gè)數(shù)

Table2Comparealgorithmstothenumberofcellsthatthemodelbuilds

求交算法單元格的數(shù)量/個(gè)圖4圖5圖6平均單元格36 480119 991179 400改進(jìn)算法(5層)13 07298 393142 945改進(jìn)算法(10層)8 39878 66477 385

表1為改進(jìn)的混合算法，速度普遍快于AABB層次包圍盒法，實(shí)驗(yàn)結(jié)果令人滿意.而且它的速度相較于平均單元格法也是有優(yōu)勢(shì)的，特別是在兩個(gè)模型相交的部分少，如圖5所示，相交部分只有四只腳部分，當(dāng)分層的次數(shù)不太多，且能大量排除無(wú)關(guān)的三角形時(shí)，省下的時(shí)間可以彌補(bǔ)分層所用的時(shí)間，與此同時(shí)，由于平均單元格法空間復(fù)雜度較大，對(duì)于大型的模型，使用該方法會(huì)消耗大量?jī)?nèi)存，以至于普遍都不采用.

表2為平均單元格法可以看作是混合算法的一種特殊情況，即不進(jìn)行分層.平均單元格空間復(fù)雜度為O(lmn)，混合算法空間復(fù)雜度為O(lmn/2k).其中k為算法層次劃分的層次數(shù)，顯而易見(jiàn)，次數(shù)越大，則復(fù)雜度越低，在大部分情況下，改進(jìn)算法能夠節(jié)省較多的空間.圖5分割5層后，需要構(gòu)建的小正方體單元格數(shù)量減少了10%；例子1，3分割10層后，則減少了60%以上.隨著分割層次增加，算法的內(nèi)存消耗下降，速度也有所放緩，但速度仍然快于AABB層次包圍盒法，與平均單元格相差無(wú)幾，很好地做到了平衡.

3 結(jié) 論

對(duì)已有的層次包圍盒法和平均單元格法算法進(jìn)行了分析與實(shí)現(xiàn)，并比較了各自的優(yōu)缺點(diǎn)，進(jìn)行了相應(yīng)的改進(jìn)，主要表現(xiàn)為在粗略檢測(cè)的時(shí)候使用層次包圍盒法，排除了大量的無(wú)關(guān)的三角面的求交計(jì)算.此步驟只需分層，并比較葉節(jié)點(diǎn)包圍盒之間是否相交，而并不需要對(duì)每個(gè)包圍中的每個(gè)三角形進(jìn)行求交運(yùn)算.在精確檢測(cè)時(shí)使用的是平均單元格法，因?yàn)槭Ｓ嗟娜切我呀?jīng)大大減少，再用包圍盒的意義已經(jīng)不大，并且隨著分層次數(shù)的增加速度反而會(huì)下降，因此用單元格反而大大提高了求交效率，減少了運(yùn)算時(shí)間,較大地減少了內(nèi)存的消耗，然后使用Ray triangle intersection將三角形的3條邊分別看成3條射線與另一個(gè)三角形求交計(jì)算.因此，改進(jìn)算法在一定程度上，要優(yōu)于前2種，而且較好的平衡了計(jì)算的速度和內(nèi)存的消耗，更加適合巨大模型場(chǎng)景的計(jì)算，實(shí)驗(yàn)數(shù)據(jù)也表明了在提高了速度的同時(shí)，避免了內(nèi)存的大量消耗.在后續(xù)的工作中，將進(jìn)一步研究一對(duì)三角形之間的求交計(jì)算方法，從而可以從質(zhì)上提高計(jì)算速度而不是篩選數(shù)量上.