三维模型特征提取算法一、特征提取需求由来虚拟装配在CAD 建模领域使用广泛，Solidworks 、Pro/E、UG 等都有自己的零件装配程序模块，但是它们相互之间并不能进行直接的数据格式转换。
比如：Solidworks 创建一个简单的零件直接用Pro/E 打开会丢失很多模型拓扑信息。
STL 文件格式是通用的固体三维模型表示文件，常用CAD 软件都能打开。
STL 文件是一种简单数据格式，其中只记录了模型的顶点和法向量（数据格式下一节具体介绍），大多数CAD 软件支持STL 文件格式的零件输出。
然而，无论何种CAD 软件打开STL 文件之后，都难以读取模型的特征信息，甚至连模型的一个表面都选不中。
在这种情况下，如果我们想把一大堆的STL 格式模型，加载到某款CAD 软件中进行装配，可能性几乎为零。
在这种情况下，出现了对提取模型拓扑信息的需求。
下面将详细介绍这种方法，并给出在OSG 场景中提取一个齿轮面的例子，供大家二、基本概念三角形是三维引擎的基本绘制图元。
任意一个三角形包括三个顶点和一个法向量（三个顶点和一个法向量确定了一个最小单位的表面），无论是什么样子的三维模型都可以分解成三角形的组合。
一个三维模型上的三角形并非独立存在，它们是有相互关系的，这些关系主要体现在两方面：（1）邻接关系（共边、共顶点）。
（2）归一化法向量之间的夹角关系（法向量相等、法向量共面等等）。
通过上述关系可以把三角形归类，从而组成不同的曲面。
下面以平面和柱面为例对三角形组成的曲面进行介绍。
定义一：模型中任意两个三角形存在公共边，则称两个三角形紧邻。
定义二：模型中任意两个三角形存在公共顶点，则称两个三角形邻接。
定义三：如果存在一组三角形它们具有邻接关系（紧邻、邻接）并且归一化法向量全等则这一组三角形在同一个平面上。
定义四：如果存在一组三角形它们具有邻接关系（紧邻、邻接）并且归一化法向量处于某个平面上则这组三角形处在同一个柱面上。
定义五：归一化法向量，满足公式：关于其他形状的定义大家可以自己总结（如球面、圆柱面、圆锥面等等），这里只给出平面和一般柱面（多面体、圆锥面、圆柱面都是柱面）的定义。
下面给出一个平面获取的例子：粉红色区域为三角形组成的平面15 边形，法向量平行（归一化法向量相等）。
在图形中可以看到，在模型的所有三角形中可以确定这样一组三角形，它们共同组成了粉红色区域，即在粉红色区域上取任意三角形作为起始，搜索模型中所有三角形能够确定一组与起始三角形归一化法向量相等且相邻。
三、特征提取算法介绍为了简洁起见，在此只讨论“曲面提取”算法，关于拉伸凸台等算法大家可以自己去推算，其实有了表面提取算法其他特征的提取也并不复杂。
下面详细介绍这个算法。
算法定义：在模型的所有三角形中搜索满足邻接条件的、法向量满足特定数学方程的三角形集合。
（本定义只能满足归一化法向量）1、类定义如下：（1）定义一个三角形或多边形的边Edge {Vertext* v1;//边的第一个顶点Vertext* v2;//边的第二个顶点Triangle *owned_triangle; // 所属的三角形}（2）定义一个三角形Triangle{Vertex *v1;//三角形的第一个顶点Vertex *v2;//三角形的第二个顶点Vertex *v3;//三角形的第三个顶点Edgee1;//三角形的第一条边Edgee2;//三角形的第二条边Edgee3;//三角形的第三条边Normal *normal;//三角形的法向量Surface *owned_surface; // 所属的曲面(3)定义一个表面Surface {Vector<Triangle*> tri_buf;//一个表面包含的三角形集合Vector<Edge*> edge_buf;//一个表面包含的边(包含三角形的边//不一定是表面的边)}(4)Vector<Triangle> all_triangle_buf; //存储模型包含的所有三角形。
2、表面搜索算法表面搜索算法大致可以分为两个步骤：第一步，在模型包含的所有三角形中搜索符合相同数学方程的三角形。
第二步，判断搜索到的三角形是否有邻接关系，如果有添加到要搜索的表面，如果没有则抛弃。
Surface* buildSurface(Triangle*pSeed，Vector<Triangle>*all_triangle){Surface *surface = new Surface(); surface->addTriangle(pSeed);std::vector<Triangle*> buf;/* 查找所有符合法线相等条件的三角形*/for (unsigned int i=0; i< all_triangle.size(); i++){Triangle* tri = all_triangle) ;//判断两个向量是否满足特定方程，这一步尤为重要//isCo nsiste nt()方法可以重载多个以便分别求解平面、//柱面、球面等数学定义。
if (isConsistent (pSeed->getNormal(),tri->getNormal())&& tri->getOwnedSurface() == NULL){ buf.push_back(tri);}}//在符合法线相等的三角形中查找和平面邻接的三角形//找到的三角片虽然都符合同一个数学方程算法，但是//它们未必处在同一个曲面上(如两个曲面平行)，所以//要进一步判定它们的邻接关系。
Triangle *tri = getAdjacencyTriangle(surface,&buf);for(;tri != NULL;){surface->addTriangle(tri); // 如果是邻接三角形则添加到曲面上surface->rebuild();//添加完三角形后需要重新构建平面//以便确定曲面的边tri = getAdjacencyTriangle(surface,&buf);// 本方法确定曲面的边和所有//符合特定数学方程三角形的//邻接关系。
}return surface;}四、STL 文件的表示格式本节将详细介绍STL 文件的格式。
以便于大家分析。
大家可以编制文件读取程序直接将STL 文件中Outer loop 关键字包含的顶点信息和Facet normal 关键字包含的法向量信息创建成第三节中介绍的Triangle 类。
然后，将Triangle 和法向量信息放到osg::Geometry 类中进而显示在osg::Viewer 中。
简洁起见，读取程序不再讨论。
1、介绍STL 是固体界面描述语言( Stereolithography Interface Language )的缩写，是一种快速成型标准。
任意表面的图元是三角形，三角形的法向量遵循逆时针轮廓方向2、关键字SolidFacetNormalOuterLoopVertexEndloopEndfacetEndsolid3、语法Solid [part name]Facet normal value value value Outer loopVertex value value value Vertex value value valueVertex value value valueEndloopEndfacetEndsolid [part name]4、正方体样例solidfacet normal 0.000000 1.000000 0.000000outer loopvertex 1.000000 1.000000 1.000000vertex 1.000000 1.000000 -1.000000vertex -1.000000 1.000000 -1.000000 endloopendfacetfacet normal 0.000000 1.000000 0.000000outer loopvertex -1.000000 1.000000 -1.000000 vertex -1.000000 1.000000 1.000000 endloop endfacetfacet normal 0.000000 0.000000 1.000000 outer loopvertex 1.000000 1.000000 1.000000 vertex -1.000000 1.000000 1.000000 vertex -1.000000 -1.000000 1.000000 endloopendfacetfacet normal 0.000000 0.000000 1.000000 outer loopvertex 1.000000 1.000000 1.000000vertex 1.000000 -1.000000 1.000000 endloopendfacet facet normal 1.000000 0.000000 0.000000outer loopvertex 1.000000 1.000000 1.000000vertex 1.000000 -1.000000 1.000000 vertex 1.000000 -1.000000 -1.000000 endloop endfacet facet normal 1.000000 0.000000 0.000000outer loopvertex 1.000000 1.000000 1.000000 vertex 1.000000 -1.000000 -1.000000 endloop endfacetfacet normal 0.000000 0.000000 -1.000000 outer loopvertex -1.000000 -1.000000 -1.000000 vertex 1.000000 1.000000 -1.000000vertex 1.000000 -1.000000 -1.000000 endloopendfacetfacet normal 0.000000 -1.000000 0.000000 outer loopvertex -1.000000 -1.000000 -1.000000 vertex 1.000000 -1.000000 -1.000000 vertex 1.000000 -1.000000 1.000000endfacet facet normal 0.000000 -1.000000 0.000000outer loopvertex -1.000000 -1.000000 -1.000000vertex 1.000000 -1.000000 1.000000 vertex -1.000000 -1.000000 1.000000 endloopendfacet facet normal -1.000000 0.000000 0.000000outer loopvertex -1.000000 -1.000000 -1.000000vertex -1.000000 -1.000000 1.000000 vertex -1.000000 1.000000 1.000000 endloop facet normal -1.000000 0.000000 0.000000 outer loopvertex -1.000000 -1.000000 -1.000000 vertex -1.000000 1.000000 1.000000 vertex -1.000000 1.000000 -1.000000 endloopendfacet facet normal 0.000000 0.000000 -1.000000 outer loopvertex -1.000000 -1.000000 -1.000000 vertex -1.000000 1.000000 -1.000000 vertex 1.000000 1.000000 -1.000000 endloopendfacet五、使用OSGConv对STL文件转换后的OSG文件格式在文件格式中我们只保留的顶点和法线向量定义部分，可以发现定点数正好是法线向量数的三倍( VertexArray Vec3Array 840 ，NormalArray Vec3Array 280 )，三个顶点(一个三角形)对应一个法线向量。