改進的全局參數化方法

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

摘要：

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

關鍵詞：

全局參數化；全純1形式；調和能量；共形映射；割圖

中圖分類號：

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.

英文關鍵詞Key words：

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

0引言

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

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

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

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

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

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

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

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

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

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

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

2.1同調群基底

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

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

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

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

算法1計算曲面割圖。

輸入：曲面M；

輸出：曲面割圖G。

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

2）采用廣度優先搜索構造的最小生成樹；

3）返回G={e|}。

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

算法2計算同調群基底。

輸入：割圖G；

輸出：同調群基底H1（M）。

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

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

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

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

2.2上同調群基底

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

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

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

接著構造調和函數fi：→R，滿足：

fi（vj）=0，vj

1，vj∈，k

0，vj∈，s

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

算法3計算上同調基底。

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

輸出：上同調群基底H1（M）。

3實驗結果與分析

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

3.1適用性

第一組實驗模型如圖1所示，從上到下、從左至右編號為1～6，虧格分別為1、2、3、5、6、7。本算法和文獻[9]算法的參數化結果對比如圖2所示。

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

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

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

然后通過計量頂點和面積的平均相對偏差來估量兩者孰優孰劣，計算公式[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為網格的三角形個數指標，S和A是三角形面積和角度，e表示三角形的角盈。該誤差測量是一個整體變形度量，實驗數據如表格1所示。

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

3.2處理效率

為了凸顯本文算法效率的提高，第二組實驗采取數據規模更大的實驗模型，如圖4所示，從上到下、從左至右編號分別為7～12。關于第二組實驗模型的數據屬性和實驗結果如表2所示。因每次實驗需隨機取點以計算同調群基底，而其所生之基底皆相異，所以采用平均時間來度量。

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

4結語

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

參考文獻：

[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]

胡國飛，方興，彭群生.凸組合球面參數化[J].計算機輔助設計與圖形學學報，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.）