三維模型特征提取算法

1、-. z.三維模型特征提取算法一、特征提取需求由來虛擬裝配在CAD建模領(lǐng)域使用廣泛，Solidworks、Pro/E、UG等都有自己的零件裝配程序模塊，但是它們相互之間并不能進(jìn)展直接的數(shù)據(jù)格式轉(zhuǎn)換。比方：Solidworks創(chuàng)立一個簡單的零件直接用Pro/E翻開會喪失很多模型拓?fù)湫畔?。STL文件格式是通用的固體三維模型表示文件，常用CAD軟件都能翻開。STL文件是一種簡單數(shù)據(jù)格式，其中只記錄了模型的頂點(diǎn)和法向量數(shù)據(jù)格式下一節(jié)具體介紹，大多數(shù)CAD軟件支持STL文件格式的零件輸出。然而，無論何種CAD軟件翻開STL文件之后，都難以讀取模型的特征信息，甚至連模型的一個外表都選不中。在這種情況下，如

2、果我們想把一大堆的STL格式模型，加載到*款CAD軟件中進(jìn)展裝配，可能性幾乎為零。在這種情況下，出現(xiàn)了對提取模型拓?fù)湫畔⒌男枨?。下面將詳?xì)介紹這種方法，并給出在OSG場景中提取一個齒輪面的例子，供大家參考。二、根本概念三角形是三維引擎的根本繪制圖元。任意一個三角形包括三個頂點(diǎn)和一個法向量三個頂點(diǎn)和一個法向量確定了一個最小單位的外表，無論是什么樣子的三維模型都可以分解成三角形的組合。一個三維模型上的三角形并非獨(dú)立存在，它們是有相互關(guān)系的，這些關(guān)系主要表達(dá)在兩方面：1鄰接關(guān)系共邊、共頂點(diǎn)。2歸一化法向量之間的夾角關(guān)系法向量相等、法向量共面等等。通過上述關(guān)系可以把三角形歸類，從而組成不同的曲面。下面

3、以平面和柱面為例對三角形組成的曲面進(jìn)展介紹。定義一：模型中任意兩個三角形存在公共邊，則稱兩個三角形緊鄰。定義二：模型中任意兩個三角形存在公共頂點(diǎn)，則稱兩個三角形鄰接。定義三：如果存在一組三角形它們具有鄰接關(guān)系緊鄰、鄰接并且歸一化法向量全等則這一組三角形在同一個平面上。定義四：如果存在一組三角形它們具有鄰接關(guān)系緊鄰、鄰接并且歸一化法向量處于*個平面上則這組三角形處在同一個柱面上。定義五：歸一化法向量，滿足公式：關(guān)于其他形狀的定義大家可以自己總結(jié)如球面、圓柱面、圓錐面等等，這里只給出平面和一般柱面多面體、圓錐面、圓柱面都是柱面的定義。下面給出一個平面獲取的例子：粉紅色區(qū)域為三角形組成的平面15邊形

4、，法向量平行歸一化法向量相等。在圖形中可以看到，在模型的所有三角形中可以確定這樣一組三角形，它們共同組成了粉紅色區(qū)域，即在粉紅色區(qū)域上取任意三角形作為起始，搜索模型中所有三角形能夠確定一組與起始三角形歸一化法向量相等且相鄰。三、特征提取算法介紹為了簡潔起見，在此只討論曲面提取算法，關(guān)于拉伸凸臺等算法大家可以自己去推算，其實有了外表提取算法其他特征的提取也并不復(fù)雜。下面詳細(xì)介紹這個算法。算法定義：在模型的所有三角形中搜索滿足鄰接條件的、法向量滿足特定數(shù)學(xué)方程的三角形集合。本定義只能滿足歸一化法向量1、類定義如下：1定義一個三角形或多邊形的邊EdgeVerte*t* v1;/邊的第一個頂點(diǎn)Vert

5、e*t* v2;/邊的第二個頂點(diǎn)Triangle *owned_triangle; /所屬的三角形2定義一個三角形TriangleVerte* *v1;/三角形的第一個頂點(diǎn)Verte* *v2;/三角形的第二個頂點(diǎn)Verte* *v3;/三角形的第三個頂點(diǎn)Edgee1;/三角形的第一條邊Edgee2;/三角形的第二條邊Edgee3;/三角形的第三條邊Normal *normal;/三角形的法向量Surface *owned_surface; /所屬的曲面3定義一個外表SurfaceVectortri_buf;/一個外表包含的三角形集合Vectoredge_buf;/一個外表包含的邊包含三角形的

6、邊/不一定是外表的邊4Vector all_triangle_buf;/存儲模型包含的所有三角形。2、外表搜索算法外表搜索算法大致可以分為兩個步驟：第一步，在模型包含的所有三角形中搜索符合一樣數(shù)學(xué)方程的三角形。第二步，判斷搜索到的三角形是否有鄰接關(guān)系，如果有添加到要搜索的外表，如果沒有則拋棄。Surface* buildSurface(Triangle*pSeed，Vector* all_triangle)Surface *surface = new Surface();surface-addTriangle(pSeed);std:vector buf;/*查找所有符合法線相等條件的三角形*/

7、for (unsigned int i=0; igetNormal(),tri-getNormal()& tri-getOwnedSurface() = NULL)buf.push_back(tri); /在符合法線相等的三角形中查找和平面鄰接的三角形/找到的三角片雖然都符合同一個數(shù)學(xué)方程算法，但是/它們未必處在同一個曲面上如兩個曲面平行，所以/要進(jìn)一步判定它們的鄰接關(guān)系。Triangle *tri = getAdjacencyTriangle(surface,&buf);for(;tri != NULL;)surface-addTriangle(tri); /如果是鄰接三角形則添加到曲面上s

8、urface-rebuild();/添加完三角形后需要重新構(gòu)建平面/以便確定曲面的邊tri = getAdjacencyTriangle(surface,&buf);/本方法確定曲面的邊和所有/符合特定數(shù)學(xué)方程三角形的/鄰接關(guān)系。return surface;四、STL文件的表示格式本節(jié)將詳細(xì)介紹STL文件的格式。以便于大家分析。大家可以編制文件讀取程序直接將STL文件中Outer loop關(guān)鍵字包含的頂點(diǎn)信息和Facet normal關(guān)鍵字包含的法向量信息創(chuàng)立成第三節(jié)中介紹的Triangle類。然后，將Triangle和法向量信息放到osg:Geometry類中進(jìn)而顯示在osg:Viewer

9、中。簡潔起見，讀取程序不再討論。1、介紹STL是固體界面描述語言Stereolithography Interface Language的縮寫，是一種快速成型標(biāo)準(zhǔn)。任意外表的圖元是三角形，三角形的法向量遵循逆時針輪廓方向。2、關(guān)鍵字SolidFacetNormalOuterLoopVerte*EndloopEndfacetEndsolid3、語法Solid part nameFacet normal value value valueOuter loop Verte* value value valueVerte* value value valueVerte* value value val

10、ueEndloopEndfacet.Endsolid part name4、正方體樣例solidfacet normal 0.000000 1.000000 0.000000outer loopverte* 1.000000 1.000000 1.000000verte* 1.000000 1.000000 -1.000000verte* -1.000000 1.000000 -1.000000endloopendfacetfacet normal 0.000000 1.000000 0.000000outer loopverte* 1.000000 1.000000 1.000000vert

11、e* -1.000000 1.000000 -1.000000verte* -1.000000 1.000000 1.000000endloopendfacetfacet normal 0.000000 0.000000 1.000000outer loopverte* 1.000000 1.000000 1.000000verte* -1.000000 1.000000 1.000000verte* -1.000000 -1.000000 1.000000endloopendfacetfacet normal 0.000000 0.000000 1.000000outer loopverte

12、* 1.000000 1.000000 1.000000verte* -1.000000 -1.000000 1.000000verte* 1.000000 -1.000000 1.000000endloopendfacetfacet normal 1.000000 0.000000 0.000000outer loopverte* 1.000000 1.000000 1.000000verte* 1.000000 -1.000000 1.000000verte* 1.000000 -1.000000 -1.000000endloopendfacetfacet normal 1.000000

13、0.000000 0.000000outer loopverte* 1.000000 1.000000 1.000000verte* 1.000000 -1.000000 -1.000000verte* 1.000000 1.000000 -1.000000endloopendfacetfacet normal 0.000000 0.000000 -1.000000outer loopverte* -1.000000 -1.000000 -1.000000verte* 1.000000 1.000000 -1.000000verte* 1.000000 -1.000000 -1.000000e

14、ndloopendfacetfacet normal 0.000000 -1.000000 0.000000outer loopverte* -1.000000 -1.000000 -1.000000verte* 1.000000 -1.000000 -1.000000verte* 1.000000 -1.000000 1.000000endloopendfacetfacet normal 0.000000 -1.000000 0.000000outer loopverte* -1.000000 -1.000000 -1.000000verte* 1.000000 -1.000000 1.00

15、0000verte* -1.000000 -1.000000 1.000000endloopendfacetfacet normal -1.000000 0.000000 0.000000outer loopverte* -1.000000 -1.000000 -1.000000verte* -1.000000 -1.000000 1.000000verte* -1.000000 1.000000 1.000000endloopendfacetfacet normal -1.000000 0.000000 0.000000outer loopverte* -1.000000 -1.000000

16、 -1.000000verte* -1.000000 1.000000 1.000000verte* -1.000000 1.000000 -1.000000endloopendfacetfacet normal 0.000000 0.000000 -1.000000outer loopverte* -1.000000 -1.000000 -1.000000verte* -1.000000 1.000000 -1.000000verte* 1.000000 1.000000 -1.000000endloopendfacetendsolid五、使用OSGConv對STL文件轉(zhuǎn)換后的OSG文件格式在文件格式中我們只保存的頂點(diǎn)和法線向量定義局部，可以發(fā)現(xiàn)定點(diǎn)數(shù)正好是法線向量數(shù)的三倍Verte*Array Vec3Array 840，NormalArray Vec3Array 280，三個頂點(diǎn)一個三角形對應(yīng)一個法線向量。大家可以編制和STL文件類似的程序來讀取OSG文件以便生成全部三角形。值得注意的是不是所有OSG文件都是這樣的存儲方法，大家應(yīng)該因地制宜編制自己需要的程序。STL文件通過osgConv轉(zhuǎn)換后的結(jié)果至少是這樣。osgE*p輸出的結(jié)果需要大家自己分析了。Geode Geometr