淺談網(wǎng)格參數(shù)化算法及應(yīng)用

周麗勤 顧立志

【摘 要】網(wǎng)格參數(shù)化不僅可以應(yīng)用在計(jì)算機(jī)圖形學(xué)，還可以應(yīng)用在計(jì)算機(jī)幾何設(shè)計(jì)及逆向工程、虛擬技術(shù)等諸多領(lǐng)域。文章根據(jù)不同的參數(shù)域，簡述了網(wǎng)格參數(shù)化的不同算法及各種算法在不同領(lǐng)域的應(yīng)用和優(yōu)缺點(diǎn)，并簡述如何控制參數(shù)化變形的方法。

【關(guān)鍵詞】網(wǎng)格參數(shù)化;參數(shù)域;控制參數(shù)變形

【中圖分類號(hào)】TP391.7 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688（2019）05-0113-03

在計(jì)算機(jī)圖形學(xué)、逆向工程、增材制造、虛擬技術(shù)等領(lǐng)域的幾何模型大部分是以網(wǎng)格的形式表示。網(wǎng)格模型所表達(dá)的物體數(shù)據(jù)是凌亂、離散、無序、難以利用的。直接處理這些網(wǎng)格模型是比較困難的。網(wǎng)格參數(shù)化是指為網(wǎng)格模型表面建立一一映射的參數(shù)域，映射后得到的參數(shù)化網(wǎng)格的拓?fù)潢P(guān)系同構(gòu)于原始曲面網(wǎng)格，且?guī)缀味攘康淖冃巫钚』?。從而對?fù)雜網(wǎng)格模型的處理可以轉(zhuǎn)化為相對簡單的參數(shù)化網(wǎng)格處理。

網(wǎng)格參數(shù)化方法可根據(jù)參數(shù)域的不同分為平面參數(shù)化、基網(wǎng)格參數(shù)化、球面參數(shù)化、柱面參數(shù)化及交叉參數(shù)化。不同的網(wǎng)格參數(shù)化方法都被不同程度地應(yīng)用到網(wǎng)格紋理映射、網(wǎng)格重構(gòu)、網(wǎng)格壓縮編輯[2]等領(lǐng)域。

1 網(wǎng)格參數(shù)域的分類

1.1 平面參數(shù)化

平面參數(shù)化是把一個(gè)空間三角網(wǎng)格盡可能均勻地?cái)偲降侥硞€(gè)平面區(qū)域，平面參數(shù)化是目前研究得最多、最簡單的參數(shù)化算法。Floater在Tutte等人提出凸組合方法的基礎(chǔ)上給每條邊附加一個(gè)與邊長相關(guān)的權(quán)值，進(jìn)面得出改進(jìn)后的凸組合方法。Floater提出保形參數(shù)化和均值參數(shù)的研究，一般是先固定網(wǎng)格邊界，用線性函數(shù)作為變形度量，這樣計(jì)算相對簡單，但得不到自由邊界的網(wǎng)格參數(shù)化結(jié)果，只能應(yīng)用于與拓?fù)鋱A盤同構(gòu)的網(wǎng)格曲面。所以，對于虧格大于0的網(wǎng)格曲面，如果按一定規(guī)則來劃分網(wǎng)格，往往會(huì)引起參數(shù)化結(jié)果不連續(xù)，并且在某些部位容易造成較大的變形[1]。

1.1.1 保相似的平面參數(shù)化

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

1.1.2 基于鄰域多邊形特征的網(wǎng)格參數(shù)化

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

1.1.3 ARAP參數(shù)化

Liu等人[9]提出一種可以在保角和保面積中，取得較好的平衡的非線性能量函數(shù)，這種函數(shù)算法僅適用于與拓?fù)鋱A盤同構(gòu)的網(wǎng)格曲面，不足之處在于此算法無法保證局部單射[1]。后來Myles等人[8]在ARAP算法的基礎(chǔ)上，改進(jìn)了ARAP算法，使之更能適用于全局參數(shù)。解決方法如下：將ARAP參數(shù)化方法從拓?fù)鋱A盤曲面拓展到三維網(wǎng)格曲面。用全局參數(shù)化算法優(yōu)化等距誤差。此能量函數(shù)方法可以在保角和保面積中取得較好的平衡，不會(huì)因?yàn)闉榱吮＝鞘沟妹娣e發(fā)生很大的變形。

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

1.1.4 ABF++保角參數(shù)化

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

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

1.2 基網(wǎng)格參數(shù)化

基網(wǎng)格參數(shù)化屬于全局參數(shù)化，適用于虧格大于0的網(wǎng)格曲面?；W(wǎng)格參數(shù)化的主要優(yōu)點(diǎn)是可以保留原始網(wǎng)格的拓?fù)潢P(guān)系，減少后續(xù)參數(shù)處理所造成的變形。

基網(wǎng)格參數(shù)化算法是通過種子點(diǎn)構(gòu)造Voronoi圖，以及Voronoi圖的對偶Delaunay三角剖分形成的，之后使用調(diào)和映射計(jì)算內(nèi)部頂點(diǎn)的參數(shù)值。雖然之后有自適應(yīng)曲面參數(shù)化、三角基網(wǎng)格、四邊形基網(wǎng)格[1]。

1.3 球面參數(shù)化

球面參數(shù)化的研究方法有球面松弛法、嚴(yán)寒冰等人提出的采用球面坐標(biāo)計(jì)算凸組合球面參數(shù)化的凸組合法及周昆等人提出的累進(jìn)網(wǎng)格方法。

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

1.4 柱面參數(shù)化

郭瀟晟等人[7]對于形態(tài)接近于圓柱或具有單支簡單骨架的封閉、半封閉的網(wǎng)格模型，提出一種骨架引導(dǎo)的網(wǎng)格模型圓柱面參數(shù)化方法。

柱面參數(shù)化研究方法：先引入超柱面參數(shù)域定義，通過模型的簡化建立其與超柱面的基本映射關(guān)系，再將頂點(diǎn)反插入柱面參數(shù)域來恢復(fù)原模型拓?fù)?，進(jìn)而對初始參數(shù)化結(jié)果，運(yùn)用拉伸形變尺度的優(yōu)化，實(shí)現(xiàn)基本的柱面參數(shù)化;對于具有強(qiáng)骨架信息的復(fù)雜模型[7]，由于超柱面?zhèn)让婵烧?，超柱面參?shù)化適用于對0虧格封閉模型的參數(shù)化。并且對人體和動(dòng)物等可以通過骨架指引對人體、動(dòng)物等0虧格封閉模型進(jìn)行超圓柱面參數(shù)化，這樣減小了模型的幾何形變。相對于球面參數(shù)化，柱面參數(shù)化變形會(huì)小一點(diǎn)。

1.5 交叉參數(shù)化

與基網(wǎng)格參數(shù)化類似，交叉參數(shù)化通常需要一個(gè)公共參數(shù)域?？梢酝ㄟ^對原始網(wǎng)格進(jìn)行簡化作為基參數(shù)域，也可以通過自動(dòng)生成模板參數(shù)域及采用四邊形面片作為公共基參數(shù)域。交叉參數(shù)化一般應(yīng)用于曲面間變形及曲面混合（blending）等（如圖4所示）。

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

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

2 減輕參數(shù)變形方法

2.1 錐狀奇異點(diǎn)

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

2.2 變形能量優(yōu)化

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

3 總結(jié)

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

參 考 文 獻(xiàn)

[1]郭鳳華，張彩明，焦文江.網(wǎng)格參數(shù)化研究進(jìn)展[J].軟件學(xué)報(bào)，2016，27（1）：112-135.

[2]錢江，陳志楊，葉修梓，等.基于參數(shù)化技術(shù)的網(wǎng)格分割[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2008（8）：1370-1375.

[3]張磊，劉利剛，王國瑾.保相似的網(wǎng)格參數(shù)化[J]. 中國圖象圖形學(xué)報(bào)，2008，13（12）：2383-2387.

[4]彭威，陳文亮.基于鄰域多邊形特征和能量優(yōu)化的網(wǎng)格參數(shù)化[J].中國機(jī)械工程，2011，22（22）：2694-2699.

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

[6]許晨旸，李靜蓉，王清輝，等.利用ABF++保角參數(shù)化的網(wǎng)格曲面刀軌規(guī)劃[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2017，29（4）：728-733.

[7]郭瀟晟，郭延文，郭凱，等.骨架引導(dǎo)的網(wǎng)格模型圓柱面參數(shù)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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.

[責(zé)任編輯：陳澤琦]