楊張龍，陳 明

(廣西師范大學(xué) 計算機(jī)科學(xué)與信息工程學(xué)院，廣西 桂林 541004) (*通信作者電子郵箱hustcm@hotmail.com)

大規(guī)模網(wǎng)格模型間的快速視覺布爾運算

楊張龍，陳 明*

(廣西師范大學(xué) 計算機(jī)科學(xué)與信息工程學(xué)院，廣西 桂林 541004) (*通信作者電子郵箱hustcm@hotmail.com)

為了解決產(chǎn)品設(shè)計階段中大規(guī)模網(wǎng)格模型間的布爾運算無法實現(xiàn)立等可得的速度瓶頸，提出了一種新算法。該算法利用離散化采樣獲得射線段點云模型，將三角面片間的3D布爾運算轉(zhuǎn)換為射線段間的1D布爾運算，對相交處的交點進(jìn)行高精度的求解和插值處理，使得布爾運算速度大為提高，從而大大提升復(fù)雜拓?fù)浣Y(jié)構(gòu)的產(chǎn)品設(shè)計效率。通過該算法所獲得射線段點云模型可獲得等同于基于三角網(wǎng)格的渲染效果，該方法可進(jìn)行工程應(yīng)用。

布爾運算；離散化采樣；點云模型；點云渲染; 組合實體造型

0 引言

組合實體造型(Constructive Solid Geometry, CSG)技術(shù)對多個簡單幾何實體通過交、并、差三種布爾運算組合可構(gòu)建復(fù)雜幾何形態(tài)(如圖1)，所以廣泛應(yīng)用于某些拓?fù)浣Y(jié)構(gòu)復(fù)雜的產(chǎn)品外形設(shè)計中[1-3]。隨著3D打印的興起以及制造工藝的提高，使復(fù)雜拓?fù)浣Y(jié)構(gòu)的產(chǎn)品擺脫傳統(tǒng)的手工雕刻加工轉(zhuǎn)化為自動化加工成為可能，進(jìn)而利用布爾運算設(shè)計復(fù)雜產(chǎn)品外形成為不可缺少的步驟。設(shè)計過程中需不斷編輯單個圖元然后反復(fù)進(jìn)行布爾運算查看整體效果，對于復(fù)雜的網(wǎng)格模型編輯來說，布爾運算的穩(wěn)定性以及效率成了設(shè)計瓶頸。以圖1(c)為例，涉及到的布爾運算總次數(shù)超過100次，而戒指外圈的每次修改將會導(dǎo)致這100次布爾運算的執(zhí)行，而每個戒指的最終產(chǎn)品設(shè)計統(tǒng)計數(shù)據(jù)表明外圈的修改次數(shù)20次以上，從而會產(chǎn)生2 000次布爾運算。在主流計算機(jī)輔助設(shè)計(Computer Aided Design, CAD)軟件的測試結(jié)果(CATIA，Rhino，Solidworks)則通常需等候120 h以上(每次修改等待6 h)，有些甚至直接告知無法進(jìn)行運算，這對于設(shè)計所需立等可得的運算效率來說是難以接受的，極大限制了此類產(chǎn)品的設(shè)計效率，業(yè)界迫切需要對這一速度瓶頸進(jìn)行突破。

迄今為止，大部分研究[4-8]均是圍繞如何構(gòu)建有效包絡(luò)盒(bounding box)來有效減小參與求交測試的三角面規(guī)模的思路進(jìn)行：分別構(gòu)建軸向包絡(luò)盒(Axis Aligned Bounding Box， AABB)[4]、方向包絡(luò)盒(Oriented Bounding Box, OBB)[5]、包圍球[6]、K-Dop[7]、Hybrid[8]等,此類方法對于超大規(guī)模的布爾運算來說仍然繞不開網(wǎng)格面片求交運算以及后期的碎片網(wǎng)格化的復(fù)雜運算，從而無法實現(xiàn)最終的快速布爾運算效果；還有學(xué)者基于重建的近似方法[9-10]來解決布爾運算存在的不穩(wěn)定性問題,主要包括體素法[11]、距離場(distance field)[12],level-set[13]、面元法(surfel)[14]、射線表示法[15-17]和八叉樹[18]。

近期Wang等[19]利用網(wǎng)格離散化采樣為點云，再利用點云通過內(nèi)外判定獲得最終布爾運算的結(jié)果點集；Adams等[20]利用八叉樹分割點云和合理的邊界單元分割方法實現(xiàn)了基于離散面片顯示的布爾操作；Wang等[21]提出了基于點云的近似布爾運算與重構(gòu)的方法，但未處理基于點云的布爾運算的相交線。除以上傳統(tǒng)網(wǎng)格模型間的布爾運算研究外，最近有工作針對某些特殊網(wǎng)格模型的布爾運算進(jìn)行了研究，包括：存在圓錐曲線或二次曲線邊界的網(wǎng)格模型間的布爾運算[22]、多面體的網(wǎng)格模型間的布爾運算[23]以及B-rep表示網(wǎng)格模型間的布爾運算[24]。綜上所述，現(xiàn)有工作均未涉及大規(guī)模網(wǎng)格模型間的布爾運算，在設(shè)計階段如何瞬間響應(yīng)獲取設(shè)計結(jié)果的問題仍然沒有解決，而本文著重解決此問題。

本文將三維網(wǎng)格模型間的布爾運算轉(zhuǎn)化為一維射線段布爾運算，從而大大降低布爾運算的復(fù)雜度，規(guī)避了面面求交所導(dǎo)致的復(fù)雜計算和不穩(wěn)定性，基于所獲得的一維射線段模型布爾運算結(jié)果直接進(jìn)行基于點云的渲染，較好地處理了相交邊界，以及放大和縮小視圖所導(dǎo)致的空洞缺陷，讓最終結(jié)果在視覺上達(dá)到基于面片渲染的效果，從而滿足設(shè)計過程中對于復(fù)雜拓?fù)浣Y(jié)構(gòu)產(chǎn)品設(shè)計中瞬間響應(yīng)的實際工程要求。本文稱這種一維布爾運算為視覺布爾運算，主要應(yīng)用在產(chǎn)品的設(shè)計階段，設(shè)計定型以后再通過之前的工作[25]進(jìn)行快速的3D布爾運算(此時用戶可以容忍等待較長時間)，從而得到最終結(jié)果后進(jìn)行后續(xù)的加工處理。

1 算法概述

整個算法流程如圖2所示：首先輸入?yún)⑴c布爾運算的各個幾何基本體以及定義它們之間的布爾運算類型，形成CSG樹形結(jié)構(gòu)；步驟②根據(jù)當(dāng)前視窗的大小尺寸，利用顯卡的GPU進(jìn)行射線段的自適應(yīng)射線段的采樣(具有法線信息的3D像素模型)，然后通過快速獲取顯存像素點的深度信息，進(jìn)而獲取每個像素的三維點位信息、貼圖以及法線等關(guān)鍵信息；步驟③針對每條射線段進(jìn)行一維的快速布爾運算；步驟④則判定出交點信息，并且插值計算出準(zhǔn)確的交點的點位坐標(biāo)以及相應(yīng)的法線；步驟⑤則將所有的交點進(jìn)行構(gòu)環(huán)，從而填補(bǔ)由于采樣精度誤差所導(dǎo)致的直接渲染的孔洞暗點，獲取較好視覺效果；步驟⑥直接對點云模型進(jìn)行自適應(yīng)的點渲染，獲得比擬基于面片的渲染效果；如果在步驟⑦中，參與布爾運算的基本圖形進(jìn)行了修改或局部放大，則需局部位置進(jìn)行再次自適應(yīng)采樣，從而在所發(fā)生變更的部位進(jìn)行步驟②至步驟⑥的流程。

自適應(yīng)射線段模型采樣利用文獻(xiàn)[25]的方法通過并行計算進(jìn)行基于八叉樹結(jié)構(gòu)采樣，快速實現(xiàn)網(wǎng)格模型到射線段模型的采樣。該方法是假想沿著屏幕射出一系列射線束(如圖3(a))，射線束將會撞擊到參與布爾運算的所有基本模型體上獲得一系列的交點；而這些交點不是通過幾何求交運算而是通過GPU從深度緩沖器和模板緩沖器快速獲取。自適應(yīng)采樣則是采用八叉樹的結(jié)構(gòu)如圖3(b)示意，采樣后的所有具有深度信息的像素點則在XYZ三個方向按坐標(biāo)大小進(jìn)行有序排列，交點XYZ方向的索引號記為(i,j,k)。

圖2 3D布爾運算轉(zhuǎn)化為1D視覺布爾運算的算法流程

圖3 基于八叉樹的射線段取樣

1.1 空間坐標(biāo)獲取

根據(jù)像素在視窗中的XY方向的像素點坐標(biāo)可利用轉(zhuǎn)換矩陣調(diào)用gluUnProject函數(shù)直接獲取三維點坐標(biāo)，實際測試中發(fā)現(xiàn)該函數(shù)需要耗費大量計算資源，所以本文結(jié)合采樣點在視窗中XY方向的像素視窗坐標(biāo)，快速計算所有采樣點的XYZ空間坐標(biāo)：設(shè)想所有基本模型的整體包絡(luò)盒記為BB,該包絡(luò)盒的左下頂點的空間坐標(biāo)為(Xmin,Ymin,Zmin)右上頂點坐標(biāo)為(Xmax,Ymax,Zmax)；視窗的XY方向的物理分辨率分別為RX和RY，代表每兩個像素間的實際物理距離，該值在模型繪制完成后可直接獲知;每個像素點的XY方向在視窗的像素坐標(biāo)已知為X·i和Y·i，其深度坐標(biāo)(Z方向)可以從深度緩沖器中獲取為Di。每個射線上所有交點的空間坐標(biāo)(Xi,Yi,Zi)則可以分別計算為：

由于采樣點三維坐標(biāo)的獲取是通過在渲染管線渲染后取樣，故存在一定的精度誤差。為防止產(chǎn)生噪聲點，獲得模板緩沖值和深度緩沖值之前需設(shè)置好渲染環(huán)境，關(guān)掉抗鋸齒功能、三角面片的偏置、燈光和抖動的功能。

1.2 法線方向獲取

針對點云模型進(jìn)行渲染前，獲取每個像素的法線值對于渲染的光順性非常重要。若該網(wǎng)格模型來自參數(shù)模型，則可直接計算該取樣點的法線值；如果該模型是通過點云重建或者頂點法線信息缺失，則需擬合每個取樣點的法線信息。文獻(xiàn)[19]采用顏色索引值的方法獲取每個采樣點所屬哪一個三角片，然后將三角片的面法線作為每個采樣點的點法線；對該方法渲染時會出現(xiàn)面片棱角，仍需進(jìn)行光順處理?？紤]到所有交點皆為有序排放，周圍鄰域點很容易獲取，從而采用一種更為精確的近似方法進(jìn)行取樣點的法線賦值。如圖4所示，Pi點為待求法線的取樣點。可以在XYZ方向，按照索引號i,j,k逐漸遞增搜索的方法快速獲取1-ring鄰域的所有鄰域點Qj，按照正投影進(jìn)行快速排序構(gòu)環(huán)三角化(參考本文構(gòu)環(huán)算法)，形成如圖4以Pi為中心的傘形結(jié)構(gòu)，將構(gòu)成扇形的所有三角片的單位面法線進(jìn)行面積加權(quán)后的和作為最終Pi的法向量Ni。

圖4 點Pi法線的構(gòu)建

2 基于點云模型的一維布爾運算

取樣建立射線段模型后，根據(jù)布爾運算的類型快速進(jìn)行射線段間的布爾運算。本文解決的是大規(guī)模網(wǎng)格模型間布爾運算(單個模型三角片的數(shù)目超過50萬)不能滿足設(shè)計階段所需的瞬間響應(yīng)問題；在實際應(yīng)用中參與運算的模型有可能需同時進(jìn)行多次布爾運算，對于此種情況為提升速度，本文采用一次性采樣，合并多次布爾運算為單次性布爾運算，從而可大大節(jié)省運算時間，滿足設(shè)計所需的速度要求。布爾運算的實質(zhì)是判定出哪些圖元需要保留、哪些圖元需要去掉，然后將保留下來的圖元進(jìn)行顯示。對于本文特定應(yīng)用，所有取樣的射線段有序點保留/去除的規(guī)則遵循2.1節(jié)所描述的判定規(guī)則。

布爾運算的保留/去除判定如下所示。

所有射線段上的點的個數(shù)均應(yīng)是偶數(shù)，奇數(shù)點的個數(shù)則對應(yīng)為退化情況(射線段經(jīng)過端點或者與面相切)。每個射線段上的取樣點屬于哪個基本體，則可以通過顏色映射快速獲?。簩⑺袇⑴c布爾運算的基本體在顯存中用不同顏色繪制，通過判斷取樣點所對應(yīng)像素的顏色值確定該取樣點屬于哪個基本體。假設(shè)參與布爾運算的兩個基本體分別為A和B(多個基本題的情況類似)，針對差集A-B與B-A，并集A∪B以及交集A∩B確定射線段點的保留/去除原則。布爾運算則需指定射線段Lk的交點集合{Ps}保留/去除取樣點的判定規(guī)則，從而獲取需要保留的取樣點。

由于實體模型的封閉特性，每條射線段Lk屬于同一基本體的交點個數(shù)應(yīng)為偶數(shù)：射入點與射出點成對并交替出現(xiàn)。對于奇數(shù)點數(shù)目的情況，則存在退化點，退化點通過鄰域關(guān)系判可快速判斷，并將該點處理成重合的兩個點。在進(jìn)行保留/去除判定之前需要完成內(nèi)外判定，從而再根據(jù)布爾運算類型完成保留/去除判定規(guī)則。

內(nèi)外判定如下所示。

對于歸屬于同一基本體不失一般性記為A的一對射入點與射出點，如圖5繪制成空心圓圈；而屬于物體B的所有取樣點則是需要進(jìn)行判斷在物體A內(nèi)或者外的點則標(biāo)記為實心圓圈。對于同一條射線段，所有取樣點按照深度信息的前后進(jìn)行有序排列。如圖5，待判定的取樣點(實心圓圈)如果位于基本體A中的射入點和射出點之間(如圖5(a))，則該點處于A的內(nèi)部；否則是位于A的外部，即圖5(b)和5(c)兩種情況。

圖5 射線段的內(nèi)外判定

保留/去除判定如下所示。

確定內(nèi)/外判定法則以后則可以針對布爾運算類型從而快速確定取樣點的保留/去除判定規(guī)則，該規(guī)則如下：

1)(A-B)差集保留/去除判定規(guī)則。

需要保留的點包括兩種類型：①所有位于B外部卻屬于A的點；②所有位于A內(nèi)部卻屬于B的點；其他的點則直接去除。

2)(B-A)差集保留/去除判定規(guī)則。

需要保留的點包括兩種類型：①所有位于A外部卻屬于B的點；②所有位于B內(nèi)部卻屬于A的點；其他的點則直接去除。

3)A∩B交集保留/去除判定規(guī)則。

需要保留的點包括兩種類型：①所有位于B內(nèi)部卻屬于A的點；②所有位于A內(nèi)部卻屬于B的點；其他的點則直接去除。

4)A∪B并集保留/去除判定規(guī)則。

需要保留的點包括兩種類型：①所有位于B外部卻屬于A的點；②所有位于A外部卻屬于B的點；其他的點則直接去除。

通過以上判定后，所有保留的取樣點則構(gòu)成最終布爾運算后的結(jié)果模型，該模型則由一系列的點構(gòu)成，若這些點直接進(jìn)行基于點(point disk)的渲染則會在交線處出現(xiàn)大量暗斑(如圖6)，從而本文后續(xù)對交線處進(jìn)行交點的插值后置處理。

圖6 交線區(qū)域產(chǎn)生的大量暗黑缺陷

3 插值交線

經(jīng)過布爾運算后的實體在兩實體相交部分會產(chǎn)生較粗糙的邊緣，在邊緣處由于采樣誤差和相交點遮蓋導(dǎo)致某些點的背面繪制出來形成暗點。該暗點可通過加大取樣密度減小，但該方法存在兩個問題：1)取樣密度的增加會顯著增加運算量；2)即便增加取樣密度，仍無法消除暗點的產(chǎn)生，只是暗點區(qū)域變小，放大后該暗點仍然影響實際視覺效果。由于暗點的產(chǎn)生是取樣精度所致，故本文在現(xiàn)有采樣精度情況下插值交點，從而填補(bǔ)空缺，并構(gòu)建交線環(huán)的方法來遮蓋這些陰暗部位。

3.1 交點定位

求解交點時需先知射線采樣點的位置，通過前后兩束射線采樣點位置對比，判斷相交點可能的位置，然后通過插值求取。設(shè)想射線沿著與坐標(biāo)軸平行的方向逐層對所有基本體進(jìn)行掃描，將會在過射線且與坐標(biāo)平面平行的平面內(nèi)得到一系列輪廓點，所有交點情況均可劃分為以下3種情況之一或者組合：如圖7,Pi屬于基本體A上的取樣點，Qi則屬于基本體B上的取樣點。

相交情形1 如圖7(a),緊鄰的兩條射線i與射線i+1上局部相鄰位置分別存在P1，Q1和Q2和P2兩個取樣點。其中P1和P2屬于基本體記為A，而Q1和Q2屬于參與布爾運算的另一基本體。這種情形則是，基本體A在P1處的區(qū)域位于基本體B的內(nèi)部(外部)而在P2處則變更為基本體B的外部(內(nèi)部)，所以在射線i與射線i+1之間存在交點。對于布爾運算的絕大部分相交情況屬于此類。

相交情形2 如圖7(b),此種情況是一種特殊相交情況，在射線i與射線i+1上局部區(qū)域內(nèi)點的取樣數(shù)目是不一樣的，在此類情況中，取樣基本體在取樣區(qū)域從取樣方向上看相對較為平緩，從而導(dǎo)致射線i+1上P1、P2兩個交點跨度較大，無法構(gòu)成情形1的交點相對位置關(guān)系，但此類情形亦容易判斷：基本體A在Q1位置處于基本體B的外部(內(nèi)部)，而在Q2處則處于基本體B的內(nèi)部，故基本體A與基本體B在射線i與i+1處存在交點。

相交情形3 如圖7(c)，類似情形2，射線i與i+1上的取樣點數(shù)目差別較大，通常表現(xiàn)為基本體A在射線i與i+1之間相對平緩，而基本體B則在此附近成多個波浪形，此時射線i只存在B的采樣點，而射線i+1上存在基本體A上的一對射入點和射出點。

圖7 相鄰兩射線段交點之間三種相對位置關(guān)系

3.2 特殊情景處理

確定三種相交情形后，針對相鄰射線i與射線i+1，讀取它們上的所有取樣點，根據(jù)它們之間的相對位置關(guān)系很容易判斷相交屬于何種情況。本文所采取的存在交點的判斷策略是：當(dāng)基本體B在射線i上的取樣點在基本體A的外部，而在射線段i+1時，B的部分或全部取樣點位于基本體A內(nèi)，此時射線i和射線i+1之間存在交點，其相交情景對應(yīng)圖7的三種情況。如果參與運算的基本體輪廓非常復(fù)雜，存在大量的細(xì)小特征時，此原理在應(yīng)用時存在以下例外：如圖8所示由于Q1和Q3均位于基本體A的外部，根據(jù)現(xiàn)有判定策略Q1和Q3之間是不存在交點的，這直接導(dǎo)致交點遺失；這種遺失產(chǎn)生的原因是，物體A在Q1和Q3之間存在尖銳的凸起或凹陷，對于此類情況處理如下：根據(jù)i+1線段一對進(jìn)入進(jìn)出點P5和P6相隔很近判斷此處存在尖銳轉(zhuǎn)折，而Q1位于P2的右端，相鄰的Q3卻位于P5的左端，這表明Q1和Q3間至少存在兩個交點；此時應(yīng)將P2，Q1和Q3和P6等同于情形1;而Q1，Q3和P4和P5等同于情形2。對于因細(xì)小凸起或凹陷均導(dǎo)致相鄰一對射入點和射出點存在多個交點的情況，需首先通過相鄰取樣點距離判定存在細(xì)小凸起或凹陷，再根據(jù)以上方法將此情況分解為情形1和情形2的組合情況。值得一提的是，在很小局部空間內(nèi)由于采樣精度的限制，以上方法仍然可能遺失掉某些小于取樣精度的交點，比如圖8中倘若基本體A在Q1和Q3中存在多個細(xì)小波浪，而根據(jù)現(xiàn)有方法本文只求取2個交點，從而會導(dǎo)致其他交點遺漏，但此種遺漏是可以接受的，因為小于取樣精度的交點與所求取的2個交點位置非常近，對最后的視覺效果無影響。

圖8 尖銳凸起引起的特殊情況

3.3 交點求解

當(dāng)相鄰兩射線段兩采樣點分別屬于不同的物體且出現(xiàn)先后次序的交替時必產(chǎn)生交點。求解時，沿射線方向?qū)⑺腥狱c按深度遞增的次序排序，剔除明顯不會相交的線段和連續(xù)出現(xiàn)的屬于同一物體的多條線段的點。然后按3.1節(jié)和3.2節(jié)確定相交的初步區(qū)域。由于獲得采樣點時的入射射線是離散的，入射射線正好射中相交點的概率極小，因此交點的高精度的近似獲得需要通過相應(yīng)計算。直觀上講，可以根據(jù)鄰接關(guān)系構(gòu)建二次曲線進(jìn)行求交，考慮到通常情況的采樣精度足夠高，并且從效率上考慮本算法采用了線性插值的方法進(jìn)行求解，實驗也表明此種近似方法已經(jīng)足夠滿足視覺精度要求。分別針對3.1節(jié)所描述的三種相交情形，對交點進(jìn)行近似，其中近似交點標(biāo)記為Mi：

對于情景1：線段P1P2和線段Q1Q2的交點作為基本體A和基本體B的交點；

對于情景2：Q1和Q2的中點作為交點；

對于情景3:Qi和Qn+i-1的中點作為系列交點。

通過以上步驟可以提取出相對較為精確的交點，并將交點添加到射線段采樣點云模型中，則可以將陰影區(qū)域較好地遮蓋。

4 交點構(gòu)環(huán)

有時需要將交點構(gòu)成環(huán)路進(jìn)行高亮顯示，從而使得整體輪廓分明，所以針對所獲的無序交點，需進(jìn)行構(gòu)環(huán)操作。現(xiàn)所獲取交點有以下特征：1)沿某個采樣射線上得到的交線環(huán)上的點沿交線環(huán)成單列分布；2)交線上的點是不均勻的，點由沿著采樣射線方向到與采樣射線垂直方向由密變疏。由于采樣發(fā)生在XYZ三個方向，根據(jù)基本體的結(jié)構(gòu)，不同方向的采樣密度存在差異，從而導(dǎo)致三個方向的交線環(huán)上的點相對于其他方向會產(chǎn)生一定程度上的微小偏移，由于微小偏移的存在，點不再沿著交線環(huán)成單列環(huán)狀分布，而是沿著交線環(huán)隨機(jī)分布(如圖9)，所以利用如下方法獲取沿交線環(huán)成單列分布的點集。

圖9 交線段的構(gòu)環(huán)

首先，對各方向上獲得的點集分別進(jìn)行以下操作：

1)將所有交點分別復(fù)制到三個結(jié)構(gòu)體數(shù)組，分別記為xArray、yArray和zArray并進(jìn)行索引編號；

2)對xArray按x坐標(biāo)值升序排序，對yArray按y坐標(biāo)值升序排序，以及對zArray按z坐標(biāo)值升序排序;

3)在xArray中取出第一個值，沿x軸以第一個點為中心往x增大和減小的方向同時搜索一個單位，將搜索得到的最小值作為當(dāng)前與第一個點距離的最小值，接著分別進(jìn)入y、z方向，重復(fù)x方向的動作。

經(jīng)過前面三步可以獲得離任意一點最近的點。接著，以xArray作為交線環(huán)上的原始數(shù)據(jù)點集，通過在稀疏的地方取出yArray或zArray中相應(yīng)點補(bǔ)充進(jìn)來。具體實施方法如下：

1)從xArray中取出一點，檢查該點處的法向量，得到最大法向量所在的方向，進(jìn)入該方向的數(shù)組(yArray或zArray)并找出和該點最近的點，記為P0。

檢查該數(shù)組中P0點并尋找下一點P1，檢查P1的法向量是否為最大，并檢查P0和P1之間的距離是否在給定的誤差限定范圍內(nèi)，若P1滿足條件則將P1取出放入目標(biāo)數(shù)組Array，將P1點沿某一給定的向量移動一個微小位移，該向量的起點為前一次搜索的數(shù)組中的法向量開始小于其他方向的第一點，終點為目標(biāo)數(shù)組中與第一個搜索點最近的點，若P1不滿足條件則進(jìn)入法向量值最大的數(shù)組搜索與該點最近的點P2。

2)重復(fù)執(zhí)行1)直至找到某點與起始點的距離在給定的精度內(nèi)則認(rèn)為一個環(huán)已經(jīng)被找到。

3)回到該環(huán)起始點所在的數(shù)組，找出與該環(huán)起始點最近的點記為Pi，沿該點繼續(xù)往前搜索，得到下一點Pj，若Pi和Pj的距離較大則將Pj作為下一個環(huán)的起始點，重復(fù)執(zhí)行2)和3)，若Pi和Pj的距離在精度誤差范圍內(nèi)則認(rèn)為沒有新的環(huán)了，停止搜索。

為消除因點云模型放大后產(chǎn)生的交線環(huán)上相鄰兩點間的距離過大現(xiàn)象，采取在兩點間動態(tài)插入一定數(shù)目的點，使任意兩點間的距離小于實際分辨率。

5 實現(xiàn)與分析

基于三角面片的模型的布爾運算的時間主要消耗在可能相交的三角面片集的獲取與交線環(huán)的提取上，隨著三角面片數(shù)目的增多消耗的時間增加。本實例將在犀牛軟件作為平臺進(jìn)行基于面片的布爾運算(如圖10～13)，作為對比算法。實驗中硬件開發(fā)環(huán)境CPU為AMD雙核速龍Ⅱ X2,主頻為3.0 GHz，內(nèi)存為3.5 GB，顯卡為ATI radeon HD4250。軟件開發(fā)環(huán)境為Windows 7操作系統(tǒng)，Visual Studio 2012開發(fā)平臺，顯示處理庫為OpenGL。對比的參考量則是運行時間，分別就不同的取樣分辨率進(jìn)行了時間統(tǒng)計。其中實例1～3為兩個幾何體進(jìn)行布爾運算，實例4和實例5則是多個基本體進(jìn)行布爾運算。

圖10 兔子模型與兔子模型間的布爾運算(A-B)

圖11 大衛(wèi)模型與兔子模型的布爾運算(A-B)

圖12 齒輪生成模型(A-B)

參考表1，可明顯發(fā)現(xiàn)所提算法具有明顯速度優(yōu)勢，尤其對于網(wǎng)格密度大且圖形拓?fù)浣Y(jié)構(gòu)相對復(fù)雜的情況(如圖11所示案例)優(yōu)勢更為明顯。由于所提算法采用點云取樣針對點云模型進(jìn)行布爾運算，所以布爾運算的速度只與取樣分辨率相關(guān)而與基本體的網(wǎng)格模型規(guī)模無關(guān)。對于基本體網(wǎng)格模型規(guī)模不大的情況(基本體網(wǎng)格數(shù)目小于104),布爾運算次數(shù)不多時相差不大，但對于簡單模型重復(fù)進(jìn)行布爾運算時，所累積的優(yōu)勢會變得明顯(如圖13)。通過表1，可以看到這個速度完全可以用在產(chǎn)品設(shè)計階段，在設(shè)計過程中用戶可以立等可得布爾運算后的視覺效果，從而支持用戶頻繁修改單個圖元從而進(jìn)行多次查看最終設(shè)計效果。如果采用3D布爾運算則需要等待較長時間，從而大大影響設(shè)計效率。在實際應(yīng)用中，采樣密度通常采用視窗自適應(yīng)的方式進(jìn)行，首先獲取所有圖元的包絡(luò)盒，然后在這個包絡(luò)盒中采取視窗的顯示分辨率(通常取128×128已足夠觀察細(xì)節(jié))；如需要查看更細(xì)節(jié)部位的結(jié)果則可通過視窗放大到需要查看的細(xì)節(jié)部位，讓該部位充滿視窗，然后利用本文方法再進(jìn)行一次視覺布爾運算即可，由于此時查看時涉及到的布爾運算部件通常只有2～3個則此運算可以實時完成。產(chǎn)品設(shè)計階段結(jié)束以后，則只需要進(jìn)行最后一次的3D布爾運算，此時用戶完全容忍等待較長時間，此時再利用之前的工作[25]快速完成3D布爾運算的3D結(jié)果模型的輸出。

圖13 戒指生成模型G-[(B-C)+(A+D)+(F-E)]

表1 犀牛軟件算法與所提算法的耗時對比

6 結(jié)語

本文針對布爾運算在設(shè)計過程中運行時間慢的瓶頸進(jìn)行了突破，能夠支持工業(yè)產(chǎn)品設(shè)計時立等可得的渲染顯示效果，從而使得產(chǎn)品設(shè)計的布爾運算效率極大提高。該算法采用基于GPU自適應(yīng)的取樣方法，將3D網(wǎng)格模型的布爾運算轉(zhuǎn)變?yōu)橐痪S的簡單射線段模型的布爾運算，從而能極大提升算法效率和魯棒性。該算法的運行效率與布爾運算基本體的網(wǎng)格模型規(guī)模及基本體的拓?fù)鋸?fù)雜性無關(guān)，而只與采樣分辨率相關(guān)?？傮w運行時間對于128×128的分辨率情況可以達(dá)到實時效果，對于高分辨率情況亦可快速完成，對比網(wǎng)格模型的3D布爾運算具有上百倍的速度提升，而且顯示效果同基于網(wǎng)格模型的渲染效果無異。該算法目前尚有提升空間，在后續(xù)工作中將就渲染效果以及分布式網(wǎng)格計算技術(shù)進(jìn)行融合，從而能讓大規(guī)模多次布爾運算達(dá)到瞬間響應(yīng)的效果。

References)

[1] 姜旭東,盛斌,馬利莊,等.基于自適應(yīng)延遲切割的三角網(wǎng)格布爾運算優(yōu)化[J].軟件學(xué)報,2016,27(10):2473-2487.(JIANG X D, SHENG B, MA L Z, et al. Optimization of set operations on triangulated polyhedrons using adaptive lazy splitting [J]. Journal of Software, 2016, 27(10): 2473-2487.)

[2] 蔡闖,成思源,楊雪榮.基于特征分解的逆向建模技術(shù)研究[J].現(xiàn)代制造工程,2016(2):119-122.(CAI C, CHENG S Y, YANG X R. Research of reverse modeling technology based on feature decomposition [J]. Modern Manufacturing Engineering, 2016(2): 119-122.)

[3] 王翀,安偉強(qiáng),王紅娟.基于圓柱體-軸向包圍盒檢測的巷道相交建模[J].計算機(jī)應(yīng)用,2015,35(12):3592-3596.(WANG C, AN W Q, WANG H J. Tunnel intersection modeling based on cylinder-axis aligned bounding box [J]. Journal of Computer Applications, 2015, 35(12): 3592-3596.)

[4] VAN DEN BERGEN G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools, 1997, 2(4): 1-13.

[5] GOTTSCHALK S, LIN M C, MANOCHA D. OBB tree: a hierarchical structure for rapid interference detection [C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1996: 171-180.

[6] HUBBARD P M. Collision detection for interactive graphics applications [J]. IEEE Transactions on Visualization and Computer Graphics, 1998, 1(3): 218-230.

[7] KLOSOWSKI J T, HELD M, MITCHELL J S B, et al. Efficient collision detection using bounding volume hierarchies ofk-DOPs [J]. IEEE Transactions on Visualization and Computer Graphics, 1998, 4(2): 21-36.

[8] PAVIC D, CAMPEN M, KOBBELT L. Hybrid Booleans [J]. Computer Graph Forum, 2010, 29: 75-87.

[9] LORENSEN W E, CLINE H E. Marching cubes: a high resolution 3D surface construction algorithm [J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 163-169.

[10] KIM Y, VARADHAN G, LIN M C, et al. Fast swept volume approximation of complex polyhedral models [C]// Proceedings of the Eighth ACM Symposium on Solid Modeling and Application. New York: ACM, 2004: 1013-1027.

[11] CHEN Y, WANG C C L. Robust and accurate Boolean operations on polygonal models [C]// ASME 2007: Proceedings of the 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. New York: ACM, 2007: 357-369.

[12] JONES M W, BARENTZEN J A, SRAMEK M. 3D distance fields: a survey of techniques and applications [J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(4): 581-599.

[13] MUSETH K, BREEN D E, WHITAKER R T, et al. Level set surface editing operators [J]. ACM Transactions on Graphics, 2002, 21(3): 330-338.

[14] ADAMS B, DUTRE P. Interactive Boolean operations on surfel-bounded solids [J]. ACM Transactions on Graphics, 2003, 22(3): 651-656.

[15] MENON J P, VOELCKER H B. On the completeness and conversion of ray representations of arbitrary solids [C]// Proceedings of the 1995 International Proceedings of ACM Symposium on Solid Modeling and Applications. New York: ACM, 1995: 175-286.

[16] WANG C L. Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction [J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(6): 836-849.

[17] HEIDELBERGER B, TESCHNER M, GROSS M. Detection of collisions and self-collisions using image space techniques [J]. Journal of WSCG, 2004, 12(1/2/3): 145-152.

[18] FEITO F R, OGAYAR C J, SEGURA R J, et al. Fast and accurate evaluation of regularized Boolean operations on triangulated solids [J]. Computer-Aided Design, 2013, 45(3): 705-716.

[19] WANG C C L, LEUNG Y S, CHEN Y. Solid modeling of polyhedral objects by layered depth-normal images on the GPU [J]. Computer-Aided Design, 2010, 42(6): 535-544.

[20] ADAMS B, DUTRE P. Interactive Boolean operations on surfel-bounded solids [J]. ACM Transactions on Graphics, 2003, 22(3): 651-656.

[21] WANG C L. Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction [J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(6): 836-849.

[22] WANG Z J, LIN X, FANG M E, et al. RE2L: an efficient output-sensitive algorithm for computing Boolean operations on circular-arc polygons and its applications [J]. Computer-Aided Design, 2017, 83: 1-14.

[23] LANDIER S. Boolean operations on arbitrary polygonal and polyhedral meshes [J]. Computer-Aided Design, 2016, 85: 138-153.

[24] JIANG X, PENG Q, CHENG X, et al. Efficient Booleans algorithms for triangulated meshes of geometric modeling [J]. Computer-Aided Design and Applications, 2016, 13(4): 1-12.

[25] CHEN M, CHEN X Y, TANG K, et al. Efficient Boolean operation on manifold mesh surfaces [J]. Computer-Aided Design and Applications, 2010, 7(3): 405-415.

This work is partially supported by the National Natural Science Foundation of China (61662006), Shenzhen Basic Research Project (JCYJ20140417172620448), Guangxi Overseas 100 Plan Project.

YANGZhanglong, born in 1992, M. S. candidate. His research interests include computer aided design.

CHENMing, born in 1979, Ph. D, professor. His research interests include computer aided design and computer aided manufacturing, virtual reality.

QuickvisualBooleanoperationonheavymeshmodels

YANG Zhanglong, CHEN Ming*

(SchoolofComputerScienceandInformationTechnology,GuangxiNormalUniversity,GuilinGuangxi541004,China)

A new algorithm was proposed to meet the instantaneous response requirements of the Boolean operation between large-scale mesh models in the product design. Discrete sampling was performed on mesh models to obtain the ray-segment point clound model and the three-dimensional Boolean operation among triangular mesh was then converted into one-dimensional one among ray segments; the intersection points could be accurately solved and interpolated around the overlapped regions of mesh models, so the Boolean operation was significantly speeded and the design efficiency of products of complex topology was greatly improved in turn. The point cloud model obtained by the proposed algorithm could be rendered with the same effect as that by the triangular mesh model. The proposed method can be adopted in engineering applications.

Boolean operation; discrete sampling; point cloud model; point cloud rendering; Constructive Solid Geometry (CSG)

TP391.72

:A

2017- 01- 13;

:2017- 03- 03。

國家自然科學(xué)基金資助項目(61662006)；深圳市基礎(chǔ)研究基金資助項目(JCYJ20140417172620448)；廣西壯族自治區(qū)海外百人計劃項目。

楊張龍(1992—)，男，湖南岳陽人，碩士研究生，主要研究方向：計算機(jī)輔助設(shè)計； 陳明(1979—)，男，湖南邵陽人，教授，博士，主要研究方向：計算機(jī)輔助設(shè)計與制造、虛擬現(xiàn)實。

1001- 9081(2017)07- 2050- 07

10.11772/j.issn.1001- 9081.2017.07.2050