韓 麗，齊曉明

（遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧 大連116029）

0 引 言

三維網(wǎng)格模型的變形通常指在不改變其拓?fù)溥B接的同時(shí)改變網(wǎng)格頂點(diǎn)的坐標(biāo)，使得模型的姿態(tài)發(fā)生變化［1］，在幾何建模和計(jì)算機(jī)動(dòng)畫(huà)中有著非常重要的應(yīng)用。

目前主要使用的變形方法有自由變形方法，多分辨率網(wǎng)格變形方法和基于骨架的變形方法。基于骨架的變形方法最早由Thalmann提出，其主要思想是將三維網(wǎng)格的變形與人體的運(yùn)動(dòng)相類比，由骨架的運(yùn)動(dòng)帶動(dòng)網(wǎng)格表面點(diǎn) （皮膚）的運(yùn)動(dòng)。該方法具有良好的直觀性，因此被廣泛應(yīng)用于人體動(dòng)畫(huà)、游戲等領(lǐng)域［1］。

文獻(xiàn) ［2］將網(wǎng)格表面的點(diǎn)與三角曲線綁定，通過(guò)對(duì)三角曲線的變形，達(dá)到網(wǎng)格表面的形變；文獻(xiàn) ［3－4］提出了一種以單純形為操作單元的骨架驅(qū)動(dòng)變形方法；文獻(xiàn) ［5］則將動(dòng)力學(xué)公式和有限元方法結(jié)合，對(duì)三維模型進(jìn)行骨架驅(qū)動(dòng)變形，取得了良好效果。以上方法均集中在單一骨架驅(qū)動(dòng)的模型變形。

本文在文獻(xiàn) ［2］的基礎(chǔ)上，改變了骨架約束方式以及約束區(qū)域劃分方式，提出了一種新的多骨架驅(qū)動(dòng)的三維模型變形方法。首先，基于Reeb圖方法實(shí)現(xiàn)網(wǎng)格模型的拓?fù)涔羌芴崛?，其次，將多個(gè)骨架節(jié)點(diǎn)進(jìn)行曲線擬合，并通過(guò)反求曲線控點(diǎn)的方式實(shí)現(xiàn)多骨架點(diǎn)驅(qū)動(dòng)的骨架變換。最終，實(shí)現(xiàn)模型自然、光順的變形效果。

1 變形算法及原理

1.1 骨架約束點(diǎn)的確定

三維模型的骨架是將三維模型的拓?fù)涮匦钥梢暬院笮纬傻念愃乒羌芮仪队谌S模型內(nèi)部的圖形。本文采用了文獻(xiàn) ［9］提出的多分辨率Reeb圖的原理，進(jìn)行模型的骨架提取。

定義1 設(shè)M是一個(gè)光滑的三維流形，μ：M→R是定義在模型M上的連續(xù)函數(shù)，則Reeb圖是通過(guò)等價(jià)關(guān)系 （v1，μ（v1））～ （v2，μ（v2））所構(gòu)成的函數(shù)μ的商空間，其中v1和v2為模型M上的任意頂點(diǎn)。因此，給定模型上兩個(gè)頂點(diǎn)vi和vj，當(dāng)且僅當(dāng)以下條件滿足，則等價(jià)關(guān)系～成立

對(duì)于曲面上的每一組等價(jià)點(diǎn)集合，我們使用一個(gè)節(jié)點(diǎn)表示，相鄰節(jié)點(diǎn)使用邊連接，從而形成了圖結(jié)構(gòu)，即Reeb骨架圖 （RG），如圖1（a）為使用高度函數(shù)作為μ函數(shù)，進(jìn)行4等分區(qū)間劃分所提取的Reeb圖骨架。

根據(jù)Reeb圖的思想，不同的連續(xù)函數(shù)μ會(huì)產(chǎn)生不同的Reeb圖。文獻(xiàn) ［7］引入測(cè)地線距離作為連續(xù)函數(shù)，創(chuàng)建了具有平移、旋轉(zhuǎn)不變性的μ函數(shù)。然而，由于需要人為選擇源點(diǎn)來(lái)計(jì)算各個(gè)頂點(diǎn)的測(cè)地線距離，不同的源點(diǎn)選擇則獲得不同的Reeb圖，因此，使提取的骨架具有極不穩(wěn)定性。多分辨率Reeb圖簡(jiǎn)稱MRG進(jìn)一步引入了基本點(diǎn)的概念，其基本思想是將μ函數(shù)定為

式中：g（v，bi）——頂點(diǎn)v距基本點(diǎn)bi的測(cè)地線距離，基本點(diǎn)為均勻散布在模型表面的頂點(diǎn)，area（bi）是每個(gè)基本點(diǎn)相對(duì)應(yīng)的模型表面積。r相當(dāng)于一個(gè)基本點(diǎn)占據(jù)的表面半徑，r越小就會(huì)得到越多的bi基本點(diǎn)，MRG算法中設(shè)置（其中area（S）為模型表面積）。使用基本點(diǎn)作為測(cè)地線距離的源點(diǎn)，大大加強(qiáng)了測(cè)地線距離的穩(wěn)定性。在模型頂點(diǎn)的測(cè)地線距離的g（v，bi）計(jì)算中，Dijkstra的最短路徑算法被引用近似測(cè)地線距離，有效提高了運(yùn)算速度。

通過(guò)應(yīng)用最短路徑算法，可計(jì)算網(wǎng)格頂點(diǎn)v到所有基本點(diǎn)bi測(cè)地線距離之和。從而，獲得各個(gè)網(wǎng)格頂點(diǎn)的μ函數(shù)值μ（v）

最終，我們將μ函數(shù)值進(jìn)行規(guī)一化處理為μN(yùn)（v），并將μN(yùn)函數(shù)值區(qū)間進(jìn)行k等分，找出劃分后每個(gè)區(qū)間內(nèi)的子連通點(diǎn)集，聚合成一個(gè)骨架的關(guān)節(jié)點(diǎn)，最后按一定順序連接這些關(guān)節(jié)點(diǎn)即生成骨架。

圖1（b）示意了使用測(cè)地線距離作為連續(xù)函數(shù)μ，并進(jìn)行4等分的區(qū)域劃分 （如圖中不同顏色所示），最終提取各等價(jià)區(qū)域的骨架節(jié)點(diǎn)，構(gòu)成Reeb圖骨架結(jié)構(gòu)。

Reeb圖中的每個(gè)骨架節(jié)點(diǎn)對(duì)應(yīng)一定范圍的模型頂點(diǎn)和面片，即子連通點(diǎn)集，則骨架關(guān)節(jié)點(diǎn)與模型面片之間就產(chǎn)生了綁定關(guān)系，關(guān)節(jié)點(diǎn)的移動(dòng)就會(huì)影響到與其有綁定關(guān)系的模型面片與頂點(diǎn)。

1.2 多骨架驅(qū)動(dòng)的三維模型變形算法

1.2.1 基于骨架點(diǎn)的Bézier擬合曲線

Bézier曲線采用由控制頂點(diǎn)組成的多邊形來(lái)控制曲線的幾何形狀，一般地，一條n次Bézier曲線可以表示為

圖1 多分辨率Reeb圖

本文中，我們利用Bézier曲線的端點(diǎn)插值性、凸包性［8］及連續(xù)性［9］等性質(zhì)，首先將骨架節(jié)點(diǎn)作為控制頂點(diǎn)，構(gòu)造Bézier擬合曲線，然后由任意一控點(diǎn) （骨架點(diǎn)）變化，得出新的Bézier曲線，最后反求Bézier曲線上其它控點(diǎn)，從而更新多骨架點(diǎn)的空間坐標(biāo)，實(shí)現(xiàn)了基于Bézier曲線的多骨架點(diǎn)連續(xù)、光順變形。

我們以3個(gè)連續(xù)的骨架點(diǎn)作為控點(diǎn)為例，進(jìn)行二次Bézier曲線擬合，并依據(jù)曲線上的任意點(diǎn)Qi的變化，更新控點(diǎn)坐標(biāo)P1，其具體過(guò)程如圖2所示。

圖2 插值的二次Bézier曲線

二次Bézier曲線P（t）

已知曲線上3個(gè)頂點(diǎn)Qi（xi，yi，zi） （i＝0，1，2），其中Q0＝P0，Q2＝P2，點(diǎn)Q1可由，l2＝，根據(jù)獲得。將Q1帶入式 （5），即可求得控點(diǎn)P1

1.2.2 3個(gè)骨架點(diǎn)的變換

假設(shè)空間中3個(gè)骨架點(diǎn)Pi（xi，yi，zi），i＝0，1，2，當(dāng)P0點(diǎn)保持固定不變時(shí)，移動(dòng)點(diǎn)P2到點(diǎn)P2′時(shí)，點(diǎn)P1對(duì)應(yīng)的新位置P1′的計(jì)算方法如下：

（1）確定曲線上Q1點(diǎn)的位置；

1）確定參數(shù)tQ的值。令則；

2）根據(jù)式 （5）計(jì)算Q1的坐標(biāo)，即Q1＝P（tQ）；

（2）計(jì)算點(diǎn)P2移到點(diǎn)P2′的移動(dòng)向量；

（3）計(jì)算Q1變化的新坐標(biāo)，其Q1′＝Q1＋t＊vec；

（4）根據(jù)更新的Q1點(diǎn)坐標(biāo)可獲得控點(diǎn)P1的變化 （如圖3所示）。令，則依據(jù)式（6），可得：。

圖3 3個(gè)骨架節(jié)點(diǎn)變化算法

該算法中，首先確定Bézier曲線上的點(diǎn)Q1，并進(jìn)行矢量方向的空間變換，從而獲得新的曲線，最終反求獲得骨架點(diǎn)P1的變化。由算法步驟 （1）中的可知，參數(shù)tQ的取值直接關(guān)系到點(diǎn)Q1的位置和控點(diǎn)P1的更新。本算法中，tQ定義為點(diǎn)P1到點(diǎn)P0的距離與其分別到點(diǎn)P0和點(diǎn)P2的距離和的比值，實(shí)驗(yàn)證明，這樣的取值方法比較tQ隨機(jī)的取值具有更自然的效果。

如圖4所示，黃色點(diǎn)為原始的3個(gè)骨架控點(diǎn)，通過(guò)拉動(dòng)右側(cè)節(jié)點(diǎn)P2到新的空間位置，則節(jié)點(diǎn)P1的位置發(fā)生變化 （紅色點(diǎn)為更新后的控點(diǎn)）。圖4（a）、圖4（b）為人為設(shè)定tQ值，控點(diǎn)的變化結(jié)果；圖4（c）為依據(jù)本算法計(jì)算tQ所獲得的控點(diǎn)，相比較圖4（a）、圖4（b）效果，其位置變化更加自然、合理。

算法充分利用了二次Bézier曲線的一階連續(xù)性，保證了骨架節(jié)點(diǎn)位置的變動(dòng)更加平滑自然。

1.2.3 多骨架點(diǎn)驅(qū)動(dòng)的變換方法

將1.2.2節(jié)中描述的算法應(yīng)用于多個(gè)骨架節(jié)點(diǎn)，即可得到多骨架節(jié)點(diǎn)的連續(xù)平滑變化。

在算法中，選定P0至Pn－1n個(gè)骨架節(jié)點(diǎn)，已知節(jié)點(diǎn)Pn－1的位置變化，先以Pn－3，Pn－2，Pn－1這3個(gè)節(jié)點(diǎn)為一個(gè)單元，計(jì)算出參數(shù)t，以及Pn－2的位置變化，然后以循環(huán)的方式分別獲得Pn－3至P1點(diǎn)的位置變化。算法中，以3個(gè)骨架節(jié)點(diǎn)為單元，t的值是與其所處單元中3個(gè)節(jié)點(diǎn)的位置相關(guān)的，從而更加保證節(jié)點(diǎn)變化的平滑性。圖5顯示了多個(gè)骨架節(jié)點(diǎn)運(yùn)用上述算法進(jìn)行變換后的效果。

圖4 tQ取不同值時(shí)骨架控點(diǎn)的變化

圖5 多節(jié)點(diǎn)骨架變換

1.3 多骨架點(diǎn)驅(qū)動(dòng)的模型變形

為了使模型表面變形更具光滑性及連續(xù)性，在此引入具有勢(shì)函數(shù)的元球。

定義2 設(shè)模型空間R3上任意點(diǎn)v＝ （x，y，z），Deform（v）為變形映射，它把點(diǎn)v變換到v′，Δv為v點(diǎn)的偏移量。依據(jù)廣義元球約束變形原理，單個(gè)約束源Pi引起的變形函數(shù)可定義為

式中：r（v，Pi）——模型上任意點(diǎn)v到約束中心點(diǎn)Pi（約束源）的歐式距離，f（r，Ri）——定義于半徑為Ri的元球上的勢(shì)函數(shù)。目前采用的勢(shì)函數(shù)基本有4種：Borrel的冪函數(shù)、Nishimura的分段二項(xiàng)式、Murakami的四次多項(xiàng)式、Wyvill的六次多項(xiàng)式［17］。本文采用了變形效果較好的Wyvill的六次多項(xiàng)式作為勢(shì)函數(shù)

從函數(shù)f（r，Ri）中可以看出約束源Pi在約束半徑R下定義了一個(gè)局部區(qū)域，在r≤Ri的區(qū)域內(nèi)，多邊形模型網(wǎng)格點(diǎn)會(huì)受到約束源的影響，而對(duì)于這個(gè)局部區(qū)域外的點(diǎn)，則不會(huì)出現(xiàn)位置的變化。Wyvill的勢(shì)函數(shù)有效保證了變形效果的局部性與光順性。

在變形過(guò)程中，用戶所選的骨架關(guān)節(jié)點(diǎn)，即為約束源Si，i＝0，1，2……n－1，約束半徑R則由關(guān)節(jié)點(diǎn)到其所對(duì)應(yīng)的區(qū)域的最大歐氏距離來(lái)確定

假設(shè)Pi＝ （xi，yi，zi）為選中的骨架關(guān)節(jié)點(diǎn)Si（約束源）所對(duì)應(yīng)的連通區(qū)域上點(diǎn)，d（dx，dy，dz）是約束源S的偏移量 （可由用戶交互式拖拽操作完成），Displacement（p）是平移變形映射，則有以下計(jì)算公式

這樣，在牽動(dòng)最后一個(gè)關(guān)節(jié)點(diǎn)移動(dòng)后，就會(huì)得到與之相連的多個(gè)骨架節(jié)點(diǎn)的以及其周圍面片相應(yīng)的動(dòng)畫(huà)變形。

骨架節(jié)點(diǎn)約束的區(qū)域變形算法描述如下：

typedef struct SubConnectPointSet//連通子集定義

｛ VNode＊＊connective＿VNode；

struct SubConnectPointSet＊next；

｝SubConnectPointSet；

typedef struct VNode //模型頂點(diǎn)定義

｛ float x，y，z；//模型頂點(diǎn)的空間坐標(biāo)值

void＊belongtoSCPS；//該頂點(diǎn)所屬的子連通點(diǎn)集

｝VNode；

typedef struct SkeletonJoint//骨架節(jié)點(diǎn)定義

｛float x，y，z；//骨架節(jié)點(diǎn)的坐標(biāo)

SubConnectPointSet＊belongtoSCPS；//該節(jié)點(diǎn)所屬的子連通點(diǎn)集。

｝SkeletonJoint；

算法步驟：

（1）交互式確定骨架節(jié)點(diǎn)，獲取約束源的坐標(biāo)SkeletonJoint＊S；

（2）遍歷骨架點(diǎn)所對(duì)應(yīng)的區(qū)域 （S－＞belongtoSCPS－＞connective＿VNode），計(jì)算區(qū)域中各頂點(diǎn)VNode＊vi距約束源S的歐式距離r：r（vi，S）；

（3）獲得約束區(qū)域的最大歐氏距離作為約束半徑R：R＝Max（r（vi，S））；

（4）計(jì)算對(duì)應(yīng)區(qū)域上頂點(diǎn)VNode＊vi的勢(shì)函數(shù)：f（r，；

（5）交互式拖拽骨架點(diǎn)S進(jìn)行空間平移d（dx，dy，dz），進(jìn)行相應(yīng)區(qū)域頂點(diǎn)的轉(zhuǎn)換，生成新的空間坐標(biāo)：Displacement（vi）＝vi＋d＊f（r，R）。

圖6是針對(duì)同一個(gè)長(zhǎng)方體模型進(jìn)行骨架驅(qū)動(dòng)變形的結(jié)果。圖6（a）為提取的長(zhǎng)方體的骨架；圖6（b）、圖6（c）為通過(guò)對(duì)骨架進(jìn)行交互式變形，獲取各骨架點(diǎn)的空間位移。圖6（d）為骨架空間位移后獲取的變形效果。圖7則顯示了對(duì)鞋模型進(jìn)行骨架驅(qū)動(dòng)變形的效果。

2 實(shí)驗(yàn)結(jié)果

我們?cè)诒简vⅣ2.8GHz，1G內(nèi)存的PC機(jī)上，以MFC和OpenGL圖形庫(kù)為基礎(chǔ)，使用VC＋＋6.0作為開(kāi)發(fā)環(huán)境，進(jìn)行了本算法的驗(yàn)證。

本算法中測(cè)地線距離是利用Dijkstra最短路徑近似得到，它的時(shí)間復(fù)雜度為O（NlogN），N代表模型頂點(diǎn)總個(gè)數(shù)。構(gòu)建骨架關(guān)節(jié)點(diǎn) （即子連通點(diǎn)集），所需消耗O（N）的時(shí)間復(fù)雜度。對(duì)于各個(gè)骨架點(diǎn)對(duì)應(yīng)的模型子區(qū)域以及其勢(shì)函數(shù)與偏移量的計(jì)算為O（M），M（M＜N）為各子區(qū)域所對(duì)應(yīng)的模型頂點(diǎn)的平均數(shù)。因此，算法總的時(shí)間復(fù)雜度為O（NlogN）。表1為本算法的實(shí)驗(yàn)性能分析。

表1 算法運(yùn)行特性分析

如表2所示，我們使用測(cè)地線距離對(duì)模型進(jìn)行分割并提取骨架關(guān)節(jié)點(diǎn)。然后，使用交互方式確定需要變形區(qū)域的多個(gè)約束關(guān)節(jié)點(diǎn)，采用拖拽末端骨架關(guān)節(jié)點(diǎn)的直觀方式實(shí)現(xiàn)局部區(qū)域的變形。表2中 （1）行所示為棱柱模型的變形，我們把棱柱模型分6區(qū)間提取Reeb圖骨架，然后選取棱柱上部4個(gè)骨架節(jié)點(diǎn)為驅(qū)動(dòng)節(jié)點(diǎn)，對(duì)棱柱進(jìn)行變形，在此結(jié)果的基礎(chǔ)上我們繼續(xù)在上部選取3個(gè)骨架節(jié)點(diǎn)、在下部選取4個(gè)骨架節(jié)點(diǎn)分別進(jìn)行多骨架節(jié)點(diǎn)驅(qū)動(dòng)變形，得到了中間和右邊的變形結(jié)果。

在表2中（2）行，展示了對(duì)海豚模型提取骨架后，選取頭部4個(gè)骨架節(jié)點(diǎn)進(jìn)行變形的效果；在表2中 （3）行，對(duì)月亮模型提取骨架并選取其面部鼻梁處的4個(gè)骨架節(jié)點(diǎn)進(jìn)行驅(qū)動(dòng)，得到了月亮模型面部的平滑變形。表2中 （4）為將貓模型提取骨架后分別對(duì)去上肢和雙腿進(jìn)行變形的結(jié)果。

?

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

本文基于Bézier曲線的擬合的方法提出了多骨架點(diǎn)驅(qū)動(dòng)的交互式局部變形方法。我們通過(guò)多分辨率Reeb圖骨架的提取方法，可以對(duì)所有模型進(jìn)行骨架提取，并且確定了骨關(guān)節(jié)點(diǎn)與骨架所對(duì)應(yīng)的局部約束區(qū)域，通過(guò)交互式拖動(dòng)實(shí)現(xiàn)基于多骨架點(diǎn)的局部變形。有效地保持了模型的局部特征，確保了模型動(dòng)畫(huà)的直觀性、高效性。且在提取骨架時(shí)所需分層數(shù)目和需要驅(qū)動(dòng)的骨架節(jié)點(diǎn)的數(shù)目都可以交互式的靈活確定，使得使用十分方便簡(jiǎn)單。通過(guò)實(shí)驗(yàn)證明，該算法計(jì)算量小，易于控制。此方法可通用在計(jì)算機(jī)造型、動(dòng)畫(huà)、游戲以及電影特效中。

［1］HU Shimin，YANG Yongliang，LAI Yukun.Research progress of digital geometry processing ［J］.Chinese Journal of Computers，2009，32 （8）：1451－1469 （in Chinese）. ［胡事民，楊永亮，來(lái)煜坤，數(shù)字幾何處理研究進(jìn)展 ［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32 （8）：1451－1469.］

［2］Sven Forstmann，Jun Ohya.Fast Seletal animation by skinned arc－spline based deformation ［C］.Eurographics，2006.

［3］YAN Hanbing，HU Shimin，Ralph Martin.Skeleton－based shape deformation using simplex transformations ［G］.LNCS 4035：Proceedings of Computer Graphics International.Berlin Heidelberg：Springer－Verlag，2006：66－77.

［4］YAN Hanbing，HU Shimin，Ralph R Martin，et al.Shape deformation using a skeleton to drive simplex transformations［J］.IEEE Transactions on Visualization and Computer Graphics，2008，14 （3）：693－706.

［5］SONG Chao，ZHANG Hongxin，HUANG Jin，et al.Fast and physical plausible elastic－deformation driven by skeleton［J］.Chinese Journal of Computers，2006，29 （12）：2194－2200（in Chinese）.［宋超，張宏鑫，黃勁，等.骨架驅(qū)動(dòng)的快速似然彈性變形 ［J］.計(jì) 算 機(jī) 學(xué) 報(bào)，2006，29 （12）：2194－2200.］

［6］HAN Li，CHU Bingzhi，GAO Xiaoshan.Gaussian curvature constrained skeleton extraction method based on MRG ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2009，21 （9）：1227－1231 （in Chinese）. ［韓麗，楚秉智，高小山.高斯曲率約束的MRG骨架提取優(yōu)化算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21 （9）：1227－1231.］

［7］Lazarus F，Verroust A.Level set diagrams of polyhedral objects［C］.Proceeding of 5th ACM Symp Solid Modeling and Applications，1999：130－140.

［8］Donald Hearn，Pauline Baker M.Computer graphics ［M］.CAI Shijie，WU Chunrong，SUN Zhengxing，transl.2nd ed.Beijing：Electronic Industry Press，2002 （in Chinese）.［Donald Hearn，Pauline Baker M.計(jì)算機(jī)圖形學(xué) ［M］.蔡士杰，吳春镕，孫正興，譯.2版.北京：電子工業(yè)出版社，2002.］

［9］Francis S Hill Jr，Stephen M Kelley.Computer graphics using OpenGL ［M］.HU Shimin，LIU Ligang，LIU Yongjin，et al transl.3rd ed.Beijing：Tsinghua University Press，2009 （in Chinese）.［Francis S Hill，Stephen M Kelley Jr.計(jì)算機(jī)圖形學(xué) （OpenGL版）［M］.胡事民，劉利剛，劉永進(jìn)，等譯.3版.北京：清華大學(xué)出版社，2009.］

［10］PENG Q S，JIN X G，WAN H G，et al.The basis of computer graphics applications ［M］.Beijing：Science Press，2009（in Chinese）.［彭群生，金小剛，萬(wàn)華根，等.計(jì)算機(jī)圖形學(xué)應(yīng)用基礎(chǔ) ［M］.北京：科學(xué)出版社，2009.］

［11］Alvaro E，Cuno Parari，Claudio Esperanca.Shape－sensitive MLS deformation ［J］.Vis Comput，2009，25 （10）：911－922.