結(jié)合重心坐標(biāo)的泊松網(wǎng)格編輯算法

武 帥，黃慶學(xué)，李宏杰 ，王安紅

(1.太原科技大學(xué)電子信息工程學(xué)院，太原 030024;2.太原理工大學(xué)，太原 030024)

在計(jì)算機(jī)動(dòng)畫中，網(wǎng)格變形日益完善，根據(jù)用戶的需求對(duì)原始網(wǎng)格進(jìn)行變形，比如給人物加上表情、給怪獸加上一系列動(dòng)作等等，以此來達(dá)到用戶的設(shè)計(jì)要求。網(wǎng)格變形最早采用自由變形技術(shù)，通過對(duì)原模型的頂點(diǎn)操作進(jìn)行變形，但由于方法簡(jiǎn)單，變形時(shí)導(dǎo)致一些細(xì)節(jié)點(diǎn)丟失。基于多分辨率技術(shù)的網(wǎng)格編輯，通過對(duì)低分辨率網(wǎng)格進(jìn)行編輯，還原到高分辨率的原模型上來實(shí)現(xiàn)變形，但只能有條件的保留模型細(xì)節(jié)點(diǎn)，變形時(shí)要對(duì)模型表面進(jìn)行分離，使變形難度增加?；谖⒎钟虻木W(wǎng)格編輯，將對(duì)頂點(diǎn)的操作轉(zhuǎn)變?yōu)閷?duì)微分屬性的操作，通過點(diǎn)的映射關(guān)系，將絕對(duì)坐標(biāo)轉(zhuǎn)為相對(duì)應(yīng)的微分坐標(biāo)，較好的保留模型的局部細(xì)節(jié)特征，但模型的部分法向量并沒有改變，從而導(dǎo)致變形后的模型看起來有點(diǎn)失真。重心坐標(biāo)可用于將三角形內(nèi)任意點(diǎn)表示為由三角形頂點(diǎn)組成的凸包組合，并用一種方便的方式無條件插在三角形頂點(diǎn)處。近年來重心坐標(biāo)的思想已經(jīng)擴(kuò)展到平面中任意多邊形和高維度的多面體，使網(wǎng)格的參數(shù)化、網(wǎng)格變形等應(yīng)用有了新的解決方案。

2014年Niklas K, Matthias N, Konrad P[1]提出用于3D形狀和紋理貼圖的交互式建模框架，在微分變形的基礎(chǔ)上結(jié)合幾何畫筆的思想，實(shí)現(xiàn)了局部縮放，但沒有考慮梯度場(chǎng)方向的改變；2013年Chen C H, Tsai M H, Lin C I[2]提出的骨架驅(qū)動(dòng)網(wǎng)格表面變形進(jìn)行實(shí)時(shí)角色動(dòng)畫，通過構(gòu)造包含輸入表面網(wǎng)格的立方體單元格子，自動(dòng)傳播骨頭平滑皮膚的重量，以驅(qū)動(dòng)表面進(jìn)行變形，但只能進(jìn)行正數(shù)的加權(quán)計(jì)算；2011年Manson J, Li K, Schaefer S[3]提出的Gordon-Wixom坐標(biāo)，在二維中引入任意閉合的重心坐標(biāo)新結(jié)構(gòu)，使用與邊界曲線相切的距離定義正和平滑的權(quán)重函數(shù)來實(shí)現(xiàn)，采用多邊形閉合解只能近似邊界光滑；2010年S Sun, B Chen[4]提出的基于重心坐標(biāo)的移動(dòng)網(wǎng)格變形方法，首先計(jì)算要移動(dòng)網(wǎng)格點(diǎn)的重心坐標(biāo)，然后根據(jù)重心坐標(biāo)插值邊界點(diǎn)的位移來計(jì)算網(wǎng)格點(diǎn)的位移，計(jì)算量較大；2009年Xian C H, Lin H W, Gao S M[5]提出采用一種全自動(dòng)的方法來生成一個(gè)包圍網(wǎng)格模型的粗籠，自動(dòng)生成的粗邊界籠可以保持原網(wǎng)格模型的拓?fù)浣Y(jié)構(gòu)和主要幾何特征，便于進(jìn)行變形、細(xì)分、融合等操作，但對(duì)原始網(wǎng)格的要求較高；2016年杜正君、張慧[6]提出的體積圖控制的近似剛性變形算法，采用體積圖的近似剛性約束變形中的體積變化，克服了傳統(tǒng)變形過程中不合理的體積變化，但算法需要多次迭代，并行計(jì)算的求解速度較慢；2015年張輝鑫[7]提出的基于廣義重心坐標(biāo)的三角網(wǎng)格變形方法，將原模型封閉到控制網(wǎng)格中，通過操作控制網(wǎng)格的變形帶動(dòng)原模型的變形，生成的是均勻的控制網(wǎng)格，沒有考慮模型的簡(jiǎn)化與光滑處理；2015年張湘玉、李明、馬希青[8]提出的基于細(xì)分的網(wǎng)格模型骨架驅(qū)動(dòng)變形技術(shù)，通過建立骨架與控制網(wǎng)格、控制網(wǎng)格對(duì)應(yīng)的細(xì)分曲面與變形區(qū)域間的關(guān)系，將對(duì)應(yīng)細(xì)分曲面變化信息轉(zhuǎn)化為網(wǎng)格模型泊松梯度場(chǎng)的改變，從而得到重建的網(wǎng)格模型，但由于模型表面拓?fù)浣Y(jié)構(gòu)的復(fù)雜，控制網(wǎng)格有時(shí)不能很好地貼合原模型形狀，出現(xiàn)誤差；2013年許斌、李忠科、呂培軍[9]等提出的保持細(xì)節(jié)的網(wǎng)格曲面局部變形算法，依據(jù)用戶對(duì)控制頂點(diǎn)的移動(dòng)和網(wǎng)格表面幾何特征，自動(dòng)判斷變形區(qū)域，將用戶對(duì)控制頂點(diǎn)的編輯操作轉(zhuǎn)為對(duì)模型泊松梯度場(chǎng)的操作，重建得到變形后的網(wǎng)格，但只考慮局部區(qū)域的變形，變形區(qū)域受限制。

通過以上比較，提出將自由變形技術(shù)與微分坐標(biāo)結(jié)合起來，以重心坐標(biāo)構(gòu)造變形控制曲面，根據(jù)對(duì)重心坐標(biāo)的編輯進(jìn)行局部變換，通過局部變換得到變形后的梯度場(chǎng)方向，以此達(dá)到網(wǎng)格變形結(jié)果。該方法可以預(yù)先計(jì)算原網(wǎng)格模型的重心坐標(biāo)，加快了并行計(jì)算，有效地克服了模型在變形過程中的變形問題，且能很好的保證變形的光滑。

1 重心坐標(biāo)

重心坐標(biāo)是指將原模型用一個(gè)空間網(wǎng)格包圍，通過操作空間網(wǎng)格來實(shí)現(xiàn)變形，是用來描述原模型與空間網(wǎng)格間的幾何關(guān)系。重心坐標(biāo)常用的有均值坐標(biāo)、調(diào)和坐標(biāo)和格林坐標(biāo)等。由于空間網(wǎng)格相對(duì)原模型有很少的頂點(diǎn)，通過對(duì)空間網(wǎng)格中的點(diǎn)進(jìn)行操作，原網(wǎng)格上的對(duì)應(yīng)位置就會(huì)發(fā)生改變。

Lipman[10]提出的格林坐標(biāo)，利用偏微分方程理論與格林第三公式對(duì)拉普拉斯方程進(jìn)行變化得到格林坐標(biāo)。在三角網(wǎng)格中，包圍網(wǎng)格P內(nèi)P=(V,T)，V表示頂點(diǎn)集合，T表示三角形面集合，η表示點(diǎn)，Φi、Φj表示坐標(biāo)函數(shù)，n(tj)表示面的外法線，則重心坐標(biāo)為：

(1)

以重心坐標(biāo)來構(gòu)造待變形模型的控制網(wǎng)格，通過對(duì)控制網(wǎng)格的操縱實(shí)現(xiàn)原模型的任意變形。由于重心坐標(biāo)具有自由變形技術(shù)的特點(diǎn)，因而本文提出的方法也具有自由變形技術(shù)的優(yōu)勢(shì)。

2 網(wǎng)格模型的泊松方程

泊松方程是一個(gè)偏微分方程

Δf=·wf|?Ω=f*|?Ω

(2)

2.1 三角網(wǎng)格梯度場(chǎng)

網(wǎng)格曲面上的分段線性標(biāo)量場(chǎng)為f(η)=fi·Φi(η).

其中，fi是標(biāo)量場(chǎng)在網(wǎng)格頂點(diǎn)η上的函數(shù)值，Φi是分段線性基函數(shù)。對(duì)于三角網(wǎng)格上的任意三角形Δvivjvk，任意一點(diǎn)η都可由其所在三角形的三個(gè)頂點(diǎn)線性插值得到：

f(η)=fi·Φi+fj·Φj+fk·Φk

(3)

則梯度為：

(4)

2.2 梯度場(chǎng)的散度

對(duì)梯度場(chǎng)求偏導(dǎo)得到三角網(wǎng)格梯度場(chǎng)的散度：

(5)

其中，V是頂點(diǎn)vi的一組三角形集，Bik表示定義在vi點(diǎn)的分段線性函數(shù)在三角形T上的梯度，A是三角形T的面積。

2.3 拉普拉斯算子

通過梯度場(chǎng)和散度算子，得到標(biāo)量場(chǎng)f在頂點(diǎn)Vi的拉普拉斯算子，如圖1所示，拉普拉斯算子為：

圖1 拉普拉斯算子
Fig.1 Laplacian operator

對(duì)整個(gè)三角網(wǎng)格的拉普拉斯算子為

(7)

2.4 泊松方程求解

(8)

2.5 邊界約束條件

泊松方程是一個(gè)微分方程，要求解微分方程，就需要有邊界條件，如果一個(gè)頂點(diǎn)在網(wǎng)格中被確定，那么該頂點(diǎn)是約束頂點(diǎn)，也就是泊松方程的邊界約束條件，如果一個(gè)頂點(diǎn)在網(wǎng)格中不被確定，那么該頂點(diǎn)是自由頂點(diǎn)。

對(duì)網(wǎng)格中的三個(gè)頂點(diǎn)不全是約束頂點(diǎn)的三角形集合進(jìn)行局部旋轉(zhuǎn)和縮放等操作，以三角網(wǎng)格的頂點(diǎn)(x,y,z)中每一維作為一個(gè)標(biāo)量場(chǎng)，對(duì)不受約束的網(wǎng)格變形區(qū)域內(nèi)每個(gè)三角形進(jìn)行局部變換得到新的梯度場(chǎng)，然后計(jì)算散度，最后通過泊松方程重建網(wǎng)格模型，實(shí)現(xiàn)網(wǎng)格變形。

3 網(wǎng)格變形

三維模型的網(wǎng)格變形技術(shù)是在幾何造型的框架下，通過引入一些權(quán)重來建立坐標(biāo)之間的線性映射關(guān)系，從而根據(jù)用戶的需求得到網(wǎng)格變形新模型。結(jié)合重心坐標(biāo)的泊松網(wǎng)格編輯算法具體流程如圖2所示，首先以原模型包圍網(wǎng)格所確定的重心坐標(biāo)生成控制網(wǎng)格，由于均值坐標(biāo)的均值向量與三角面表面法向相同時(shí)，坐標(biāo)值可能出現(xiàn)負(fù)數(shù)，不能滿足局部特性；調(diào)和坐標(biāo)包圍網(wǎng)格的的復(fù)雜程度直接與計(jì)算過程的復(fù)雜性連接，進(jìn)一步的發(fā)展較難；格林坐標(biāo)是拉普拉斯方程的解，變形的光滑性高達(dá)C，這里主要采用格林坐標(biāo)，一方面保證模型變形后的光滑自然，另一方面由于格林坐標(biāo)中引入了法向信息，能很好的保持模型的細(xì)節(jié)特征，在大規(guī)模變形后使變形結(jié)果相對(duì)比較自然。然后任意改變包圍網(wǎng)格，將對(duì)應(yīng)重心坐標(biāo)變化的信息轉(zhuǎn)換為對(duì)應(yīng)的標(biāo)量場(chǎng)，估算網(wǎng)格模型每個(gè)頂點(diǎn)變形前后的局部旋轉(zhuǎn)變換矩陣，求得每個(gè)頂點(diǎn)變形后的梯度場(chǎng)方向，對(duì)梯度場(chǎng)方向求導(dǎo)得到散度，最后通過求解系數(shù)矩陣進(jìn)行網(wǎng)格重構(gòu)得到變形模型。

圖2 流程示意圖
Fig.2 Flow chart

3.1 確定重心坐標(biāo)

構(gòu)建包圍網(wǎng)格是結(jié)合重心坐標(biāo)進(jìn)行泊松網(wǎng)格編輯的基礎(chǔ)，采用簡(jiǎn)化模型來構(gòu)造包圍網(wǎng)格，然后對(duì)包圍網(wǎng)格按照2.1節(jié)所示方法求取重心坐標(biāo)得到控制網(wǎng)格，求出原網(wǎng)格模型每個(gè)頂點(diǎn)在包圍網(wǎng)格上所對(duì)應(yīng)的重心坐標(biāo)位置。

3.2 確定局部變換矩陣

由于微分變形具有平移不變性，因而只考慮旋轉(zhuǎn)變換和縮放變換。在原模型新頂點(diǎn)處定義局部標(biāo)架，局部標(biāo)架其中一個(gè)方向是邊界點(diǎn)的法矢方向，另外兩個(gè)方向在過邊界點(diǎn)且以法矢方向?yàn)槊娣ㄏ蛄康那衅矫鎯?nèi)，計(jì)算出變形前后控制網(wǎng)格頂點(diǎn)處的局部標(biāo)架，從而確定唯一的旋轉(zhuǎn)變換矩陣。得到三角形中心點(diǎn)變形前后的局部標(biāo)架，根據(jù)局部標(biāo)架法矢方向叉乘得到第一旋轉(zhuǎn)軸，點(diǎn)乘得到第一旋轉(zhuǎn)角度，局部標(biāo)架以編輯前的位置為旋轉(zhuǎn)中心，繞第一旋轉(zhuǎn)軸和第一旋轉(zhuǎn)角度得到中間標(biāo)架，將中間標(biāo)架與編輯后控制網(wǎng)格位置在切平面上投影向量叉乘得到第二旋轉(zhuǎn)軸，點(diǎn)乘得到第二旋轉(zhuǎn)角度。

根據(jù)編輯前后控制網(wǎng)格上三角面的周長(zhǎng)確定縮放變換矩陣，三角網(wǎng)格中所有頂點(diǎn)的三個(gè)位置坐標(biāo)分量構(gòu)成三個(gè)標(biāo)量場(chǎng)，按照2.2節(jié)所示方法求出每個(gè)標(biāo)量場(chǎng)對(duì)應(yīng)的梯度場(chǎng)。

如圖3所示，任意的變形區(qū)域內(nèi)，變形前后兩關(guān)聯(lián)位置vd和vd′，得到兩個(gè)局部正交標(biāo)架，其中的一個(gè)方向即為nd和nd′，另外的兩個(gè)方向即為e1、e2和e1′、e2′.

圖3 局部標(biāo)架
Fig.3 Local frame

3.3 實(shí)現(xiàn)泊松變形

用戶根據(jù)需求確定待變形區(qū)域的包圍網(wǎng)格，以包圍網(wǎng)格所確定的重心坐標(biāo)生成控制網(wǎng)格，通過對(duì)包圍網(wǎng)格的操作，將對(duì)應(yīng)重心坐標(biāo)變化的信息作為局部原點(diǎn)進(jìn)行局部變換得到新的梯度場(chǎng)，代入泊松方程求最小二乘解得到變形的網(wǎng)格模型。

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

結(jié)合重心坐標(biāo)的泊松網(wǎng)格編輯算法在Microsoft Visual Studio 2013平臺(tái)上，編寫基于MFC的圖形界面，配有2.60GHz CPU，4.00GB內(nèi)存，Windows 7系統(tǒng)的個(gè)人筆記本電腦。圖4、圖5和圖6展示了采用本文算法對(duì)不同模型的變形效果。

a b

c

圖4 立方體模型及變形
Fig.4 Cube model and deformation

圖4a是變形前立方體模型，圖4b是本文算法進(jìn)行扭曲變形的結(jié)果，圖4c是本文算法進(jìn)行彎曲變形的結(jié)果。圖5a是變形前牛模型，圖5b是本文算法對(duì)后腿進(jìn)行變形的結(jié)果，圖6a是變形前bunny模型，圖6b是采用本文算法對(duì)bunny耳朵進(jìn)行變形的結(jié)果。

a

b

圖5 牛模型及變形
Fig.5 Cattle model and deformation

a

b

圖6 bunny模型及變形
Fig.6 Bunny model and deformation

通過上述變形實(shí)驗(yàn)結(jié)果可以看出，本文算法充分體現(xiàn)了重心坐標(biāo)作為變形控制網(wǎng)格進(jìn)行任意拓?fù)涞膬?yōu)勢(shì)，無論對(duì)模型哪個(gè)部位進(jìn)行變形，變形結(jié)果都保留很好的連續(xù)性，而且對(duì)模型的大尺度形變也能得到理想的編輯效果。圖中的紅色部分是編輯前后重心坐標(biāo)構(gòu)成的控制網(wǎng)格，白色部分是設(shè)置的固定區(qū)域。從變形結(jié)果可以看出，模型的細(xì)節(jié)特征在變形后都得到了很好的保持。

圖7 傳統(tǒng)泊松網(wǎng)格變形
Fig.7 Traditional Poisson mesh deformation

與傳統(tǒng)的泊松網(wǎng)格變形算法相比較，針對(duì)圖4b扭轉(zhuǎn)變形結(jié)果，圖7給出扭轉(zhuǎn)變形的對(duì)比實(shí)驗(yàn)結(jié)果。可以看出，使用傳統(tǒng)的泊松網(wǎng)格變形算法，扭轉(zhuǎn)模型變形結(jié)果出現(xiàn)失真，有明顯的棱角，而使用本文算法，模型扭轉(zhuǎn)變形更自然，有很好的連續(xù)性。

5 結(jié) 論

要實(shí)現(xiàn)網(wǎng)格模型的保特征變形，不能直接用原網(wǎng)格的梯度場(chǎng)方向來重建變形后的網(wǎng)格模型，因而采用與重心坐標(biāo)結(jié)合的泊松網(wǎng)格編輯方法，以包圍網(wǎng)格來確定重心坐標(biāo)進(jìn)而得到控制網(wǎng)格，達(dá)到重新設(shè)置微分坐標(biāo)方向的效果，對(duì)梯度場(chǎng)方向進(jìn)行調(diào)整，最后重建出變形模型。該方法能夠較好地保持網(wǎng)格模型的局部細(xì)節(jié)，使得變形后的模型更加光順自然。尚有的缺陷是在網(wǎng)格進(jìn)行局部旋轉(zhuǎn)時(shí)，泊松變形將原來的非線性能量?jī)?yōu)化為線性融合，直觀性不強(qiáng)。