李明，張湘玉，馬希青

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

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

1 局部骨架的提取流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 截平面的生成

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

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

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

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

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

求解S0和S1兩初始截平面中心點(diǎn)(求解過程詳見第2.4和2.5)，將其連接線段m等分，分別得到m－1個(gè)等分頂點(diǎn)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ù)各等分頂點(diǎn)Ci(等分截面上的點(diǎn))和等分截面的法向量qi，可求得各等分點(diǎn)處截平面。

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

2.4 截交線的求解

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

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

空間截平面方程為

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

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

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

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

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

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

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

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

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

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

2.5 生成骨架線

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

3 骨架提取實(shí)例

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

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

4 結(jié)論

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

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

3)該方法算法簡(jiǎn)單，易于控制。

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

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

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

［3］劉小鳳，吳艷蘭，胡海.面狀要素的多層次骨架線提?。跩］.測(cè)繪學(xué)報(bào)，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］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24(6):793 －798.

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

［7］黃香，程筱勝，戴寧，等.基于骨架驅(qū)動(dòng)的牙齒形態(tài)設(shè)計(jì)［J］.東南大學(xué)學(xué)報(bào):醫(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］王海強(qiáng)，毛天露，王兆其，等.運(yùn)動(dòng)狀態(tài)下虛擬人全身皮膚實(shí)時(shí)變形方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(12):2722 －2728.

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

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