(1.廣西大學計算機與電子信息學院, 廣西南寧530004;2.廣西電網(wǎng)有限責任公司信息中心廣西南寧530023)

在計算機圖形學領(lǐng)域中常用多邊形網(wǎng)格模型表示各種幾何形狀,主要包括三角網(wǎng)格和四邊形網(wǎng)格。三角網(wǎng)格模型發(fā)展成熟、應用廣泛,是最常用的三維幾何模型表示方法之一。四邊形網(wǎng)格模型也是一類重要的三維幾何模型表示方法, 在機械制造、考古、醫(yī)學、計算視覺等領(lǐng)域有廣泛應用。與三角形網(wǎng)格相比，四邊形網(wǎng)格更符合人類的視覺感知，在計算精度、計算效率等方面均優(yōu)于三角形網(wǎng)格，更適用于CAD/CAM、紋理合成、計算機動畫以及數(shù)值仿真等領(lǐng)域[1-4]。

模型變形編輯是數(shù)字幾何處理的主要內(nèi)容之一,也是提升幾何模型設計效率的重要途徑之一[5]。很多時候,需要按照指定的參考姿態(tài)進行變形使之具有與參考模型相似的姿態(tài)。作為基于樣例的建模技術(shù),變形遷移[6-9]提供了這一可能,它將模型的形變信息傳遞至源網(wǎng)格模型,使之作相似的變形,最終得到具有與參考模型相似的姿態(tài)。與變形遷移相比,譜姿態(tài)遷移僅僅需要輸入?yún)⒖寄Ｐ偷囊粋€姿態(tài),極大地擴展了基于樣例的建模技術(shù)的應用范圍。

三維網(wǎng)格模型的譜分析技術(shù),揭示了拉普拉斯矩陣的特征向量的系數(shù)與網(wǎng)格模型的形狀之間的聯(lián)系[10-15]。Lévy等[16]將源網(wǎng)格模型和參考網(wǎng)格模型用各自的調(diào)和基展開,通過交換低頻系數(shù)實現(xiàn)譜姿態(tài)遷移。Kovnatsky等[17]通過輸入兩組對應函數(shù),采用聯(lián)合近似對角化算法求解出兩組近似等距對應的準調(diào)和基來解決姿態(tài)扭曲的問題。Yin等[18]在以上工作基礎(chǔ)之上,一方面結(jié)合Laplacian編輯算法[19-20],建立了保細節(jié)的譜姿態(tài)遷移框架;另一方面,把參考姿態(tài)看作是一個分層結(jié)構(gòu)的,將局部姿態(tài)(中高頻姿態(tài))轉(zhuǎn)化為全局姿態(tài)(低頻姿態(tài)),并對局部區(qū)域應用同樣的譜姿態(tài)遷移方法,形成了分層譜姿態(tài)遷移框架。

但是,目前譜姿態(tài)遷移建立在三角網(wǎng)格模型的拉普拉斯矩陣的特征分解基礎(chǔ)之上,主要在三角網(wǎng)格模型之間進行。

本文在三角網(wǎng)格模型譜姿態(tài)遷移的基礎(chǔ)之上,研究并實現(xiàn)了四邊形網(wǎng)格模型與三角形網(wǎng)格模型間低頻譜姿態(tài)遷移。首先引入多邊形網(wǎng)格模型的拉普拉斯矩陣,并對多邊形網(wǎng)格模型的光順[21]和重構(gòu)進行了代碼實現(xiàn)。其次,在多邊形網(wǎng)格模型的情形下討論了泛函映射和網(wǎng)格模型的特征對應,并對泛函矩陣、調(diào)和基以及耦合準調(diào)和基進行了可視化。最后,在多邊形網(wǎng)格模型上分別設計并實現(xiàn)了平凡的譜姿態(tài)遷移、基于耦合準調(diào)和基的譜姿態(tài)遷移和基于拉普拉斯坐標投影的低頻譜姿態(tài)遷移。

1 拉普拉斯矩陣及其特征分解

Alexa等[22]在一般多邊形網(wǎng)格模型上構(gòu)造了拉普拉斯矩陣,包括非凸多邊形和非平面多邊形的情形,為本文研究多邊形網(wǎng)格模型譜姿態(tài)遷移提供了堅實的理論基礎(chǔ)。本文正是在以上工作基礎(chǔ)上研究多邊形網(wǎng)格模型譜姿態(tài)遷移。本文所使用的多邊形網(wǎng)格模型主要是三角網(wǎng)格模型和四邊形網(wǎng)格模型。

1.1 拉普拉斯矩陣的譜與特征向量

若Lφi=λiφi(i=0,…,|V|-1),且φi≠0,則λi和φi為矩陣L的特征值和其對應的特征向量。對矩陣L作廣義特征分解LΦ=M0ΦΛ便可以求出其全部特征值及其對應的特征向量,并假定特征值及對應的特征向量按照特征值的大小從小到大進行排列,其中Λ=diag{λ0,λ1,…,λ|V|-1},Φ={φ0,φ1,…,φ|V|-1}。這些全體特征值就是拉普拉斯矩陣L的譜,特征向量被稱為網(wǎng)格M的調(diào)和基。同理,也可以對L作廣義特征分解。但因其存在對稱性,故其特征向量彼此正交。

1.2 多邊形網(wǎng)格模型的Laplace光順算法

Laplace光順算法[21]是三角網(wǎng)格模型處理領(lǐng)域中的經(jīng)典算法。文獻[22]的算法能夠被無縫遷移到多邊形網(wǎng)格模型上。如圖1所示,最左邊為四邊形網(wǎng)格模型Fertility, 依次向右為對其進行多次Laplace光順的結(jié)果。

圖1 四邊形網(wǎng)格的Laplace光順Fig.1 Laplace smoothing of the quad mesh

1.3 多邊形網(wǎng)格模型重構(gòu)

文獻[16]將網(wǎng)格模型投影到拉普拉斯矩陣的特征向量上,并用基函數(shù)將其展開,即:

(1)

如圖2所示,左一為原模型,該模型有10 493個頂點,從左2依次向右分別為使用20、50、100和300個調(diào)和基對原模型進行重構(gòu)。

圖2 網(wǎng)格重構(gòu)Fig.2 Mesh reconstruction

2 耦合準調(diào)和基

在很多應用中,涉及到兩個模型之間的對應關(guān)系。Ovsjanikov等[23]提出了泛函映射的方法,為研究兩個模型之間的對應關(guān)系提供了新的手段。文獻[17]在此基礎(chǔ)之上,提出了耦合準調(diào)和基。

2.1 耦合準調(diào)和基的原理

圖3 調(diào)和基可視化Fig.3 Visualization of the harmonic bases

圖4 耦合準調(diào)和基可視化Fig.4 Visualization of the quasi-harmonic bases

2.2 多邊形網(wǎng)格模型的特征對應

文獻[17]通過優(yōu)化調(diào)和基以得到兩組新的耦合準調(diào)和基,從而克服了調(diào)和基表達不一致的問題。但是,耦合調(diào)和基的計算依賴于兩個模型的特征對應關(guān)系,需要構(gòu)造對應函數(shù),并利用聯(lián)合近似對角化算法求解。在本文中,通過手動選擇對應點的方式構(gòu)造k-鄰域指示函數(shù)作為兩個模型之間的對應函數(shù),如圖5(a)所示。如圖5(b)所示,右半部分是耦合準調(diào)和基的泛函矩陣的可視化,左半部分是調(diào)和基的泛函矩陣的可視化,耦合準調(diào)和基的對角化程度明顯比調(diào)和基高。

(a) 模型之間的對應頂點 (b) 泛函矩陣可視化

設在源模型M和參考模型M′上選取的p組對應頂點的集合為P={(v0′,v0),…,(vp′,vp)}。相應地,這兩組對應函數(shù)可設為F={f0,…，fp}和G={g0,…，gp}，其中:

注意,本文是在多邊形網(wǎng)格情形下討論網(wǎng)格模型特征對應,包括三角網(wǎng)格和四邊形網(wǎng)格,故頂點集合Nik′可以統(tǒng)一表示為頂點vi′的k-鄰域中所有頂點構(gòu)成的集合。集合Nik的表示與此類似。如圖6所示,空心頂點構(gòu)成的集合為實心頂點vi的1-鄰域,其他情形與此類似。

圖6 頂點vi的鄰域1鄰域Fig.6 One-ring neighborhood of the vertex vi

3 多邊形網(wǎng)格模型譜姿態(tài)遷移

在以上基礎(chǔ)之上,本文將文獻[16]提出的平凡譜姿態(tài)遷移和文獻[17]提出的基于耦合準調(diào)和基的譜姿態(tài)遷移擴展到多邊形網(wǎng)格模型上,并給出相應的實驗結(jié)果。

3.1 平凡的譜姿態(tài)遷移

根據(jù)前面拉普拉斯矩陣及其特征分解等有關(guān)理論可知,低頻系數(shù)編碼了網(wǎng)格的整體姿態(tài),而高頻系數(shù)則編碼了網(wǎng)格的局部細節(jié)。文獻[16]通過交換兩個網(wǎng)格的低頻系數(shù)的方式實現(xiàn)了姿態(tài)遷移,使得源網(wǎng)格模型與參考網(wǎng)格模型具有相似的姿態(tài),同時保持源網(wǎng)格自身的細節(jié)特征。本文將這一方法應用到多邊形網(wǎng)格模型上,實現(xiàn)了多邊形網(wǎng)格模型譜姿態(tài)遷移。

(2)

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

譜姿態(tài)遷移依賴于兩組一致表達的調(diào)和基。但事實上,在大多數(shù)情況下調(diào)和基是非等距對應的,調(diào)和基也因此往往表達不一致。正是此原因?qū)е缕椒沧V姿態(tài)遷移在網(wǎng)格不等距對應的情況下出現(xiàn)姿態(tài)扭曲等情況,詳見文獻[17]。

3.2 基于耦合準調(diào)和基的譜姿態(tài)遷移

將基于耦合準調(diào)和基的譜姿態(tài)遷移擴展到多邊形網(wǎng)格模型上,并給出兩類實現(xiàn)方法,即基于笛卡爾坐標投影的譜姿態(tài)遷移和基于拉普拉斯坐標投影的譜姿態(tài)遷移。

3.2.1 基于笛卡爾坐標投影的譜姿態(tài)遷移

耦合準調(diào)和基克服了調(diào)和基在非等距對應的情況下表達不一致的問題。為此,可用耦合準調(diào)和基替換調(diào)和基以解決平凡譜姿態(tài)遷移所存在的姿態(tài)扭曲等問題。

(3)

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

3.2.2 基于拉普拉斯坐標投影的譜姿態(tài)遷移

Lévy等[16]在文獻中提到另一種譜姿態(tài)遷移實現(xiàn)的途徑,即將局部坐標投影到調(diào)和基上,例如拉普拉斯坐標。作者認為,對于大尺度形變的姿態(tài)遷移,通過投影局部坐標實現(xiàn)姿態(tài)遷移的方式更合適,而不是直接投影笛卡爾坐標。但是,作者并沒有給出具體的實現(xiàn)步驟。

通過投影局部坐標的方式實現(xiàn)姿態(tài)遷移需要解決如何從新拉普拉斯坐標恢復出笛卡爾坐標。由于拉普拉斯矩陣是半正定的,因此從拉普拉斯坐標恢復出笛卡爾坐標需要額外的約束條件。本文結(jié)合拉普拉斯編輯算法[19-20],采用固定頂點位置的約束方法實現(xiàn)從局部坐標恢復出歐氏坐標。

設源網(wǎng)格模型M和參考網(wǎng)格模型M′的拉普拉斯坐標分別為:

δ=LMV=(δo,δ1,…,δ|V|-1)T,δ′=LM′V′=(δ0′,δ1′,…,δ|V′|-1′)T。

(4)

設M的固定頂點集合Vc={vc0,vc1,…,vcm}。通過約束固定頂點的位置,則有下面的能量函數(shù):

(5)

(a) 參考網(wǎng)格 (b) 源網(wǎng)格 (c) 目標網(wǎng)格

4 實驗結(jié)果與分析

為了說明本文工作的正確性和有效性,本文進行了不同類型的實驗,并對實驗結(jié)果進行說明和分析。

圖7和圖8分別展示了兩個具有相同連接關(guān)系的同一三角網(wǎng)格模型不同姿態(tài)之間的平凡譜姿態(tài)遷移和基于耦合準調(diào)和基的譜姿態(tài)遷移。可以看出本文方法能夠遷移模型的低頻姿態(tài)(全局姿態(tài))，但局部姿態(tài)沒有被遷移, 如圖7所示,目標網(wǎng)格的尾巴并未像參考姿態(tài)那樣彎曲。

圖9和圖10分別展示了相同對象和不同對象的三角網(wǎng)格模型與四邊形網(wǎng)格模型之間的低頻譜姿態(tài)遷移。局部姿態(tài)(中高頻姿態(tài))沒有學習到, 尾巴彎曲程度學習不充分。

圖11展示了兩個具有相同連接關(guān)系的同一四邊形網(wǎng)格模型不同姿態(tài)之間的譜姿態(tài)遷移。目標網(wǎng)格較好地學習了參考模型的姿態(tài)。

圖12展示了兩個不同對象不同連接關(guān)系的三角網(wǎng)格模型之間的姿態(tài)遷移。模型的細節(jié)特征未隨姿態(tài)變化而做相應地旋轉(zhuǎn),導致細節(jié)丟失,如圖12所示,目標網(wǎng)格左前腿較為扁平。

5 結(jié)語

本文在文獻[16-17]工作的基礎(chǔ)之上,研究多邊形網(wǎng)格模型譜姿態(tài)遷移,使其能夠操縱更多類型的網(wǎng)格模型,主要包括三角網(wǎng)格模型和四邊形網(wǎng)格模型。此外,也給出了四邊形網(wǎng)格光順和重構(gòu)的實驗結(jié)果。實驗結(jié)果表明,本文姿態(tài)遷移方法能夠操縱三角網(wǎng)格模型和四邊形網(wǎng)格模型。但是僅限于低頻姿態(tài)的遷移，而且所采用的保持源模型的細節(jié)方法需要計算網(wǎng)格模型的拉普拉斯矩陣的大量特征值與特征向量，當模型頂點數(shù)較大時，運算量很大，計算耗時較嚴重。

以后的工作將從兩方面展開：一方面嘗試新的保持目標網(wǎng)格的細節(jié)特征的方法，避免計算模型的拉普拉斯矩陣大部分甚至全部特征向量;另一方面采用分割手段,嘗試建立起四邊形網(wǎng)格分層譜姿態(tài)遷移框架,以解決局部姿態(tài)丟失的問題。