改進的全局參數(shù)化方法

洪程　章登義　蘇科華　武小平　鄭昌金

摘要：

針對多虧格曲面參數(shù)化變形較大、運算復(fù)雜度高的問題，提出一種改進的基于全純1形式的全局參數(shù)化方法。該方法以參數(shù)化的梯度場為出發(fā)點，采用更快速的同調(diào)群和上同調(diào)群計算方法。首先，利用簡化的割圖法計算曲面的同調(diào)群以確定其拓撲結(jié)構(gòu)；其次，定義特定的調(diào)和函數(shù)計算閉合1形式來構(gòu)造由梯度場形成的線性空間的上同調(diào)群；然后，最小化調(diào)和能量將上同調(diào)群擴散為調(diào)和1形式；最后，線性組合調(diào)和1形式構(gòu)造出全純1形式并在基本域上積分即得到參數(shù)化。由上同調(diào)群、同調(diào)群相關(guān)理論分析表明，該方法所得參數(shù)化是一種全局的、邊界自由的共形映射。基于多組高虧格模型的實驗證明，與原有基于全純1形式的全局參數(shù)化算法相比，本算法視覺效果更好，平均誤差更小，運算效率更高。

關(guān)鍵詞：

全局參數(shù)化；全純1形式；調(diào)和能量；共形映射；割圖

中圖分類號：

TP391.41

文獻標志碼：A

Abstract：

Focusing on the issue that nonzero genus surface parameterization has large deformation and high computational complexity， an improved global parameterization approach based on holomorphic 1form was proposed， which starts from the gradient field and adapts easier and faster method to compute homology and cohomology group. Firstly， a simplified cut graph method was used to construct homology group to determine the topology. Secondly， cohomology group of the linear space formed by the gradient field was calculated by defining special harmonic function to figure out closed 1form. Thirdly， homology group was diffused to harmonic 1form through minimizing harmonic energy. Finally， holomorphic 1form was computed by combining linearly harmonic 1form and the parameterization was obtained by integrating holomorphic 1form on the surface basic domain. Theoretical analysis of homology group and cohomology group shows that the parameterization is a global， borderfree conformal mapping. Experimental results based on nonzero genus model show that， compared with the former global parameterization based on holomorphic 1form， the proposed algorithm has better visual effect， smaller average error and higher operation efficiency.

英文關(guān)鍵詞Key words：

global parameterization； holomorphic 1form； harmonic energy； conformal mapping； cut graph

0引言

曲面參數(shù)化是一種幾何處理的基本工具，它將三維曲面投射到標準域（如平面區(qū)域、球面、多面體），從而把復(fù)雜幾何模型的幾何處理操作轉(zhuǎn)移到簡單幾何模型上，大大簡化數(shù)字幾何處理操作，因此廣泛應(yīng)用于紋理映射、曲面可視化、重新網(wǎng)格化和曲面擬合等過程。

參數(shù)化本質(zhì)是一種三維網(wǎng)格曲面與參數(shù)域之間的可逆映射關(guān)系，一個有效的參數(shù)化必須是雙射且不能存在網(wǎng)格重疊。理想情況是三角網(wǎng)格曲面與參數(shù)域之間的映射等距，但除可擴展曲面外絕大多數(shù)曲面難以實現(xiàn)，因此在該過程中必定產(chǎn)生圖形扭曲。保證有效性的同時使變形最小成為參數(shù)化中的關(guān)鍵問題。隨著曲面參數(shù)化應(yīng)用愈加廣泛，針對不同參數(shù)性質(zhì)的方法相繼提出，以下是五種針對零虧格曲面的經(jīng)典方法。

1）Floater[1]采用網(wǎng)格頂點與其相連接的頂點的凸組合表示三角網(wǎng)格的平面參數(shù)化，通過求解線性方程組得到結(jié)果；但是該方法要求邊界必須為凸多邊形，因此極大程度上限制了其實際應(yīng)用。

2）能量方程最小化方法關(guān)鍵在于建立能量方程，基于此，在邊界條件下求出極值得到參數(shù)化。最早由Eck等[2]引入調(diào)和映射并在連續(xù)Dirichlet積分基礎(chǔ)上提出調(diào)和能量方程，因調(diào)和映射具有局部保角性，從而使角度變形縮小。隨后，Desbrun等[3]給出基于曲面高斯曲率積分的歐拉示性函數(shù)，引進并最小化二次能量最終得到與文獻[2]類似效果；該方法運算復(fù)雜度低，但需要固定邊界，因此可能產(chǎn)生較大形變。Sander等[4]提出最大限度地減少紋理在曲面上的位置和方向偏移的最小拉伸方法，Jin等[5]將該方法推廣至3D，取得了較好效果。

3）最小二乘共形映射方法由Lévy等[6]提出，以正交性和齊次空間理論為基礎(chǔ)定義連續(xù)的共形映射，并使用最小二乘法逼近離散的柯西黎曼方程得到參數(shù)化，取得了較好的保角效果；但不能保證結(jié)果為雙射，意味著可能存在網(wǎng)格局部重疊。

4）Sheffer等[7]提出的保角展平方法將復(fù)雜三角網(wǎng)格分割為多個可展面片進行參數(shù)化，并列出一系列約束條件，以防止網(wǎng)格展平重疊，最終取得極小的角度形變；但計算量大，也不能解決多邊界問題。

5）最佳等距參數(shù)化方法由Hormann等[8]提出，在原始網(wǎng)格和參數(shù)域之間引進線性映射，以求解帶約束的非線性系統(tǒng)。該方法在平移、縮放、旋轉(zhuǎn)等變換下度量均為定值，無需固定邊界，但是運算復(fù)雜度較高。

上述五種方法均針對零虧格曲面，而在實際應(yīng)用中多虧格曲面普遍存在，因此將參數(shù)化向多虧格曲面推廣十分必要。最經(jīng)典的方法是Gu[9]在2003年提出的基于全純1形式的全局參數(shù)化方法，基于Hodge理論使用熱擴散的方式計算每個上同調(diào)類的調(diào)和形式，利用Hodge星算子構(gòu)成全純形式，這是首次將參數(shù)化方法應(yīng)用到高虧格曲面，為全局參數(shù)化開辟新道路。但該方法在奇點的處理效果一般，此外關(guān)于同調(diào)群和上同調(diào)群的構(gòu)造過程較為復(fù)雜，處理速度偏慢。

隨后出現(xiàn)了不少基于文獻[9]方法擴展的參數(shù)化方法及應(yīng)用。2006年，受到幾何處理應(yīng)用的啟發(fā)，Ray等[10]結(jié)合幾何信息，對輸入指定的正交向量場提供一種曲率自適應(yīng)的參數(shù)化方法，能實現(xiàn)同時保面積和角度的效果，適合網(wǎng)格化和曲面擬合；但是該方法需指定輸入，不能自動完成所有曲面的參數(shù)化。Tong等[11]推廣到帶有錐奇點的1形式方法并用來網(wǎng)格修復(fù)和平鋪。2009年， Zeng等[12-13]將全純微分方法應(yīng)用于計算帶多個邊界的虧格為0的曲面上的共形映射以及擬共形映射。上述所有的推廣方法均在奇點的處理方式提出改進，取得更好的效果，但仍存在提升空間。

除離散全純微分外全局參數(shù)化還有另一種重要方法：里奇流（Ricci Flow），其中較為突出的是cicle packing[14]和circle pattern[15]度量方法。近幾年仍有不少學者提出新的全局參數(shù)化方法并取得較好的效果。例如2012年Myles等[16]提出基于迭代壓扁方式最小化ARAP（AsRigidAsPossible）能量的全局參數(shù)化方法，并于2014年提出采用交叉場對曲面四邊形網(wǎng)格化，實現(xiàn)對任意輸入曲面的參數(shù)化[17]。

為了尋找更優(yōu)的全局參數(shù)化方法，所面臨的挑戰(zhàn)有：一是對結(jié)構(gòu)更復(fù)雜的高虧格曲面，如何準確獲取其拓撲信息并降低計算復(fù)雜度；二是如何保證參數(shù)化的有效性，并最小化形變。針對以上問題，本文基于文獻[9]提出以下改進：采用改進的割圖法計算同調(diào)群；定義特定的調(diào)和函數(shù)求解閉合1形式來構(gòu)造上同調(diào)群。同調(diào)群和上同調(diào)群理論為改進方法的合理性和可行性提供解釋，實驗采用多組多虧格模型并從適用性、誤差和處理速率進行比較，突出改進之處的效果。

2.1同調(diào)群基底

從理論角度探討，存在諸多計算同調(diào)群基底的方法。文獻[9]中計算同調(diào)群基底的方法是通過誘導(dǎo)邊界算子成為Smith標準型。首先將網(wǎng)格采用漸進網(wǎng)格算法[18]簡化，例如將4000個面的網(wǎng)格降為400個面的網(wǎng)格；當找到降采樣網(wǎng)格的同調(diào)群基底后拉回到原始網(wǎng)格并檢查每個頂點的鄰域以保證每個基底的連通性；最后采用Dijkstra算法簡化基底。

本算法用到割圖（cut graph）概念，割圖是指三角網(wǎng)格曲面上的一族邊集，使得曲面去掉這些邊后變成拓撲圓盤。Seifertvan Kampen理論可以證明割圖的生成元就是同調(diào)群的生成元，因此可將求同調(diào)群基底轉(zhuǎn)化為求割圖基底。

割圖相關(guān)算法有treecotree decomposition[19]，本文基于文獻[19]的思想提出用最小生成樹構(gòu)造割圖。文獻[19]通過不斷迭代執(zhí)行插入和刪除操作，動態(tài)更新生成元且不斷逼近最短割圖，最終得到同調(diào)群基底。而在參數(shù)化中著重點并非尋找最短割圖而是梯度場的基底構(gòu)造，因此采用過程更為簡單的最小生成樹方法。

得到割圖后利用最小生成樹方法計算割圖基底，對于每個葉子節(jié)點都存在到根節(jié)點的一條唯一回路，所有的回路便構(gòu)成同調(diào)群的基底。

算法1計算曲面割圖。

輸入：曲面M；

輸出：曲面割圖G。

1）計算對偶曲面，頂點v的對偶為面，面f的對偶為頂點，邊e的對偶為；

2）采用廣度優(yōu)先搜索構(gòu)造的最小生成樹；

3）返回G={e|}。

算法1所得割圖G可迭代刪除與度為1的頂點相連的邊，以減少后期不必要的運算。沿割圖G剪開曲面M得到曲面基本域D。

算法2計算同調(diào)群基底。

輸入：割圖G；

輸出：同調(diào)群基底H1（M）。

1）G中選定根節(jié)點v，構(gòu)建最小生成樹T，記每個葉子節(jié)點vi到根節(jié)點v的唯一路徑為γi；

2）GT={e1，e2，…，e2g}，對ek∈GT，且ek =[vi，vj] 則存在回路lk = γi[vi，vj]γ-1j；

3）返回同調(diào)群基底H1（M） ={l1，l2，…，l2g}。

從時間復(fù)雜度上分析，文獻[9]引進漸進網(wǎng)格算法簡化的原因是在誘導(dǎo)中本身會產(chǎn)生大量計算花費，同時這種類似降采樣的方式雖然能提高計算效率，但是不能完全保留原始網(wǎng)格信息，對同調(diào)群基底的構(gòu)造具有局限性。當對虧格為g，頂點數(shù)為n的網(wǎng)格參數(shù)化時，簡化網(wǎng)格的時間復(fù)雜度為o（n log n），誘導(dǎo)邊結(jié)算子為Smith標準型的時間復(fù)雜度為o（n2），拉回到原始網(wǎng)格后需遍歷檢查每個頂點的鄰域關(guān)系o（n），總的時間復(fù)雜度為o（n+n log n+n2）。而本算法只需要兩次遍歷，平均時間復(fù)雜度為o（n log n）。相比之下，用改進的割圖法求同調(diào)群的算法過程更簡單，時間復(fù)雜度更低。

2.2上同調(diào)群基底

文獻[9]先選取任意兩個同調(diào)群基底并沿基底剪開曲面；然后將剪開的曲面映射到單位矩形或單位圓盤，計算其對偶1形式；最后將對偶1形式拉回原曲面，直至所有同調(diào)群基底遍歷完畢得到上同調(diào)群基底。

本算法利用同調(diào)群和上同調(diào)群的對偶關(guān)系定義特定的調(diào)和函數(shù)計算閉合1形式，組成上同調(diào)群的基底。首先將曲面M沿著割圖G剪開得到拓撲盤，每條半邊∈都唯一對應(yīng)一條半邊h∈M。將邊界上的點按序排列，={v0，v1，…，vk，vk+1，…，vn-1}。假定M上的半邊h+i，h-i均與邊e相鄰，那么在上：

+i=[vk，vk+1]，-i=[vs，vs+1]

接著構(gòu)造調(diào)和函數(shù)fi：→R，滿足：

fi（vj）=0，vj

1，vj∈，k

0，vj∈，s

然后定義閉合1形式ωi（h）=dfi（），那么Ω={ω1，ω2，…，w2g}便組成了上同調(diào)群H1（M）的基底。

算法3計算上同調(diào)基底。

輸入：虧格為g的閉合曲面M；

輸出：上同調(diào)群基底H1（M）。

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

實驗環(huán)境為Windows 8.1操作系統(tǒng)，Intel i5 4200處理器，1.6GHz主頻，4GB內(nèi)存。使用VS2010、C++編程實現(xiàn)，采用圖形處理庫openMesh 3.3，矩陣計算工具Eigen 3.2.4。輸入的網(wǎng)格文件格式為off格式，顯示網(wǎng)格的可視化軟件為基于開源軟件MeshViewer二次開發(fā)的miniMeshViewer。實驗分析將從本算法對高虧格曲面的適用性和對數(shù)據(jù)的處理效率兩方面入手。

3.1適用性

第一組實驗?zāi)Ｐ腿鐖D1所示，從上到下、從左至右編號為1～6，虧格分別為1、2、3、5、6、7。本算法和文獻[9]算法的參數(shù)化結(jié)果對比如圖2所示。

一般衡量參數(shù)化之好壞主要使用以下兩種方法，第一種是通過視覺上的平滑效果進行主觀判定，但人眼無法分辨更細微的差異；另一種是采用度量的方法，計算三維網(wǎng)格和參數(shù)域之間的幾何度量偏差[20]，得以衡量整體形變。

首先通過直接的觀察判斷兩種算法的整體效果，由圖2所示知兩者對非邊界區(qū)域的處理均較為合理，無明顯的變形。現(xiàn)放大邊界處區(qū)域進行仔細對比，由于本算法與文獻[9]均采用梯度場的方法，生成的同調(diào)群基底各有所異，故現(xiàn)在分別考量割圖同倫群基底即銜接之處的細節(jié)，圖3展示編號為1、3、6模型的局部放大結(jié)果。

由圖3可知，兩者在割圖分裂之處均存在不連貫細節(jié)，原因在于兩種方法均立足于全純微分方法，差異在于獲取曲面拓撲結(jié)構(gòu)和梯度場的構(gòu)造方法。仔細觀察文獻[9]所展示的鋸齒狀更為明顯，黑白棋盤的交錯更加劇烈，究其根源是采用了漸進算法簡化網(wǎng)格，而本算法利用改進的割圖方法去構(gòu)造同倫群基底更加精準，保留曲面的所有信息，故而取得相對連貫的效果，但仍存在改進空間。

然后通過計量頂點和面積的平均相對偏差來估量兩者孰優(yōu)孰劣，計算公式[20]如下：

Distarea=∑jS（Tj）∑Ti∈MS（Ti）-S（T*j）∑Ti∈MS（T*i）2

Distangle=∑j∑i=1，2，3Ai2π-A*i2π+e2

其中： j為網(wǎng)格的三角形個數(shù)指標，S和A是三角形面積和角度，e表示三角形的角盈。該誤差測量是一個整體變形度量，實驗數(shù)據(jù)如表格1所示。

從表1可對比得，當曲面虧格越高，兩者的誤差差距更加明顯，證實本文算法相對文獻[9]取得更小的平均誤差。其中緣由在于本文算法采用調(diào)和函數(shù)計算閉合1形式去構(gòu)造梯度場的基底，更貼近曲面的真實情況，文獻[9]基于映射到單位矩形或單位圓盤求對偶1形式的方法不可避免會對梯度場造成扭曲，故而產(chǎn)生額外的誤差。綜合直觀效果和誤差數(shù)據(jù)分析，總體上說，本文算法實現(xiàn)了對高虧格曲面的參數(shù)化，并取得較小的形變誤差。

3.2處理效率

為了凸顯本文算法效率的提高，第二組實驗采取數(shù)據(jù)規(guī)模更大的實驗?zāi)Ｐ停鐖D4所示，從上到下、從左至右編號分別為7～12。關(guān)于第二組實驗?zāi)Ｐ偷臄?shù)據(jù)屬性和實驗結(jié)果如表2所示。因每次實驗需隨機取點以計算同調(diào)群基底，而其所生之基底皆相異，所以采用平均時間來度量。

的差異越來越大，可知本文算法相對于文獻[9]所述方法，在計算速度上有較大提高?？紤]算法本身的平均時間復(fù)雜度是o（g3n log n），與網(wǎng)格的大?。c、邊、面數(shù)）、虧格g有關(guān)，取得提升的根本原因得益于求同調(diào)群和上同調(diào)群過程的簡化。一方面，基于割圖的思想且繞開尋找最優(yōu)割圖采用最實用的最小生成樹方法計算割圖及其基底，降低了構(gòu)造同調(diào)群的時間花銷；另一方面，采用特定的調(diào)和函數(shù)逐一計算同調(diào)群基底的對偶形式，避免重復(fù)剪開、映射曲面的中間過程，精簡了計算過程。

4結(jié)語

本文基于文獻[9]改進的全局參數(shù)化方法利用同調(diào)群和上同調(diào)群的理論對多虧格曲面實現(xiàn)了更連貫的視覺效果和更高的處理效率，并且能控制角度和面積平均誤差在更小的范圍內(nèi)，因此提高了在實際應(yīng)用如紋理映射中的適用性。但是在曲面同倫群基底的邊界處理上仍有提升的空間，未來將深入探究如何在不同的參數(shù)化結(jié)果中篩選最優(yōu)解。

參考文獻：

[1]

FLOATER M S. Parametrization and smooth approximation of surface triangulations [J]. Computer Aided Geometric Design， 1997， 14（3）： 231-250.

[2]

ECK M， DEROSE T， DUCHAMP T， et al. Multiresolution analysis of arbitrary meshes [C]// SIGGRAPH 95： Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1995： 173-182.

[3]

DESBRUN M， MEYER M， ALLIEZ P. Intrinsic parameterizations of surface meshes [J]. Computer Graphics Forum， 2002， 21（3）： 209-218.

[4]

SANDER P V， SNYDER J， GORTLER S J， et al. Texture mapping progressive meshes [C]// SIGGRAPH 01： Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 2001： 409-416.

[5]

JIN Y， QIAN G P， ZHAO J Y， et al. Stretchminimizing volumetric parameterization [J]. Journal of Computer Science and Technology， 2015， 30（3）： 553-564.

[6]

LVY B， MALLET J L. Nondistorted texture mapping for sheared triangulated meshes [C]// SIGGRAPH 98： Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. New York：ACM， 1998： 343-352.

[7]

SHEFFER A， DE STURLER E. Parameterization of faceted surfaces for meshing using anglebased flattening [J]. Engineering with Computers， 2001， 17（3）： 326-337.

[8]

KAI H， GREINER G. MIPS： an efficient global parametrization method [C]// Curve & Surface Design： Saint-Malo. Nashville：Vanderbilt University Press， 2000.

HORMANN K， GREINER G. MIPS： an efficient global parametrization method [EB/OL]. [20151123]. http：//www.inf.usi.ch/hormann/papers/Hormann.2000.MAE.pdf.

[9]

GU X， YAU S T. Global conformal surface parameterization [C]// SGP 03： Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. AirelaVille， Switzerland： Eurographics Association， 2003： 127-137.

[10]

RAY N， LI W C， LVY B， et al. Periodic global parameterization [J]. ACM Transactions on Graphics， 2006， 25（4）： 1460-1485.

[11]

TONG Y， ALLIEZ P， COHENSTEINER D， et al. Designing quadrangulations with discrete harmonic forms [C]// SGP 06： Proceedings of the 4th Eurographics Symposium on Geometry Processing. AirelaVille， Switzerland： Eurographics Association， 2006： 201-210.

[12]

ZENG W， YIN X， ZHANG M， et al. Generalized Koebes method for conformal mapping multiply connected domains [C]// SPM 09： Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. New York： ACM， 2009： 89-100.

[13]

ZENG W， LUO F， YAU S T， et al. Surface quasiconformal mapping by solving Beltrami equations [M]// HANCOCK E R， MARTIN R R， SABIN M A. Mathematics of Surfaces XIII， LNCS 5654. Berlin： Springer， 2009： 391-408.

[14]

RODIN B， SULLIVAN D. The convergence of circle packings to the Riemann mapping [J]. Journal of Differential Geometry， 1987， 26（26）： 349-360.

[15]

KHAREVYCH L， SPRINGBORN B， SCHRDER P. Discrete conformal mappings via circle patterns [J]. ACM Transactions on Graphics， 2006， 25（2）： 412-438.

[16]

MYLES A， ZORIN D. Global parametrization by incremental flattening [J]. ACM Transactions on Graphics， 2012， 31（4）： Article No. 109.

[17]

MYLES A， PIETRONI N， ZORIN D. Robust fieldaligned global parametrization [J]. ACM Transactions on Graphics， 2014， 33（4）： Article No. 135.

[18]

HOPPE H. Viewdependent refinement of progressive meshes [C]// SIGGRAPH 97： Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM Press/AddisonWesley Publishing Company， 1997： 189-198.

[19]

EPPSTEIN D. Dynamic generators of topologically embedded graphs [C]// SODA 03： Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms. Philadelphia， PA： SIAM， 2003： 599-608.

[20]

胡國飛，方興，彭群生.凸組合球面參數(shù)化[J].計算機輔助設(shè)計與圖形學學報，2004，16（5）：632-637.（HU G F， FANG X， PENG Q S. Convex combi nation spherical parameterization [J]. Journal of ComputerAided Design and Computer Graphics， 2004， 16（5）： 632-637.）