三维模型特征提取算法.docx

三维模型特征提取算法.docx

《三维模型特征提取算法.docx》由会员分享，可在线阅读，更多相关《三维模型特征提取算法.docx（15页珍藏版）》请在冰点文库上搜索。

三维模型特征提取算法

三维模型特征提取算法

一、特征提取需求由来

    虚拟装配在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）Vectorall_triangle_buf;

//存储模型包含的所有三角形。

2、表面搜索算法

  表面搜索算法大致可以分为两个步骤：

第一步，在模型包含的所有三角形中搜索符合相

同数学方程的三角形。

第二步，判断搜索到的三角形是否有邻接关系，如果有添加到要搜索

的表面，如果没有则抛弃。

Surface*buildSurface（Triangle*

pSeed，Vector*

all_triangle）{

Surface*surface=newSurface（）;

surface->addTriangle（pSeed）;

std:

:

vectorbuf;

/*查找所有符合法线相等条件的三角形*/

for（unsignedinti=0;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）;//本方法确定曲面的边和所有

//符合特定数学方程三角形的

//邻接关系。

}

returnsurface;

}

四、STL文件的表示格式

    本节将详细介绍STL文件的格式。

以便于大家分析。

大家可以编制文件读取程序直接将STL文件中Outerloop关键字包含的顶点信息和Facetnormal关键字包含的法向量信息创建成第三节中介绍的Triangle类。

然后，将Triangle和法向量信息放到osg:

:

Geometry类中进而显示在osg:

:

Viewer中。

简洁起见，读取程序不再讨论。

1、介绍

STL是固体界面描述语言（StereolithographyInterfaceLanguage）的缩写，是一种快速成型标准。

任意表面的图元是三角形，三角形的法向量遵循逆时针轮廓方向。

2、关键字

Solid

Facet

Normal

Outer

Loop

Vertex

Endloop

Endfacet

Endsolid

3、语法

Solid[partname]

Facetnormalvaluevaluevalue

Outerloop

        Vertexvaluevaluevalue

Vertexvaluevaluevalue

Vertexvaluevaluevalue

Endloop

Endfacet

…..

Endsolid[partname]

4、正方体样例

solid

facetnormal0.0000001.0000000.000000

outerloop

vertex1.0000001.0000001.000000

vertex1.0000001.000000-1.000000

vertex-1.0000001.000000-1.000000

endloop

endfacet

facetnormal0.0000001.0000000.000000

outerloop

vertex1.0000001.0000001.000000

vertex-1.0000001.000000-1.000000

vertex-1.0000001.0000001.000000

endloop

endfacet

facetnormal0.0000000.0000001.000000

outerloop

vertex1.0000001.0000001.000000

vertex-1.0000001.0000001.000000

vertex-1.000000-1.0000001.000000

endloop

endfacet

facetnormal0.0000000.0000001.000000

outerloop

vertex1.0000001.0000001.000000

vertex-1.000000-1.0000001.000000

vertex1.000000-1.0000001.000000

endloop

endfacet

facetnormal1.0000000.0000000.000000

outerloop

vertex1.0000001.0000001.000000

vertex1.000000-1.0000001.000000

vertex1.000000-1.000000-1.000000

endloop

endfacet

facetnormal1.0000000.0000000.000000

outerloop

vertex1.0000001.0000001.000000

vertex1.000000-1.000000-1.000000

vertex1.0000001.000000-1.000000

endloop

endfacet

facetnormal0.0000000.000000-1.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex1.0000001.000000-1.000000

vertex1.000000-1.000000-1.000000

endloop

endfacet

facetnormal0.000000-1.0000000.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex1.000000-1.000000-1.000000

vertex1.000000-1.0000001.000000

endloop

endfacet

facetnormal0.000000-1.0000000.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex1.000000-1.0000001.000000

vertex-1.000000-1.0000001.000000

endloop

endfacet

facetnormal-1.0000000.0000000.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex-1.000000-1.0000001.000000

vertex-1.0000001.0000001.000000

endloop

endfacet

facetnormal-1.0000000.0000000.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex-1.0000001.0000001.000000

vertex-1.0000001.000000-1.000000

endloop

endfacet

facetnormal0.0000000.000000-1.000000

outerloop

vertex-1.000000-1.000000-1.000000

vertex-1.0000001.000000-1.000000

vertex1.0000001.000000-1.000000

endloop

endfacet

endsolid

五、使用OSGConv对STL文件转换后的OSG文件格式

    在文件格式中我们只保留的顶点和法线向量定义部分，可以发现定点数正好是法线向量数的三倍（VertexArrayVec3Array840，NormalArrayVec3Array280），三个顶点（一个三角形）对应一个法线向量。

大家可以编制和STL文件类似的程序来读取OSG文件以便生成全部三角形。

值得注意的是不是所有OSG文件都是这样的存储方法，大家应该因地制宜编制自己需要的程序。

STL文件通过osgConv转换后的结果至少是这样。

osgExp输出的结果需要大家自己分析了。

Geode{

Geometry{

VertexArrayVec3Array840

{

//第一个三角形的顶点

25.590976.977556

6.7361282.489556

21.966170.446856

//第二个三角形的顶点

21.966170.446856

6.7361282.489556

3.0282374.036456

….

}

NormalBindingPER_PRIMITIVE

NormalArrayVec3Array280

{

001

//第一个三角形的normal

001

//第二个三角形的normal

}

}

}

六、在OSG中抽取“齿轮”表面的样例程序