三维模型特征提取算法 一、特征提取需求由来 虚拟装配在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; //三角形的第三个顶点
Edge e1; //三角形的第一条边
Edge e2; //三角形的第二条边
Edge e3; //三角形的第三条边
Normal *normal; //三角形的法向量
Surface *owned_surface; //所属的曲面 ｝ （3）定义一个表面 Surface｛
Vector tri_buf; //一个表面包含的三角形集合
Vector edge_buf; //一个表面包含的边（包含三角形的边 //不一定是表面的边） ｝ （4）Vector all_triangle_buf; //存储模型包含的所有三角形。
2、表面搜索算法 表面搜索算法大致可以分为两个步骤：第一步，在模型包含的所有三角形中搜索符合相 同数学方程的三角形。第二步，判断搜索到的三角形是否有邻接关系，如果有添加到要搜索 的表面，如果没有则抛弃。 Surface* buildSurface(Triangle* pSeed，Vector* all_triangle){ Surface *surface = new Surface(); surface->addTriangle(pSeed); std::vector buf;
/*查找所有符合法线相等条件的三角形*/ for (unsigned int i=0; i< all_triangle.size(); i++) { Triangle* tri = all_triangle);
//判断两个向量是否满足特定方程，这一步尤为重要 //isConsistent()方法可以重载多个以便分别求解平面、 //柱面、球面等数学定义。
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、关键字 Solid
Facet Normal
Outer
Loop
Vertex
Endloop Endfacet
Endsolid
3、语法 Solid [part name]
Facet normal value value value Outer loop Vertex value value value Vertex value value value
Vertex value value value Endloop Endfacet ….. Endsolid [part name] 4、正方体样例 solid
facet normal 0.000000 1.000000 0.000000 outer loop vertex 1.000000 1.000000 1.000000 vertex 1.000000 1.000000 -1.000000 vertex -1.000000 1.000000 -1.000000 endloop endfacet facet normal 0.000000 1.000000 0.000000 outer loop vertex 1.000000 1.000000 1.000000 vertex -1.000000 1.000000 -1.000000 vertex -1.000000 1.000000 1.000000 endloop endfacet facet normal 0.000000 0.000000 1.000000 outer loop vertex 1.000000 1.000000 1.000000 vertex -1.000000 1.000000 1.000000 vertex -1.000000 -1.000000 1.000000 endloop endfacet facet normal 0.000000 0.000000 1.000000 outer loop vertex 1.000000 1.000000 1.000000 vertex -1.000000 -1.000000 1.000000