復用拉普拉斯算子的高效網(wǎng)格融合方法?

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

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

2(深圳信息職業(yè)技術學院 機電工程學院,廣東 深圳 518172)

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 泊松融合算法框架

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

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

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

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

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

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

其中,Lc=AL+λC.

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

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

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

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

步驟1:設置源網(wǎng)格模型與目標網(wǎng)格模型邊界頂點的對應關系;

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

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

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

3 基于可復用拉普拉斯算子的融合

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

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

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

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

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

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

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

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

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

3.2 紋理坐標的融合

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

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

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

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

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

3.3.1 融合邊界頂點的對應

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

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

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

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

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

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

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

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

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

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

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

圖3是圖2所示例子的完整結(jié)果圖,其中,圖3(a)為源網(wǎng)格(下邊界線)與目標網(wǎng)格(上邊界線),圖中所示為其實際朝向與大小(下同);圖 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)格與目標網(wǎng)格的頂點數(shù)、面片數(shù)、邊界對應前的邊界頂點數(shù)與邊界對應后的邊界頂點數(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ū)域的紋理坐標隨之失效.為快速恢復其紋理坐標,本文利用第3.2節(jié)所述方法建立調(diào)和映射.由于建立調(diào)和映射的網(wǎng)格域拓撲未發(fā)生變化,其矩陣結(jié)構(gòu)與公式(9)相同,因此可對該式的拉普拉斯算子進行復用,即省卻了矩陣的結(jié)構(gòu)分解步驟,而僅對其進行數(shù)值分解與回代計算即可.

4 實驗與討論

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

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

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

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

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

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

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

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

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

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

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

本文算法用較小的時間代價實現(xiàn)了旋轉(zhuǎn)場與尺度場的插值,但其融合結(jié)果能與傳統(tǒng)的基于測地線的泊松方法相媲美.圖7給出了將男人上半身融合到馬身的例子(圖7(a)為源網(wǎng)格與目標網(wǎng)格,圖7(b)為本文算法得到的結(jié)果,圖7(c)為基于測地線的算法得到的結(jié)果,圖7(d)為將圖7(b)模型(人身)和圖7(c)模型(馬身)置于同一坐標系下的結(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é)果

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

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

本文提出的局部網(wǎng)格優(yōu)化方法能夠適應頂點密度差異較大的邊界約束.如圖9所示(圖9(a)為源網(wǎng)格與目標網(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)格密度較大的兔子耳朵與密度較小的牛頭進行融合(如圖9(a)所示),得到結(jié)果圖9(b)～圖9(d).從圖9(c)的局部網(wǎng)格放大圖可見:經(jīng)過本文算法的優(yōu)化,網(wǎng)格質(zhì)量得到了明顯改善,且頂點密度的分布能從高密度向低密度區(qū)域平緩過渡.該特點得益于Triangle[35]強大的三角化功能.

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

我們在各種不同模型上進行了大量測試,發(fā)現(xiàn)本文算法均能較好地實現(xiàn)高效融合.圖10給出了更多融合的例子(圖10(a)飛機(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)).這些例子均進一步驗證了本文算法所具有的上述優(yōu)點.

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

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

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

此外,為展示本文紋理坐標融合算法的結(jié)果,本文在圖11中給出了未經(jīng)局部網(wǎng)格優(yōu)化與經(jīng)過局部網(wǎng)格優(yōu)化后的融合結(jié)果(圖11(a)為源網(wǎng)格與目標網(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ù)性(狄利克雷)條件,但其紋理坐標的尺寸和方向過渡自然,猶如施加了一階連續(xù)性條件(圖12亦然).這一現(xiàn)象表明,在紋理空間“挖洞”并進行保持位置約束的“填充”后,盡管其填充曲面形狀發(fā)生了變化,但是其紋理的方向依然能獲得較好的保持.同時,本文在進行局部網(wǎng)格優(yōu)化后更新了紋理坐標,其結(jié)果與未更新前幾乎沒有差異(如圖11(d)和圖11(e)).該現(xiàn)象一方面體現(xiàn)了余切拉普拉斯幾何敏感的特性(與網(wǎng)格無關),另一方面也說明了本文紋理坐標融合方法的有效性.

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

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

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

5 總結(jié)與展望

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

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

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