骨架驅動的三維模型變形方法

韓 麗，齊曉明

（遼寧師范大學 計算機與信息技術學院，遼寧 大連116029）

0 引 言

三維網格模型的變形通常指在不改變其拓撲連接的同時改變網格頂點的坐標，使得模型的姿態發生變化［1］，在幾何建模和計算機動畫中有著非常重要的應用。

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

文獻 ［2］將網格表面的點與三角曲線綁定，通過對三角曲線的變形，達到網格表面的形變；文獻 ［3－4］提出了一種以單純形為操作單元的骨架驅動變形方法；文獻 ［5］則將動力學公式和有限元方法結合，對三維模型進行骨架驅動變形，取得了良好效果。以上方法均集中在單一骨架驅動的模型變形。

本文在文獻 ［2］的基礎上，改變了骨架約束方式以及約束區域劃分方式，提出了一種新的多骨架驅動的三維模型變形方法。首先，基于Reeb圖方法實現網格模型的拓撲骨架提取，其次，將多個骨架節點進行曲線擬合，并通過反求曲線控點的方式實現多骨架點驅動的骨架變換。最終，實現模型自然、光順的變形效果。

1 變形算法及原理

1.1 骨架約束點的確定

三維模型的骨架是將三維模型的拓撲特性可視化以后形成的類似骨架且嵌于三維模型內部的圖形。本文采用了文獻 ［9］提出的多分辨率Reeb圖的原理，進行模型的骨架提取。

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

對于曲面上的每一組等價點集合，我們使用一個節點表示，相鄰節點使用邊連接，從而形成了圖結構，即Reeb骨架圖 （RG），如圖1（a）為使用高度函數作為μ函數，進行4等分區間劃分所提取的Reeb圖骨架。

根據Reeb圖的思想，不同的連續函數μ會產生不同的Reeb圖。文獻 ［7］引入測地線距離作為連續函數，創建了具有平移、旋轉不變性的μ函數。然而，由于需要人為選擇源點來計算各個頂點的測地線距離，不同的源點選擇則獲得不同的Reeb圖，因此，使提取的骨架具有極不穩定性。多分辨率Reeb圖簡稱MRG進一步引入了基本點的概念，其基本思想是將μ函數定為

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

通過應用最短路徑算法，可計算網格頂點v到所有基本點bi測地線距離之和。從而，獲得各個網格頂點的μ函數值μ（v）

最終，我們將μ函數值進行規一化處理為μN（v），并將μN函數值區間進行k等分，找出劃分后每個區間內的子連通點集，聚合成一個骨架的關節點，最后按一定順序連接這些關節點即生成骨架。

圖1（b）示意了使用測地線距離作為連續函數μ，并進行4等分的區域劃分 （如圖中不同顏色所示），最終提取各等價區域的骨架節點，構成Reeb圖骨架結構。

Reeb圖中的每個骨架節點對應一定范圍的模型頂點和面片，即子連通點集，則骨架關節點與模型面片之間就產生了綁定關系，關節點的移動就會影響到與其有綁定關系的模型面片與頂點。

1.2 多骨架驅動的三維模型變形算法

1.2.1 基于骨架點的Bézier擬合曲線

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

圖1 多分辨率Reeb圖

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

我們以3個連續的骨架點作為控點為例，進行二次Bézier曲線擬合，并依據曲線上的任意點Qi的變化，更新控點坐標P1，其具體過程如圖2所示。

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

二次Bézier曲線P（t）

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

1.2.2 3個骨架點的變換

假設空間中3個骨架點Pi（xi，yi，zi），i＝0，1，2，當P0點保持固定不變時，移動點P2到點P2′時，點P1對應的新位置P1′的計算方法如下：

（1）確定曲線上Q1點的位置；

1）確定參數tQ的值。令則；

2）根據式 （5）計算Q1的坐標，即Q1＝P（tQ）；

（2）計算點P2移到點P2′的移動向量；

（3）計算Q1變化的新坐標，其Q1′＝Q1＋t＊vec；

（4）根據更新的Q1點坐標可獲得控點P1的變化 （如圖3所示）。令，則依據式（6），可得：。

圖3 3個骨架節點變化算法

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

如圖4所示，黃色點為原始的3個骨架控點，通過拉動右側節點P2到新的空間位置，則節點P1的位置發生變化 （紅色點為更新后的控點）。圖4（a）、圖4（b）為人為設定tQ值，控點的變化結果；圖4（c）為依據本算法計算tQ所獲得的控點，相比較圖4（a）、圖4（b）效果，其位置變化更加自然、合理。

算法充分利用了二次Bézier曲線的一階連續性，保證了骨架節點位置的變動更加平滑自然。

1.2.3 多骨架點驅動的變換方法

將1.2.2節中描述的算法應用于多個骨架節點，即可得到多骨架節點的連續平滑變化。

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

圖4 tQ取不同值時骨架控點的變化

圖5 多節點骨架變換

1.3 多骨架點驅動的模型變形

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

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

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

從函數f（r，Ri）中可以看出約束源Pi在約束半徑R下定義了一個局部區域，在r≤Ri的區域內，多邊形模型網格點會受到約束源的影響，而對于這個局部區域外的點，則不會出現位置的變化。Wyvill的勢函數有效保證了變形效果的局部性與光順性。

在變形過程中，用戶所選的骨架關節點，即為約束源Si，i＝0，1，2……n－1，約束半徑R則由關節點到其所對應的區域的最大歐氏距離來確定

假設Pi＝ （xi，yi，zi）為選中的骨架關節點Si（約束源）所對應的連通區域上點，d（dx，dy，dz）是約束源S的偏移量 （可由用戶交互式拖拽操作完成），Displacement（p）是平移變形映射，則有以下計算公式

這樣，在牽動最后一個關節點移動后，就會得到與之相連的多個骨架節點的以及其周圍面片相應的動畫變形。

骨架節點約束的區域變形算法描述如下：

typedef struct SubConnectPointSet//連通子集定義

｛ VNode＊＊connective＿VNode；

struct SubConnectPointSet＊next；

｝SubConnectPointSet；

typedef struct VNode //模型頂點定義

｛ float x，y，z；//模型頂點的空間坐標值

void＊belongtoSCPS；//該頂點所屬的子連通點集

｝VNode；

typedef struct SkeletonJoint//骨架節點定義

｛float x，y，z；//骨架節點的坐標

SubConnectPointSet＊belongtoSCPS；//該節點所屬的子連通點集。

｝SkeletonJoint；

算法步驟：

（1）交互式確定骨架節點，獲取約束源的坐標SkeletonJoint＊S；

（2）遍歷骨架點所對應的區域 （S－＞belongtoSCPS－＞connective＿VNode），計算區域中各頂點VNode＊vi距約束源S的歐式距離r：r（vi，S）；

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

（4）計算對應區域上頂點VNode＊vi的勢函數：f（r，；

（5）交互式拖拽骨架點S進行空間平移d（dx，dy，dz），進行相應區域頂點的轉換，生成新的空間坐標：Displacement（vi）＝vi＋d＊f（r，R）。

圖6是針對同一個長方體模型進行骨架驅動變形的結果。圖6（a）為提取的長方體的骨架；圖6（b）、圖6（c）為通過對骨架進行交互式變形，獲取各骨架點的空間位移。圖6（d）為骨架空間位移后獲取的變形效果。圖7則顯示了對鞋模型進行骨架驅動變形的效果。

2 實驗結果

我們在奔騰Ⅳ2.8GHz，1G內存的PC機上，以MFC和OpenGL圖形庫為基礎，使用VC＋＋6.0作為開發環境，進行了本算法的驗證。

本算法中測地線距離是利用Dijkstra最短路徑近似得到，它的時間復雜度為O（NlogN），N代表模型頂點總個數。構建骨架關節點 （即子連通點集），所需消耗O（N）的時間復雜度。對于各個骨架點對應的模型子區域以及其勢函數與偏移量的計算為O（M），M（M＜N）為各子區域所對應的模型頂點的平均數。因此，算法總的時間復雜度為O（NlogN）。表1為本算法的實驗性能分析。

表1 算法運行特性分析

如表2所示，我們使用測地線距離對模型進行分割并提取骨架關節點。然后，使用交互方式確定需要變形區域的多個約束關節點，采用拖拽末端骨架關節點的直觀方式實現局部區域的變形。表2中 （1）行所示為棱柱模型的變形，我們把棱柱模型分6區間提取Reeb圖骨架，然后選取棱柱上部4個骨架節點為驅動節點，對棱柱進行變形，在此結果的基礎上我們繼續在上部選取3個骨架節點、在下部選取4個骨架節點分別進行多骨架節點驅動變形，得到了中間和右邊的變形結果。

在表2中（2）行，展示了對海豚模型提取骨架后，選取頭部4個骨架節點進行變形的效果；在表2中 （3）行，對月亮模型提取骨架并選取其面部鼻梁處的4個骨架節點進行驅動，得到了月亮模型面部的平滑變形。表2中 （4）為將貓模型提取骨架后分別對去上肢和雙腿進行變形的結果。

?

3 結束語

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

［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）. ［胡事民，楊永亮，來煜坤，數字幾何處理研究進展 ［J］.計算機學報，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）.［宋超，張宏鑫，黃勁，等.骨架驅動的快速似然彈性變形 ［J］.計 算 機 學 報，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骨架提取優化算法 ［J］.計算機輔助設計與圖形學學報，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.計算機圖形學 ［M］.蔡士杰，吳春镕，孫正興，譯.2版.北京：電子工業出版社，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.計算機圖形學 （OpenGL版）［M］.胡事民，劉利剛，劉永進，等譯.3版.北京：清華大學出版社，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）.［彭群生，金小剛，萬華根，等.計算機圖形學應用基礎 ［M］.北京：科學出版社，2009.］

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