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

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

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

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

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

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

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

Alexa等[22]在一般多邊形網(wǎng)格模型上構(gòu)造了拉普拉斯矩陣,包括非凸多邊形和非平面多邊形的情形,為本文研究多邊形網(wǎng)格模型譜姿態(tài)遷移提供了堅(jiān)實(shí)的理論基礎(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的特征值和其對(duì)應(yīng)的特征向量。對(duì)矩陣L作廣義特征分解LΦ=M0ΦΛ便可以求出其全部特征值及其對(duì)應(yīng)的特征向量,并假定特征值及對(duì)應(yīng)的特征向量按照特征值的大小從小到大進(jìn)行排列,其中Λ=diag{λ0,λ1,…,λ|V|-1},Φ={φ0,φ1,…,φ|V|-1}。這些全體特征值就是拉普拉斯矩陣L的譜,特征向量被稱為網(wǎng)格M的調(diào)和基。同理,也可以對(duì)L作廣義特征分解。但因其存在對(duì)稱性,故其特征向量彼此正交。

1.2 多邊形網(wǎng)格模型的Laplace光順?biāo)惴?/h3>

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

(a) 模型之間的對(duì)應(yīng)頂點(diǎn) (b) 泛函矩陣可視化

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

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

圖6 頂點(diǎn)vi的鄰域1鄰域Fig.6 One-ring neighborhood of the vertex vi

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

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

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

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

(2)

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

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

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

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

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

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

(3)

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

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

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

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

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

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

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

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

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

(4)

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

(5)

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖7和圖8分別展示了兩個(gè)具有相同連接關(guān)系的同一三角網(wǎng)格模型不同姿態(tài)之間的平凡譜姿態(tài)遷移和基于耦合準(zhǔn)調(diào)和基的譜姿態(tài)遷移?？梢钥闯霰疚姆椒軌蜻w移模型的低頻姿態(tài)(全局姿態(tài))，但局部姿態(tài)沒有被遷移, 如圖7所示,目標(biāo)網(wǎng)格的尾巴并未像參考姿態(tài)那樣彎曲。

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

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

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

5 結(jié)語

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

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