金 耀 , 熊宇龍 , 周泳全 , 張華熊 , 何利力

1(浙江理工大學(xué) 信息學(xué)院 圖形與數(shù)據(jù)智能研究所,浙江 杭州 310018)

2(深圳信息職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院,廣東 深圳 518172)

隨著計(jì)算機(jī)軟硬件的迅猛發(fā)展,計(jì)算機(jī)輔助設(shè)計(jì)(CAD)、虛擬現(xiàn)實(shí)技術(shù)(VR)、增強(qiáng)現(xiàn)實(shí)技術(shù)(AR)得到了廣泛應(yīng)用,并逐漸融入人們的生活.如何高效地對虛擬場景進(jìn)行建模,成為當(dāng)前圖形學(xué)領(lǐng)域的重要研究課題之一.在此背景下,交互式三維建模的方式越來越豐富,其中組裝式建模,即通過部件組合的方式合成新模型,是一種低門檻、高效率的建模手段[1,2],受到人們的青睞;尤其是近年來與機(jī)器學(xué)習(xí)方法的結(jié)合[1,3,4],使其變得更為智能、高效與便捷,逐漸成為幾何建模領(lǐng)域的一個研究熱點(diǎn).

組裝式建模涉及的網(wǎng)格融合問題,是指將源網(wǎng)格與目標(biāo)網(wǎng)格進(jìn)行融合以合成新的網(wǎng)格模型.現(xiàn)有的主流方法大致可分為構(gòu)造過渡曲面法與重建幾何法.

· 構(gòu)造過渡曲面法在源網(wǎng)格與目標(biāo)網(wǎng)格邊界之間構(gòu)造了隱式曲面實(shí)現(xiàn)光滑拼接[5?8],這類方法適用多個復(fù)雜邊界的融合,但隱式曲面(如徑向基函數(shù)插值)通常需求解稠密矩陣方程且需網(wǎng)格化,較為耗時,因此往往難以達(dá)到交互響應(yīng)速度;

· 重建法如經(jīng)典的泊松融合[9]能夠針對差異(形狀、大小與頂點(diǎn)密度)較大的融合邊界重建出可靠的源網(wǎng)格幾何形狀,但其旋轉(zhuǎn)場與尺度場涉及測地線的計(jì)算,影響了效率,難以滿足交互需求.為避免耗時的旋轉(zhuǎn)場與尺度場計(jì)算,現(xiàn)有方法往往借助交互手段將源模型與目標(biāo)網(wǎng)格進(jìn)行對齊,然后運(yùn)用代價較小的變形方法進(jìn)行幾何重建實(shí)現(xiàn)融合[10];為避免方程組的求解,進(jìn)一步提高效率,變形過程采用了廣義重心坐標(biāo)法[4,11],但以增加交互量為代價.

為提高算法效率便于交互應(yīng)用,同時盡可能減少用戶的交互量,本文基于泊松融合框架,充分利用重構(gòu)幾何所用的拉普拉斯算子的性質(zhì),將幾何重建、旋轉(zhuǎn)場與尺度場的插值問題均轉(zhuǎn)化為拉普拉斯(泊松)方程的求解,實(shí)現(xiàn)網(wǎng)格的高效融合.異于傳統(tǒng)的局部變換(旋轉(zhuǎn)與伸縮變換)傳遞方法,即通過計(jì)算權(quán)重場對局部變換進(jìn)行局部線性混合插值,本文復(fù)用拉普拉斯算子將局部變換轉(zhuǎn)化成若干個標(biāo)量場進(jìn)行全局插值;求解時,由于所用拉普拉斯矩陣是固定的,僅需預(yù)分解一次、通過多次耗時較少的回代計(jì)算快速獲得8個標(biāo)量場.此外,在進(jìn)行網(wǎng)格融合時,用戶通常希望網(wǎng)格附帶的其他屬性也能隨之融合,因此本文針對帶紋理坐標(biāo)的模型,在幾何融合時考慮了紋理坐標(biāo)的融合,求解時亦通過復(fù)用拉普拉斯算子實(shí)現(xiàn)紋理坐標(biāo)的快速更新,從而避免了紋理坐標(biāo)的重計(jì)算.同時,本文還考慮了融合區(qū)域網(wǎng)格的優(yōu)化問題.本文有3個貢獻(xiàn)點(diǎn):(1) 提出了一種基于復(fù)用拉普拉斯算子的高效幾何融合方法;(2) 提出了一種基于復(fù)用拉普拉斯算子的高效紋理坐標(biāo)融合方法;(3) 提出了基于Delaunay三角化與離散極小曲面的魯棒局部網(wǎng)格優(yōu)化方法.

1 相關(guān)工作

網(wǎng)格融合作為組裝式建模的重要手段,在幾何建模與處理領(lǐng)域一直受到人們的關(guān)注,并出現(xiàn)了大量的研究工作.現(xiàn)有的網(wǎng)格融合方法大致分可為兩大類:構(gòu)造光滑邊界法與重建幾何法.

構(gòu)造光滑邊界法類似于補(bǔ)洞算法,即:在源網(wǎng)格和目標(biāo)網(wǎng)格之間構(gòu)造一個過渡曲面,將兩者光滑地連接起來.重點(diǎn)在于如何構(gòu)造該曲面,其代表方法有配準(zhǔn)法與構(gòu)造過渡曲面法.配準(zhǔn)法即將源網(wǎng)格與目標(biāo)網(wǎng)格在邊界處的重疊區(qū)域進(jìn)行非剛體變換實(shí)現(xiàn)拼接.Sharf等人[12]提出了Soft-ICP方法,在重疊區(qū)域迭代地進(jìn)行對應(yīng)點(diǎn)搜索與配準(zhǔn).Kreavoy等人[13]采用交互方法對融合區(qū)域進(jìn)行對齊,然后采用上述方法進(jìn)行融合.Zhu等人[14]構(gòu)造了一個公共邊界,使其到目標(biāo)網(wǎng)格和源網(wǎng)格的邊界的距離平方和最小化,并計(jì)算一個權(quán)重場對其進(jìn)行加權(quán)的拉普拉斯光順.Liu等人[15]采用類似生成掃成體的方法構(gòu)造過渡曲面.萬華根[6]采用徑向基函數(shù)構(gòu)造變分隱式曲面進(jìn)行插值,然后抽取等值面將其轉(zhuǎn)化成多邊形網(wǎng)格.Jin等人[7]結(jié)合徑向基函數(shù)與有向距離場構(gòu)造過渡隱式曲面.Lin等人[8]基于前述方法[6,7],采用勾畫式交互手段勾勒過渡曲面輪廓線,以控制插值曲面的形狀.繆永偉等人[16]則采用了Hermite插值曲面作為過渡曲面.總而言之,這類方法雖然能實(shí)現(xiàn)復(fù)雜模型的拼接與融合,但是由于構(gòu)造過渡曲面計(jì)算代價較大,通常難以滿足交互響應(yīng)的要求.

幾何重建法是根據(jù)源網(wǎng)格的幾何信息重建出在新邊界條件下的幾何形狀,并盡可能保持其幾何度量,代表方法又可細(xì)分為參數(shù)化法與變形法.

參數(shù)化法將源網(wǎng)格與目標(biāo)網(wǎng)格的融合區(qū)域參數(shù)化到一個共同區(qū)域,然后根據(jù)對應(yīng)頂點(diǎn)的重心坐標(biāo)插值重構(gòu)幾何.Kanai等人[17]在兩個網(wǎng)格的融合區(qū)域邊界進(jìn)行對齊,并運(yùn)用全局調(diào)和映射建立網(wǎng)格頂點(diǎn)的對應(yīng)關(guān)系,并通過融合控制函數(shù)調(diào)整形狀.Biermann等人[18]基于角度展平(ABF)參數(shù)化實(shí)現(xiàn)模型表面細(xì)節(jié)的遷移與融合,該方法被用于基于樣例的建模[2]與基于最小割的網(wǎng)格融合[19].劉剛等人[20]在此基礎(chǔ)上提出了基于局部調(diào)和映射的融合算法,利用等距線抽取待融合區(qū)域,更為簡單、快速.Fu等人[21]同樣基于該算法的思想,利用參數(shù)化編碼表面細(xì)節(jié),有效處理具有復(fù)雜拓?fù)涞木W(wǎng)格.但是參數(shù)化法對于具有復(fù)雜幾何細(xì)節(jié)的源模型易引起較大的形變誤差,從而導(dǎo)致重建效果不理想,且往往受到網(wǎng)格拓?fù)涞南拗贫贿m用于一般的網(wǎng)格.

變形法主要運(yùn)用基于微分域的變形技術(shù)[22]重建源網(wǎng)格.泊松融合法[9,23,24]通過構(gòu)造新的梯度場(一階微分量)使之逼近原幾何模型的梯度場,并求解泊松方程從新梯度場恢復(fù)其幾何;拉普拉斯變形法[25]則利用了二階微分量,通過擬合拉普拉斯坐標(biāo)重建幾何.兩者均為后續(xù)的變形與融合方法產(chǎn)生了重要的奠基作用.變形法所涉及的一個重要問題為局部變換(旋轉(zhuǎn)與伸縮)的傳遞,現(xiàn)有的方法往往通過構(gòu)造光滑的權(quán)重場并運(yùn)用該標(biāo)量場進(jìn)行線性混合將局部變換由邊界處傳遞至網(wǎng)格內(nèi)部.這種幾何域標(biāo)量場在幾何處理中有著廣泛的應(yīng)用[26,27],其計(jì)算方法也較為成熟[28].如泊松融合法[9,24]采用測地線計(jì)算標(biāo)量場,但極為耗時,使其難以滿足交互響應(yīng).Zayer等人[29]提出用調(diào)和場替換測地距離場,提高了變形的計(jì)算效率,但是該方法需指定源(固定)和目標(biāo)(編輯)頂點(diǎn)的邊界條件,而融合問題僅給出源頂點(diǎn)而無法確定目標(biāo)頂點(diǎn),因此難以直接采用.為避免局部變換傳遞的計(jì)算,不少研究者預(yù)先將源網(wǎng)格與目標(biāo)網(wǎng)格對齊,然后直接采用變形法進(jìn)行融合.Deng等人[11]與劉驪等人[4]則采用了中值坐標(biāo)求解泊松方程,改善了效率.Takayama等人[10]采用了兩步變形法:首先,根據(jù)融合邊界構(gòu)造籠子,并基于籠子變形法重構(gòu)源網(wǎng)格幾何,使之與目標(biāo)網(wǎng)格對齊;然后,用拉普拉斯變形法進(jìn)行邊界融合與細(xì)節(jié)恢復(fù),但其籠子變形法對于復(fù)雜的源網(wǎng)格易產(chǎn)生不理想的變形效果.Qian等人[30]在此基礎(chǔ)上提出了金字塔球面坐標(biāo),其魯棒性得到了改善.

本文方法基于泊松融合框架,因此具有傳統(tǒng)泊松融合法的優(yōu)點(diǎn),適用于邊界差異較大的網(wǎng)格,且交互方式便捷,僅需在源網(wǎng)格與目標(biāo)網(wǎng)格邊界指定稀疏的對應(yīng)點(diǎn)便能實(shí)現(xiàn)融合.本文利用全局拉普拉斯光順法并多次復(fù)用拉普拉斯矩陣,實(shí)現(xiàn)旋轉(zhuǎn)場、尺度場與幾何坐標(biāo)的高效計(jì)算,比起基于測地線的泊松融合法,避免了測地距離場的計(jì)算,提高了效率,使之適合于交互應(yīng)用;比起中值坐標(biāo)法,本文可自動調(diào)整模型的尺寸且拼接邊界處過渡更為自然.此外,在現(xiàn)有的網(wǎng)格融合方法中,通常僅考慮幾何坐標(biāo)的融合,而較少同時考慮網(wǎng)格的其他屬性的融合,如文獻(xiàn)[31]提出的紋理圖像的融合.據(jù)我們所知,在幾何融合時考慮紋理坐標(biāo)的融合的工作未曾見有報(bào)道.本文針對帶紋理的網(wǎng)格模型,再次復(fù)用拉普拉斯矩陣,用較小的時間代價生成合成模型的紋理坐標(biāo).

2 泊松融合算法框架

泊松網(wǎng)格融合[9,24]的思想是在新邊界約束下,用待重建模型的梯度算子擬合源網(wǎng)格模型的幾何梯度場.設(shè)源三角形網(wǎng)格Ω為二維流形且表示為〈V,F〉,其中,V={vi}為頂點(diǎn)集(i=1,2,…,|V|),T={ti}為三角形面片集(i=1,2,…,|F|).為每個頂點(diǎn)vi賦予一個標(biāo)量值f(vi)=fi,則網(wǎng)格Ω上定義了一個標(biāo)量場,其上任意點(diǎn)v處的標(biāo)量值為

其中,φi(?)為分段線性基函數(shù).若將該標(biāo)量函數(shù)定義為三維幾何坐標(biāo)x,y,z這3個分量,則泊松融合問題可描述為在邊界約束下的向量場擬合問題:

其中,At是三角形t的面積,ft是待求網(wǎng)格面片t上的三個標(biāo)量場,gt為目標(biāo)梯度場.由于源網(wǎng)格與目標(biāo)網(wǎng)格通常處于不同的局部坐標(biāo)系,兩個模型在擺放方向與尺寸上存在差異,因此,其對應(yīng)的目標(biāo)梯度場需要進(jìn)行校正.在實(shí)際應(yīng)用中,需將源模型三角形t上的梯度經(jīng)過局部伸縮變換st與旋轉(zhuǎn)變換Rt(根據(jù)兩個網(wǎng)格的邊界信息進(jìn)行估計(jì))使其位于目標(biāo)網(wǎng)格坐標(biāo)系下.

上述優(yōu)化問題(公式(1))可通過對梯度場進(jìn)行積分轉(zhuǎn)化成泊松方程進(jìn)行求解,進(jìn)而重構(gòu)出幾何坐標(biāo):

其中,Δ是拉普拉斯算子,div為散度算子.由于f是分段線性函數(shù)、頂點(diǎn)i的拉普拉斯算子通常離散化為幾何敏感的余切算子[32]:

其中,j遍歷頂點(diǎn)i的1-環(huán)鄰域頂點(diǎn),αij與βij是網(wǎng)格邊〈i,j〉的對角,ui,uj分別為頂點(diǎn)i與頂點(diǎn)j的標(biāo)量值,L為拉普拉斯矩陣,u為網(wǎng)格頂點(diǎn)坐標(biāo)分量形成的向量.若將邊界頂點(diǎn)的位置約束轉(zhuǎn)化為軟約束,則泊松方程可離散化為對稱正定的稀疏線性方程組:

其中,Lc=AL+λC.

·A為網(wǎng)格頂點(diǎn)的Voronoi面積構(gòu)成的對角陣,其對角元表示為頂點(diǎn)1-環(huán)鄰域三角形面積總和的三分之一:(j遍歷頂點(diǎn)i的鄰接三角形);

·C為位置約束的對角系數(shù)矩陣;

·λ為軟約束權(quán)重,默認(rèn)取作108.

綜上,泊松融合算法的步驟可描述如下.

步驟1:設(shè)置源網(wǎng)格模型與目標(biāo)網(wǎng)格模型邊界頂點(diǎn)的對應(yīng)關(guān)系;

步驟2:根據(jù)源網(wǎng)格與對應(yīng)目標(biāo)網(wǎng)格邊界頂點(diǎn)信息計(jì)算局部變換——旋轉(zhuǎn)變換與縮放尺度;

步驟3:計(jì)算源網(wǎng)格融合邊界頂點(diǎn)到其他頂點(diǎn)的測地距離,并由此構(gòu)造權(quán)函數(shù)標(biāo)量場,根據(jù)該標(biāo)量場,運(yùn)用線性混合法插值出新邊界下源網(wǎng)格上的旋轉(zhuǎn)場與尺度場;

步驟4:根據(jù)步驟3得到的局部變換場計(jì)算新梯度場,運(yùn)用泊松方程對該梯度場進(jìn)行積分(公式(4)),并求解該泊松方程獲得源網(wǎng)格模型在新邊界約束下的幾何坐標(biāo).

3 基于可復(fù)用拉普拉斯算子的融合

泊松融合的核心是求解泊松方程,其系數(shù)矩陣為拉普拉斯矩陣.拉普拉斯算子被稱為幾何處理的“瑞士軍刀”[33],在幾何處理領(lǐng)域有著廣泛的應(yīng)用背景,例如網(wǎng)格變形[9]、參數(shù)化[32]、光順[27]、距離場計(jì)算[28,29]、形狀分析[33]等.本文基于上述傳統(tǒng)的泊松融合算法,充分利用拉普拉斯算子的優(yōu)良性質(zhì),將融合中的若干問題,如幾何重建、旋轉(zhuǎn)場與尺度場的光滑插值、紋理坐標(biāo)融合等,均采用拉普拉斯算子進(jìn)行建模,使其多個計(jì)算步驟均可復(fù)用同一個拉普拉斯算子,從而減少計(jì)算時間,使其適合交互應(yīng)用.

3.1 旋轉(zhuǎn)場與尺度場的插值

融合算法步驟中,最為耗時的是步驟3,即旋轉(zhuǎn)場與尺度場的插值.在計(jì)算旋轉(zhuǎn)場時,由于旋轉(zhuǎn)矩陣對加法運(yùn)算不封閉,不能直接用于插值計(jì)算,因此往往需轉(zhuǎn)化成四元素q=〈qx,qy,qz,qw〉,并在四元素空間進(jìn)行插值.為得到光滑的旋轉(zhuǎn)場與尺度場,文獻(xiàn)[9]采用了線性加權(quán)法,即非邊界頂點(diǎn)處的四元素qi與尺度值si表示為邊界頂點(diǎn)處對應(yīng)值的線性組合:

其中,ωij可取關(guān)于頂點(diǎn)i到j(luò)的測地距離的單調(diào)遞減函數(shù),通?？扇〉箶?shù)函數(shù)、高斯函數(shù)等.由此可見:為計(jì)算整個源網(wǎng)格域上的標(biāo)量場,共需計(jì)算對測地線距離(VB為融合邊界頂點(diǎn)集).因此,該方法不僅需借助一個大型稠密矩陣進(jìn)行存儲而耗費(fèi)內(nèi)存空間,而且由于測地線的計(jì)算非常耗時,限制了其交互應(yīng)用.

局部變換場,尤其是旋轉(zhuǎn)變換場的插值,是常用變形算法的一個重要環(huán)節(jié).文獻(xiàn)[29]在變形時,利用拉普拉斯算子的光滑性質(zhì),采用調(diào)和場作為權(quán)重場傳遞局部變換:構(gòu)建一個拉普拉斯方程Δu=0,并由用戶指定其邊界條件,其中,在固定頂點(diǎn)處設(shè)置為0,在變形的編輯頂點(diǎn)處設(shè)置為1,則任意頂點(diǎn)處的變換可表示為固定頂點(diǎn)標(biāo)量場與編輯頂點(diǎn)標(biāo)量場的線性混合.該方法僅需求解一個線性系統(tǒng),比起基于測地線的局部變換傳遞方法顯著地減少了計(jì)算量.但該方法僅適合一般的變形應(yīng)用,對于網(wǎng)格融合應(yīng)用,由于沒有約束頂點(diǎn)與可編輯頂點(diǎn)之區(qū)分,難以指定其邊界條件,因而不能用于構(gòu)造光滑的權(quán)重場.

異于上述根據(jù)邊界標(biāo)量場進(jìn)行線性混合的思路[9,29],本文受到拉普拉斯光順?biāo)惴ǖ膯l(fā)[27],將局部變換場轉(zhuǎn)化成5個標(biāo)量場(四元素標(biāo)量場qx,qy,qz,qw與一個尺度標(biāo)量場s),并采用全局拉普拉斯光順法對其進(jìn)行平滑插值.即在新的邊界約束下構(gòu)造使得定義域上的標(biāo)量場變化的能量和達(dá)到極小值的能量函數(shù):

其中,約束條件為狄利克雷邊界條件.因此,該問題的極小值可轉(zhuǎn)化為拉普拉斯方程的解:

由公式(7)可見其形式與公式(2)相似,它們均可轉(zhuǎn)化成公式(4)進(jìn)行求解.由于標(biāo)量場與幾何坐標(biāo)共享一個網(wǎng)格域,該方程的系數(shù)矩陣——拉普拉斯矩陣完全相同,并且它們的約束頂點(diǎn)相同,因此在求解時可重復(fù)利用這些信息.

求解公式(4)的對稱正定方程可采用Cholesky分解法,即:將矩陣分解為一個下三角矩陣及其轉(zhuǎn)置的乘積,即Lc=AAt(A為下三角矩陣),然后利用其三角陣特點(diǎn)進(jìn)行快速回代計(jì)算,即:分別求解方程AY=b,Au=Y,得到方程最終的解u.對于線性求解器而言,它一般可分為3個步驟:結(jié)構(gòu)分解、數(shù)值分解與回代.其中,結(jié)構(gòu)分解與數(shù)值分解耗時相對最多,而回代計(jì)算耗時較少.利用該特點(diǎn),本文多次復(fù)用拉普拉斯矩陣分解的結(jié)果,以加速計(jì)算上述8個標(biāo)量場(3個位置分量場、4個四元素分量場與1個尺度場):對拉普拉斯矩陣進(jìn)行一次結(jié)構(gòu)分解與數(shù)值分解,然后執(zhí)行8次回代計(jì)算.因此,比起基于測地線的標(biāo)量場插值法,該方法通過復(fù)用拉普拉斯矩陣,避免了測地線的計(jì)算,不僅減少了計(jì)算量,也節(jié)省了存儲距離場的空間.

3.2 紋理坐標(biāo)的融合

對帶紋理坐標(biāo)的模型進(jìn)行幾何融合,往往希望融合結(jié)果的紋理坐標(biāo)得到保持.但是若僅融合幾何坐標(biāo),而簡單地將源模型的紋理坐標(biāo)“拷貝”至目標(biāo)模型,則無法保持紋理坐標(biāo)的連續(xù)性;若對合成模型重新計(jì)算紋理坐標(biāo),則不僅計(jì)算代價太大,而且將改變目標(biāo)模型上原有的紋理坐標(biāo),這在某些場合是不允許的.為此,本文在考慮幾何融合的同時,再次復(fù)用拉普拉斯算子實(shí)現(xiàn)紋理坐標(biāo)的融合,以快速地更新源網(wǎng)格的紋理坐標(biāo),使之能夠保持目標(biāo)網(wǎng)格的紋理坐標(biāo)并保證其連續(xù)性.

紋理坐標(biāo)可通過計(jì)算網(wǎng)格參數(shù)化得到.參數(shù)化通常轉(zhuǎn)化為極小化某種幾何度量問題.這種幾何度量可以是角度、面積、長度誤差等,它們均與幾何敏感的拉普拉斯存在著密切的關(guān)系.本文采用調(diào)和參數(shù)化,即求解如下拉普拉斯方程的解:

其中:Δ同公式(2)與公式(7)所定義的拉普拉斯算子;u為頂點(diǎn)紋理坐標(biāo)構(gòu)成的矩陣,其大小為|V|×2.為保證紋理坐標(biāo)的連續(xù)性,該拉普拉斯方程的邊界條件設(shè)置為源網(wǎng)格的融合邊界對應(yīng)目標(biāo)網(wǎng)格上頂點(diǎn)處的紋理坐標(biāo)值.因此,該方程的系數(shù)矩陣與約束頂點(diǎn)均與公式(2)與公式(7)一致,從而無需重新構(gòu)造、分解該系數(shù)矩陣,可利用前述拉普拉斯矩陣的分解結(jié)果,僅需兩次回代計(jì)算,便可得到紋理坐標(biāo).

3.3 融合邊界的網(wǎng)格處理

利用泊松融合框架對兩個模型進(jìn)行融合,其前提是融合邊界的網(wǎng)格頂點(diǎn)存在一一對應(yīng)關(guān)系,且融合后模型的拓?fù)涫嵌S流形.文獻(xiàn)[9]給出了3種對應(yīng)策略:投影法、參數(shù)化法與稀疏對應(yīng)與插值法,并且指出第3種方法最為有效.但這種對應(yīng)方法將使融合邊界區(qū)域的網(wǎng)格質(zhì)量變差,可能為后續(xù)的幾何處理帶來數(shù)值問題.為此,本文基于第3種方法的思想建立邊界頂點(diǎn)對應(yīng)關(guān)系,并給出了一種基于平面Delaunay三角化與離散極小曲面的網(wǎng)格優(yōu)化方法,以改善融合邊界處的網(wǎng)格質(zhì)量.

3.3.1 融合邊界頂點(diǎn)的對應(yīng)

源網(wǎng)格與目標(biāo)網(wǎng)格的融合邊界均為一個封閉的空間曲線.為建立兩個邊界的對應(yīng)關(guān)系,需由用戶指定幾個稀疏的對應(yīng)頂點(diǎn)(這是本算法唯一需要用戶交互的環(huán)節(jié));并對每相鄰兩個指定頂點(diǎn)之間的曲線段,利用弦長參數(shù)化方法建立對應(yīng)關(guān)系.具體地,

· 首先,將兩個曲線段弦長參數(shù)化到單位長度線段上;

· 然后,分別對其中一條線段的每一個頂點(diǎn),根據(jù)等距關(guān)系在另一條線段上找到對應(yīng)點(diǎn):若該頂點(diǎn)靠近該線段上已有的頂點(diǎn),則將該頂點(diǎn)作為對應(yīng)點(diǎn);否則,對該點(diǎn)所在的邊進(jìn)行細(xì)分,將所生成的頂點(diǎn)作為對應(yīng)點(diǎn).

圖1示意了該算法的思想,其中,S與T分別表示源網(wǎng)格與目標(biāo)網(wǎng)格邊界對應(yīng)的單位長度參數(shù)域,實(shí)線分別表示邊界,虛線表示對應(yīng)關(guān)系,實(shí)心方框表示原邊界上的頂點(diǎn),空心方框表示插入的頂點(diǎn).

Fig.1 Illustration of the correspondence of merging boundary vertices圖1 融合邊界網(wǎng)格頂點(diǎn)對應(yīng)關(guān)系示意圖

3.3.2 融合邊界區(qū)域網(wǎng)格的優(yōu)化

上述對應(yīng)方法易使網(wǎng)格融合邊界區(qū)域產(chǎn)生狹長或接近退化的三角形(如圖2(a)所示),可能對后續(xù)的幾何處理帶來數(shù)值問題.為此,本文在進(jìn)行網(wǎng)格融合后,對該區(qū)域進(jìn)行局部網(wǎng)格優(yōu)化.

Fig.2 Comparison of the mesh before and after local mesh optimization圖2 融合邊界區(qū)域局部網(wǎng)格優(yōu)化前后對比

為使融合邊界處的網(wǎng)格既能得到網(wǎng)格質(zhì)量的優(yōu)化,又盡可能少地改變原兩個網(wǎng)格的幾何與拓?fù)?限定其優(yōu)化區(qū)域?yàn)榘l(fā)生拓?fù)渥兓倪B通區(qū)域,亦即融合邊界頂點(diǎn)的1-環(huán)鄰域三角形所構(gòu)成的帶狀區(qū)域.為此,問題轉(zhuǎn)化成帶邊界約束的網(wǎng)格優(yōu)化.現(xiàn)成的網(wǎng)格優(yōu)化的工具很多,例如經(jīng)典的各項(xiàng)同性重網(wǎng)格化[34],但該方法對于狹長區(qū)域易產(chǎn)生自交.為此,本文給出了一種魯棒的局部網(wǎng)格優(yōu)化算法.其思想是:利用帶狀區(qū)域類柱形拓?fù)涮匦?沿著連接柱形邊界的網(wǎng)格邊將其剪開成與拓?fù)浔P同胚的開曲面,并利用弦長參數(shù)化方法將該曲面的邊界映射到一個平面矩形;然后,運(yùn)用成熟的帶約束Delaunay三角化算法(借助Triangle庫[35])對該區(qū)域進(jìn)行三角剖分(如圖2(b)所示),該算法根據(jù)邊界頂點(diǎn)的密度自適應(yīng)地插入適當(dāng)數(shù)量的頂點(diǎn)并進(jìn)行三角化;最后,在原融合網(wǎng)格的邊界約束下,由拉普拉斯方程構(gòu)造極小曲面(如圖2(c)所示):

其中,Δ為拉普拉斯矩陣;X為待求網(wǎng)格頂點(diǎn)的三維坐標(biāo)構(gòu)成的矩陣,其大小為|V|×3.

在離散化求解公式(9)時,本文不采用幾何敏感的余切拉普拉斯,而使用拓?fù)淅绽?即,將公式(3)中的權(quán)重設(shè)置為均一權(quán)重.由于拓?fù)淅绽古c模型的幾何無關(guān),這將帶來兩項(xiàng)益處:不僅能更大程度上減少發(fā)生自交的概率,而且能使網(wǎng)格分布更趨于各項(xiàng)同性,從而提高網(wǎng)格質(zhì)量.由于公式(9)所構(gòu)造的拉普拉斯矩陣僅針對狹長的局部區(qū)域,其規(guī)模較小,因此可快速求得結(jié)果.

為使所構(gòu)造的矩形區(qū)域的形狀和大小盡可能接近原網(wǎng)格區(qū)域,本文采用保面積的思想,分別取該矩形的寬w和高h(yuǎn)如下:

其中,ls,lt分別是源網(wǎng)格與目標(biāo)網(wǎng)格融合邊界的長度,A為帶狀區(qū)域的面積,即區(qū)域內(nèi)所有三角形面積之和.圖2為一個花瓶模型的融合邊界處進(jìn)行局部網(wǎng)格優(yōu)化前后的對比結(jié)果.圖2(a)為優(yōu)化前的網(wǎng)格,圖2(b)為將網(wǎng)格邊界參數(shù)化到一個矩形區(qū)域并進(jìn)行約束Delaunay三角化得到的平面網(wǎng)格,圖2(c)為優(yōu)化后的網(wǎng)格.經(jīng)過本文算法優(yōu)化不僅改善了局部區(qū)域的網(wǎng)格質(zhì)量,網(wǎng)格頂點(diǎn)密度分布自然,而且還起到一定的光順作用.

圖3是圖2所示例子的完整結(jié)果圖,其中,圖3(a)為源網(wǎng)格(下邊界線)與目標(biāo)網(wǎng)格(上邊界線),圖中所示為其實(shí)際朝向與大小(下同);圖 3(b)與圖 3(c)分別為經(jīng)過與未經(jīng)局部網(wǎng)格優(yōu)化的融合結(jié)果,其網(wǎng)格規(guī)模為1051/2070/54/84,3209/6359/27/84,分別表示源網(wǎng)格與目標(biāo)網(wǎng)格的頂點(diǎn)數(shù)、面片數(shù)、邊界對應(yīng)前的邊界頂點(diǎn)數(shù)與邊界對應(yīng)后的邊界頂點(diǎn)數(shù)(下同).可見:經(jīng)過網(wǎng)格優(yōu)化后,網(wǎng)格單元的質(zhì)量得到了顯著改善,并且融合邊界處曲面過渡更為自然.

Fig.3 Results of the vase model 1 before and after merging圖3 花瓶1模型融合前后的結(jié)果

融合邊界處經(jīng)過網(wǎng)格優(yōu)化后,該區(qū)域的紋理坐標(biāo)隨之失效.為快速恢復(fù)其紋理坐標(biāo),本文利用第3.2節(jié)所述方法建立調(diào)和映射.由于建立調(diào)和映射的網(wǎng)格域拓?fù)湮窗l(fā)生變化,其矩陣結(jié)構(gòu)與公式(9)相同,因此可對該式的拉普拉斯算子進(jìn)行復(fù)用,即省卻了矩陣的結(jié)構(gòu)分解步驟,而僅對其進(jìn)行數(shù)值分解與回代計(jì)算即可.

4 實(shí)驗(yàn)與討論

本文算法在硬件環(huán)境為Inter(R) 4 Core(TM)i5-4590 3.30GHz CPU以及8G內(nèi)存的PC機(jī),軟件環(huán)境為Windows 7操作系統(tǒng),開發(fā)工具為Visual C++2017,矩陣相關(guān)運(yùn)算采用Eigen庫[36],其中,算法涉及的所有線性方程組的求解均采用其提供的Cholesky分解接口:Eigen::SimplicalLLT〈〉.

為考察融合邊界對結(jié)果的影響,本文對鯨魚模型進(jìn)行切割、擾動后再進(jìn)行融合,得到圖4結(jié)果.

· 圖4(a)上圖為原鯨魚模型;

· 圖4(b)上圖為分割后的模型,將頭部和尾部分別作為源網(wǎng)格與目標(biāo)網(wǎng)格,其規(guī)模為6949/13824/72/72,3177/6280/72/72;

· 圖4(b)下圖為擾動后的模型,即:對源網(wǎng)格施加旋轉(zhuǎn)縮放變換后,并對源網(wǎng)格和目標(biāo)網(wǎng)格的邊界頂點(diǎn)沿著切向進(jìn)行隨機(jī)干擾,擾動公式為v=v0+t?rand(?1,1)e/5.其中:v0為原頂點(diǎn)坐標(biāo);t為該頂點(diǎn)單位切向;e為網(wǎng)格邊平均長度;rand(?1,1)為隨機(jī)函數(shù),生成[?1,1]之間的隨機(jī)數(shù);

· 圖4(a)下圖為經(jīng)本文算法融合后得到的結(jié)果.由圖可見:本文算法能自動調(diào)整模型的尺寸與方向,且對融合邊界形狀敏感度較小,不僅能較好地保持原模型形狀,而且在融合邊界處保持一定的光滑度.

Fig.4 Merging result for a model with boundary perturbation圖4 對模型進(jìn)行切割擾動后再進(jìn)行融合的結(jié)果

本文算法能夠適用于邊界頂點(diǎn)密度、形狀差異較大模型的融合.本文將圖3的目標(biāo)網(wǎng)格作為源網(wǎng)格,與一個具有方形邊界且網(wǎng)格密度較大的目標(biāo)網(wǎng)格(規(guī)模為18953/37720/184/240)進(jìn)行融合,并得到圖5(b)的結(jié)果.由結(jié)果可見:雖然兩者在尺寸、密度和形狀上具有很大差異,但本文算法能夠自適應(yīng)計(jì)算源網(wǎng)格的尺寸場,使之與目標(biāo)網(wǎng)格相吻合,并且其融合結(jié)果依然較好地保持原模型的整體形狀.

Fig.5 Merging result of vase model 2圖5 花瓶2的融合結(jié)果

本文算法能夠?qū)哂袕?fù)雜拓?fù)涞哪Ｐ瓦M(jìn)行融合.圖6分別給出了一個帶柄環(huán)與一個帶兩個邊界的源網(wǎng)格的融合例子.圖6(a)將帶橢圓形邊界與柄環(huán)的模型作為源網(wǎng)格(規(guī)模為1638/3716/102/131),把圖3中帶圓形邊界的源網(wǎng)格作為目標(biāo)網(wǎng)格進(jìn)行融合,得到圖6(b)的結(jié)果.由圖可見:其融合邊界處形狀過渡自然,由于邊界形狀由圓形變?yōu)闄E圓,其重建網(wǎng)格也被適當(dāng)拉伸,但其整體形狀亦然保持較好.圖6(c)將帶雙邊界的模型與一個平面網(wǎng)格(規(guī)模為958/1782/134/237,1845/3394/106/237)進(jìn)行融合,得到圖6(d)的結(jié)果.與單個邊界類似,該情況將狄利克雷邊界條件施加在所有邊界的頂點(diǎn)上進(jìn)行求解.圖中可見:本文算法能實(shí)現(xiàn)多邊界的融合效果,雖然邊界差異巨大,導(dǎo)致重建模型的邊界處形變拉伸很大,但其整體形狀獲得了一定程度的保持.

Fig.6 Merging results for models with handles and multi-boundaries圖6 帶柄環(huán)與多邊界的模型融合

本文算法用較小的時間代價實(shí)現(xiàn)了旋轉(zhuǎn)場與尺度場的插值,但其融合結(jié)果能與傳統(tǒng)的基于測地線的泊松方法相媲美.圖7給出了將男人上半身融合到馬身的例子(圖7(a)為源網(wǎng)格與目標(biāo)網(wǎng)格,圖7(b)為本文算法得到的結(jié)果,圖7(c)為基于測地線的算法得到的結(jié)果,圖7(d)為將圖7(b)模型(人身)和圖7(c)模型(馬身)置于同一坐標(biāo)系下的結(jié)果,網(wǎng)格規(guī)模為24997/49960/32/105,15654/31227/79/105).由圖可見:在視覺上,兩種方法得到的結(jié)果雖然在大小和朝向上存在一定的差異,但是其形狀均能被較好地保持.

Fig.7 Comparison results of our method and geodesic-based Poisson method[9]圖7 本文方法與傳統(tǒng)泊松融合方法[9]的比較結(jié)果

與基于中值坐標(biāo)的融合方法[4,11]比較,本文方法更為靈活、融合效果更好.本文將小孩頭模型作為源網(wǎng)格(規(guī)模為28513/56905/81/119),把圖7中的人身作為目標(biāo)網(wǎng)格(圖8(a)),分別采用本文方法與基于中值坐標(biāo)的方法進(jìn)行融合,得到的結(jié)果如圖8(b)、圖8(c)所示,其運(yùn)行時間分別為225ms與127ms.雖然后者比本文方法快近一倍,但是本文方法能夠根據(jù)邊界差異自動調(diào)整源網(wǎng)格尺寸,而后者無法實(shí)現(xiàn);并且本文方法在融合邊界處幾何過渡更為自然,效果更好.

Fig.8 Comparison results with our method and MVC-based method[11]圖8 本文方法與基于中值坐標(biāo)融合方法的比較結(jié)果

本文提出的局部網(wǎng)格優(yōu)化方法能夠適應(yīng)頂點(diǎn)密度差異較大的邊界約束.如圖9所示(圖9(a)為源網(wǎng)格與目標(biāo)網(wǎng)格;圖9(b)與圖9(d)為融合結(jié)果的不同渲染效果;圖9(c)為局部網(wǎng)格放大圖,其中,上下兩圖分別為經(jīng)過網(wǎng)格優(yōu)化前后的結(jié)果.網(wǎng)格規(guī)模為8003/15886/118/134,4285/8668/17/134).將網(wǎng)格密度較大的兔子耳朵與密度較小的牛頭進(jìn)行融合(如圖9(a)所示),得到結(jié)果圖9(b)～圖9(d).從圖9(c)的局部網(wǎng)格放大圖可見:經(jīng)過本文算法的優(yōu)化,網(wǎng)格質(zhì)量得到了明顯改善,且頂點(diǎn)密度的分布能從高密度向低密度區(qū)域平緩過渡.該特點(diǎn)得益于Triangle[35]強(qiáng)大的三角化功能.

Fig.9 Result of merging rabbit ears with cattle model圖9 兔耳與牛的融合結(jié)果

我們在各種不同模型上進(jìn)行了大量測試,發(fā)現(xiàn)本文算法均能較好地實(shí)現(xiàn)高效融合.圖10給出了更多融合的例子(圖10(a)飛機(jī)(1829/3616/40/68,4515/8806/30/68),圖10(b)狗(803/1552/52/77,7983/15884/26/77),圖10(c)駱駝(11373/22695/56/91,3408/6773/41/91),圖10(d)龍(21595/43030/158/191,15138/30153/121/191)).這些例子均進(jìn)一步驗(yàn)證了本文算法所具有的上述優(yōu)點(diǎn).

Fig.10 More merging results of various models圖10 其他模型的融合結(jié)果

為定量地比較本算法與基于測地線的泊松融合算法的重建誤差,借鑒網(wǎng)格參數(shù)化中形變誤差的度量方法,本文采用了共形(角度)形變誤差[37]進(jìn)行度量.即:將原網(wǎng)格與重建網(wǎng)格的每個三角形平攤到平面,并計(jì)算平攤后原網(wǎng)格三角形到重建網(wǎng)格三角形之間的仿射變換的兩個奇異值σ1和σ2,則該變換的共形形變誤差可表示為σ1/σ2+σ2/σ1.基于該形變誤差度量,本文比較了兩種算法的3種度量誤差.

表1列出了本實(shí)驗(yàn)所用例子的3種誤差比較結(jié)果.其中,第2列～第4列斜杠前與斜杠后的數(shù)據(jù)分別表示本文算法與基于測地線算法[9]的3種形變誤差,即最大誤差、最小誤差與平均誤差.由表可見,本文算法與傳統(tǒng)泊松融合算法形變誤差非常接近,且在多數(shù)情況下,本文算法得到的結(jié)果具有更小的形變誤差.

此外,為展示本文紋理坐標(biāo)融合算法的結(jié)果,本文在圖11中給出了未經(jīng)局部網(wǎng)格優(yōu)化與經(jīng)過局部網(wǎng)格優(yōu)化后的融合結(jié)果(圖11(a)為源網(wǎng)格與目標(biāo)網(wǎng)格,圖11(b)與圖11(d)分別為未經(jīng)網(wǎng)格優(yōu)化的融合模型及其紋理圖,圖11(c)與圖11(e)分別為經(jīng)過網(wǎng)格優(yōu)化后的融合模型及其紋理圖,網(wǎng)格規(guī)模為3233/6400/41/107,19826/38492/63/107).由圖中汽車外殼的融合邊緣處可見:本文雖然在其邊界處僅考慮了零階連續(xù)性(狄利克雷)條件,但其紋理坐標(biāo)的尺寸和方向過渡自然,猶如施加了一階連續(xù)性條件(圖12亦然).這一現(xiàn)象表明,在紋理空間“挖洞”并進(jìn)行保持位置約束的“填充”后,盡管其填充曲面形狀發(fā)生了變化,但是其紋理的方向依然能獲得較好的保持.同時,本文在進(jìn)行局部網(wǎng)格優(yōu)化后更新了紋理坐標(biāo),其結(jié)果與未更新前幾乎沒有差異(如圖11(d)和圖11(e)).該現(xiàn)象一方面體現(xiàn)了余切拉普拉斯幾何敏感的特性(與網(wǎng)格無關(guān)),另一方面也說明了本文紋理坐標(biāo)融合方法的有效性.

另一方面,為考察紋理融合算法的魯棒性,本文將具有不同形狀、不同融合邊界的鼻子“嫁接”到帶紋理坐標(biāo)的人臉模型上,得到圖12所示的融合結(jié)果(圖12(a)為目標(biāo)網(wǎng)格,圖12(b)～圖12(d)為不同形狀的源網(wǎng)格,圖12(e)～圖12(g)為對應(yīng)的紋理融合結(jié)果).由圖可見,本文算法能同時較好地實(shí)現(xiàn)幾何融合與紋理坐標(biāo)融合,合成模型的幾何與紋理坐標(biāo)均能在融合邊界處光滑過渡,并較好地保持源網(wǎng)格的形狀.

比起傳統(tǒng)的基于測地線的泊松融合算法,本文算法不僅能夠獲得相似的融合結(jié)果,而且在效率上有顯著的提升.本文將算法分為3個部分:邊界對應(yīng)、幾何重建與網(wǎng)格優(yōu)化,分別測試了各個部分的運(yùn)行時間.其中,幾何重建中,旋轉(zhuǎn)場與尺度場的插值是原算法最為耗時的環(huán)節(jié),本文分別比較了兩者所耗時間.在比較實(shí)驗(yàn)中,本文采用了基于熱核的高效測地線算法[38].表2列出了上述實(shí)驗(yàn)例子的運(yùn)行時間,其中,R/S場表示旋轉(zhuǎn)場與尺度場的計(jì)算,第3列、第4列斜杠前與斜杠后的數(shù)據(jù)分別表示本文算法與基于測地線算法[9]所耗時間.由表中可見,本文算法在邊界對應(yīng)與網(wǎng)格優(yōu)化均耗費(fèi)較少的時間.這是由于算法處理的是局部網(wǎng)格,計(jì)算代價較小.從表中第3列和第4列的比較結(jié)果可看出:本文的算法在計(jì)算旋轉(zhuǎn)與尺度場時僅需若干毫秒甚至低于1ms,比起基于測地線的算法快2個數(shù)量級以上;相應(yīng)地,其幾何重建部分得到了較大的加速.因此,本文算法使泊松融合的交互應(yīng)用成為現(xiàn)實(shí).

Table 2 Running time of the two merging algorithms on different models (ms)表2 兩種融合算法在不同模型上的運(yùn)行時間 (毫秒)

5 總結(jié)與展望

本文利用拉普拉斯算子的優(yōu)良性質(zhì),將網(wǎng)格融合中幾何、旋轉(zhuǎn)場、尺度場、紋理坐標(biāo)的計(jì)算統(tǒng)一運(yùn)用該算子進(jìn)行建模,使之在計(jì)算中得到多次復(fù)用,從而提高了計(jì)算效率.比起傳統(tǒng)的泊松融合方法,本文方法不僅能獲得相媲美的實(shí)驗(yàn)結(jié)果,能夠?qū)崿F(xiàn)紋理坐標(biāo)的快速融合,而且在效率上大為提升,達(dá)到交互響應(yīng)速度.此外,本文提出了針對融合算法的魯棒高效的局部網(wǎng)格優(yōu)化方法,能夠有效地改善融合邊界區(qū)域的網(wǎng)格質(zhì)量,可為高質(zhì)量組裝式建模應(yīng)用提供高效方法[39].

本文提出的紋理坐標(biāo)融合方法采用了單片全局參數(shù)化,對于融合邊界有割縫或者源模型具有復(fù)雜拓?fù)涞那樾伪悴辉龠m用.今后,我們將考慮基于多片全局參數(shù)化的紋理融合,引入切割線處理復(fù)雜拓?fù)?并在切割線處考慮連續(xù)性約束,以拓展該算法的應(yīng)用范圍.由于多片全局參數(shù)化最終亦可轉(zhuǎn)化為泊松方程,因此我們將研究如何在該情況下復(fù)用拉普拉斯矩陣以提高效率.同時,我們也將考慮定義在網(wǎng)格上的其他標(biāo)量場的融合問題.

致謝本文實(shí)驗(yàn)所用的部分模型來自模型庫AIM@Shape以及國防科技大學(xué)徐凱博士的個人主頁(http://kevinkaixu.net/projects/civil.html),在此表示感謝.