白 茂 東， 華 順 剛， 蘇 鐵 明

( 大連理工大學(xué) 機(jī)械工程學(xué)院, 遼寧 大連 116024 )

組件匹配與融合的三維形狀建模研究

白 茂 東， 華 順 剛*， 蘇 鐵 明

( 大連理工大學(xué) 機(jī)械工程學(xué)院, 遼寧 大連 116024 )

提出一種基于組件匹配、融合的三維形狀生成算法.根據(jù)Hausdorff距離對(duì)輸入形狀的各組件進(jìn)行匹配，形成匹配組件對(duì)，進(jìn)行球面參數(shù)化映射，合并組件對(duì)的球面網(wǎng)格模型；通過(guò)反映射建立組件間的頂點(diǎn)對(duì)應(yīng)關(guān)系，采用不同的融合系數(shù)進(jìn)行插值融合，生成一系列連續(xù)變化的組件；最后根據(jù)輸入形狀的連接關(guān)系進(jìn)行重新連接，生成完整的變形形狀．實(shí)驗(yàn)表明，采用所提算法可以生成合理、相似的變形形狀，同時(shí)保留了輸入形狀的功能和表面細(xì)節(jié)．

組件匹配；球面參數(shù)化；網(wǎng)格融合；重連接

0 引 言

基于實(shí)例的三維形狀建模技術(shù)通過(guò)對(duì)已有形狀的編輯修改生成新的、功能相似的三維形狀，該技術(shù)可廣泛應(yīng)用于CAD、工業(yè)造型設(shè)計(jì)、創(chuàng)新設(shè)計(jì)以及計(jì)算機(jī)動(dòng)畫(huà)和虛擬現(xiàn)實(shí)等領(lǐng)域[1-2]，近年來(lái)已成為計(jì)算機(jī)圖形學(xué)界的研究熱點(diǎn)．

目前已有多種三維形狀變形生成算法涌現(xiàn)，其中具有代表性的方法是對(duì)現(xiàn)有形狀的組件進(jìn)行替換、重組得到具有創(chuàng)意的三維形狀[3]，這類方法包括：基于形狀的約束推導(dǎo)分析生成新形狀[4]、根據(jù)樣式轉(zhuǎn)移方法生成融合形狀[5]、利用概率形狀結(jié)構(gòu)指導(dǎo)組件的替換或重組[6]，以及基于集合演變方法進(jìn)行三維形狀的生成[7]等．該類方法依賴輸入形狀結(jié)構(gòu)，當(dāng)替換含有不兼容的組件結(jié)構(gòu)時(shí)，會(huì)導(dǎo)致不合理的結(jié)果．另一類方法通過(guò)拓?fù)渥儞Q、融合及重建來(lái)生成具有新的拓?fù)浣Y(jié)構(gòu)的三維形狀[8]．這類方法可以生成拓?fù)浣Y(jié)構(gòu)不同的形狀，但因需泊松重建，所以難以保證形狀的細(xì)節(jié)；且在變形過(guò)程中因拓?fù)浒l(fā)生了改變，會(huì)生成較多不合理的新形狀，需進(jìn)行人工干預(yù)排除．此外，Kanai等[9]提出了一種針對(duì)等拓?fù)鋑enus-0模型的變形框架，這種變形方法需要模型特征的嚴(yán)格對(duì)齊．

本文提出一種基于實(shí)例的三維網(wǎng)格形狀變形生成算法．三維網(wǎng)格形狀由點(diǎn)、線和面片組成，通過(guò)組件匹配、融合、重連接生成新的連續(xù)變化的形狀，這里的組件是在預(yù)處理過(guò)程中形成且具有模型部分功能意義的封閉網(wǎng)格．算法輸入的是經(jīng)規(guī)則化及組件分割等預(yù)處理后的形狀，算法步驟綜述如下：首先，基于Hausdorff距離[10]進(jìn)行輸入形狀中各組件的匹配，形成匹配組件對(duì)；其次，對(duì)各組件進(jìn)行球面參數(shù)化映射，合并兩組件的球面網(wǎng)格模型，該模型中包括兩個(gè)輸入組件的所有頂點(diǎn)，通過(guò)反映射使組件對(duì)間建立頂點(diǎn)對(duì)應(yīng)關(guān)系，進(jìn)行插值融合；最后，根據(jù)輸入形狀的接觸及連接關(guān)系信息，進(jìn)行重連接生成完整的變形形狀．其中插值融合形成新的網(wǎng)格模型包含組件的表面細(xì)節(jié)特征，采用不同的融合系數(shù)，可產(chǎn)生一系列連續(xù)變化的形狀．

1 組件匹配

根據(jù)設(shè)計(jì)者意圖選取兩個(gè)三維形狀作為輸入，其中一個(gè)作為原始形狀，另一個(gè)作為參考形狀，為便于組件的匹配和融合，需要對(duì)輸入的形狀進(jìn)行預(yù)處理操作，包括形狀規(guī)則化、方向歸一化以及組件分割等．通過(guò)調(diào)整參考形狀頂點(diǎn)可以對(duì)形狀的外形尺寸進(jìn)行規(guī)則化處理，根據(jù)主成分分析法[11]可以對(duì)模型方向進(jìn)行歸一化．此外，許多現(xiàn)有算法[3，12]可以對(duì)形狀進(jìn)行組件分割，使所輸入形狀由若干組件組成．由于本文所述重點(diǎn)是組件的匹配和融合，在此，對(duì)預(yù)處理操作不做詳細(xì)敘述．

組件匹配的目的是建立兩個(gè)給定形狀所有組件之間最佳的對(duì)應(yīng)關(guān)系．對(duì)于來(lái)源于不同形狀的兩組件，可以計(jì)算它們點(diǎn)云數(shù)據(jù)之間的Hausdorff距離來(lái)測(cè)量組件距離．

Hausdorff距離表示的是一個(gè)度量空間內(nèi)兩個(gè)非空子集之間的相互距離．它可以反映兩個(gè)集合之間的差距，因此，用它表示兩個(gè)組件之間的不相似度．

對(duì)于一個(gè)度量空間內(nèi)的兩個(gè)非空集合X={x1，x2，…，xm}和Y={y1，y2，…，yn}，X到Y(jié)的Hausdorff距離定義為

(1)

H(X，Y)=max {h(X，Y)，h(Y，X)}

(2)

該式反映了兩個(gè)集合之間的相似程度[13-14]．

組件距離為通過(guò)式(2)計(jì)算的組件網(wǎng)格點(diǎn)云數(shù)據(jù)之間的Hausdorff距離．

本文使用一種貪婪算法對(duì)兩個(gè)形狀中的組件進(jìn)行匹配．其具體過(guò)程如下：首先，對(duì)于原始形狀中的每一個(gè)組件，它到參考形狀中每個(gè)組件的距離，可以通過(guò)式(2)計(jì)算，并保存在距離集H中；其次，找出其最小的Hausdorff距離Hmin，如果Hmin小于相似度閾值θ，那么與Hmin距離對(duì)應(yīng)的兩個(gè)組件被認(rèn)為是匹配的并作為一個(gè)匹配組件對(duì)；然后，刪除集合H中與此匹配組件對(duì)相關(guān)的其他元素，重復(fù)這一過(guò)程直到出現(xiàn)Hmin大于相似度閾值θ或者一個(gè)形狀中的所有組件都完成配對(duì)，如果仍存在不可匹配的組件，則被視為沒(méi)有對(duì)應(yīng)關(guān)系．圖1列舉了兩個(gè)形狀匹配的一些具體實(shí)例，其中匹配的組件對(duì)用相同的顏色表示，無(wú)匹配關(guān)系的組件用淺棕色表示．

圖1 兩個(gè)形狀的組件匹配

2 基于球面參數(shù)化的組件融合

為充分保持組件表面特征，對(duì)于匹配組件對(duì)，采用基于組件融合的球面參數(shù)化[15]方法進(jìn)行融合．該方法分為以下3步：第1步對(duì)匹配組件對(duì)的方向和大小進(jìn)行標(biāo)準(zhǔn)化；第2步將匹配的組件分別參數(shù)化到一個(gè)單位球面上生成拓?fù)淝騇o和Mr，并融合生成新的拓?fù)淝騇c；第3步利用Mc頂點(diǎn)對(duì)匹配組件對(duì)進(jìn)行反映射，獲得頂點(diǎn)對(duì)應(yīng)關(guān)系，并進(jìn)行頂點(diǎn)插值生成新的融合組件．

2.1 組件標(biāo)準(zhǔn)化

組件標(biāo)準(zhǔn)化的實(shí)質(zhì)是對(duì)匹配組件對(duì)的頂點(diǎn)集Vo和Vr進(jìn)行標(biāo)準(zhǔn)化．首先使用主成分分析法(principal component analysis，PCA)[11,16]對(duì)組件點(diǎn)云信息進(jìn)行分析，然后計(jì)算出組件3個(gè)主成分，確定組件的主軸．

通常把組件的第一主成分作為主軸，但對(duì)于不同的組件，其參考組件的第一主成分可能會(huì)存在很大差異，因此，將原始組件的第一主成分作為主軸，對(duì)于參考組件，將最接近原始組件主軸的主成分作為匹配組件的主軸．如圖2所示，原始組件的第一主成分e1作為主軸eorig．顯然，對(duì)于參考組件，其第一主成分e′1與e1(即eorig)存在很大差異，因此，將最接近eorig的主成分e′2作為參考組件的主軸eref．

圖2 原始和參考組件的主軸選擇

接著將匹配組件對(duì)的主軸eorig和eref進(jìn)行對(duì)齊．在由eorig和eref確定的平面中，通過(guò)旋轉(zhuǎn)向量eorig，使之與向量eref一致，在三維坐標(biāo)系中，可以通過(guò)旋轉(zhuǎn)矩陣M實(shí)現(xiàn)向量的旋轉(zhuǎn)：

(3)

由此可以得到旋轉(zhuǎn)矩陣

(4)

同時(shí)得到主軸規(guī)范后原始組件和參考組件的頂點(diǎn)集V′o(V′o=VoM)和V′r(V′r=Vr)．為了將參考組件轉(zhuǎn)變成與原始組件具有相同包圍盒大小的結(jié)構(gòu)，利用一個(gè)3×3對(duì)角矩陣S，S=diag{sx，sy，sz}，對(duì)組件進(jìn)行縮放，其中sx、sy和sz分別為原始組件和參考組件的包圍盒3個(gè)主軸方向邊的長(zhǎng)度比．

2.2 球面參數(shù)化

組件標(biāo)準(zhǔn)化后，根據(jù)球面中心投影法將組件映射到一個(gè)單位球上，組件的質(zhì)心即為球心．為了消除映射產(chǎn)生的疊影，本文使用拉普拉斯迭代方法[17]進(jìn)行過(guò)濾．拉普拉斯算子通常被定義為一種低通濾波器，它可以過(guò)濾高頻，而疊影常發(fā)生在球體表面頂點(diǎn)的高頻區(qū)域，所以使用拉普拉斯迭代來(lái)消除疊影．其數(shù)學(xué)表達(dá)式為

(5)

V′=V+ΔV={v′i|v′i=vi+Δvi，Δvi=L(vi)}

(6)

迭代的過(guò)程即為消除疊影的過(guò)程，迭代完成后，即可得到原始組件和參考組件的球面參數(shù)化網(wǎng)格模型Mo和Mr．

接下來(lái)對(duì)網(wǎng)格模型Mo和Mr進(jìn)行拓?fù)淙诤仙赏負(fù)淝騇c，拓?fù)淝騇c包含Mo和Mr中所有頂點(diǎn)及網(wǎng)格相交生成的交點(diǎn)．如圖3所示，實(shí)心點(diǎn)屬于參數(shù)化到Mo上的頂點(diǎn)，空心點(diǎn)屬于參數(shù)化到Mr上的頂點(diǎn)．在Mo和Mr的網(wǎng)格模型上，其任意一條邊與球心O的連線可以形成新的面，在Mc中當(dāng)兩者相交時(shí)會(huì)產(chǎn)生一條通過(guò)球心的直線(如圖3中的紅線所示)，該直線與單位球表面的交點(diǎn)，即為新生成的點(diǎn)．然后遍歷每一條邊，并按照順時(shí)針?lè)较蜻M(jìn)行邊循環(huán)創(chuàng)建面，如圖4所示，新形成的面可能含有3條邊、4條邊等，最后基于銳角三角形原則進(jìn)行三角化形成最終的網(wǎng)格模型Mc．

圖3 Mo和Mr之間的交點(diǎn)

圖4 在Mc中沿著邊循環(huán)創(chuàng)建面

2.3 反映射與組件生成

融合生成的網(wǎng)格模型Mc包含了原始組件和參考組件的所有頂點(diǎn)信息，反映射的過(guò)程實(shí)際就是利用Mc的頂點(diǎn)坐標(biāo)分別表示原始組件及參考組件頂點(diǎn)的過(guò)程．根據(jù)上述Mc的頂點(diǎn)分類，反映射過(guò)程中，它的每一個(gè)頂點(diǎn)都必須被考慮和確定，這里用計(jì)算反映射原始組件Vc-o的變換進(jìn)行說(shuō)明．對(duì)于Mo的每一個(gè)頂點(diǎn)，它必須被包含在Mc上一個(gè)確定的三角形面片中，考慮到三角形頂點(diǎn)的相對(duì)位置，利用Mc包含的三角形去計(jì)算Mo的頂點(diǎn)，并用Mc上的頂點(diǎn)坐標(biāo)進(jìn)行表示．這樣Mo的頂點(diǎn)就得到了重新計(jì)算，也就完成了Vc-o的變換．同理可得到反映射參考組件的Vc-r的變換，具體的組件融合與反映射過(guò)程如圖5所示．

如上所述，利用Mc的網(wǎng)格結(jié)構(gòu)表示原始組件以及參考組件的變換，即Vc-o和Vc-r，可以獲取原始組件及參考組件上所有頂點(diǎn)的對(duì)應(yīng)關(guān)系．如圖6所示，通過(guò)在Vc-o和Vc-r進(jìn)行頂點(diǎn)插值，生成組件由原始組件向參考組件進(jìn)行轉(zhuǎn)變．融合頂點(diǎn)可以計(jì)算如下：

Vc(k)=kVc-o+(1-k)Vc-r

(7)

其中k(0

圖5 組件球面參數(shù)化、網(wǎng)格融合及重建過(guò)程

圖6 組件融合

3 組件重連接

(a) 融合后的組件分離現(xiàn)象

(b) 重連接后的合理形狀

圖7 組件重連接

Fig.7 Component relinking

雖然組件融合保留了原始頂點(diǎn)的拓?fù)潢P(guān)系，但融合生成的組件在幾何形狀、維度以及位置上會(huì)產(chǎn)生變化．如果直接將生成的組件進(jìn)行連接，則可能會(huì)發(fā)生如圖7(a)所示的組件分離等現(xiàn)象．為確保連接和拓?fù)渥兓暮侠硇裕疚倪x擇幾何尺寸最大或者位于原始形狀正中心的組件作為基礎(chǔ)組件，然后獲取相對(duì)于該組件其他所有組件的位置，從而進(jìn)行組件重連接．如果原始形狀的兩個(gè)組件具有連接關(guān)系c1=(S1，S2)，S1和S2是通過(guò)兩個(gè)組件最近的頂點(diǎn)集，那么，可以類似地獲得它們?cè)趨⒖夹螤钪蟹謩e匹配的組件對(duì)應(yīng)的連接關(guān)系c2=(S′1，S′2)．對(duì)于融合系數(shù)k，融合后的組件對(duì)應(yīng)連接關(guān)系cb(k)可以通過(guò)公式cb(k)=kc1+(1-k)c2計(jì)算得到．如圖7(b)所示，按照其計(jì)算后的連接關(guān)系調(diào)整融合后的組件，將形成完整合理的形狀．

4 實(shí)驗(yàn)驗(yàn)證

在Intel i5處理器、3.30 GHz主頻、 8 GB內(nèi)存臺(tái)式機(jī)上對(duì)本文算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，使用C++ 語(yǔ)言在VS2010開(kāi)發(fā)平臺(tái)對(duì)off網(wǎng)格模型進(jìn)行處理．為驗(yàn)證本文算法的有效性和實(shí)用性，從互聯(lián)網(wǎng)和一些文獻(xiàn)中[8，18]收集若干三維網(wǎng)格模型，如桌子、椅子、飛機(jī)等，實(shí)驗(yàn)結(jié)果如圖8所示．

每一行從左到右融合系數(shù)k依次取值為0、0.2、0.4、0.6、0.8、1.0．對(duì)于輸入形狀，如果所有組件都具有一對(duì)一匹配關(guān)系，那么無(wú)論選擇誰(shuí)作為原始組件，其變形結(jié)果都相同；對(duì)于沒(méi)有匹配關(guān)系的組件，只作簡(jiǎn)單保留．相較于組件替換及拓?fù)渥兓男螤钌煞椒╗8]，本文算法能夠生成合理的表面變形，同時(shí)保留輸入模型功能合理性和表面細(xì)節(jié)．在圖8中，每行模型都能基于輸入產(chǎn)生完整的過(guò)渡變化效果且保持了輸入的功能合理性，第1、2和4行原始桌腿的表面紋理在變化中被很好地繼承下來(lái)，第9和10行娃娃頭部特征也被很好地繼承下來(lái)．

圖8 形狀生成實(shí)例

根據(jù)輸入形狀的多樣性，雖然所提出的算法可以生成大量的變形形狀，但每一個(gè)三角形面片和頂點(diǎn)都將基于輸入的網(wǎng)格模型被計(jì)算處理成新的網(wǎng)格，因此，需要輸入具有良好網(wǎng)格結(jié)構(gòu)的形狀模型．

5 結(jié) 語(yǔ)

基于組件匹配和融合，實(shí)現(xiàn)了三維形狀的生成．算法首先基于Hausdorff距離對(duì)輸入形狀的組件進(jìn)行匹配，獲得匹配組件對(duì)；為避免表面凹凸遮擋現(xiàn)象，解決頂點(diǎn)對(duì)應(yīng)的準(zhǔn)確性，便于獲得形狀表面細(xì)節(jié)，將匹配組件對(duì)球面參數(shù)化，融合生成新的包含兩組件全部頂點(diǎn)的網(wǎng)格模型；然后用融合的網(wǎng)格對(duì)組件進(jìn)行反映射計(jì)算，新生成的網(wǎng)格模型包含輸入組件的所有頂點(diǎn)對(duì)應(yīng)關(guān)系．頂點(diǎn)插值時(shí)根據(jù)融合系數(shù)的不同取值，獲得不同的組件形狀；最后基于輸入形狀的連接關(guān)系將生成的組件進(jìn)行重連接，產(chǎn)生連續(xù)變化的形狀．本文提出的匹配融合算法生成的形狀具有合理的幾何外觀和功能，并保留了輸入形狀的細(xì)節(jié)．

[1] WATSON I, PERERA S. Case-based design: A review and analysis of building design applications [J]. Artificial Intelligence for Engineering Design Analysis and Manufacturing, 1997, 11(1):59-87.

[2] LIU Qiaosheng, XI Juntong. Case-based parametric design system for test turntable [J]. Expert Systems with Applications, 2011, 38(6):6508-6516.

[3] KALOGERAKIS E, CHAUDHURI S, KOLLER D A. A probabilistic model for component-based shape synthesis [J]. ACM Transactions on Graphics, 2012, 31(4):55.

[4] JAIN A, THORMHLEN T, RITSCHEL T,etal. Exploring shape variations by 3D-model decomposition and part-based recombination [J]. Computer Graphics Forum, 2012, 31(2):631-640.

[5] HAN Zhizhong, LIU Zhenbao, HAN Junwei,etal. 3D shape creation by style transfer [J]. The Visual Computer, 2015, 31(9):1147-1161.

[6] CHAUDHURI S, KALOGERAKIS E, GUIBAS L,etal. Probabilistic reasoning for assembly-based 3D modeling [J]. ACM Transactions on Graphics, 2011, 30(4):35.

[7] XU Kai, ZHANG Hao, COHEN-OR D,etal. Fit and diverse:Set evolution for inspiring 3D shape galleries [J]. ACM Transactions on Graphics, 2012, 31(4):57.

[8] ALHASHIM I, LI Honghua, XU Kai,etal. Topology-varying 3D shape creation via structural blending [J]. ACM Transactions on Graphics, 2014, 33(4):158.

[9] KANAI T, SUZUKI H, KIMURA F. Metamorphosis of arbitrary triangular meshes [J]. IEEE Computer Graphics and Applications, 2000, 20(2):62-75.

[10] Wikipedia. Hausdorff distance [Z/OL]. [2016-07-28]. https://en.wikipedia.org/wiki/Hausdorff_distance.

[11] ABDI H, WILLIAMS L J. Principal component analysis [J]. Wiley Interdisciplinary Reviews:Computational Statistics, 2010, 2(4):433-459.

[12] SHAMIR A. A survey on mesh segmentation techniques [J]. Computer Graphics Forum, 2008, 27(6):1539-1556.

[13] ROTE G. Computing the minimum Hausdorff distance between 2 point sets on a line under translation [J]. Information Processing Letters, 1991, 38(3):123-127.

[14] RUCKLIDGE W. Efficient computation of the minimum Hausdorff distance for visual recognition [D]. Ithaca:Cornell University, 1995.

[15] ALEXA M. Recent advances in mesh morphing [J]. Computer Graphics Forum, 2002, 21(2):173-196.

[16] PAPADAKIS P, PRATIKAKIS I, PERANTONIS S,etal. Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation [J]. Pattern Recognition, 2007, 40(9):2437-2452.

[17] TAUBIN G. Signal processing approach to fair surface design [C] // Proceedings of the ACM SIGGRAPH Conference on Computer Graphics. New York: ACM, 1995:351-358.

[18] ALHASHIM I, XU Kai, ZHUANG Yixin,etal. Deformation-driven topology-varying 3D shape correspondence [J]. ACM Transactions on Graphics, 2015, 34(6):236.

Research on 3D shape modeling using component matching and merging

BAI Maodong, HUA Shungang*, SU Tieming

( School of Mechanical Engineering, Dalian University of Technology, Dalian 116024, China )

A 3D shape creation algorithm based on component matching and merging is proposed. Components are matched between two input shapes according to the Hausdorff distance metric to generate matched component-pairs. The components are mapped onto the spherical surface to carry out the spherical parameterization. The spherical meshes of two matched components are merged, and the vertices correspondence between matched component-pairs are built through reverse mapping.The interpolation is concluded to create a series of in-betweens in terms of the merging coefficient. Finally, the novel variations are obtained by relinking components with reference to the connection of input shapes. Experiments show that the proposed algorithm can generate reasonable and plausible variations, while retaining the function and adequate surface details of the input shapes.

components matching; spherical parameterization; mesh merging; relinking

1000-8608(2017)03-0241-06

2016-08-15；

2017-03-28．

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300085).

白茂東(1989-)，男，博士生，E-mail:baimaodong@mail.dlut.edu.cn；華順剛*(1964-)，男，教授， E-mail:hsgang02@dlut.edu.cn；蘇鐵明(1972-)，男，講師，E-mail:tiemings@dlut.edu.cn.

TP391

A

10.7511/dllgxb201703004