邵茂真，壽華好

?

熱測地場控制的近似剛性網(wǎng)格變形技術(shù)

邵茂真，壽華好

(浙江工業(yè)大學(xué)理學(xué)院，浙江 杭州 310023)

為保持三維模型局部細(xì)節(jié)，修正近似剛性網(wǎng)格變形算法(ARAP)應(yīng)用于大尺度以及非完全剛性變形中出現(xiàn)的扭曲、翻折問題，提出了一種基于測地場約束的近似剛性變形方法。首先對模型進(jìn)行Laplacian變形，并通過奇異值分解求得局部單位的旋轉(zhuǎn)矩陣，計算模型剛性變形能量；然后通過求解稀疏線性系統(tǒng)，更新變形點，再通過求解兩次稀疏線性系統(tǒng)，計算變形過程中產(chǎn)生的測地場偏差，并修正變形網(wǎng)格，得到與原始網(wǎng)格測地場接近的變形結(jié)果；反復(fù)迭代上述步驟，直到熱測地場偏差滿足一定要求，獲得最終變形結(jié)果。結(jié)果表明，該方法能在網(wǎng)格變形過程中快速地完成網(wǎng)格點修正功能，在應(yīng)用于大尺度變形中也能有效地避免網(wǎng)格出現(xiàn)翻折問題。

近似剛性變形；熱測地場；稀疏線性系統(tǒng)；翻折

隨著近年來計算機圖形學(xué)飛速發(fā)展，三維幾何模型尤其是三角網(wǎng)格模型在動畫、游戲、3D打印、電影等相關(guān)領(lǐng)域得到了廣泛應(yīng)用。三角網(wǎng)格變形作為常用的一個幾何處理工具，能根據(jù)用戶的交互操作，對原模型進(jìn)行變形，以表達(dá)用戶特定的創(chuàng)作 意圖。

網(wǎng)格變形一直是計算機圖形學(xué)中較為活躍的一個方向。本文只討論與微分域的網(wǎng)格變形方法相關(guān)的方法以及所用的一些思想和概念。

微分域網(wǎng)格變形實質(zhì)上是一個用微分坐標(biāo)描述網(wǎng)格變化的問題，其是非線性問題，因為微分坐標(biāo)是非線性的依賴頂點位置。Laplacian變形[1-4]方法已經(jīng)得到了廣泛的發(fā)展，可通過保持變形前后的Laplacian坐標(biāo)來保持局部細(xì)節(jié)，但其變形均需對旋轉(zhuǎn)變形加入約束或定義[5]。另一種解決旋轉(zhuǎn)變換的方法，是從保持局部的剛性入手以保持局部細(xì)節(jié)，使用ARAP能量體現(xiàn)，在幾何處理中得到了廣泛的應(yīng)用?；诖四芰?，SORKINE和ALEXA[3]提出了一種網(wǎng)格變形方法，只需要控制頂點的約束，整個變形就能自動的完成，并且局部的旋轉(zhuǎn)變換也能自動地在迭代優(yōu)化中產(chǎn)生。該變形方法近年來在效率[6]和效果[7]上得到了發(fā)展。

ZHOU等[4]引入體積圖Laplacian算子，將三角網(wǎng)格內(nèi)部與表面巧妙地聯(lián)系起來，使得變形后的圖形能較好地保持原有體積，同時能夠很好地避免曲面的自交。通過類似泊松變形的傳播方法將控制曲線的變換顯式地傳播到興趣區(qū)域，最后通過線性變分的方法求解變形網(wǎng)格。文獻(xiàn)[8]將該方法簡化后應(yīng)用到近似剛性網(wǎng)格變形之中，實現(xiàn)了保細(xì)節(jié)以及整體近似剛性的變形。文獻(xiàn)[9]另辟蹊徑，以三角形與坐標(biāo)原點構(gòu)成的四面體的有向體積加權(quán)和表示模型體積。通過將模型的剛性保持和體積保持轉(zhuǎn)化為網(wǎng)格頂點位移的約束求解，實現(xiàn)三維物體的近剛性保體變形。

GAO等[10]用L1范數(shù)代替?zhèn)鹘y(tǒng)的L2范數(shù)優(yōu)化ARAP能量函數(shù)，使得扭曲處得到減少，且更好地保持幾何特征。文獻(xiàn)[7]將旋轉(zhuǎn)差項加入到ARAP能量函數(shù)中，實現(xiàn)了相對剛性旋轉(zhuǎn)的光滑處理。CHAO等[11]將1-鄰域的ARAP能量框架擴展到2鄰域上，得到了一個連續(xù)的ARAP能量框架。CHEN等[12]將此鄰域擴展為任意大小的并且內(nèi)部可以存在多種鄰域結(jié)構(gòu)的ARAP能量框架，實現(xiàn)了剛性可控的ARAP網(wǎng)格變形技術(shù)。

AU等[13]將等值線和剛性信息與控制點(handle)聯(lián)系起來，提出了一種控制點等值線引導(dǎo)的網(wǎng)格編輯手段與本文方法較為相似。CRAME等[14]巧妙地將熱傳播與測地距離兩者聯(lián)立起來，將熱傳播方向認(rèn)為是測地距離的負(fù)梯度方向，極大地提高了求源點到網(wǎng)格上其他點距離所需的時間。本文認(rèn)為在近似剛性的網(wǎng)格變形中，變形前后對于源點的測地距離標(biāo)量場(測地場)應(yīng)該是大致不變的，此觀點在做近似剛性變形的迭代過程中得到了佐證，同時，測地場也在不斷地逼近變形前網(wǎng)格測地場。

1 本文算法框架

傳統(tǒng)的ARAP變形技術(shù)只能保證相連頂點之間的剛性結(jié)構(gòu)，這使得在變形的過程中不相連頂點之間會發(fā)生較大的拉扯從而改變原來的測地距離，如圖1所示。

圖1 網(wǎng)格變形前后測地距離路徑發(fā)生改變

針對此現(xiàn)象，本文提出了一種測地場約束的ARAP網(wǎng)格變形技術(shù)。且分別采用剛性變形能量E和測地場變形能量E衡量曲面的剛性變形誤差和距離場誤差。相應(yīng)地，模型的變形過程即是最小化變形能量的過程，即

2 熱測地場控制的ARAP網(wǎng)格變形

2.1 ARAP網(wǎng)格變形技術(shù)[3]

當(dāng)給定一個三角網(wǎng)格，其主要拓?fù)浣Y(jié)構(gòu)由個點和個三角形構(gòu)成。()為與頂點相連的所有頂點的集合，稱為1-鄰域頂點。

ARAP變形算法定義網(wǎng)格頂點與1-鄰域的頂點和邊構(gòu)成剛性變形單元，每個相似大小的變形單元重疊地覆蓋整個網(wǎng)格表面。變形的過程假設(shè)所有的變形單元只發(fā)生剛性變換，即

整個變形區(qū)域的能量函數(shù)是每個變形單元的能量函數(shù)之和，即

一般的網(wǎng)格變形就在?預(yù)定義部分約束點，其中包括靜態(tài)不變動的點與主導(dǎo)變形的控制點(handle vectices)，一般由用戶交互地給定

反復(fù)迭代上述的和，如此反復(fù)迭代直到能量誤差達(dá)到一定的閾值或趨于穩(wěn)定為止。

2.2 熱測地場[14]

文獻(xiàn)[14]提出了利用熱運動方程來計算網(wǎng)格測地線的方法，即當(dāng)一根燙的針尖接觸到曲面上的一點時，熱量會隨著時間的推移而擴散，測地距離因此可以和熱運動相聯(lián)系。

熱測地線算法步驟如下：

輸入：熱源點v。

步驟3. 得到測地距離的梯度之后，測地線的問題即為

根據(jù)變分法，式(8)最小化即為求解泊松方程

應(yīng)用在三角網(wǎng)格中時，通過離散化處理，只要求解兩次稀疏線性方程組，在時間和效率上均有較好的改進(jìn)。

本文將每個頂點到熱源點測地距離構(gòu)成標(biāo)量場簡稱為熱測地場，如圖2所示。

本文提出假設(shè)：近似剛性網(wǎng)格變形前后的熱測地場也是近似不變的，在此基礎(chǔ)上觀察近似剛性網(wǎng)格變形過程中熱測地場的變化，此時變形非完全剛性的變形，發(fā)現(xiàn)熱測地場也以較為緩慢的速度逼近變形前網(wǎng)格測地場，如圖3所示。

在上述例子中近似剛性網(wǎng)格變形迭代5次后，近似剛性能量已經(jīng)趨于不變，如果按原先的標(biāo)準(zhǔn)圖3(b)當(dāng)作最終的變形結(jié)果輸出，本文對其繼續(xù)迭代并做測地場觀察發(fā)現(xiàn)，盡管其近似剛性能量不再變小反而會出現(xiàn)微微增大的情形，但其測地場能量仍在持續(xù)減小，并在迭代30次時達(dá)到收斂，此時測地場與原測地場的差異已經(jīng)非常小。

圖2 標(biāo)準(zhǔn)兔子模型的熱測地場

圖3 ARAP算法測地場差異圖

(黑色圓點為變形控制點，其中橘色越深代表該處測地距離差異越大，藍(lán)色則表示該處測地距離沒有發(fā)生變化)

2.3 熱測地場控制的ARAP能量函數(shù)構(gòu)造

針對上述觀察結(jié)果，本文提出了一種新的測地場控制下的近似剛性網(wǎng)格變形技術(shù)。

采用距離場差的和表示熱測地場變形能量

將其帶入式(1)，則原問題就變成最小化總能量函數(shù)

2.4 熱測地場控制的ARAP模型框架

本文在非完全剛性的變形應(yīng)用ARAP網(wǎng)格變形技術(shù)時，其近似剛性變形能量并非向0收斂，相反會收斂于一個較大的常數(shù)。此時三角網(wǎng)格的邊長有很大一部分發(fā)生了伸縮變換，影響能量函數(shù)對輸出結(jié)果的一個判斷，因此采用式(11)作為新的能量函數(shù)，其中w取較大常數(shù)時，該能量函數(shù)具有收斂性，同時定義變形終止條件為

本文算法步驟如下：

輸入.起始三角網(wǎng)格，控制點，熱源點v。

輸出.變形后網(wǎng)格。

步驟2. 根據(jù)所得和式(6)更新。

源點的選擇直接決定了其他點的測地距離，以及測地場修正過程中的導(dǎo)向。若選用控制變形的控制點作為源點，修正過程將在修正測地場的同時，其他參與修正的頂點也將向變形最終位置逼近，加入測地距離修正能加快變形收斂速度的原因也在于此；若選用其他參與變形的頂點，由于該頂點自身存在隨機偏差的原因，最終修正雖然能夠修復(fù)網(wǎng)格內(nèi)部折疊現(xiàn)象，但會導(dǎo)致整體變形都加入隨機偏差，該偏差會在下次ARAP變形中修正，一個不好的源點選擇可能導(dǎo)致網(wǎng)格變形消耗更多的時間。若選用不動點作為源點，同參與變形點一樣極有可能變形減慢，增加時間 成本。

測地場約束是如何修正網(wǎng)格內(nèi)部折疊的呢？

網(wǎng)格內(nèi)部折疊的根本原因在于ARAP網(wǎng)格變形過于強調(diào)cell結(jié)構(gòu)的不變性，為了能達(dá)到此效果，當(dāng)發(fā)生非剛性變形或大幅度變形時，會以折疊和拉伸的方式來保證cell結(jié)構(gòu)的近似不變，在此情況下ARAP的能量消耗最小。而折疊區(qū)域的另一直觀結(jié)果，就是到某一源點的測地距離場發(fā)生了極大變化，即改變了原先的測地距離分布。圖8(b) Tyra模型尾巴部分可以直觀地看到這一現(xiàn)象。

式(13)以前一次變形的測地場梯度方向作為修正方向，測地距離的差值作為修正值，重新定位頂點位置，不改變原拓?fù)浣Y(jié)構(gòu)，近似地得到與前一次測地距離場分布相同的變形結(jié)果。

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

本文算法運行環(huán)境為：Windows 7，i5-4590CPU@3.30 GHz，4 GB。且在Visual Studio 2012上實現(xiàn)的，稀疏線性方程組和矩陣的奇異值分解使用的均是Eigen庫，為了加快線性方程組的求解過程，對所有方程組的求解均用了基于Cholesky分解的解法。

圖4為本文算法在測地場差異變化過程，并與圖3進(jìn)行比較，還以折線圖(圖5)的方式展示了兩者的迭代收益。

本文算法以熱測地場為約束進(jìn)行網(wǎng)格的重新排列，對每次迭代出現(xiàn)的畸形網(wǎng)格做優(yōu)化處理，以保證每次迭代所得網(wǎng)格拓?fù)浣Y(jié)構(gòu)不發(fā)生變化，同時在一定程度上縮減了ARAP變形所需的時間。圖6(b)展示了在第5次ARAP變形迭代時Armadillo鼻子處出現(xiàn)的畸變，此時其熱測地場能量高頂點主要分布在Armadillo上部分。通過本文算法對Armadillo進(jìn)行熱測地場修正，有效地消除了在鼻子處的畸變問題，同時其熱測地場也與原形狀的熱測地場趨于接近。

圖4 本文算法測地場差異圖

(黑色圓點為變形控制點，其中橘色越深代表該處測地距離變化越大，藍(lán)色則表示該處測地距離沒有發(fā)生變化)

圖5 Bunny變形Eg變化對比圖

對尾巴、腳這類動畫常用變形進(jìn)行觀察(圖7)，當(dāng)出現(xiàn)大角度的非完全剛性變形時(圖中尾巴部分)，ARAP變形極其容易發(fā)生改變網(wǎng)格內(nèi)部翻折的情形。圖7紅色框內(nèi)為不參與變形網(wǎng)格頂點，紅色頂點為控制點，將其分別變形到藍(lán)點位置，ARAP算法和本文算法均迭代8次。可以看到圖7(b)中在尾巴位置發(fā)生了網(wǎng)格折疊的情形，這是由于ARAP對大尺度、非完全剛性變形的缺點。而本文算法則很好地解決了這一問題，如圖7(c)所示。圖8為Tyra尾部網(wǎng)格對比圖，圖9為Cactus變形對比圖。

圖6 Armadillo變形對比圖

圖7 Tyra變形網(wǎng)格對比圖

圖8 Tyra尾部網(wǎng)格對比圖

圖9 Cactus變形對比圖

在時間效率上，本文算法加入了計算測地場的步驟，但慶幸的是，計算測地場中多次所用的Laplacian算子在ARAP變形中已經(jīng)計算得到，因此在一定程度上縮減了測地場計算所需的時間。在圖形效果上，加入測地場約束能有效地避免大尺度以及非剛性變形所出現(xiàn)的畸變情況，通過測地場能量的約束，可加速圖形的收斂速度。從表1可以看出，加入測地場優(yōu)化所需要的時間僅為ARAP變形的1/3。

表1 本文算法運行時間

4 結(jié)束語

本文對ARAP變形技術(shù)進(jìn)行拓展，加入了測地場優(yōu)化這一步驟，改善了大尺度變形以及非剛性變形中出現(xiàn)的畸變，在保持ARAP變形技術(shù)的同時保持曲面細(xì)節(jié)，用測地場優(yōu)化來實現(xiàn)宏觀調(diào)控，加速了網(wǎng)格變形。以測地場能量來衡量網(wǎng)格變形優(yōu)劣，避免了ARAP變形技術(shù)在非完全剛性變換時，能量函數(shù)在迭代過程中出現(xiàn)逆增長，而影響變形評價系統(tǒng)對變形完成程度的衡量。

本文算法的不足之處，當(dāng)網(wǎng)格變形改變圖形拓?fù)浣Y(jié)構(gòu)時，所提假設(shè)變形前后測地場變化較小將被否決；另并未將測地信息直接地加入到網(wǎng)格變形中，在今后的工作中需對其進(jìn)行改進(jìn)。

[1] YU Y Z, ZHOU K, XU D, et al. Mesh editing with poisson-based gradient field manipulation [C]//ACM SIGGRAPH. New York: ACM Press, 2004: 644-651.

[2] SORKINE O, COHEN-OR D, LIPMAN Y, et al. Laplacian surface editing [C]//In Proceeding of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. New York: ACM Press, 2004: 175-184.

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

[4] ZHOU K, HUANG J, SNYDER J, et al. Large mesh deformation using the volumetric graph Laplacian [J]. ACM Transactions on Graphics, 2005, 24(3): 496-503.

[5] LIPMAN Y, SORKINE O, LEVIN D, et al. Linear rotation-invariant coordinates for meshes [J]. ACM Transactions on Graphics, 2005, 24(3): 479-487.

[6] SUESSMUTH J, ZOLLH?FER M, SERT E, et al. GPU based ARAP deformation using volumetric lattices [C]// Eurographics 2012. Goslar: Eurographics Association Press, 2012: 85-88.

[7] LEVI Z, GOTSMAN C. Smooth rotation enhanced as-rigid-as-possible mesh animation [J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(2): 264-277.

[8] 杜正君, 張慧. 體積圖控制的近似剛性的網(wǎng)格變形[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2016, 28(2): 218-227.

[9] 劉炯宙, 李基拓, 陸國棟. 三維模型近剛性保體變形[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2013, 25(4): 533-540.

[10] GAO L, ZHANG G X, LAI Y K. Lp, shape deformation [J]. Science China Information Sciences, 2012, 55(5): 983-993.

[11] CHAO I, PINKALL U, SANAN P, et al. A simple geometric model for elastic deformations [J]. ACM Transactions on Graphics, 2010, 29(4): 157-166.

[12] CHEN S Y, GAO L, LAI Y K, et al. Rigidity controllable as-rigid-as-possible shape deformation [J]. Graphical Models, 2017, 91: 13-21.

[13] AU K C, FU H, TAI C L, et al. Handle-aware isolines for scalable shape editing [J]. ACM Transactions on Graphics, 2007, 26(3): 83.1-83.10.

[14] CRANE K, WEISCHEDEL C, WARDETZKY M. Geodesics in heat: A new approach to computing distance based on heat flow [J]. ACM Transactions on Graphics, 2013, 32(5): 13-15.

As-Rigid-As-Possible Mesh Deformation Controlled by Geometric Field in Heat

SHAO Mao-zhen, SHOU Hua-hao

(College of Science, Zhejiang University of Technology, Hangzhou Zhejiang 310023, China)

In order to maintain the details of the 3D model, correct the problem of distortion and folding of the as-rigid-as-possible (ARAP) mesh deformation used in large and nonperfect rigid deformation, an ARAP deformation method is proposed based on geometric field in heat. First, the Laplacian deformation of the model is carried out. On this basis, the rotation matrix of local cell is solved by singular value decomposition, and the rigid deformation energy of the model is calculated. Then by solving the sparse linear system, the deformation points are updated. By solving the two-time sparse linear system, we calculate the geometric field deviation of the deformation process, and correct the deformed mesh to get the deformation results close to those of the original mesh. Iterate the above steps until the geometric field deviation to meet certain requirements, and finally the final deformation results are obtained. The example shows that the method can quickly complete the mesh point correction function in mesh deformation process, and it can also effectively avoid grid collapse when applied to large-scale deformation.

as-rigid-as-possible mesh deformation; geometric field in heat; sparse linear system; folding

TP 391

10.11996/JG.j.2095-302X.2019010001

A

2095-302X(2019)01-0001-07

2018-06-26；

2018-07-13

國家自然科學(xué)基金項目(61572430)

邵茂真(1994-)，男，浙江金華人，碩士研究生。主要研究方向為可視化計算。E-mail：434850246@qq.com

壽華好(1964-)，男，浙江諸暨人，教授，博士，碩士生導(dǎo)師。主要研究方向為計算機輔助幾何設(shè)計與圖形學(xué)。E-mail：shh@zjut.edu.cn