快速成型切片数据的优化算法研究 - 文章

快速成型切片数据的优化算法研究

作者：中科院沈阳自动化所赵吉宾刘伟军王越超

欢迎访问e展厅
展厅 5	三维打印机展厅三维打印机, 快速成型机, 3D打印材料/光固化材料, 快速成型制造软件, ...

摘　要：为了能够顺利地进行STL模型切片轮廓数据的进一步处理，提出了对切片数据进行优化处理的算法。对由于STL模型的缺陷造成切片之后的轮廓信息数据有大量的冗余数据，提出了一种冗余数据的滤除算法；针对切片轮廓的不封闭，给出了有效的修正算法；同时给出了对切片轮廓的内外边界进行自动识别的算法。该算法高效简单，提高了后续的数据处理的效率和成型件的加工质量，改善了零件成型的加工性能。
关键词：快速成型制造；STL文件；数据优化

1　引　言快速成型技术(RapidPrototypingTechnology)是一种基于离散堆积成型思想的新型成形技术[1]，自80年代产生以来得到了迅速的发展。由于其具有生产的敏捷性、制造技术的高度集成化以及适合于制造几乎任何形状等的优点广泛应用于机械、电子、汽车、玩具、通讯、航空航天等领域。其基本制造原理为：将CAD模型在计算机内用切片软件沿Z方向切片离散，得到一系列具有一定厚度的薄片，然后激光束(或紫外光束)在计算机的控制下在二维的切片层面上固化或粘结某一区域，从而形成零件实体的一个层面，随后再同样固化下一个层面，如此反复，逐渐堆积便形成一个三维零件。快速成形技术根据制造工艺的不同可以分为：叠层实体制造(LOM)、选择形激光烧结(SLS)、光固化法(SL)、熔融沉积制造法(FDM)、三维立体印刷法(TDP)等。

STL文件是CAD实体数据模型经三角化网格化处理后的数据文件，是用许多空间三角形小平面逼近原CAD实体模型，因为STL文件格式简单而且不需要复杂的CAD系统支持，现在已经发展成为CAD系统与快速成型系统之间数据交换格式的不成文标准。尽管STL文件在快速成型领域有着极其广泛的应用，但是其缺点也是十分明显的，例如缺少三角面片之间的拓扑信息，而且还会有裂缝、间隙、面片重叠和法向量反转的错误[2]。由于STL文件所固有的缺陷，使得切片之后得到的轮廓信息有大量的冗余数据，甚至会产生轮廓线不封闭等错误。如果我们不对这些冗余数据和错误不加以处理，就很难进行以后光斑的半径补偿等以后数据处理，影响零件加工的稳定性和加工效率，甚至不能成型正确的零件形状。因此对截面轮廓数据进行优化处理就显得十分的必要。

2　切片轮廓数据的特性

STL文件用许多空间小三角形来表示零件的表面，对每一个空间小三角形面片用三角形的三个顶点的坐标及三角形面片的法向量来描述，法向量由零件的内部指向外部，三角形三个顶点的次序与法向量满足右手规则。

STL文件中每相邻的两个三角形只能有一条公共边。STL文件有两种格式，一种是ASCII格式，另一种是二进制格式。ASCII格式的STL文件具有可读性，但占用较大的空间，大约是二进制STL文件的五倍。

ASCII格式的STL文件结构如下：

solid ASCII　　　　　　　　　　　//ASCII为文件名
facet normal nx ny nz//三角形面片的法向量
　　outer loop
　　　　vertex V1xV1yV1z//顶点V1的坐标
　　　　vertex V2xV2yV2z//顶点V2的坐标
　　　　vertex V3xV3yV3z//顶点V3的坐标
　　end loop
end facet

在快速成型技术中，对模型的切片过程实际上就是一个平面和平面求交的过程，也就是由平行于XOY的一系列平行平面和组成模型的三角面片求交的过程。实际上这个过程也可以认为是直线和平面的求交，即组成三角形面片的三条边和平行于XOY平面的求交。在这个过程中，首先选取切片平面(z=zi)，然后在STL文件中搜索与这个Z平面相交的所有三角面片，记录下这样的一个个交点，假如STL文件没有错误的话，就会得到一系列Z值不相同的封闭的截面轮廓多边形。

STL切片之后的截面轮廓信息是指由一系列有序点集，顺序连接构成的多个折线。其中第i条折线的点集为：

Vi={v1，v2，…，vn}其中n为点数。

它们必须符合三条规则：

1这条折线应该是简单的封闭的，构成一个多边形。不应该存在自相交和不封闭的情况，自相交的情况很少出现，本文只对比较常见的轮廓不封闭给出了相应的算法。

2vn是足以描述这条折线的最少的点。其中不应该存在多余的数据点，本文对于冗余点的去除提出了一种有效的算法。

3切片之后得到多条封闭的折线形成的截面多边形组成实体区域的边界，必须对这些边界识别并进行方向性处理，其正向规定为：沿封闭折线前进时，区域总保持在左侧，如图1所示。

图1　轮廓区域边界的方向

3　轮廓信息错误的修正算法

3.1　错误的轮廓信息

由于CAD系统的计算精度以及网格化功能的漏洞等问题，会造成由CAD模型向STL模型转化时，在大曲率曲面的交界处会出现孔洞等缺陷，这些缺陷的存在会导致切片后截面轮廓的不封闭。在实际的切片过程中，首先对STL文件建立邻接关系的链表[3]，每一个小三角形面片都有三个邻接的三角形面片，当在某个层面切片时，先随机地找到要切的第一个三角形，然后寻找这个三角形的邻接三角形，找到的三角形如果在切片范围内，那么朝向这个方向进行切片，每切一个三角形都是通过他的邻接三角形进行下一个切片，直到回到第一个被切的三角形。如果STL文件有孔洞，那么在孔洞周边的小三角形就会只有两个甚至只有一个邻接三角形。在这种情况下，切片过程不会回到第一个被切的三角形，结果一条轮廓线被分成两段甚至几段。

如图2所示，在某个层面进行切片时，由于孔洞，造成的不封闭，程序中将其强制闭合的情况。

图2　不封闭截面轮廓的强制闭合

3.2　错误轮廓信息的修正算法

作者把切片得到的轮廓数据存放在循环链表中，如果同一截面有多个轮廓，它们每一个轮廓环用一个链表，尽管一条轮廓环可能由于错误被分成了几段。下面为链表的数据结构。

链表的头节点为：

struct Head
{
floatLayHeight；　　//该层轮廓的高度
boolInOrOut；//内外环标志，外环为0
boolHaveBug；//错误标志，轮廓有错为1
DataPoint*Pointer；//指针　
}

数据节点为：

struct DataPoint
{
floatXdata，Ydata；//数据点的x，y坐标
boolHaveGap；//断点标志
DataPoint*Pointer；//指针
}

在本文中，如果轮廓不封闭，在头节点置错误标志；在断开处，置数据节点的断点标志。如图3所示截面轮廓不闭合，同一轮廓被分成了两段轮廓线AB和AC，其轮廓信息数据都存放在同一个链表中，但是两段轮廓线的走向可能不相同。断开点之间的距离一般十分接近，所以可以比较容易地将断开点连接上。

图3　不封闭的截面轮廓及其修正

对于轮廓数据不封闭的修正算法具体步骤为：

(1)调入轮廓信息的链表，检查头节点的错误标志，如果该链表没有错，调入新的链表；如果链表有错，进入(2)。
(2)搜索链表各个节点的断点标志，找出所有断开点。
(3)计算各个断开点之间的距离，连接距离较近的断开点，并且修正各段轮廓线的方向。如图3(a)所示，一个有错的切片轮廓没有将其强制闭合的情况，图3(b)为修正后的结果。

4　轮廓信息冗余数据的滤除算法

4.1　轮廓信息冗余数据分析

由于STL文件格式本身的特点，使得切片之后得到的截面轮廓信息有大量的冗余数据，这些冗余数据的存在，不仅影响以后的信息处理，如光斑的半径补偿[4]；而且影响最后对零件的加工，如对一条直线多次进行插补，造成加工过程不稳定，效率低下。

STL文件的粗糙程度与产生STL时CAD系统指定的毗邻误差有关，当STL模型的毗邻误差较小时，用来近似零件表面的三角形面片数目较多，当STL模型的毗邻误差较大时，用来近似零件表面的三角形面片数目较少。轮廓信息就是用一系列平行于XOY平面的截平面去截交STL模型，得到的STL模型在某个平面上截面的内外轮廓环。在进行零件加工时，激光或者其他的光源在扫描截面实体部分时，为了使零件更加光滑，减小粗糙度，还要进行截面轮廓型的扫描。而当STL模型的精度较高时，切片得到的轮廓环会有大量的细碎线段。同时在同一条直线段上还会存在多个数据点，以及在同一个数据点上有多个重合点的存在。如图4所示，截交平面L1在切STL模型时在靠近顶点V1处，得到几段相当短小的线段；截交平面L2在切STL模型是刚好经过顶点V2，在得到的轮廓信息中就会存在几个坐标完全相同的数据；截交平面L3在切STL模型时，由于小三角面F1、F2和F3在同一个平面上，在得到的轮廓信息中，直线段T1T4，还会存在冗余顶点数据T2和T3。

图4　轮廓信息冗余数据的产生

在轮廓信息中的微小线段，在当前的快速成型系统的精度下，根本无法插补加工，可以去除这些数据；重合点和同一条直线段的多余点的数据，应该剔除。

4.2　算法原理

为了有效地去除冗余数据，本文中将轮廓信息中的直线段作为矢量处理，通过计算矢量积模的方法去除冗余数据。如图5所示，通过计算下式：

实际上是计算三角形APB的面积，如果下式：

|S|≤

，(

为定义的误差范围)。(2)

成立，则可以去掉点A。

图5　冗余数据的去除方法

当满足公式(2)时，因为

取值很小，所以|PA|、|PB和sin∠APB中至少有一个值很小，此时，A点为重合点或者PAB在同一条直线上，也有可能三角形PAB十分微小，以至于小于加工精度，可以将A点去除。

如果只使用上述算法中的公式(2)判断进行去除冗余数据时，如果遇到下面的情况时可能会产生错误。如图6a，b所示，ABCDE之间的距离相当近，首先计算三角形PAB的面积，满足公式(2)，删除点A。同样，随后BCD相继被删除，最后只剩下E点，以PE代替PABCDE，这样多次累计，可能造成较大的误差。

图6　多个重合点删除的情况

综合上面提到的情况作者提出了相应的算法，由于本文将轮廓信息数据存放在循环链表中，对于删除操作的执行效率较高。

Step1：判断三角形APB的面积是否满足公式(2)，如果满足，进入Step2，否则转向Step4
Step2：计算三角形APB的面积是否等于零，如果等于零，直接删除A点，转向Step4，否则进入Step3。
Step3：计算线段AB的长度，如果AB小于设定的值δ(即AB为微小线段)，再计算BC的长度，如果BC小于δ，继续计算接下来的线段的长度，直到E点，删除BCD点；如果AB小于δ，删除A点。
Step4：调入新的轮廓信息数据，转向Step1。
Step5：到达头节点，结束。

5　截面轮廓内外边界的自动识别

在STL模型切片之后，得到的是一系列截面轮廓多边形，在每一个截面上，可能有多个轮廓多边形，这些轮廓多边形可能是实体的内边界也可能是实体的外边界，有的可能含有多个外边界和内边界[5]，为了随后的数据处理能够顺利进行，必须将这些截面轮廓的内外边界进行识别，并使轮廓数据遵循外边界逆时针、内边界顺时针的规则。基于STL模型的切片轮廓边界所具有的特点，本文提出一种简单的内外边界识别算法。

定义。轮廓多边形的特征点是指在多边形的所有顶点中，x坐标值最大而y坐标值相对较小的那个顶点。

由定义可知，多边形的特征点可定时多边形的凸顶点，通过特征点可以判断轮廓多边形的走向。如图7所示，Vi为多边形的特征点，是凸顶点，可通过计算Vi点邻近的两条边的矢量积，来判断多边形为顺时针还是逆时针。

　　s=Vi-1Vi×ViVi+1(3)

如果s大于零，则该多边形为逆时针(如图7(a)所示)，如果s小于零，则该多边形为顺时针(如图7(b)所示)。

图7　轮廓多边形走向的判别方法

内外边界识别的详细算法描述如下：

Step1：搜索截面的所有轮廓多边形的x坐标的极大值点、极小值点和y坐标的极大值点、极小值点，这些点所在的多边形一定为外边界，并对这些多边形作外边界标志。

Step2：取余下未作标志的一个多边形，找到特征点，从该点起沿x轴正向作射线，求此射线与所有多边形的交点个数，若交点个数为奇数，则此多边形为内边界，并作内边界标志，若交点个数为偶数，则此多边形为外边界，并作外边界标志；

Step3：判断是否还有未作边界标志的多边形，若有，则转Step2。

Step4：查找轮廓多边形的特征点，根据公式(2)判断多边形的走向，如果为内边界，则将多边形走向改为顺时针，如为外边界将其改为逆时针。

Step5：直到所有多边形判别完毕，自动识别结束。

算法首先要找出轮廓极限点与各多边形的特征点，然后利用其位置的特殊性识别出一些内外边界，当然，该识别算法的时间复杂度与截面轮廓中多边形的个数和边数有关。该算法是一个通用的算法，适合于截面轮廓含有一个或多个内外边界的情况。

6　结　论

(1)本文所述截面轮廓的错误修正算法，对于截面轮廓不封闭的情况，能够较好的进行修正。
(2)通过对截面轮廓信息冗余数据的滤除，提高了后续的数据处理的速度，在不失掉加工精度的情况下，提高加工的稳定性和效率。
(3)通过利用截面的轮廓极限点和各多边形的特征点快速地识别出实体截面轮廓的内外边界，为快速成形技术中激光光斑半径的实时自动补偿提供了必要的前提条件。本文的算法已经应用到紫外光固化快速成型系统中，实践证明，效果较为理想。

附中文参考文献：

3蔡小康.智能化的快速成形切片算法[J].中国机械工程，1997，8(5)：49-51.
4刘　斌，肖跃加，韩　明.LOM技术中激光光斑半径的自动补偿算法[J].华中理工大学学报，1996，24(10)：26-29.
5刘　斌，肖跃加等.实体截面轮廓内外边界的自动识别算法[J].华中理工大学学报，1996，24(10)：23-25.(end)

文章内容仅供参考 (投稿) (如果您是本文作者，请点击此处) (2/2/2005)


您的位置：首页 > CAD/CAM/PDM/PLM展区 > 三维打印机展厅 > 产品库 > 快速成型机 > 技术论文 > 正文	产品库会展人才帮助 \| 注册登录