復用拉普拉斯算子的高效網格融合方法?

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 泊松融合算法框架

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

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

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

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

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

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

其中,Lc=AL+λC.

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

·C為位置約束的對角系數矩陣;

·λ為軟約束權重,默認取作108.

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

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

步驟2:根據源網格與對應目標網格邊界頂點信息計算局部變換——旋轉變換與縮放尺度;

步驟3:計算源網格融合邊界頂點到其他頂點的測地距離,并由此構造權函數標量場,根據該標量場,運用線性混合法插值出新邊界下源網格上的旋轉場與尺度場;

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

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

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

3.1 旋轉場與尺度場的插值

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

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

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

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

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

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

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

3.2 紋理坐標的融合

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

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

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

3.3 融合邊界的網格處理

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

3.3.1 融合邊界頂點的對應

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

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

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

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

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

3.3.2 融合邊界區域網格的優化

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

Fig.2 Comparison of the mesh before and after local mesh optimization圖2 融合邊界區域局部網格優化前后對比

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

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

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

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

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

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

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

融合邊界處經過網格優化后,該區域的紋理坐標隨之失效.為快速恢復其紋理坐標,本文利用第3.2節所述方法建立調和映射.由于建立調和映射的網格域拓撲未發生變化,其矩陣結構與公式(9)相同,因此可對該式的拉普拉斯算子進行復用,即省卻了矩陣的結構分解步驟,而僅對其進行數值分解與回代計算即可.

4 實驗與討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們在各種不同模型上進行了大量測試,發現本文算法均能較好地實現高效融合.圖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)).這些例子均進一步驗證了本文算法所具有的上述優點.

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

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

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

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

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

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

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

5 總結與展望

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

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

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