邵茂真，壽華好

?

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

邵茂真，壽華好

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

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

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

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

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

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

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

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

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

1 本文算法框架

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

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

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

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

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

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

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

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

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

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

2.2 熱測(cè)地場(chǎng)[14]

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

熱測(cè)地線算法步驟如下：

輸入：熱源點(diǎn)v。

步驟3. 得到測(cè)地距離的梯度之后，測(cè)地線的問(wèn)題即為

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

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

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

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

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

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

圖3 ARAP算法測(cè)地場(chǎng)差異圖

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

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

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

采用距離場(chǎng)差的和表示熱測(cè)地場(chǎng)變形能量

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

2.4 熱測(cè)地場(chǎng)控制的ARAP模型框架

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

本文算法步驟如下：

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

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

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

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

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

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

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

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

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

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

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

圖4 本文算法測(cè)地場(chǎng)差異圖

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

圖5 Bunny變形Eg變化對(duì)比圖

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

圖6 Armadillo變形對(duì)比圖

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

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

圖9 Cactus變形對(duì)比圖

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

表1 本文算法運(yùn)行時(shí)間

4 結(jié)束語(yǔ)

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

本文算法的不足之處，當(dāng)網(wǎng)格變形改變圖形拓?fù)浣Y(jié)構(gòu)時(shí)，所提假設(shè)變形前后測(cè)地場(chǎng)變化較小將被否決；另并未將測(cè)地信息直接地加入到網(wǎng)格變形中，在今后的工作中需對(duì)其進(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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2016, 28(2): 218-227.

[9] 劉炯宙, 李基拓, 陸國(guó)棟. 三維模型近剛性保體變形[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(61572430)

邵茂真(1994-)，男，浙江金華人，碩士研究生。主要研究方向?yàn)榭梢暬?jì)算。E-mail：434850246@qq.com

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