淺談網格參數化算法及應用

周麗勤 顧立志

【摘 要】網格參數化不僅可以應用在計算機圖形學，還可以應用在計算機幾何設計及逆向工程、虛擬技術等諸多領域。文章根據不同的參數域，簡述了網格參數化的不同算法及各種算法在不同領域的應用和優缺點，并簡述如何控制參數化變形的方法。

【關鍵詞】網格參數化;參數域;控制參數變形

【中圖分類號】TP391.7 【文獻標識碼】A 【文章編號】1674-0688（2019）05-0113-03

在計算機圖形學、逆向工程、增材制造、虛擬技術等領域的幾何模型大部分是以網格的形式表示。網格模型所表達的物體數據是凌亂、離散、無序、難以利用的。直接處理這些網格模型是比較困難的。網格參數化是指為網格模型表面建立一一映射的參數域，映射后得到的參數化網格的拓撲關系同構于原始曲面網格，且幾何度量的變形最小化。從而對復雜網格模型的處理可以轉化為相對簡單的參數化網格處理。

網格參數化方法可根據參數域的不同分為平面參數化、基網格參數化、球面參數化、柱面參數化及交叉參數化。不同的網格參數化方法都被不同程度地應用到網格紋理映射、網格重構、網格壓縮編輯[2]等領域。

1 網格參數域的分類

1.1 平面參數化

平面參數化是把一個空間三角網格盡可能均勻地攤平到某個平面區域，平面參數化是目前研究得最多、最簡單的參數化算法。Floater在Tutte等人提出凸組合方法的基礎上給每條邊附加一個與邊長相關的權值，進面得出改進后的凸組合方法。Floater提出保形參數化和均值參數的研究，一般是先固定網格邊界，用線性函數作為變形度量，這樣計算相對簡單，但得不到自由邊界的網格參數化結果，只能應用于與拓撲圓盤同構的網格曲面。所以，對于虧格大于0的網格曲面，如果按一定規則來劃分網格，往往會引起參數化結果不連續，并且在某些部位容易造成較大的變形[1]。

1.1.1 保相似的平面參數化

張磊等人[3]提出了保相似的平面參數化，這種方法的優點是建立相應三角形的相似性。通過控制網格的相鄰兩邊的夾角和長度比例，在最小二乘的意義下基本保持不變，進而達到三角形的相似。此方法也適用于添加任何線性約束條件，與現有的一些方法相比，該算法幾何意義直觀，而且求解速度很快，參數化的結果也比較理想，操作簡便。缺點：無法保證平面參數化結果的有效性，即不會發生三角片的翻轉[3]。保相似平面參數化和Sheffer方法的對比如圖1所示。

1.1.2 基于鄰域多邊形特征的網格參數化

因保相似平面參數化，在距離約束點較遠的網格處有較大的參數化變形。彭威等人[4]利用保相似原理，通過鄰域多邊形頂點建立了網格頂點一階鄰域多邊形特征方程組，求解該線性方程組得到了空間網格在二維平面上的展平結果[4]。此方法適用于包含三角形和四邊形單元的混合網格模型，得到的參數化結果具有自由的邊界，且使得網格參數化扭曲較小。例如：工程零件、汽車鈑金類零件網格模型。車身側板模型網格參數化對比圖如圖2所示。

1.1.3 ARAP參數化

Liu等人[9]提出一種可以在保角和保面積中，取得較好的平衡的非線性能量函數，這種函數算法僅適用于與拓撲圓盤同構的網格曲面，不足之處在于此算法無法保證局部單射[1]。后來Myles等人[8]在ARAP算法的基礎上，改進了ARAP算法，使之更能適用于全局參數。解決方法如下：將ARAP參數化方法從拓撲圓盤曲面拓展到三維網格曲面。用全局參數化算法優化等距誤差。此能量函數方法可以在保角和保面積中取得較好的平衡，不會因為為了保角使得面積發生很大的變形。

文獻[5]中提出基于盡可能保形（As-Rigid-As-PosSible，ARAP）參數化的約束紋理映射算法，使得三維人臉網格三角形角度變形和面積變形均達到最小，進而使得紋理映射的形變最小。并利用比例嵌入方法控制形變，使映射效果更加自然，而且減少了優化次數。

1.1.4 ABF++保角參數化

文獻[5]中提出基于ABF++保角參數化的網格曲面刀軌規劃方法。通過保角參數化算法，可以將三維網格展平到參數域內，分析參數網格映射后產生的變形量，并由變形量計算出每個三角片內的映射拉伸系數與梯度，將三維網格上的軌跡參數轉換為二維，再根據參數域內的二維軌跡參數直接生成線性刀具軌跡和非線性刀具軌跡。

ABF++算法計算速度快，角度變形較小，如果網格模型不存在邊界處變形較大的問題，可保證三維網格與參數網格之間的一一映射關系[5]。

1.2 基網格參數化

基網格參數化屬于全局參數化，適用于虧格大于0的網格曲面。基網格參數化的主要優點是可以保留原始網格的拓撲關系，減少后續參數處理所造成的變形。

基網格參數化算法是通過種子點構造Voronoi圖，以及Voronoi圖的對偶Delaunay三角剖分形成的，之后使用調和映射計算內部頂點的參數值。雖然之后有自適應曲面參數化、三角基網格、四邊形基網格[1]。

1.3 球面參數化

球面參數化的研究方法有球面松弛法、嚴寒冰等人提出的采用球面坐標計算凸組合球面參數化的凸組合法及周昆等人提出的累進網格方法。

球面參數化產生的變形扭曲較大、計算困難、失真程度高，因此此算法主要適用于0虧格的閉曲面（如圖3所示）。

1.4 柱面參數化

郭瀟晟等人[7]對于形態接近于圓柱或具有單支簡單骨架的封閉、半封閉的網格模型，提出一種骨架引導的網格模型圓柱面參數化方法。

柱面參數化研究方法：先引入超柱面參數域定義，通過模型的簡化建立其與超柱面的基本映射關系，再將頂點反插入柱面參數域來恢復原模型拓撲，進而對初始參數化結果，運用拉伸形變尺度的優化，實現基本的柱面參數化;對于具有強骨架信息的復雜模型[7]，由于超柱面側面可展，超柱面參數化適用于對0虧格封閉模型的參數化。并且對人體和動物等可以通過骨架指引對人體、動物等0虧格封閉模型進行超圓柱面參數化，這樣減小了模型的幾何形變。相對于球面參數化，柱面參數化變形會小一點。

1.5 交叉參數化

與基網格參數化類似，交叉參數化通常需要一個公共參數域。可以通過對原始網格進行簡化作為基參數域，也可以通過自動生成模板參數域及采用四邊形面片作為公共基參數域。交叉參數化一般應用于曲面間變形及曲面混合（blending）等（如圖4所示）。

這些方法研究的困難在于以下幾個方面：①對于狹長和復雜的網格，難于在健壯和效率之間取得平衡。②因公共參數域的映射誤差在后續映射被放大，這樣會造成曲面間的變形相對較大。③面片間不連續，這樣就需要對網格進行各種后處理。

后續研究可以考慮將柱面參數化方法作為交叉參數化方法的公共參數，以減少各面片之間不連續。

2 減輕參數變形方法

2.1 錐狀奇異點

文獻[4]直接把原始網格的頂點作為錐狀奇異點，將部分錐狀奇異點進行算法處理得到曲率為0的點，接下來采用貪心策略算法優化這些低失真的原始網格曲面，這樣參數化的曲面變形相對較小。這樣通過原始網上的錐狀奇導點可以避免映射誤差被放大，同時可以減小參數化變形的產生。

2.2 變形能量優化

文獻[12]對MIPS（Most-Isometric Parameterizations）、BDM（有界失真映射）、LIM（局部內射映射）、AMIPS（能量函數）及ABF++（Fast and Robust Angle based flattening）基于角度空間的保角參數化算法作了大量的對比研究。從最大偏差、平均偏差和標準偏差對比到最大角度扭曲、均值角度扭曲及各種算法的運行時間等都進行了研究，最后得出結論：AMIPS（能量函數）的優點是能夠抑制網格曲面的最大變形，這樣就能進一步地控制變形分布，實現局部單射。AMIPS相對其他能量優化函數的計算速度僅次于ABF++，扭曲變形相對較小，能夠比較好地保持等距;ABF++算法計算速度快，但是會產生較大的偏差，從而造成曲面產生大的曲面變形;BDM算法雖可以限定扭曲上界，但不易選擇，算法運行時間長;LIM算法的優點是均值扭曲小，可是最大值扭曲高。每個算法都有其優缺點，可以根據不同場合及需要達到的效果進行選擇。

3 總結

網格參數化為了適應不同的場景有不同的參數化算法，從而獲得高質量的網格參數化。不論哪一種算法，其目的都是讓網格有較小的扭曲，減少變形量，降低失真性。這需要運用不同的數學算法對原始網格信息進行處理。文中通過保角度、保面積、保特征、柱面特征族及能量函數等方法，使參數化簡單化，原始網格失真性低來對圖形進行處理。這個過程需要涉及很多領域，如逼近理論、應用數學和有限元建模、數字圖像處理等。本文中提到的參數化算法，只是網格參數化中的一小部分，還有半自動網格參數、自動網格參數化、全局參數化、局部參數化等，需要我們不斷學習和研究。

參 考 文 獻

[1]郭鳳華，張彩明，焦文江.網格參數化研究進展[J].軟件學報，2016，27（1）：112-135.

[2]錢江，陳志楊，葉修梓，等.基于參數化技術的網格分割[J].浙江大學學報（工學版），2008（8）：1370-1375.

[3]張磊，劉利剛，王國瑾.保相似的網格參數化[J]. 中國圖象圖形學報，2008，13（12）：2383-2387.

[4]彭威，陳文亮.基于鄰域多邊形特征和能量優化的網格參數化[J].中國機械工程，2011，22（22）：2694-2699.

[5]閆婷，齊美彬，蔣建國，等.基于ARAP參數化算法的約束紋理映射[J].合肥工業大學學報（自然科學版），2017，40（6）：757-762.

[6]許晨旸，李靜蓉，王清輝，等.利用ABF++保角參數化的網格曲面刀軌規劃[J].計算機輔助設計與圖形學學報，2017，29（4）：728-733.

[7]郭瀟晟，郭延文，郭凱，等.骨架引導的網格模型圓柱面參數化[J].計算機輔助設計與圖形學學報，2011，23（1）：161-169.

[8]Myles A，Zorin D.Global parametrization by incremental flattening[J].ACM Trans. on Graphics，2012，31（4）：109-111.

[9]Liu L，Zhang L，Xu Y，et al.A local/global approach to mesh parameterization[J].Computer Gr-aphics Forum，2008，27（5）：1495-1504.

[10]Wu H，Pan C，Zha H，et al.Partwise cross-parameterization via nonregular convex hull domains. IEEE Trans[J].on Visualization and Computer Gra-phics，2011，17（10）：1531-1544.

[11]Zayer R，Rssl C，Seidel HP.Curvilinear spherical parameterization. In：Proc. of the 2006 Intl Conf.on Shape Modeling and Applications（SMI 2006）[J].IEEE Computer Society，2006（4）：57-64.

[12]Fu X，Liu Y，Guo B.Computing locally injective mappings by advanced MIPS[J]. ACM Trans. on Graphics，2015，34（4）：71-72.

[責任編輯：陳澤琦]