一种有效的STL文件修补算法

1、一种有效的文件修补算法唐杰周来水周儒荣（南京航空航天大学工程研究中心南京）摘要大多数快速原蛋制造系统采用文件作为与系统之问的数据交换接口。但是。文件是通过用一系列的三角片逼近实际曲面而产生的，文件本身及其创建过程均存在许多问题，如裂缝、孔洞、覆盖等。这些缺陷会给后续处理带来许多不便。针对这十问题。本文提出了一种文件的修补算法。该算法首先建立三角片之同的拓扑关系，然后检查三角片模盈是否存在上述缺陷如果存在则对其进行修补。该算法已在。超人”系统中宴现，算法稳定可靠。且对上述缺陷。基本能正确有效地进行检测与修补。关键调快速原型制造文件（，）盯。，蛇”引言快速原型技术作为一项关键技术在九十年代得到了飞

2、速的发展。而（）文件则成为系统与快速原型系统之间数据交换格式的不成文的标准。目前，国内外几乎所有的快速型系统都以。文件为其数据输入格式，同时，大多数国际上典型的软件系统（如，等）都带有生成文件格式的模块，只需调用该模块，就能将系统构造的三维模型转换成格式文件。然而由于软件和。文件格式本身的缺陷。以及转换过程造成的问题，所产生的，本文研究得到航空基金的资助。一格式文件难免会有一些缺陷。据文献介绍有将近的文件存在这样或那样的缺陷，其中，最常见的有（如图所示）：孔垌鼎炙高唑艋忙瑚梳图文件的缺陷丢失三角片造成孔洞。二个以上三角片共用一条边（不符合文件规定）。三角形顶点计算时的舍入误差造成覆盖或裂缝。如

3、果不对这些缺陷进行修补必然会给后续处理带来不便。针对上述问题，本文提出一种有效的文件修补算法。该算法首先建立三角片之间的拓朴关系，然后检查三角片模型是否存在上述缺陷，如果存在，则对其进行修补。下面介绍修补的具体算法。数据结构虽然，文件作为快速成型系统的输入格式已经得到广泛的认可，但由于。文件仅包含三角片顶点和其法向量的座标，而缺少三角片之间的拓朴信息，因而给后续处理带来麻烦。【】【纠等人在进行。文件修补时略去了三角片的拓朴关系，采用遍历算法来处理。这种方法虽然简单，明了但却耗费了大量的机时，效率低。为了更有效地处理文件，本文采用了一种空间剖分树的数据结构（如图所示）。首先求得模型的外接包围盒，

4、然后根据每个三角片的包围盒将其加入相应的单元中。在空间剖分过程中，依据下列条件判断是否进行空间剖分：单元（）空问潮分（）单元树结构图空间剖分示意图每个空间单元中所包含的三角片数是否大于指定值。一单元树的深度是否超过指定深度。对于属于两个以上单元的三角片，如三角形，可在两个单元结点下都记录。为避免查找时返回多次，必须设置标志位。单元树（如图所示）中的非叶结点存储有以该结点为根结点的子树的包围盒的数据叶结点不仅存有该单元包围盒的数据，还存有指向属于该单元的三角片链表的头指针。该数据结构建好后，我们就可以根据某个三角片所在的空间位置查找与其位置相接近的三角片链表。算法实现建立拓朴关系。文件本身并不包

5、含三角片之间的拓朴信息，这给后续处理带来极大的麻烦。建立拓朴关系即将文件中的三角片加入到前述的数据结构中，按如下步骤进行：）从文件中读入一个三角片信息。）检查该三角片是否畸异（如三个顶点共线或重合），如是，则舍弃该三角片。）求三角片外接包围盒。）根据三角片的外接包围盒将该三角片加入数据结构。）重复步骤（）步骤（），直到文件中所有的三角片均已处理完。孔洞的检测和修补对于一个正确的模型来说，它的任何一条边属于且仅属于两个三角片。对于。文件来说，它的任何一个三角片的每一条边必有另一个三角片的一条边与之重合，方向相反且仅有一条这样的边存在。这就是本文检查文件是否有缺陷的准则。如果某些三角片中的一条或几

6、条边没有对应边。则该模型必然存在孔洞（如图所示）；如果某些三角片中的某条边有一条以上的边与其对应，则是如图所示的缺陷。如果某些三角片中的一条或几条边没有对应边则该模型必然存在孔洞（如图所示）。检测孔洞的步骤如下：）读入三角片的一条边。）根据该三角的外接包围盒取得与其相邻的三角片链表头指针。）在所得链表中寻找与该边相对应的边。）如果找到对应的边，则给这两条边均置找到标致位。如未找到，则将该边存入一临时链表）重复步骤（）步骤（），直到文件中所有的三角片均已处理完。经过上述步骤我们得到所有没有对应边的边。从模型生成文件时，某些三角片的丢失就形成孔蔼。孔洞的存在给后续处理带来不便甚至灾难性的后果。经过

7、孔洞的检测步骤。我丁查出所有的没寿对应边的边。将这些边排序首尾相连，就构成了孔洞的边界。它是一条或几条封闭的连续折线段。虽然我们已经得到了孔洞的边界，但是填补这个孔洞并不是一件容易的事。其中一个问题是：我们并不知道设计者最初的设计意图。要较好的符合设计意阖，就必须进行人机交互。这就降低了算法的独立性。因而大多数研究人员还是赞同由计算机自行修补，哪怕丢失一些原有的意图。对于如图所示的孔洞，其边界为有个顶点的连续折线段，。其中，。定义。一为顶点到顶点一的距离；为顶点到顶点的距离。本文采取的孔漏修补算法如下：、对于从到一，计算一、；、取。一、中最小者，不妨设为，则构造三角片；、计算边、所在三角片法矢

8、的平均值；、计算的三角片的法矢；、如果与之间的偏差超过给定精度（图所示情况），取。中次小者，返回；、如果与之间的偏差小于给定精度，将三角片加入三角片数据结构。图孔满修补、从孔嗣边界中删除边仉、“增加、，一；返回；、直至所有边处理完毕。覆盖缺陷的修补覆盖缺陷（如图所示）产生的主要原因是：模型三角化时，在曲面相交处的三角片分别属于不同的曲面，当从参数域向三维空间映射三角片时的计算误差引起覆盖缺陷。如果不处理它也会使后续处理不能正确进行。本文在实麓孔洞检测时，对覆盖缺陷进行了处理。给定一个精度，当空间两个点之间的距离小于时，我们说这两个点蕈台。当莱条边的两个顶点与另一条边的两个顶点分别重合且方向相反

9、时，我们说是的对应边。同时用的顶点取代的顶点。这样就完成了对覆盖缺陷的多边共缦的修补多边菸攀口蜒彝如匣所示，这也是在文件中不允许出现曲情：况。对多边共线龋藕滞；过器如下。在孔洞检测时，的对虚边有三种情况：、两对应边完全重合，且方向相反，这是正常情况，如前述处理。、两对应边部分重和，且有一个顶点重合，方向相反（匿中与）。此时应将三角片删除。同时增加三角片和。、两对应边部分重和，且两个顶点都不重合，方向相反（图中与）。此时应删除三角片。同时增加三角片。和。应用实例图多边共线图为一应用实倒。图为用生成的烟灰缸文件。但在图中左上角的部位有一孔洞缺陷，图为缺陷的放大表录。图为经本文的算法修补后的模型。图为激光快速烧结的零件。结论本文分析了文件作为快速原型制造系统与系统之间的数据交换接口所存在的问题，如裂缝、孔洞、覆盖等。提出了一种文件的修补算法。该算法首先利用空间剖分树建立起一三角片之间的拓朴关系，然后检查三角片模型是否存在孔洞缺陷，如果存在。则对其进行修补。该算法已在“超人”系统中实现，算法表现稳定且对文件的孔洞、覆盖以及多边共线等缺陷，基本能正确有效地进行检测与修