STL文件错误的快速修复-精选资料

1、STL文件错误的快速修复FastrepairingerrorsinSTLfilesHEQiangZHANGShu-shengBAIXiao-liang(KeyLaboratoryofContemporaryDesign&IntegratedManufacturingTechnologyforMinistryofEducationNorthwesternPolytechnicalUniversityXi'an710072China):ThemainproblemofSTLfilesistheirvariouserrors.Inordertorepairthemthispaperf

2、irstlyclassifiedtheerrorsaccordingtotheircharacteristicsthenmodeledthefilesbyhalfedgedatastructure.EmployeddetectingedgesasthebasisforSTLfileserrorsdetection.Proposedabasicfillprocessstep-by-steporderedbyimportingSTLunstructuredmeshpopularmesherrorsdetectionerrorsfillingupdateerrorsinformation.Theal

3、gorithmperformsfastbyusingbalancedbinarytrees.Theexperimentalresultdemonstratestheeffectivenessofthisproposedalgorithm.Thismethodcanbeappliedtorapidformandreverseengineeringfieldasapre-processmodule.0引言快速原型制造技术是采用基于离散/堆积的方式快速制造零件原型的工艺方法,能直接从CAC®体数据模型生成三维产品模型.STL文件那么为CAD系统与快速原型系统之间数据交换格式的事实上的标准.

4、逆向工程是从实物样件获取产品数字化模型的技术,测量的实体模型可以STL数据文件方式导出以进行再设计,如先进的光学测量系统Atos就可以导出测量模型的STL数据文件.由于系统间容错、转换方法和逆向测量过程的不完美等原因STL文件中存在大量的错误,由STL重构的实体有很多错误.修复这些错误对后续处理具有重要意义.要检测和修复这些缺陷,拓扑关系重建是必需的.本文首先分析了STL文件中常见的几种错误,然后采用半边数据结构进行快速的拓扑重建,深入分析错误特点的根底上,系统高效地实现了STL文件错误的修复.1 STL文件常见错误分析根据STL文件错误的特点,可大致将错误分成以下几类：a)孔洞,如图1(a)

5、所示.主要是CA喳体外表三角化时缺少足量的数据造成的.b)顶点错位,如图1(b)所示.三角形的边没有被两个三角形共享,也没有出现裂缝.c)法向量错误,如图1(c)所示.三角片的旋向有错误,即违反了STL文件的取向规那么,产生的原因主要是生成STL文件时顶点记录顺序混乱.d)多余,如图1(d)所示.正常的网格拓扑结构的根底上多出了一些独立的面片2 STL实体的快速拓扑重建拓扑关系不仅要修复STL文件中的错误必须借助拓扑关系用于修复缺陷,也用于后续处理.例如逆向工程中的区域分割、曲面拟合等.本文采用半边数据结构表示实体的拓扑关系.在数据结构中有五类节点：网格(CPolyMesh)、三角形(tria

6、ngle)、边(edge)、半边(halfedge)、顶点(vertex).所有的节点都各自组成一个双向链表.实体拓扑关系建立之后,可以直接实现：a)由一个CPolyMesh可以遍历它包含的所有triangles;b)由一个triangle可以找到构成它的三条halfedge；c)由一个triangle可以找到前后的邻接三角形；d)由一个vertex关联其生成的半边,且一条edge由两条半边构成,属于一条边的两条半边之间可以相互查找.当实体模型存在缺陷时,会出现只有一条半边的边.拓扑重建主要包括两个步骤：无结构三角网格的建立和流形网格的生成.2.1 无结构三角网格的建立导入STL数据文件,由每

7、个顶点生成一条半边,同一三角形的三个顶点生成的三条半边构成一个triangle,将triangle参加到CPolyMesh链表中.同时建立关联顶点和其生成的半边集合的二叉平衡树.二叉平衡树能自动将原本为一个顶点,但在STL文件中却屡次出现的顶点合并成一个顶点,这样才能正确地建立实体的拓扑关系.导入文件结束后,生成的三角形相互间没有邻接关系,故称之为无结构网格.2.2 流行网格的生成通过上述步骤,每个顶点都生成了一条或多条半边,每个顶点属于一个或多个三角形,但三角形之间没有邻接关系.本文通过半边匹配的方式完成三角形邻接关系的建立.半边匹配是查找与当前半边的两个端点都相同的另一条半边,找到后将这两

8、条半边生成一条边.由2.1节建立的二叉平衡树可得到每个顶点的半边集合,因此查找对应半边时只需从半边集合中寻找,大大缩小了查找范围.图2为半边匹配简图.其中：F1为已输入的三角形；Fn为当前读入的三角形.显然H6将与H1匹配,从顶点V1的半边表中可以直接找到H1.3错误修复考虑到不同错误的特点及修复方法,根本的修复步骤为：a遍历网格CPolyMesh中所有triangles,找出每个triangle的三条半边中匹配的半边为空的半边,由这样的半边集合建立一个新的链表VSo如果VS为空,根本可以认为这个实体模型没有缺陷,程序结束.b由VS中的半边建立半边与顶点关联的集合vs_in半边是指向顶点的、v

9、s_out半边是背向顶点的.在vs_in中取出一个顶点和其关联的半边集合,利用该顶点获得vs_out中该顶点的半边集合.在这两个半边集合中,寻找每对方向相反的半边.假设存在这样的半边对,那么该错误属于顶点错位的情况,将半边对存入集合vs_repair中,转c；假设找不到这样的半边对,转ec)对vs_repair中的每对错误半边,计算半边边长,在长半边所在的三角形中新生成一个与短半边匹配的三角形.同时删除集合VSvs_in和vs_out中已经消除错误的半边和顶点,参加新增加错误半边和顶点,称之为错误更新.如图3所示,虚线表示新生成三角形的边.修复完成后,清空vs_repair.d)重复执行b),

10、直至集合vs_repair中半边对数量为零,转e).e)从VS中取出一条半边,进行孔洞检测算法.假设存在孔洞,转步骤f),并删除属于VS中的所有孔洞半边；否那么转g)o孔洞检测算法如下：(a)首先从VS中取出一条半边e,检测出CPolyMesh总与之相邻的一条没有匹配的半边,并将其标记.(b)根据半边匹配关系,检测出与前一步骤找出的不匹配半边相邻的另一条孔洞的半边,将其标记.(c)重复步骤(b)直到检测的半边为e时停止.单个孔洞就是由这些首尾相连的半边集合构成的.(d)重复(a)(c)就可以检测出所有的孔洞,注意重复步骤(a)时,CPolyMesh中的半边必须是没有标记的,这样才能保证孔洞的不

11、重复检测.f)对每个检测到的孔洞,获取孔洞的每个顶点,计算顶点的法矢量,再采用MarchingCubes算法对每个孔洞进行三？腔？.孔洞顶点法矢量的计算如下：三角网格模型上孔洞任意顶点vi的法矢量可以根据过该点的三角形法矢量的加权平均来计算,一般取三角形的面积为权值.过vi点有n个三角形,分别记为Tj,三角形的法矢记为Nj,面积记为Aj,那么三角网格中点vi的法矢量为ni=Enj=1AjNj/Enj=1Ajg假设VS中半边数量不再减少且不为空,这是由于有少量的非典型错误,程序很难判断,可由用户进行人工交互修复.采用本文算法开发的软件系统提供了一些辅助功能,如鼠标拾取边、三角形、顶点、删除边、三角形、向实体中添加边、三角形等.h整个修复过程结束,由修复后的实体模型生成正确的STL文件.4修复实验为了