李明，張湘玉，馬希青

(河北工程大學(xué)機電工程學(xué)院，河北邯鄲056038)

現(xiàn)有骨架提取方法主要有拓撲細化法、距離變換法、Voronoi圖和Reeb圖法，以及手工提取方法等［1－8］。這些方法大多應(yīng)用于模型骨骼關(guān)節(jié)動畫中的整體骨架提取，有的可以實現(xiàn)骨架的自動提取但算法比較復(fù)雜;有的通過交互方式得到骨架，算法簡單但交互過程過于繁瑣，甚至得到的骨架不夠精確。另外，現(xiàn)實中在對一些模型進行運動模擬或變形設(shè)計時，往往并不需要對模型進行整體骨架提取，而只需要針對其局部區(qū)域進行變形，如:只考慮動物四肢的運動，只進行椅子扶手的設(shè)計，只修改水壺壺嘴的形狀等等。因此，本文提出一種三維網(wǎng)格模型局部區(qū)域骨架交互式提取方法，并應(yīng)用于自行開發(fā)的骨架驅(qū)動變形軟件中，實現(xiàn)了模型局部骨架的精確提取。

1 局部骨架的提取流程

當(dāng)三維網(wǎng)格模型整體或局部具有近似圓柱體的形狀時，可認為其是廣義圓柱體。此時骨架曲線可認為是廣義圓柱體的軸線［9］。本文利用截交線求骨架點的方法就是基于上述觀點。首先對三維網(wǎng)格模型是廣義圓柱體的局部區(qū)域作幾何截面，得到幾何截面與模型的截交線，然后求取截交線的幾何中心得到骨架點，最后順次連接各骨架點即得到局部骨架。圖1是局部骨架提取流程圖。

2 局部骨架的交互式提取方法

骨架提取算法需要對模型上局部區(qū)域的邊界點進行拾取，然后通過拾取不在一直線上的三點確定出初始截平面。因此，網(wǎng)格頂點的拾取是成功實現(xiàn)局部骨架提取的基礎(chǔ)。

2.1 基于OpenGL的網(wǎng)格頂點拾取

為了利用OpenGL拾取網(wǎng)格頂點，須先對各個頂點使用不同的ID進行命名，定義鼠標(biāo)所在位置的拾取矩陣，然后在選擇模式下對網(wǎng)格進行虛擬繪圖。在具體操作中，由于可能會拾取到鼠標(biāo)點附近的多個頂點，故需要對選中的頂點進行深度處理，以保證頂點的準(zhǔn)確拾取。

選擇模式下，頂點拾取繪圖函數(shù)為

對空間三維網(wǎng)格頂點定義了相應(yīng)的類，點類定義如下:

至此，由于每個網(wǎng)格頂點ID的賦予規(guī)則與相應(yīng)存儲在vector中的索引號相一致，故一旦選中某個頂點，就可以根據(jù)其ID得到其在vector中的位置，繼而得到該頂點的相關(guān)信息。

拾取頂點的結(jié)構(gòu)體定義如下:

在拾取過程中，有時會出現(xiàn)同時選中多個頂點的情況，如封閉網(wǎng)格和S形網(wǎng)格等。此時應(yīng)對所有拾取到的頂點進行深度分析，并從中找出深度值最小的頂點ID，此頂點即為選中對象，它與觀察者的距離最小。

2.2 確定模型的局部區(qū)域

確定模型的局部區(qū)域其實就是對三維網(wǎng)格模型的頂點和三角面片信息進行采集。即:先劃定局部區(qū)域邊界，然后在邊界內(nèi)用種子生長算法確定局部區(qū)域［10－11］。具體實現(xiàn)步驟如下:

在擬提取區(qū)域邊界位置處，按一定方向拾取若干個網(wǎng)格頂點。

利用Dijkstra算法，求解網(wǎng)格上相鄰兩拾取頂點的最短路徑，并按順序首尾相連各最短路徑折線段，即得局部區(qū)域的邊界曲線。同時將邊界曲線上的網(wǎng)格頂點存入邊界點集K0。

在骨架提取區(qū)域內(nèi)拾取一網(wǎng)格頂點作為種子點，并將該點分別存入點集K和K1;同時將種子頂點所在三角面片不重復(fù)保存到三角面片集合J中。

對點集K中各頂點進行1－環(huán)鄰域(頂點1－環(huán)鄰域是指該頂點及與其相鄰接的邊和面所構(gòu)成的局部網(wǎng)格)搜索，將搜索到的且不屬于點集K0和K1的頂點保存到點集K1和清空后的點集K中;這時需要判斷點集K中各頂點所在三角面片是否已存在三角面片集合J中。若沒有，不重復(fù)保存到三角面片集合J中。

判斷點集K是否為空集。若是，結(jié)束算法;否則，重復(fù)執(zhí)行上一步驟。

由此得到的點集K1和三角面片集合J即為所需要的骨架提取區(qū)域的網(wǎng)格信息。

2.3 截平面的生成

三維網(wǎng)格模型局部區(qū)域截平面生成的好壞直接影響獲得骨架點位置準(zhǔn)確性。故下面兩類截平面的生成至關(guān)重要。

初始截平面。在骨架提取區(qū)域兩端位置處的網(wǎng)格表面拾取三個不共線的網(wǎng)格頂點，據(jù)此確定出初始截平面。圖2給出了在圓桌腿部區(qū)域確定的兩個初始截平面。

等分截平面。在骨架提取區(qū)域兩端初始截平面中間進行插值，得到若干等分截平面。其實現(xiàn)的步驟如下:

首先對兩端初始截平面S0和S1的法向量n0和n1進行叉乘，得到旋轉(zhuǎn)軸。然后由空間向量夾角公式得到旋轉(zhuǎn)角度α。

根據(jù)要插入的等分截平面?zhèn)€數(shù)，這里不妨設(shè)為m－1個，對旋轉(zhuǎn)角度α進行m等分。

求解S0和S1兩初始截平面中心點(求解過程詳見第2.4和2.5)，將其連接線段m等分，分別得到m－1個等分頂點Ci(i=1，2，…，m－1)。

由初始截平面S0的法向量n0分別繞旋轉(zhuǎn)軸旋轉(zhuǎn)角度值 α·i/m(i=1，2，…，m －1)，得到各等分截面的法向量 qi(i=1，2，…，m －1)。

根據(jù)各等分頂點Ci(等分截面上的點)和等分截面的法向量qi，可求得各等分點處截平面。

圖3給出了等分截平面生成示意圖。

2.4 截交線的求解

求解截交線其實就是求解幾何截面與三維網(wǎng)格模型局部區(qū)域三角面片交點的有序集合。本文求解截交線分為兩步:(1)確定與幾何截面相交的三角面片。(2)確定幾何截面與相交三角面片的交點。

確定相交三角面片。幾何截面與三角面片的相交情況分為五種，如圖4所示。

空間截平面方程為

將三維網(wǎng)格模型三角面片的A、B、C三個頂點坐標(biāo)分別代入方程(1)，頂點相對幾何截面的空間位置不同，F(xiàn)的值也各不相同。表1中給出了幾何截面與三角面片相交的五種情況下，對應(yīng)三角面片三個頂點的不同F(xiàn)值。據(jù)此就可以提取出局部區(qū)域內(nèi)所有與幾何截面相交的三角面片。

表1 不同相交情況下三角面片頂點F值Tab.1 Triangular patches of different vertex Fvalues intersect case

求解交點。得到所有與截平面相交的三角面片后，還需要求解截平面與所有這些三角面片的交點，將這些交點按一定順序連接即得到截交線。在確定相交三角面片環(huán)節(jié)得到的初始相交三角面片集合中包含了圖4中的1、2、3、4四種情況，欲求解交點，需要首先對初始相交三角面片集合進行相應(yīng)處理，然后結(jié)合搜索、求交算法得到交點。

對初始相交三角面片集合進行預(yù)處理。針對圖4中第1種情況的兩個共邊相交三角面片，集合中只保留其中一個三角面片，對另一個進行刪除;對于第2種情況的相交三角面片全部進行刪除，這樣處理后得到相交三角面片集合V。

從相交三角面片集合V中，任意指定某一三角面片S作為起始搜索三角面片S0，定義已搜索三角面片集合VS初始為空。

搜索與S相鄰(含有共同頂點，非VS集合內(nèi))的三角面片T。

記錄S與T兩個相鄰三角面片共同頂點的個數(shù)p，判斷S與T相同頂點是否位于截平面上或相交線段是否與截平面相交，若是，執(zhí)行下一步驟;否則，轉(zhuǎn)上一步驟。

若p=1，則S與T相交共同頂點即所求截交線上的點;若p=2，則S與T相交線段與截平面的交點即為所求，將求得交點保存至交點集合U內(nèi)。

保存S至已搜索三角形集合VS內(nèi)，更新搜索三角形S=T，判斷S與起始搜索三角形S0是否為同一三角形，若是，算法結(jié)束，否則轉(zhuǎn)第3步驟。

圖5中給出了幾何截面與相鄰三角面片相交的七種情況。通過以上算法，就可以得到截平面與所有相交三角面片的交點集合U，順序連接U中各點即可生成截交線。圖6所示給出了圓桌腿部網(wǎng)格模型表面初始截交線及放大圖。

2.5 生成骨架線

三維模型的骨架是模型的中心曲線，曲線上每個點是模型相應(yīng)幾何截面的中心。本文首先根據(jù)網(wǎng)格模型與初始及等分截平面求交獲得若干截交線，然后分別計算這些截交線上頂點的幾何中心，即得到若干骨架點，將這些骨架點按順序連接生成局部骨架線。

3 骨架提取實例

分別選取單峰駱駝腿部、圓桌腿部和茶壺的壺嘴作為模型局部骨架提取區(qū)域。模型局部骨架提取效果，如圖7、圖8、圖9所示。

從上述模型的局部骨架提取效果圖，可以看出本文基于截交線的骨架提取算法可以實現(xiàn)對三維網(wǎng)格模型局部骨架的精確提取。

4 結(jié)論

1)與傳統(tǒng)手工提取骨架相比，該方法通過人機交互生成初始截平面，自動插值獲得中間等分截平面，交互更為方便、快捷。

2)根據(jù)截平面與模型相交線確定骨架點，可以實現(xiàn)對三維模型局部骨架的精確提取，所提取骨架位于模型的中心位置。

3)該方法算法簡單，易于控制。

4)該方法也存在一些不足之處，比如:當(dāng)三維網(wǎng)格模型局部區(qū)域頂點分布很不均勻時，所提取到的骨架與預(yù)期骨架之間存在一定差距。

［1］曾榮軍.基于聚類分析的三維網(wǎng)格骨架提?。跠］.中南大學(xué)，2011.

［2］劉俊濤，劉文予，吳彩華，等.一種提取物體線形骨架的新方法［J］.自動化學(xué)報，2008，34(6):617 －622.

［3］劉小鳳，吳艷蘭，胡海.面狀要素的多層次骨架線提?。跩］.測繪學(xué)報，2013，42(4):588 －594.

［4］CEM DIREKOGLU，ROZENN DAHYOT ，MICHAEL MANZKE.On using anisotropic diffusion for skeleton extraction［J］ .International Journal of Computer Vision，2012，100(2):170 ～189.

［5］林佼，李 重，金小剛，等.基于凸殼與有向包圍盒的骨架提取方法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2012，24(6):793 －798.

［6］馬銳，伍鐵如.基于廣義勢場的三維形體多層次線骨架構(gòu)建［J］.計算機應(yīng)用，2011，31(1):16－19.

［7］黃香，程筱勝，戴寧，等.基于骨架驅(qū)動的牙齒形態(tài)設(shè)計［J］.東南大學(xué)學(xué)報:醫(yī)學(xué)版，2012，31(1):18－23.

［8］CAO J，TAGLIASACCHI A，OLSON M，et al.Point cloud skeletons via laplacian based contraction［C］.Shape Modeling International Conference(SMI)，2010.IEEE，2010:187－197.

［9］王海強，毛天露，王兆其，等.運動狀態(tài)下虛擬人全身皮膚實時變形方法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005，17(12):2722 －2728.

［10］張湘玉.基于細分的曲線曲面變形技術(shù)研究［D］.南京:南京航空航天大學(xué)，2011.

［11］郭來德，劉輝林，劉蘭哲，等.農(nóng)業(yè)信息搜索引擎設(shè)計與實現(xiàn)［J］.河北工程大學(xué)學(xué)報:自然科學(xué)版，2007，24(3):41－43.