三角網(wǎng)格模型骨架提取算法

王洪申 張家振 張小鵬

摘? ?要：骨架圖能夠直觀表達(dá)三維模型幾何形狀，很好地反映模型的拓?fù)涮卣?，在工業(yè)機(jī)器人抓取、特征識(shí)別等領(lǐng)域有著廣泛的應(yīng)用。針對三角網(wǎng)格表達(dá)的工業(yè)零件給出一種骨架提取算法，該算法采用Reeb圖對三角網(wǎng)格進(jìn)行骨架的抽取運(yùn)算。首先讀取三角網(wǎng)格文件，并對復(fù)雜的三角網(wǎng)格進(jìn)行簡化處理，然后遍歷所有的三角網(wǎng)格，采用Dijkstra算法抽取基本點(diǎn)集，根據(jù)定義的連續(xù)函數(shù)計(jì)算每個(gè)頂點(diǎn)的函數(shù)值，最后根據(jù)函數(shù)值得出模型的基本骨架。實(shí)驗(yàn)表明，該算法具有良好的計(jì)算效果和效率，提取出的骨架圖較好地保存了三維模型拓?fù)浣Y(jié)構(gòu)和姿態(tài)，可作為后續(xù)研究三維模型搜索的特征描述符。

關(guān)鍵詞：骨架圖;三角網(wǎng)格;三維模型;拓?fù)浣Y(jié)構(gòu);Reeb圖

中圖分類號：G633.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：1003—6199（2020）02—0145—05

Abstract：The skeleton diagram can visually express the geometry of the 3D model and reflect the topological features of the model well. It has a wide range of applications in the fields of industrial robot capture and feature recognition. A skeleton extraction algorithm is proposed for the industrial parts expressed by the triangle mesh. The algorithm uses the Reeb diagram to extract the skeleton from the triangular mesh. First read the triangle mesh file，and simplify the complex triangle mesh，then traverse all the triangle meshes，extract the basic point set by Dijkstra algorithm，calculate the function value of each vertex according to the defined continuous function，and finally The function deserves the basic skeleton of the model. Experiments show that the proposed algorithm has good computational efficiency and efficiency. The extracted skeleton map preserves the topology and pose of the 3D model，and can be used as a feature descriptor for the subsequent research of 3D model search.

Key words：skeleton diagram;triangular mesh;3D model;topology;Reeb diagram

隨著計(jì)算機(jī)圖形學(xué)的發(fā)展，對三維模型的研究日益深入，骨架作為形狀表示的一種有效形式，在三維模型的各個(gè)研究領(lǐng)域被運(yùn)用。骨架的狹義定義最初由Blum[1]提出，當(dāng)時(shí)他稱骨架為“中軸”（Medial Axis）[2]。骨架的經(jīng)典定義有兩種[3]：一種是燒草模型，如圖1所示，從模型表面開始點(diǎn)火，火焰從物體邊界上的兩點(diǎn)同時(shí)向內(nèi)部推進(jìn)，軌跡隨時(shí)間形成等距的同心圓，同心圓的相遇點(diǎn)所構(gòu)成的集合即為骨架;另外一種是更直觀的定義，即最大圓盤模型。如圖2所示，骨架點(diǎn)是所有最大圓盤的圓心集合，最大圓盤即是完全包含在物體內(nèi)部且至少與物體邊界相切于兩點(diǎn)的圓。骨架上的每一個(gè)點(diǎn)都是這些內(nèi)切圓的圓心，這些圓沿著骨架分布正好填充物體的內(nèi)部。由于模型的骨架很好地保留了模型的拓?fù)湫螒B(tài)及其連接特性，所以經(jīng)常被用于模型渲染、模型表面重建、碰撞檢測、模型檢索等應(yīng)用中，在工業(yè)零件的視覺識(shí)別領(lǐng)域也有廣泛的用途。

針對三維模型，骨架的提取方法主要有如下幾種：（1）基于拓?fù)浼?xì)化技術(shù)[3]。該類算法主要用于體表示的模型上，通過不斷地進(jìn)行體元素的削減來實(shí)現(xiàn)骨架的抽取，所以整個(gè)過程比較耗時(shí)，效率不高;（2）基于距離矩陣的方法[4]。它一般也是針對體表示的模型，通過計(jì)算每個(gè)體元素的距離來求取模型的脊點(diǎn);（3）基于二維圖像領(lǐng)域的Voronoi圖技術(shù)。有學(xué)者將二維領(lǐng)域的Voronoi圖技術(shù)引入到三維模型的骨架提取中來，Dey等人提出過一種利用Voronoi圖直接近似中軸的算法[2];（4）燒草模型法。正如上面的燒草模型所述，在模型的一端點(diǎn)火，模型兩側(cè)同時(shí)燃燒，火焰相聚處形成連貫的燒痕，這就是模型骨架的相似軌跡，但是這種方法理論性強(qiáng)，實(shí)際操作起來卻十分復(fù)雜;（5）基于Reeb圖的思想。如圖3所示，該算法首先在模型上定義一個(gè)連續(xù)函數(shù)，計(jì)算每個(gè)頂點(diǎn)的函數(shù)值，將相同函數(shù)值的頂點(diǎn)聚合成一個(gè)頂點(diǎn)，連接各個(gè)聚合后的頂點(diǎn)，形成骨架圖。其中最著名的是Hilaga等人提出的多分辨率Reeb圖 （Multiresolutional Reeb Graph，簡稱MRG） 算法[5]，它可以表示不同分辨率級別的3D形狀的骨架和拓?fù)浣Y(jié)構(gòu)。圖3表示了不同分辨率的Reeb圖，在模型上定義一個(gè)連續(xù)函數(shù)U，通過三種不同分辨率來計(jì)算Reeb圖，由圖可見，函數(shù)區(qū)間分割的層次越多，所得的Reeb圖越精確。

另外，國內(nèi)外的其他學(xué)者也對物體的骨架提取技術(shù)進(jìn)行了一些研究。意大利學(xué)者Jacopo Aleotti[6]通過攝像機(jī)觀測三維物體，將三維物體拓?fù)浞纸獬扇舾刹糠?，從而?shí)現(xiàn)骨架的提取;葡萄牙學(xué)者Diego R. Faria[7]提出了兩種模型拓?fù)浞蛛x方法：基于物體主軸的分離方法和基于高斯混合模型的分離方法，結(jié)果發(fā)現(xiàn)后者運(yùn)算效率低，花費(fèi)時(shí)間長，采用基于主軸的分離方法效果要好;國內(nèi)學(xué)者宮法明[8]提出了基于特征點(diǎn)求解的骨架提取算法，能夠快速的提取出模型骨架，但對于復(fù)雜的模型還存在過多的問題。

提出了針對三角網(wǎng)格模型的骨架提取算法，首先對復(fù)雜的三角網(wǎng)絡(luò)進(jìn)行簡化處理，然后遍歷所有的三角形，采用Dijkstra算法抽取基本點(diǎn)集，根據(jù)定義的Morse函數(shù)計(jì)算每個(gè)頂點(diǎn)的函數(shù)值，最后根據(jù)函數(shù)值得出模型的基本骨架。算法的程序流程圖如下所示：

1? ?讀入模型文件

STL文件是在計(jì)算機(jī)圖形應(yīng)用系統(tǒng)中用于表示三維網(wǎng)格模型的一種文件格式[9]。三維模型采用STL文件格式進(jìn)行表達(dá)。

以vs2010為平臺(tái)，運(yùn)用VTK開源軟件包面向?qū)ο笤碓O(shè)計(jì)和實(shí)現(xiàn)算法。VTK自身提供了一種進(jìn)行網(wǎng)格讀取的方法，它是將一個(gè)模型三角網(wǎng)格的所有頂點(diǎn)坐標(biāo)以及它們的索引號直接在程序中表達(dá)出來，然后通過循環(huán)遍歷讀取每一個(gè)網(wǎng)格及頂點(diǎn)。這種方法具有局限性，只適用于三角網(wǎng)格所有頂點(diǎn)坐標(biāo)以及每個(gè)點(diǎn)的索引號已知的情況下，模型三角網(wǎng)格的讀取。而大量的三維模型網(wǎng)格復(fù)雜，無法得到模型三角網(wǎng)格所有頂點(diǎn)以及索引號，這時(shí)就需要利用程序讀取模型的網(wǎng)格信息。

旨在設(shè)計(jì)出一種針對任意模型，可以讀取三角網(wǎng)格信息的算法，這樣可以處理的模型范圍廣泛，也能精簡程序的長度，以長方體為例進(jìn)行說明。

長方體有8個(gè)頂點(diǎn)，6個(gè)面，對應(yīng)的STL文件中有8個(gè)頂點(diǎn)和12個(gè)三角形網(wǎng)格。圖5是一個(gè)長方體的三角網(wǎng)格模型，每個(gè)面被分成了兩個(gè)三角網(wǎng)格。取其中一個(gè)三角網(wǎng)格進(jìn)行分析，它包含了3個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)對應(yīng)著一個(gè)索引號。所以，如果想要完全表達(dá)這個(gè)長方體，分為兩個(gè)步驟：1.從某一個(gè)頂點(diǎn)開始遍歷所有的頂點(diǎn)，給出頂點(diǎn)的三維坐標(biāo)，并將索引號與每個(gè)頂點(diǎn)相對應(yīng);2.從某一個(gè)三角網(wǎng)格開始遍歷所有的三角網(wǎng)格，并給出每一個(gè)網(wǎng)格頂點(diǎn)的索引號。

根據(jù)以上的分析，可以列出求解各個(gè)頂點(diǎn)三維坐標(biāo)的程序：

如圖6所示，其中i代表第i個(gè)頂點(diǎn)，N代表總頂點(diǎn)數(shù)，Pi[3]代表第i個(gè)頂點(diǎn)的三維坐標(biāo)，而vId代表該頂點(diǎn)對應(yīng)的索引號。三維STL文件導(dǎo)入后，由第一個(gè)頂點(diǎn)開始遍歷，遍歷每個(gè)頂點(diǎn)時(shí)，輸出頂點(diǎn)的三維坐標(biāo)，然后將每個(gè)頂點(diǎn)的索引號與坐標(biāo)相對應(yīng)，直到遍歷完所有的頂點(diǎn)。

同樣的思路，也可以列出求解網(wǎng)格數(shù)據(jù)的程序流程圖，如圖7所示。

在圖7中，j代表第j個(gè)網(wǎng)格，M代表總網(wǎng)格數(shù)目，k代表第j個(gè)網(wǎng)格的第k個(gè)頂點(diǎn)。GetCellPoints（）將每個(gè)三角網(wǎng)格的頂點(diǎn)提取出來，然后根據(jù)提取出來的頂點(diǎn)進(jìn)行二次遍歷。GetId（k）將第k個(gè)頂點(diǎn)的索引號提取出來。依次循環(huán)遍歷，直到遍歷完所有的網(wǎng)格。

用上述方法提取出長方體每個(gè)索引號對應(yīng)的頂點(diǎn)坐標(biāo)，如表1所示。（P—頂點(diǎn)索引號）

上述長方體共有12個(gè)三角網(wǎng)格，每個(gè)網(wǎng)格對應(yīng)三個(gè)頂點(diǎn)，每個(gè)三角網(wǎng)格對應(yīng)三個(gè)頂點(diǎn)的索引號如表2所示。（M—三角網(wǎng)格序號）

這樣，就將長方體模型的幾何特性完全表達(dá)了出來，為后續(xù)研究提供了前提。

2? ?三維模型網(wǎng)格的簡化

導(dǎo)入網(wǎng)格文件后，為了便于后續(xù)處理，需要先對三維模型進(jìn)行簡化，采用OpenGL中使用層次細(xì)節(jié)（level of details，縮寫LOD）方法來實(shí)現(xiàn)[10]。

LOD方法運(yùn)用最多的有兩種算法，分別是壓縮三角形算法和折疊三角形算法[11]。對于第一種算法，是將要簡化的三角形網(wǎng)格的三個(gè)頂點(diǎn)壓縮至一個(gè)點(diǎn)，實(shí)現(xiàn)網(wǎng)格的簡化。如圖8所示，△M1M2M3是要壓縮的三角形，將三角形的三條邊設(shè)為0，則△M1M2M3就變成了點(diǎn)M。

對于第二種算法，基本思路是將兩個(gè)三角形的共線端的兩頂點(diǎn)重合，使兩個(gè)三角形折疊，從而達(dá)到簡化三角形網(wǎng)格的效果。如圖9所示，要簡化△N1M1M2和 △N2M1M2，將頂點(diǎn)M1和M2重合至頂點(diǎn)M，則邊L1、L2、L3和L4也重合至邊L。

對比兩種算法，折疊三角形算法可以同時(shí)簡化兩個(gè)三角形，運(yùn)用此方法，迭代簡單，運(yùn)行速度快，采用這種算法進(jìn)行復(fù)雜模型的簡化。

本算法在OpenGL平臺(tái)上實(shí)現(xiàn)，基本數(shù)據(jù)結(jié)構(gòu)由Vertex，Triangle，Process三個(gè)結(jié)構(gòu)體組成，如下所示：

struct Vertex

{

GLfloat? k[]=new GLfloat[3]; //頂點(diǎn)的三維坐標(biāo)

GLint? vId;? ? ? ? ? ? ? ?//頂點(diǎn)的索引號

}

struct Triangle

{

Glint? tId;? ? ? ? //三角網(wǎng)格的索引號

Bool? t_flag;? ? ? //標(biāo)識(shí)該三角網(wǎng)格是否被刪除

GLTVector3? t_normal;? ? ? ? ?//三角網(wǎng)格法向量

}

struct Process

{

GLint? process[]=new GLint[4]; //順序存儲(chǔ)了一次簡化操作中除去的點(diǎn)、三角網(wǎng)格的索引號