三维模型特征提取算法

1、三维模型特征提取算法一、特征提取需求由来虚拟装配在 CAD 建模领域使用广泛， Solidworks 、Pro/E、 UG 等都有自己的零件装配 程序模块，但是它们相互之间并不能进行直接的数据格式转换。比如： Solidworks 创建一个 简单的零件直接用 Pro/E 打开会丢失很多模型拓扑信息。 STL 文件格式是通用的固体三维模 型表示文件，常用 CAD 软件都能打开。 STL 文件是一种简单数据格式，其中只记录了模型 的顶点和法向量 （数据格式下一节具体介绍） ，大多数 CAD 软件支持 STL 文件格式的零件 输出。然而，无论何种 CAD 软件打开 STL 文件之后，都难以读取模型的

2、特征信息，甚至连 模型的一个表面都选不中。在这种情况下，如果我们想把一大堆的 STL 格式模型，加载到 某款 CAD 软件中进行装配，可能性几乎为零。在这种情况下，出现了对提取模型拓扑信息 的需求。下面将详细介绍这种方法，并给出在 OSG 场景中提取一个齿轮面的例子，供大家二、基本概念 三角形是三维引擎的基本绘制图元。任意一个三角形包括三个顶点和一个法向量（三 个顶点和一个法向量确定了一个最小单位的表面） ，无论是什么样子的三维模型都可以分解 成三角形的组合。 一个三维模型上的三角形并非独立存在， 它们是有相互关系的， 这些关系 主要体现在两方面： （ 1）邻接关系（共边、共顶点）。（ 2）归

3、一化法向量之间的夹角关系 （法向量相等、 法向量共面等等） 。通过上述关系可以把三角形归类， 从而组成不同的曲面。 下面以平面和柱面为例对三角形组成的曲面进行介绍。 定义一：模型中任意两个三角形存在公共边，则称两个三角形紧邻。 定义二：模型中任意两个三角形存在公共顶点，则称两个三角形邻接。定义三：如果存在一组三角形它们具有邻接关系（紧邻、邻接）并且归一化法向量全等则 这一组三角形在同一个平面上。定义四： 如果存在一组三角形它们具有邻接关系 （紧邻、邻接） 并且归一化法向量处于某个 平面上则这组三角形处在同一个柱面上。定义五：归一化法向量，满足公式： 关于其他形状的定义大家可以自己总结（如球面、

4、圆柱面、圆锥面等等），这里只给出 平面和一般柱面（多面体、圆锥面、圆柱面都是柱面）的定义。下面给出一个平面获取的例 子：粉红色区域为三角形组成的平面 15 边形，法向量平行（归一化法向量相等）。 在图形中可以看到， 在模型的所有三角形中可以确定这样一组三角形， 它们共同 组成了粉红色区域， 即在粉红色区域上取任意三角形作为起始， 搜索模型中所有 三角形能够确定一组与起始三角形归一化法向量相等且相邻。三、特征提取算法介绍 为了简洁起见，在此只讨论“曲面提取”算法，关于拉伸凸台等算法大家可以自己去 推算，其实有了表面提取算法其他特征的提取也并不复杂。下面详细介绍这个算法。算法定义： 在模型的所有三

5、角形中搜索满足邻接条件的、 法向量满足特定数学方程的三角形 集合。（本定义只能满足归一化法向量）1、类定义如下：（1）定义一个三角形或多边形的边Edge Vertext* v1;/边的第一个顶点Vertext* v2;/边的第二个顶点Triangle *owned_triangle; / 所属的三角形（2）定义一个三角形TriangleVertex *v1;/三角形的第一个顶点Vertex *v2;/三角形的第二个顶点Vertex *v3;/三角形的第三个顶点Edgee1;/三角形的第一条边Edgee2;/三角形的第二条边Edgee3;/三角形的第三条边Normal *normal;/三角形的

6、法向量Surface *owned_surface; / 所属的曲面(3) 定义一个表面Surface Vector tri_buf;/一个表面包含的三角形集合Vector edge_buf;/一个表面包含的边(包含三角形的边 /不一定是表面的边)(4) Vector all_triangle_buf; /存储模型包含的所有三角形。2、表面搜索算法 表面搜索算法大致可以分为两个步骤：第一步，在模型包含的所有三角形中搜索符合相 同数学方程的三角形。 第二步， 判断搜索到的三角形是否有邻接关系， 如果有添加到要搜索 的表面，如果没有则抛弃。Surface* buildSurface(Triangl

7、e*pSeed， Vector*all_triangle)Surface *surface = new Surface(); surface-addTriangle(pSeed);std:vector buf;/* 查找所有符合法线相等条件的三角形 */for (unsigned int i=0; igetNormal(),tri-getNormal()& tri-getOwnedSurface() = NULL) buf.push_back(tri);/在符合法线相等的三角形中查找和平面邻接的三角形/找到的三角片虽然都符合同一个数学方程算法，但是 /它们未必处在同一个曲面上(如两个曲面平行)

8、，所以 /要进一步判定它们的邻接关系。Triangle *tri = getAdjacencyTriangle(surface,&buf);for(;tri != NULL;)surface-addTriangle(tri); / 如果是邻接三角形则添加到曲面上surface-rebuild();/添加完三角形后需要重新构建平面/以便确定曲面的边 tri = getAdjacencyTriangle(surface,&buf);/ 本方法确定曲面的边和所有 /符合特定数学方程三角形的/邻接关系。return surface;四、STL 文件的表示格式本节将详细介绍 STL 文件的格式。以便于大

9、家分析。大家可以编制文件读取程序直接 将 STL 文件中 Outer loop 关键字包含的顶点信息和 Facet normal 关键字包含的法向量信息创 建成第三节中介绍的 Triangle 类。然后，将 Triangle 和法向量信息放到 osg:Geometry 类中 进而显示在 osg:Viewer 中。简洁起见，读取程序不再讨论。1、介绍STL 是固体界面描述语言( Stereolithography Interface Language )的缩写，是一种快速成型标准。任意表面的图元是三角形，三角形的法向量遵循逆时针轮廓方向2、关键字SolidFacetNormalOuterLoop

10、VertexEndloopEndfacetEndsolid3、语法Solid part nameFacet normal value value valueOuter loopVertex value value valueVertex value value valueVertex value value valueEndloopEndfacetEndsolid part name4、正方体样例solidfacet normal 0.000000 1.000000 0.000000outer loopvertex 1.000000 1.000000 1.000000vertex 1.0000

11、00 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 -

12、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.000000vertex 1.000000 -1.000000 1.000000 endloopendfacet facet normal 1.000000 0.000000 0.000000outer loopvert

13、ex 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.000000 vertex 1.000000 -1.000000 -1.000000endloop endfacetfacet normal 0.000000 0.000000 -1.000000 outer loo

14、pvertex -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.000000endloopendfacet fac

15、et 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.000000endloopendfacet facet normal -1.000000 0.000000 0.000000outer loopvertex -1.000000 -1.000000 -1.000000vertex -1.000000 -1.000000 1.000000 vertex -1

16、.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.000000vertex -1.000000 1.000000 -1.000000 endloopendfacet facet normal 0.000000 0.000000 -1.000000 outer loopvertex -1.000000 -1.000000 -1.000000 vert

17、ex -1.000000 1.000000 -1.000000vertex 1.000000 1.000000 -1.000000 endloopendfacetendsolid五、使用OSGConv对STL文件转换后的OSG文件格式在文件格式中我们只保留的顶点和法线向量定义部分，可以发现定点数正好是法线向 量数的三倍( VertexArray Vec3Array 840 ，NormalArray Vec3Array 280 )，三个顶点(一个三 角形)对应一个法线向量。大家可以编制和 STL 文件类似的程序来读取 OSG 文件以便生成 全部三角形。值得注意的是不是所有 OSG 文件都是这样的存储方法，大家应该因地制宜编 制自己需要的程序。 STL 文件通过 osgConv 转换后的结果至少是这样。 osgExp 输出的结果 需要大家自己分析了。Geode Geomet