楊張龍，陳 明

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

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

楊張龍，陳 明*

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

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

布爾運(yùn)算；離散化采樣；點(diǎn)云模型；點(diǎn)云渲染; 組合實(shí)體造型

0 引言

組合實(shí)體造型(Constructive Solid Geometry, CSG)技術(shù)對(duì)多個(gè)簡單幾何實(shí)體通過交、并、差三種布爾運(yùn)算組合可構(gòu)建復(fù)雜幾何形態(tài)(如圖1)，所以廣泛應(yīng)用于某些拓?fù)浣Y(jié)構(gòu)復(fù)雜的產(chǎn)品外形設(shè)計(jì)中[1-3]。隨著3D打印的興起以及制造工藝的提高，使復(fù)雜拓?fù)浣Y(jié)構(gòu)的產(chǎn)品擺脫傳統(tǒng)的手工雕刻加工轉(zhuǎn)化為自動(dòng)化加工成為可能，進(jìn)而利用布爾運(yùn)算設(shè)計(jì)復(fù)雜產(chǎn)品外形成為不可缺少的步驟。設(shè)計(jì)過程中需不斷編輯單個(gè)圖元然后反復(fù)進(jìn)行布爾運(yùn)算查看整體效果，對(duì)于復(fù)雜的網(wǎng)格模型編輯來說，布爾運(yùn)算的穩(wěn)定性以及效率成了設(shè)計(jì)瓶頸。以圖1(c)為例，涉及到的布爾運(yùn)算總次數(shù)超過100次，而戒指外圈的每次修改將會(huì)導(dǎo)致這100次布爾運(yùn)算的執(zhí)行，而每個(gè)戒指的最終產(chǎn)品設(shè)計(jì)統(tǒng)計(jì)數(shù)據(jù)表明外圈的修改次數(shù)20次以上，從而會(huì)產(chǎn)生2 000次布爾運(yùn)算。在主流計(jì)算機(jī)輔助設(shè)計(jì)(Computer Aided Design, CAD)軟件的測試結(jié)果(CATIA，Rhino，Solidworks)則通常需等候120 h以上(每次修改等待6 h)，有些甚至直接告知無法進(jìn)行運(yùn)算，這對(duì)于設(shè)計(jì)所需立等可得的運(yùn)算效率來說是難以接受的，極大限制了此類產(chǎn)品的設(shè)計(jì)效率，業(yè)界迫切需要對(duì)這一速度瓶頸進(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]等,此類方法對(duì)于超大規(guī)模的布爾運(yùn)算來說仍然繞不開網(wǎng)格面片求交運(yùn)算以及后期的碎片網(wǎng)格化的復(fù)雜運(yùn)算，從而無法實(shí)現(xiàn)最終的快速布爾運(yùn)算效果；還有學(xué)者基于重建的近似方法[9-10]來解決布爾運(yùn)算存在的不穩(wěn)定性問題,主要包括體素法[11]、距離場(distance field)[12],level-set[13]、面元法(surfel)[14]、射線表示法[15-17]和八叉樹[18]。

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

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

1 算法概述

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

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

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

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

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

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

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

1.2 法線方向獲取

針對(duì)點(diǎn)云模型進(jìn)行渲染前，獲取每個(gè)像素的法線值對(duì)于渲染的光順性非常重要。若該網(wǎng)格模型來自參數(shù)模型，則可直接計(jì)算該取樣點(diǎn)的法線值；如果該模型是通過點(diǎn)云重建或者頂點(diǎn)法線信息缺失，則需擬合每個(gè)取樣點(diǎn)的法線信息。文獻(xiàn)[19]采用顏色索引值的方法獲取每個(gè)采樣點(diǎn)所屬哪一個(gè)三角片，然后將三角片的面法線作為每個(gè)采樣點(diǎn)的點(diǎn)法線；對(duì)該方法渲染時(shí)會(huì)出現(xiàn)面片棱角，仍需進(jìn)行光順處理?？紤]到所有交點(diǎn)皆為有序排放，周圍鄰域點(diǎn)很容易獲取，從而采用一種更為精確的近似方法進(jìn)行取樣點(diǎn)的法線賦值。如圖4所示，Pi點(diǎn)為待求法線的取樣點(diǎn)?？梢栽赬YZ方向，按照索引號(hào)i,j,k逐漸遞增搜索的方法快速獲取1-ring鄰域的所有鄰域點(diǎn)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 點(diǎn)Pi法線的構(gòu)建

2 基于點(diǎn)云模型的一維布爾運(yùn)算

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

布爾運(yùn)算的保留/去除判定如下所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 插值交線

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

3.1 交點(diǎn)定位

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

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

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

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

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

3.2 特殊情景處理

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

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

3.3 交點(diǎn)求解

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

對(duì)于情景1：線段P1P2和線段Q1Q2的交點(diǎn)作為基本體A和基本體B的交點(diǎn)；

對(duì)于情景2：Q1和Q2的中點(diǎn)作為交點(diǎn)；

對(duì)于情景3:Qi和Qn+i-1的中點(diǎn)作為系列交點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)現(xiàn)與分析

基于三角面片的模型的布爾運(yùn)算的時(shí)間主要消耗在可能相交的三角面片集的獲取與交線環(huán)的提取上，隨著三角面片數(shù)目的增多消耗的時(shí)間增加。本實(shí)例將在犀牛軟件作為平臺(tái)進(jìn)行基于面片的布爾運(yùn)算(如圖10～13)，作為對(duì)比算法。實(shí)驗(yàn)中硬件開發(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ā)平臺(tái)，顯示處理庫為OpenGL。對(duì)比的參考量則是運(yùn)行時(shí)間，分別就不同的取樣分辨率進(jìn)行了時(shí)間統(tǒng)計(jì)。其中實(shí)例1～3為兩個(gè)幾何體進(jìn)行布爾運(yùn)算，實(shí)例4和實(shí)例5則是多個(gè)基本體進(jìn)行布爾運(yùn)算。

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

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

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

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

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

表1 犀牛軟件算法與所提算法的耗時(shí)對(duì)比

6 結(jié)語

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

References)

[1] 姜旭東,盛斌,馬利莊,等.基于自適應(yīng)延遲切割的三角網(wǎng)格布爾運(yùn)算優(yōu)化[J].軟件學(xué)報(bào),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ì)算機(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é)基金資助項(xiàng)目(61662006)；深圳市基礎(chǔ)研究基金資助項(xiàng)目(JCYJ20140417172620448)；廣西壯族自治區(qū)海外百人計(jì)劃項(xiàng)目。

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

1001- 9081(2017)07- 2050- 07

10.11772/j.issn.1001- 9081.2017.07.2050