蔡興泉 孫辰 葛亞坤

摘 要：針對(duì)當(dāng)前網(wǎng)格參數(shù)化效率較低、映射失真較嚴(yán)重的問(wèn)題，提出一種限制失真的網(wǎng)格參數(shù)化方法。首先，預(yù)處理原始網(wǎng)格模型。輸入原3D網(wǎng)格模型，采用Half-Edge數(shù)據(jù)結(jié)構(gòu)來(lái)重新組織網(wǎng)格并切割網(wǎng)格模型產(chǎn)生相應(yīng)的切縫;構(gòu)建Tutte映射把3D網(wǎng)格映射到一個(gè)2D凸多邊形域，即構(gòu)建2D網(wǎng)格模型。然后，進(jìn)行限制失真的網(wǎng)格參數(shù)化計(jì)算。將Tutte映射后的2D網(wǎng)格模型作為限制失真計(jì)算的初始數(shù)據(jù)，建立相對(duì)于原3D模型網(wǎng)格的失真度量函數(shù);求得該度量函數(shù)的最小值點(diǎn)，即為映射后的網(wǎng)格坐標(biāo)集合;將映射后的網(wǎng)格作為限制失真映射的輸入網(wǎng)格，設(shè)定迭代終止條件，循環(huán)迭代直至迭代結(jié)束，得到收斂的最優(yōu)網(wǎng)格坐標(biāo);在計(jì)算映射失真度時(shí)，針對(duì)等距映射失真采用Dirichlet能量函數(shù)度量，針對(duì)共形映射失真采用盡可能等距（MIPS）能量函數(shù)度量;在求解映射失真度量函數(shù)的最小值點(diǎn)時(shí)采用代理函數(shù)法結(jié)合組合牛頓法的最優(yōu)解方法。最終，實(shí)現(xiàn)了該方法并開(kāi)發(fā)了一個(gè)原型系統(tǒng)。在原型系統(tǒng)中，分別設(shè)計(jì)了限制等距失真和限制共形失真的網(wǎng)格參數(shù)化實(shí)驗(yàn)，對(duì)程序執(zhí)行時(shí)間和失真能量下降情況進(jìn)行了統(tǒng)計(jì)和對(duì)比，提供了相應(yīng)的紋理映射效果展示。實(shí)驗(yàn)數(shù)據(jù)表明，所提出的方法執(zhí)行效率高、映射失真能量下降快，最優(yōu)值收斂質(zhì)量穩(wěn)定;紋理映射時(shí)紋理著色均勻、布局緊致、線條均勻，符合實(shí)際應(yīng)用的標(biāo)準(zhǔn)。

關(guān)鍵詞：網(wǎng)格參數(shù)化;限制失真;等距映射;共形映射;能量函數(shù);最優(yōu)坐標(biāo)點(diǎn)

中圖分類(lèi)號(hào)： TP391.9

文獻(xiàn)標(biāo)志碼：A

Abstract：Aiming at the low efficiency and serious mapping distortion of current mesh parameterization， a mesh parameterization method with limiting distortion was proposed. Firstly， the original mesh model was pre-processed. After inputting the original 3D mesh model， the Half-Edge data structure was used to reorganize the mesh and the corresponding seams were generated by cutting the mesh model. The Tutte mapping was constructed to map the 3D mesh to a 2D convex polygon domain， that is to construct the 2D mesh model. Then， the mesh parameterization calculation with limiting distortion was performed. The Tutte-mapped 2D mesh model was used as the initial data for limiting distortion calculation， and the distortion metric function relative to the original 3D model mesh was established. The minimum value points of the metric function were obtained， which form the mapped mesh coordinate set. The mapped mesh was used as the input mesh to limit the distortion mapping， and the iteration termination condition was set. The iteration was performed cyclically until the termination? condition was satisfied， and the convergent optimal mesh coordinates were obtained. In calculating the mapping distortion， the Dirichlet energy function was used to measure the isometric mapping distortion， and the Most Isometric Parameterizations （MIPS） energy function was used for the conformal mapping distortion. The minimum of the mapping distortion energy function was solved by proxy function combining assembly-Newton method. Finally， this method was implemented and a prototype system was developed. In the prototype system， mesh parameterization experiments for limiting isometric distortion and limiting conformal distortion were designed respectively， statistics and comparisons of program execution time and distortion energy falling were performed， and the corresponding texture mapping effects were displayed. Experimental? results show that the proposed method has high execution efficiency， fast falling speed of mapping distortion energy and stable quality of optimal value convergence. When texture mapping is performed， the texture is evenly colored， close laid and uniformly lined， which meets the practical application standards.Key words：? mesh parameterization; limiting distortion; isometric mapping; conformal mapping; energy function; optimal coordinate point

0 引言

網(wǎng)格參數(shù)化是數(shù)字幾何處理中的熱點(diǎn)和難點(diǎn)[1]。網(wǎng)格參數(shù)化的任務(wù)是將三維空間的網(wǎng)格映射到二維空間，稱(chēng)為平面參數(shù)化。網(wǎng)格參數(shù)化可用在紋理映射、網(wǎng)格變形、網(wǎng)格編輯等領(lǐng)域。

最初，數(shù)學(xué)家Tutte[2]證明了網(wǎng)格模型任何一個(gè)頂點(diǎn)的坐標(biāo)可表示為其鄰接頂點(diǎn)坐標(biāo)的加權(quán)組合，提出了邊界域凸組合映射，為網(wǎng)格參數(shù)化提供了理論基礎(chǔ)。在映射計(jì)算時(shí)，容易產(chǎn)生失真，如三角網(wǎng)格的邊長(zhǎng)可能會(huì)變，三角網(wǎng)格的內(nèi)角可能會(huì)變。三角網(wǎng)格的邊長(zhǎng)在映射前后發(fā)生變化稱(chēng)為等距失真;三角網(wǎng)格的內(nèi)角在映射前后發(fā)生變化稱(chēng)為共形失真。但是，Tutte算法在映射的過(guò)程中并沒(méi)有對(duì)映射失真進(jìn)行約束。Hormann等[3]提出了保證無(wú)網(wǎng)格翻轉(zhuǎn)的映射，以保證網(wǎng)格不發(fā)生翻轉(zhuǎn)并降低映射產(chǎn)生的失真。Lipman[4]于2012年提出了限定失真的映射，設(shè)定了失真閾值，從而進(jìn)一步減少映射帶來(lái)的失真，并拓寬了網(wǎng)格參數(shù)化的應(yīng)用范圍。受該方法啟發(fā)，本文主要研究限制失真的網(wǎng)格參數(shù)化方法。

在限制失真時(shí)，需要構(gòu)建映射失真度量函數(shù)。關(guān)于等距失真映射，Hormann提出了盡可能等距（Most Isometric Parameterizations， MIPS）能量函數(shù)，Alexa等[5]提出盡可能剛體（As Rigid As Possible， ARAP）能量函數(shù)，Smith等[6]于2015年提出了對(duì)稱(chēng)狄利克雷（Symmetric Dirichlet， Dirichlet）能量函數(shù)。關(guān)于共形失真映射，Sorkine等[7]提出了比值能量函數(shù)，隨后又在文獻(xiàn)[8]中提出了盡可能相似（As Similar As Possible， ASAP）能量函數(shù)。綜合考慮能量函數(shù)的度量精確性和易優(yōu)化性，本文選用狄利克雷能量函數(shù)作為等距映射的失真度量函數(shù)，選用盡可能等距能量函數(shù)作為共形映射的失真度量函數(shù)。

映射失真函數(shù)的最優(yōu)坐標(biāo)解依賴(lài)于數(shù)值最優(yōu)化方法。文獻(xiàn)[9]中常用的數(shù)值優(yōu)化方法有梯度下降法、牛頓法、擬牛頓法等。失真度量函數(shù)通常是非線性非凸的，有些能量函數(shù)帶有約束項(xiàng)。因此，需要改進(jìn)這些最優(yōu)化方法以解決最優(yōu)坐標(biāo)快速求解問(wèn)題。對(duì)于梯度下降法，主要是根據(jù)原函數(shù)的一階導(dǎo)數(shù)確定下降方向。Kovalsky等[10]于2016年提出利用網(wǎng)格的Laplacian矩陣確定能量函數(shù)初始的下降方向。該方法在迭代前期失真下降較快，但是由于一階導(dǎo)數(shù)缺少自由度之間的耦合信息，導(dǎo)致在迭代后期收斂質(zhì)量和效率較差。Rabinovich等[11]于2018年提出了代理函數(shù)方法，將難以優(yōu)化求解的度量函數(shù)轉(zhuǎn)化為易優(yōu)化的簡(jiǎn)單函數(shù)，利用局部全局（Local-Global）的思想結(jié)合代理函數(shù)的一階導(dǎo)數(shù)信息確定下降方向。該方法在最優(yōu)值求解迭代初期，能量下降速度很快。對(duì)于牛頓法，主要利用能量函數(shù)的Hessian矩陣確定原函數(shù)下降方向，要保持Hessian的正定。為此，Teran等[12]提出了投影牛頓法，對(duì)Hessian矩陣進(jìn)行特征值分解，將非正的特征值設(shè)定為較小的正值，保持了矩陣的正定，從而保持了最優(yōu)解的穩(wěn)定性。該方法在實(shí)際求解過(guò)程中其計(jì)算過(guò)于復(fù)雜，時(shí)間復(fù)雜度表現(xiàn)較差。Shtengel等[13]提出組合牛頓法，對(duì)失真函數(shù)進(jìn)行局部凸化，把非凸函數(shù)轉(zhuǎn)化為凸函數(shù)，并保持Hessian正定，保證了最優(yōu)解的收斂穩(wěn)定性和求解的效率。對(duì)于擬牛頓法，則介于梯度下降法和牛頓法之間，主要思想是利用一階導(dǎo)數(shù)信息來(lái)近似二階導(dǎo)數(shù)確定下降方向。Nocedal提出了低內(nèi)存占用的擬牛頓法，此方法解決與初始解的選取無(wú)關(guān)的優(yōu)化問(wèn)題的能力較弱。為了在最優(yōu)坐標(biāo)解的求解中充分利用各種優(yōu)化方法的優(yōu)勢(shì)，當(dāng)初始解離最優(yōu)解距離較遠(yuǎn)時(shí)，用代理函數(shù)法求解最優(yōu)坐標(biāo);在當(dāng)前解離最優(yōu)解距離較近時(shí)，用組合牛頓法求解最優(yōu)坐標(biāo)。

當(dāng)前網(wǎng)格參數(shù)化算法效率較低、映射失真較嚴(yán)重，本文主要研究限制失真的網(wǎng)格參數(shù)化方法。首先預(yù)處理原始網(wǎng)格模型，然后進(jìn)行限制失真的網(wǎng)格參數(shù)化計(jì)算。

1 預(yù)處理原始網(wǎng)格模型

在進(jìn)行網(wǎng)格參數(shù)化運(yùn)算前，需要預(yù)處理原始網(wǎng)格模型。首先，輸入的是原網(wǎng)格模型OriginalModel。該網(wǎng)格模型是以頂點(diǎn)集和面片集為存儲(chǔ)格式的3D網(wǎng)格模型。這種3D網(wǎng)格模型是網(wǎng)格建模常用的存儲(chǔ)結(jié)構(gòu);然后，采用OpenMesh網(wǎng)格處理庫(kù)中高效的Half-Edge數(shù)據(jù)結(jié)構(gòu)來(lái)重新組織網(wǎng)格數(shù)據(jù);接著，切割網(wǎng)格模型，產(chǎn)生Seam，即在模型上產(chǎn)生相應(yīng)的切縫;最后，利用切割好的模型構(gòu)建Tutte映射，把3D網(wǎng)格映射到一個(gè)2D凸多邊形域，即2D網(wǎng)格模型。

1.1 切割網(wǎng)格模型

輸入原網(wǎng)格模型，利用Half-Edge數(shù)據(jù)結(jié)構(gòu)來(lái)重新組織網(wǎng)格數(shù)據(jù)后，對(duì)原3D網(wǎng)格模型進(jìn)行切割，產(chǎn)生切縫。目的是將虧格大于1、有多個(gè)洞的模型轉(zhuǎn)化為虧格為0、無(wú)洞的片狀拓?fù)淠Ｐ汀?/p>

對(duì)原3D網(wǎng)格模型進(jìn)行切割時(shí)，有兩種方法，即Seamster網(wǎng)格切割法和幾何圖像法。Seamster網(wǎng)格切割法根據(jù)3D模型的高曲率點(diǎn)和模型中不可視區(qū)域確定切線，采用最小Steiner樹(shù)算法盡量縮短切縫長(zhǎng)度;幾何圖像法采用網(wǎng)格參數(shù)化與網(wǎng)格切割交替迭代，將參數(shù)化失真嚴(yán)重的點(diǎn)作為下次切割的切點(diǎn)。

在實(shí)現(xiàn)時(shí)，本文用這兩種方法完成網(wǎng)格模型切割。這兩種方法都是運(yùn)用代數(shù)拓?fù)淅碚摫ＷC切線能把任意虧格的模型轉(zhuǎn)化為虧格為0的開(kāi)網(wǎng)格。

1.2 構(gòu)建Tutte映射

由于Tutte映射既可以保證網(wǎng)格不發(fā)生翻轉(zhuǎn)，又可以保證映射后的網(wǎng)格不發(fā)生交叉，即可保證雙射。因此，本文在完成切割網(wǎng)格模型后，對(duì)模型構(gòu)建Tutte映射，為后續(xù)參數(shù)化計(jì)算做好準(zhǔn)備。

對(duì)模型構(gòu)建Tutte映射時(shí)，首先將網(wǎng)格模型的邊界頂點(diǎn)集序列組成凸多邊形的邊界頂點(diǎn)集序列。邊界頂點(diǎn)較多，因此所圍成的凸多邊形邊界近似一個(gè)圓。本文在實(shí)現(xiàn)時(shí)，將凸多邊形邊界頂點(diǎn)集序列依次平均分布在一個(gè)單位圓上。

然后，解重心坐標(biāo)映射方程（1）得到此凸多邊形區(qū)域所有內(nèi)點(diǎn)的坐標(biāo)。

這些內(nèi)點(diǎn)的坐標(biāo)即構(gòu)建Tutte映射后的2D網(wǎng)格頂點(diǎn)的坐標(biāo)。

重心坐標(biāo)映射方程把內(nèi)點(diǎn)坐標(biāo)的求解運(yùn)算轉(zhuǎn)化為線性系統(tǒng)的計(jì)算，也就是求解兩個(gè)線性系統(tǒng)Au=和Av=。在方程（1）中，向量u和向量v代表凸多邊形域所有內(nèi)點(diǎn)的（u， v）坐標(biāo)，向量和向量代表凸多邊形域所有邊界點(diǎn)的（u， v）坐標(biāo)。

2 限制失真的網(wǎng)格參數(shù)化計(jì)算

網(wǎng)格參數(shù)化計(jì)算最基本的要求是：保證映射計(jì)算后的2D網(wǎng)格模型無(wú)網(wǎng)格翻轉(zhuǎn)，即映射前后兩個(gè)階段的2D網(wǎng)格的三個(gè)頂點(diǎn)順序均按逆時(shí)針順序排列。在映射計(jì)算時(shí)，容易產(chǎn)生失真，包括等距失真和共形失真。在網(wǎng)格參數(shù)化計(jì)算的過(guò)程中，嚴(yán)格消除等距失真或共形失真是難以做到的，但是，采用限制失真的方法在映射計(jì)算中盡量減少失真是可行的。

本文采用限制失真的網(wǎng)格參數(shù)化計(jì)算，具體步驟如下：

Step1：將Tutte映射計(jì)算后的2D網(wǎng)格作為限制失真計(jì)算的初始數(shù)據(jù)，建立相對(duì)于原3D模型網(wǎng)格OriginalModel的失真度量函數(shù);

Step2：利用失真度量函數(shù)求得該度量函數(shù)的最小值點(diǎn)，即為映射后的網(wǎng)格坐標(biāo)集合;

Step3：將映射后的網(wǎng)格作為限制失真映射的輸入網(wǎng)格，設(shè)定迭代終止條件，循環(huán)迭代Step1～2，直至迭代結(jié)束，得到收斂的最優(yōu)網(wǎng)格坐標(biāo)。

2.1 構(gòu)建失真度量函數(shù)

網(wǎng)格參數(shù)化的處理過(guò)程實(shí)際上是每個(gè)網(wǎng)格的映射過(guò)程。該映射類(lèi)型為分段線性映射。該映射定義在每個(gè)三角網(wǎng)格上，表達(dá)式如式（3）所示：

其中：J是映射函數(shù)的Jacobian二階矩陣，決定了映射的性質(zhì);b是位移平移量，為一個(gè)常量向量，在實(shí)際使用時(shí)一般用零向量代替;x、 y是映射前的網(wǎng)格頂點(diǎn)坐標(biāo);u和v是映射后的網(wǎng)格頂點(diǎn)坐標(biāo)。無(wú)網(wǎng)格翻轉(zhuǎn)的約束條件為J的行列式值大于0。

計(jì)算映射失真度需要建立失真刻畫(huà)精確、計(jì)算簡(jiǎn)單、容易求得最小值的失真度量函數(shù)。鑒于此，采用Dirichlet能量函數(shù)度量等距映射失真，采用MIPS能量函數(shù)度量共形映射失真。

2.1.1 基于Dirichlet能量函數(shù)度量的等距映射

等距映射保持三角網(wǎng)格的邊長(zhǎng)在映射前后不變。由于Jacobian矩陣決定了變換的幾何性質(zhì)，J的特征值決定了J的性質(zhì)，故能量函數(shù)主要以J的特征值為變量。Dirichlet能量函數(shù)描述如式（4）所示：

共形映射保證映射前后網(wǎng)格的內(nèi)角不變，即保證相似性。MIPS能量函數(shù)最初用來(lái)約束等距映射失真，但是其約束目標(biāo)主要是σ1=σ2，更傾向于共形映射的約束目標(biāo)，對(duì)等距失真的約束效果不如Dirichlet函數(shù)，所以用它作為共形映射的失真能量函數(shù)。此函數(shù)同樣具有計(jì)算量小、度量精確、魯棒性強(qiáng)等特點(diǎn)，MIPS能量函數(shù)描述如式（6）所示：

2.2 基于能量函數(shù)求解最優(yōu)坐標(biāo)點(diǎn)

映射失真度量函數(shù)的最小值點(diǎn)是映射后網(wǎng)格的最優(yōu)坐標(biāo)點(diǎn)?？紤]到數(shù)值最優(yōu)化方法各有優(yōu)勢(shì)，采用代理函數(shù)法結(jié)合組合牛頓法的最優(yōu)解方法。為了加速失真能量的下降，在前期失真能量值高的迭代步引入了參考網(wǎng)格，用參考網(wǎng)格代替原3D模型網(wǎng)格建立能量函數(shù);接著利用此最優(yōu)解方法求解映射后最優(yōu)坐標(biāo)，優(yōu)化方法采用全局優(yōu)化。通過(guò)數(shù)學(xué)理論分析結(jié)合實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)得出實(shí)驗(yàn)的控制參數(shù)，參數(shù)具有普遍意義，對(duì)于不同的數(shù)據(jù)集有良好的魯棒性。

當(dāng)失真能量下降率大于0.1時(shí)采用代理函數(shù)法;當(dāng)能量下降率小于0.1大于0.01時(shí)采用組合牛頓法;當(dāng)能量下降率小于0.001時(shí)，就不再建立參考網(wǎng)格，直接用組合牛頓法迭代得出最優(yōu)解。對(duì)于Dirichlet能量函數(shù)，當(dāng)能量梯度范數(shù)小于1×10-6時(shí)迭代停止;對(duì)于MIPS能量函數(shù)，當(dāng)能量梯度范數(shù)小于1×10-4時(shí)迭代停止，最大迭代步數(shù)為100。

2.2.1 基于梯度下降的代理函數(shù)最優(yōu)坐標(biāo)解法

代理函數(shù)法的主要思想是通過(guò)優(yōu)化比能量函數(shù)更易優(yōu)化的代理能量函數(shù)來(lái)間接優(yōu)化能量函數(shù)，而代理能量的優(yōu)化可以看作盡可能剛體失真能量的局部全局優(yōu)化方法的推廣。該方法的代理函數(shù)P（x）寫(xiě)成式（8）的形式：

其中：矩陣U和V是當(dāng)前Jacobian矩陣做特征值分解后的兩個(gè)旋轉(zhuǎn)矩陣;k指當(dāng)前第k次迭代;λ取1×10-4;A表示網(wǎng)格的面積; f表示每個(gè)三角網(wǎng)格;‖·‖表示求矩陣的歐氏范數(shù);SJ是Jacobian矩陣的特征值矩陣;D（SJ）是失真能量函數(shù);

Λ為一個(gè)常量矩陣，根據(jù)失真能量函數(shù)確定。對(duì)于Dirichlet能量函數(shù)，旋轉(zhuǎn)矩陣的特征值矩陣SΛ兩個(gè)值均為1;對(duì)于MIPS能量函數(shù)，SΛ兩個(gè)值均為σ1 σ2。

最后利用函數(shù)的一階導(dǎo)數(shù)求得代理函數(shù)的下降方向。

2.2.2 組合牛頓最優(yōu)坐標(biāo)解法

組合牛頓法的主要思想是把非凸的失真能量函數(shù)做局部凸化轉(zhuǎn)化為凸函數(shù)，再用牛頓法得出函數(shù)的下降方向。失真能量函數(shù)可寫(xiě)成復(fù)合函數(shù)，如式（11）所示：

最后利用所求得的Hessian矩陣確定能量函數(shù)的下降方向。

為求解能量函數(shù)的下降步長(zhǎng)，首先根據(jù)能量函數(shù)的下降方向確定所有網(wǎng)格發(fā)生翻轉(zhuǎn)時(shí)的步長(zhǎng)，并取所有步長(zhǎng)的最小值作為最大步長(zhǎng);接著根據(jù)最大步長(zhǎng)用基于Armijo準(zhǔn)則的回溯算法求得失真函數(shù)的實(shí)際下降步長(zhǎng);最后結(jié)合能量函數(shù)的下降方向和下降步長(zhǎng)得出映射后的網(wǎng)格坐標(biāo)，即本次迭代后的網(wǎng)格坐標(biāo)。

2.2.3 建立參考網(wǎng)格

遞進(jìn)參數(shù)化的思想主要是建立參考網(wǎng)格代替原模型網(wǎng)格。本文在實(shí)現(xiàn)遞進(jìn)參數(shù)化的計(jì)算時(shí)，具體步驟如下：

Step1：首先設(shè)定一個(gè)失真閾值，然后根據(jù)前一個(gè)迭代步結(jié)束后生成的模型網(wǎng)格，再結(jié)合原模型網(wǎng)格建立能量函數(shù)，最后根據(jù)能量函數(shù)確定映射函數(shù)Jacobian矩陣的特征值，再結(jié)合原模型網(wǎng)格計(jì)算得到參考網(wǎng)格;

Step2：首先由前一個(gè)迭代步產(chǎn)生的模型網(wǎng)格結(jié)合當(dāng)前的參考網(wǎng)格建立能量函數(shù)，然后求解能量函數(shù)的最優(yōu)坐標(biāo)值得出當(dāng)前迭代步的模型網(wǎng)格;

Step3：設(shè)定迭代終止條件，循環(huán)迭代Step1和Step2，直至迭代結(jié)束，得到收斂的最優(yōu)網(wǎng)格坐標(biāo)。

遞進(jìn)參數(shù)化的原理是，較高的失真能量會(huì)影響最優(yōu)解的求解速度。采用建立參考網(wǎng)格的方法，每次優(yōu)化一個(gè)較小的失真，可以提高優(yōu)化的效率。特別在選用了產(chǎn)生高失真能量值的能量函數(shù)，或迭代初始點(diǎn)離最優(yōu)解距離較遠(yuǎn)時(shí)使用效果更佳。但此方法會(huì)增加內(nèi)存的開(kāi)銷(xiāo)，故迭代次數(shù)不宜過(guò)多，當(dāng)失真能量降到一個(gè)較低的水平時(shí)，此方法沒(méi)有明顯優(yōu)勢(shì)。對(duì)Dirichlet能量約束的等距映射，首先采用指數(shù)插值法讓失真能量值等于200，方程如式（15）所示：

然后對(duì)每個(gè)網(wǎng)格用牛頓求根法計(jì)算t值。接著對(duì)所有網(wǎng)格取t的最小值，以最小值作為參數(shù)求得新的Jacobian矩陣特征值，最后根據(jù)特征值求出每個(gè)參考網(wǎng)格的頂點(diǎn)。對(duì)MIPS能量約束的共形映射，直接采用線性插值法根據(jù)約束目標(biāo)迭代讓特征值相互接近，失真能量值小于3時(shí)迭代停止，取當(dāng)前的特征值，以此求得參考網(wǎng)格的頂點(diǎn)坐標(biāo)。

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

本文設(shè)計(jì)并實(shí)現(xiàn)了所提出的限制失真的網(wǎng)格參數(shù)化方法，并開(kāi)發(fā)了一個(gè)驗(yàn)證系統(tǒng)。本文實(shí)驗(yàn)中所采用的輸入模型選自法國(guó)INRIA的Unwarpped Meshes網(wǎng)格模型庫(kù)和中國(guó)科技大學(xué)的Disk-topology Meshes網(wǎng)格模型庫(kù)。實(shí)驗(yàn)中的牛、兔、手掌模型取自Unwarpped Meshes庫(kù)，魚(yú)、人、玩偶模型取自Disk-topology Meshes網(wǎng)格模型庫(kù)。牛模型網(wǎng)格數(shù)量為69451個(gè)，兔模型網(wǎng)格數(shù)量為34504個(gè)，手掌模型網(wǎng)格數(shù)量為72598個(gè)，魚(yú)模型網(wǎng)格數(shù)量為16428個(gè)，人模型網(wǎng)格數(shù)量為19012個(gè)，玩偶模型網(wǎng)格數(shù)量為25082個(gè)。實(shí)驗(yàn)硬件環(huán)境為Intel Core i7 7700 HQ，2.8GHz，四核心八線程CPU，Samsung 2400MHz 8GB內(nèi)存，NVIDIA 1050 Ti 4GB顯卡，Windows 10 操作系統(tǒng)的筆記本電腦。在實(shí)現(xiàn)驗(yàn)證系統(tǒng)時(shí)，采用C++作為編程語(yǔ)言，采用Visual Studio 2017作為開(kāi)發(fā)工具。在進(jìn)行相關(guān)稀疏矩陣和稀疏向量的計(jì)算時(shí)，利用Eigen計(jì)算庫(kù)完成。

網(wǎng)格參數(shù)化計(jì)算非常注重運(yùn)行效率和映射失真的下降速度。失真分為等距失真和共形失真，因此，本文設(shè)計(jì)了限制等距失真映射實(shí)驗(yàn)和限制共形失真映射實(shí)驗(yàn)。兩個(gè)實(shí)驗(yàn)均進(jìn)行了較為客觀的實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)和較為主觀的紋理映射效果展示。實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)包括程序執(zhí)行時(shí)間對(duì)比、失真能量下降情況對(duì)比等。在統(tǒng)計(jì)程序執(zhí)行時(shí)間數(shù)據(jù)時(shí)，分別對(duì)牛、兔、手掌、魚(yú)、人、玩偶等模型進(jìn)行1000次網(wǎng)格參數(shù)化計(jì)算，統(tǒng)計(jì)時(shí)間，最終求得平均值。在統(tǒng)計(jì)失真能量下降情況數(shù)據(jù)時(shí)，對(duì)每個(gè)模型迭代計(jì)算，統(tǒng)計(jì)相應(yīng)的失真能量值。在紋理映射的實(shí)驗(yàn)中，利用OpenGL紋理映射函數(shù)綁定參數(shù)化后的網(wǎng)格坐標(biāo)，即原模型的紋理坐標(biāo)，從而生成OriginalModel模型的紋理貼圖。

3.1 限制等距失真的網(wǎng)格參數(shù)化實(shí)驗(yàn)

限制等距失真的網(wǎng)格參數(shù)化執(zhí)行時(shí)間如表1所示。

從表1可看出：在處理相同模型時(shí)，本文算法程序執(zhí)行時(shí)間明顯比代理函數(shù)算法和組合牛頓算法短。

等距映射失真能量下降對(duì)比情況如圖1所示，取前10次迭代。通過(guò)對(duì)比可以看出，在失真能量下降速度方面，本文算法明顯比代理函數(shù)法和組合牛頓法下降速度快，收斂質(zhì)量?jī)?yōu)于代理函數(shù)法。

3.2 限制共形失真的網(wǎng)格參數(shù)化實(shí)驗(yàn)

限制共形失真的網(wǎng)格參數(shù)化執(zhí)行時(shí)間如表2所示。從表2可看出：在處理相同模型時(shí)，本文算法的程序執(zhí)行時(shí)間明顯比組合牛頓法的短，但比代理函數(shù)法稍長(zhǎng)。共形映射失真能量下降對(duì)比情況如圖3所示，取前10次迭代。通過(guò)對(duì)比可以看出，在失真能量下降速度方面，本文算法比代理函數(shù)法和組合牛頓法下降速度快，收斂質(zhì)量?jī)?yōu)于代理函數(shù)法。模型共形映射后的結(jié)果和紋理貼圖效果如圖4所示?？梢钥闯龈鲄^(qū)域紋理著色均勻，不同區(qū)域的紋理圖案具有相似性。

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

對(duì)映射實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析。對(duì)于等距映射，能量函數(shù)每一項(xiàng)均為平方項(xiàng)，所以在映射失真時(shí)所產(chǎn)生的能量值較大，遞進(jìn)式參數(shù)化策略在迭代前期能充分地發(fā)揮其優(yōu)勢(shì)。采用代理函數(shù)法結(jié)合組合牛頓的方法使得求解效率得到提高，既能發(fā)揮基于梯度下降的代理函數(shù)方法在前期迭代的快速下降的優(yōu)勢(shì)，又能發(fā)揮出牛頓法的二次收斂性和收斂穩(wěn)定性。對(duì)于共形映射，由于所選用的失真能量函數(shù)每一項(xiàng)是比值項(xiàng)，所以產(chǎn)生的失真能量值相對(duì)較小，建立參考網(wǎng)格需要一定的程序時(shí)間和內(nèi)存空間，所以最優(yōu)坐標(biāo)點(diǎn)的求解效率比等距映射低，但是相對(duì)于不采用參考網(wǎng)格的方法在程序時(shí)間上和優(yōu)化結(jié)果上仍有優(yōu)勢(shì)。值得注意的是，在迭代前期單獨(dú)使用代理函數(shù)法優(yōu)化效率較高，但隨著迭代次數(shù)增加，當(dāng)前解逐漸靠近最優(yōu)解時(shí)收斂速度很慢。

從紋理映射效果上直觀分析，對(duì)于等距映射，映射產(chǎn)生的紋理效果布局緊致，紋理?xiàng)l紋呈現(xiàn)均勻，但在局部區(qū)域出現(xiàn)角度失真。對(duì)于共形映射，紋理布局在局部區(qū)域呈現(xiàn)松弛，出現(xiàn)距離失真，但是不同區(qū)域的相似性得到了體現(xiàn)，各區(qū)域紋理著色均勻，對(duì)于角度的失真約束更加可觀。在實(shí)際應(yīng)用中，在對(duì)距離失真和紋理的均勻性要求嚴(yán)格的情況下，建議采用等距映射的參數(shù)化方法，在對(duì)角度失真和紋理的相似性要求嚴(yán)格的情況下，建議采用共形映射參數(shù)化。經(jīng)實(shí)驗(yàn)分析，該算法的魯棒性強(qiáng)，參數(shù)化結(jié)果對(duì)參數(shù)的調(diào)整很穩(wěn)定。

4 結(jié)語(yǔ)

針對(duì)當(dāng)前網(wǎng)格參數(shù)化效率較低、映射失真較嚴(yán)重的問(wèn)題，本文提出了一種限制失真的網(wǎng)格參數(shù)化方法。首先，預(yù)處理原始網(wǎng)格模型。然后，進(jìn)行限制失真的網(wǎng)格參數(shù)化計(jì)算。在計(jì)算映射失真度時(shí)，采用Dirichlet能量函數(shù)度量等距映射失真;采用MIPS能量函數(shù)度量共形映射失真。在求解映射失真度量函數(shù)的最小值點(diǎn)時(shí)，采用代理函數(shù)法結(jié)合組合牛頓法的最優(yōu)解方法。最終設(shè)計(jì)并實(shí)現(xiàn)了該限制失真的網(wǎng)格參數(shù)化方法，開(kāi)發(fā)了一個(gè)驗(yàn)證系統(tǒng)，分別設(shè)計(jì)了限制等距失真和限制共形失真的網(wǎng)格參數(shù)化實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)表明，本文方法執(zhí)行效率高，映射失真能量下降快，最優(yōu)值收斂質(zhì)量穩(wěn)定;紋理映射時(shí)，紋理著色均勻、布局緊致、線條均勻、符合實(shí)際應(yīng)用的標(biāo)準(zhǔn)。該方法可用在紋理映射、網(wǎng)格變形、網(wǎng)格編輯等領(lǐng)域。

下一步研究工作包括將本文方法擴(kuò)展，應(yīng)用于二維網(wǎng)格模型變形、三維網(wǎng)格模型變形、網(wǎng)格編輯、形狀插值、網(wǎng)格質(zhì)量提升等工作中。

參考文獻(xiàn)（References）

[1] 郭鳳華， 張彩明， 焦文江. 網(wǎng)格參數(shù)化研究進(jìn)展[J]. 軟件學(xué)報(bào)， 2016， 27（1）： 112-135（GUO F H， ZHANG C M， JIAO W J. Research progress on mesh parameterization[J]. Journal of Software， 2016， 27（1）： 112-135）.

[2] TUTTE W T. How to draw a graph[J]. Proceedings of the London Mathematical Society， 1963， 3（1）： 743-767.

[3] HORMANN K， GREINER G. MIPS： an efficient global parameterization method[EB/OL]. [2019-01-10]. https：//pdfs.semanticscholar.org/02e4/f09c9a6d0d770d31c9289d30b7b4e9b5d974.pdf.

[4] LIPMAN Y. Bounded distortion mapping spaces for triangular meshes[J]. ACM Transactions on Graphics， 2012， 31（4）： 108.

[5] ALEXA M， COHEN-OR D， LEVIN D. As-rigid-as-possible shape interpolation[C]// Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 2000： 157-164.

[6] SMITH J， SCHAEFER S. Bijective parameterization with free boundaries[J]. ACM Transations on Graphics， 2015， 34（4）： 70.

[7] SORKINE O， COHEN-OR D， GOLDENTHAL R. Bounded-distortion piecewise mesh parameterization[C]// Proceedings of the 2002 Conference on Visualization. Piscataway： IEEE， 2002： 355-362.

[8] SORKINE O， ALEXA M. As-rigid-as-possible surface modeling[C]// Proceedings of the 5th Eurographics Symposium on Geometry Processing. Aire-la-Ville， Switzerland： Eurographics Association， 2007： 109-116.

[9] NOCEDAL J， WRINGT S J. Numerical Optimization[M]. Berlin： Springer， 1999： 1-10.

[10] KOVALSKY S Z， GALUN M， LIPMAN Y. Accelerated quadratic proxy for geometric optimization[J]. ACM Transactions on Graphics， 2016， 35（4）： 134.

[11] RABINOVICH M， PORANNE R， PANOZZO D， et al. Scalable locally injective maps[J]. ACM Transactions on Graphics， 2017， 36（4）： 37a.

[12] TERAN J， SIFAKIS E， IRVING G， et al. Robust quasi static finite elements and mesh simulation[C]// Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York： ACM， 2005： 181-190.

[13] SHETENGEL A， PORANNE R， SORKINE-HORNUNG O， et al. Geometric optimization via composite majorization[J]. ACM Transactions on Graphics， 2017， 36（4）： 38.

[14] SHEFFER A， HART J C. Seamster： inconspicuous low-distortion texture seam layout[C]// Proceedings of the 2002 Conference on Visualization. Piscataway： IEEE， 2002： 291-298.

[15] GU X F， STEVEN J G， HOPPE H. Geometry images[J]. ACM Transactions on Graphics， 2002， 21（3）： 355-361.

[16] FLOATER M S. One-to-one piecewise linear mappings over triangulations[J]. Mathematics of Computation， 2003， 72（242）： 685-696.

[17] LIU L， YE C， NI R， et al. Progressive parameterizations[J]. ACM Transations on Graphics， 2018， 37（4）： 41.

[18] AIGERMAN N， LIPMAN Y. Injective and bounded distortion mappings in 3D[J]. ACM Transactions on Graphics， 2013， 32（4）： 106.

[19] FU X， LIU Y， GUO B. Computing locally injective mappings by advanced MIPS[J]. ACM Transactions on Graphics， 2015， 34（4）： 71.

[20] WEBER O， ZORIN D. Locally injective parameterization with arbitrary fixed boundaries[J]. ACM Transactions on Graphics， 2014， 33（4）： 75.

[21] ZHU Y， BRIDSON R， KAUFMAN D M. Blended cured quasi-newton for distortion optimization[J]. ACM Transactions on Graphics， 2018， 37（4）： 40.

[22] RODOL E， LHNER Z， BRONSTEIN A M， et al. Functional maps representation on product manifolds[J]. Comouter Graphics Forum， 2019， 38（1）： 678-689.