3D打印中一种快速分层处理算法的研究
2017-09-28刘大伟王苏洲
刘大伟，王苏洲
(1.南京工程学院 自动化学院 ，南京 211167；2.南京工业大学 电气工程与控制科学学院 ，南京 211816)
3D打印中一种快速分层处理算法的研究
刘大伟1，王苏洲2
(1.南京工程学院 自动化学院 ，南京 211167；2.南京工业大学 电气工程与控制科学学院 ，南京 211816)
通过对3D打印中STL数据模型分层规则的分析建立有向加权图数据结构，该数据结构在找到邻接三角形的同时也记录了其权值信息，运用图的深度优先遍历法，建立递归搜索函数，针对递归切片中出现的三角形“点切”问题，提出了一种基于STL模型的快速分层算法即分组排序的有向加权递归算法。此算法通过对三角形面片分组排序后，进行有向加权图递归搜素，获得三角形面片之间有序排列的交点，在OpenGL环境中实现了截面轮廓的自动生成，根据每个轮廓环切割的第一个三角形面片数据，确定截面轮廓的走向。实验结果证明该算法可以减少面片之间建立拓扑关系的时间，实现简单，稳定可靠。
3D打印；分层算法；STL模型
0 引言
3D打印采用分层制造原理，以STL模型作为3D打印的文件格式，但它无法直接作为3D打印的输入数据，必须通过分层软件对输入数据进行处理。基于STL分层算法的关键步骤是在获取轮廓时，先判断三角面片和切平面的位置关系，若相交则求交。这种求交过程中，要遍历所有三角形面片，而大部分三角形面片与切平面不相交，查找过程比较费时。并且每条边都要求交两次，交线排序过程也比较费时。为了提高分层效率，研究者对STL模型数据先进行预处理，其中主要分层算法有两类。
一是基于STL模型几何特征分类的算法。此算法对STL文件的三角形直接进行分级分类，然后进行求交计算，但必须整理截面轮廓信息形成封闭的有向线段。利用三角面片存在的特点：在Z方向上如果三角面片越长，那么与其相交的切平面将会越多；三角面片在Z方向的最低点越是最低，与切平面相交将越快。但这种方法对三角面片类的划分指标是模糊值，因此难以完全杜绝位置关系的无效判断。
二是基于STL模型拓扑结构信息的分层算法。三角形面片在STL模型中毫无顺序，这一算法首先建立三角形面片的几何拓扑数据，在拓扑信息的基础上进行分层处理。如果没有建立拓扑信息，搜索三角形面片比较费时，但是建立拓扑信息后，能够搜索到构成该三角形面片的三个顶点和三条边，通过边的信息还可以搜索到邻接三角形面片。此方法算法在三角形面片和切平面求交时，每个三角形面片只对一条边求交，可以直接得到有向封闭轮廓，但是建立拓扑数据过程费时，且占用内存较大。
本文在充分研究上述分层算法特点的基础上，吸取各自优点，提出了基于分组排序的有向加权图递归分层算法。首先对所有三角形面片分组排序，把排序之后三角形面片建立分层关系矩阵，再对活性三角形面片分别进行有向加权图递归搜素，并求交点，最终生成截面轮廓数据。该算法可以减少面片之间建立拓扑关系的时间，实现简单，稳定可靠。
1 分层算法原理
1.1 分组排序
分组排序可以减少判断三角形面片与切平面位置关系的次数，假设切平面为n个，那么所有的三角形面片可以被分成n组。根据分层方向上三角形面片3个顶点中的坐标最小值来决定该片初次在分层中出现的层号。依据矩阵关系遍历模型中全部的三角形面片，将与相同切平面相交的三角形面片放在同一组中，每层重新生成以层号为索引的相交面片集合表[4]。
如图2所示Fi表示一个新的与第i个切平面相交三角形面片的集合，即Fi=(fi1，fi2…fij…fim),与当前切平面相交的三角形面片组成的集合称为活性三角面片表，可以提高分层效率。
图2 分层关系矩阵的结构
1.2 有向加权图递归算法原理
假设V是非空有限顶点的集合，集合内的元素表示顶点。假设E也是非空有限边的集合，集合内的元素分别于V(V中的元素一一对应，则称G=(V，G)组成一个图，E内的每个元素为图的一条边。如果E中一条边的两个顶点出现的顺序不重要的时候则称图G为无向图；如果E中一条边的两个顶点出现的顺序不能颠倒时，则称图G为有向图，图内的边成为有向边。
2 分层算法的实现
2.1 分组排序的建立
设STL模型起始的分层高度为H[1],面片在Z轴上的最大值为Hmax，最小值为Hmin，厚度为△H。介于i和j两者之间的切平面的序号即与这个面片相交，i和j的值为：
(1)
(2)
由公式(1)和公式(2)可以判断三角面片位于哪个分层，同时形成三角面片与分层面片序列号的对应关系，产生两者之间的分层关系矩阵。当Hmax=Hmin时，表示三角形面片与分层平面相互平行，这些的面片将不需要加入到分层矩阵关系矩阵中。
2.2 有向加权图的建立
根据上文所述的算法原理与图论知识，建立一种能够详细对STL模型毗邻关系进行描述的有向加权图数据结构。
定义：设STL模型的有向加权图C=(V,A,W)使一个有序的三元组，Q为边的权值，V，A，W，Q代表的含义如下[5]：
(1)V={V0,V1…Vn}，V内的元素表示图D所有顶点的集合。
(2)A={A
(3)W={W
(4)Q={Q
如图3所示，假设三角形面片的三条边的权值互相等，设定共享相应边的邻接面片的权值大小，设连接顶点(v0,vt)两个顶点的权值Q(v0,vt)=1，则Q(v1,v0)=1；同理Q(v0,v2)=2，则Q(v2,v0)=2；Q(v1,v2)=2，则Q(v2,v1)=2。根据权值得大小可以很快查找到切平面的邻接三角形面片[6]。
如图4所示，三棱锥有四个三角形面片，分别取序号为0,1,2,3。那么三角形面片邻接关系如图5所示。三棱锥各三角形面片权值有向加权图如图6所示。
图3 三角形面片权值
图4 三棱锥
图5 三角形邻接关系
图6 三棱锥的有问加权图
可使用一个加权有向的关联矩阵将三棱锥顶点邹城的有向加权图描述出来，邻接矩阵表达如下表1所示。
表1 加权有向邻接矩阵
邻接矩阵用来表达由STL模型顶点组成的有向图，而这个邻接矩阵是稀疏矩阵，用它来表达邻接关系占用的内存空间大。本文采用适合存储这种这种稀疏矩阵的三角形邻接出边链表，结构如图7所示。三棱锥有向加权图的邻接表的存储数据结构如图8所示。
图7 结构图
图8 邻接表
邻接表C语言的数据结构如下:
Typedef struct triangle
{
float normal [3]; //三角形面片的法向量
float x [3]; //三角形顶点坐标
float y [3];
float z [3];
int slice_flag; //三角形面片的访问标志
int vertex; //三角形面片编号
int Q[3]; //三角形面片的权值
struct triangle next//链表指针
}
建立三角形面片邻接关系主要根据一个三角形的任意两个顶点是否与另一个三角形的两个坐标相同，如果相同则判定这两个三角形是邻接三角形。由于CAD或是其他作图软件在绘制STL模型文件中经常在不同三角形的顶点坐标计算时发生错误，出现同一顶点在不同位置的现象。为了正确的建立三角形之间的邻接关系，如果比较任意两个顶点的距离小于设定值δ，则认为这两点是一个顶点[7]。
2.3 递归搜索过程分析过程
通过建立的三角形面片的有向加权图，使用深度优先遍历法搜索图中所有的三角形找出相交点，即递归搜索。首先从图中V0开始搜索，接着访问Vi(Vi与V0相邻且没有被访问)连续重复上述遍历方法，访问全部顶点及其相邻的顶点，直到访问截止。被访问过的顶点用标置位slice_flag=1表示。通过递归搜索找出与切平面相交但未曾被访问的三角形。递归搜索程序流程如图9所示。
图9 递归搜索程序流程
如图10所示，在递归搜索过程中，碰到L2切平面搜索工作顺利结束，同时生成封闭的轮廓线。遇到L1情况时，只有部分顶点在L直线上，则无法搜索到邻接三角形。
对这种情况进行处理，就是判断三角形面片的顶点与直线是否相交。如果相交，将把这个三角形面片设置slice_flag=1，不再求交计算。以此三角形面片为基础，依据它的权值，求其邻接的三角形面片，搜索将继续进行。如果三角形面片在搜索过程中处于求交的范围内，但未被求交计算，则表示在这个切平面高度还有封闭的轮廓，将重新开始搜索递归算法，生成一条新的封闭轮廓[8]。
图10 三角形搜索状况
3 分层算法的实现
3.1 三角面片与切平面交点求取
求取三角形面片与切平面的交点可能会出现下列情况[9]：①相邻切平面与同一个三角形面片相交的交点求取；②切平面与未相交过的三角形面片的交点求取。
(1) 相邻切平面与同一个三角形面片相交的交点求取
采用迭代算法中的增量计算法，即每一步的计算结果上一步的计算结果和增量组成，这种算法计算量少，效率高。
如图11所示，ΔABC的顶点坐标分表为B(x1，y1，z1)，C(x2，y2，z2)，A(x3，y3，z3),假设L1的切平面高度为Z=zi，边BC与L1相交的点设为Vi，坐标设为(xi，yi，zi)。当L1增加ΔZ高度时，则L2切平面的高度zi+1=zi+Δz，那么边BC与L2的交点为Vi+1，坐标则为(xi+1，yi+1，zi+1)。一个三角形面片存在与多个切平面相交，交点之间存在相关性，利用这种相关性可求其他的交点。
图11 Δ ABC与切平面求交情况
边BC的方程表示为:
(3)
则边BC与相邻切平面Z=zi与Z=zi+1的相交对的交点Vi，Vi+1可以用如下公式计算：
(4)
(5)
(6)
(7)
由式(4)和式(5)两个表达式可得：
(8)
(9)
yi+1=yi+Δy
(10)
使用增量算法进行交点求取，假设三角形面片一边与N个切面相交，在求解N个交点的坐标时，可以降低计算量，提高效率。
(2)切平面与未相交过的三角形面片的交点求取
利用平行于xoy面的切平面与三角形面片求取交点，设分层方向为z轴的正方向，将切平面与三角形面片相交的交点连接起来的线段就是截面轮廓。如图12所示，切平面z=h与ΔABC相交的交点为V1，V2，已知AB两点的坐标设为(x1，y1，z1)，(x2，y2，z3)，V1与V2交点V1的坐标设为(x，y，z)，那么直线V1V2可以用式(3)表示。可以求得V1的坐标为：
(11)
图12 截面轮廓方向的确定
3.2 分层算法描述
本文采用的分层算法根据三角形面片的Z轴方向建立分层关系矩阵，根据确定的分层关系矩阵可以建立分组三角形面片的有向加权图，使用递归搜索法对三角形面片进行求交运算，最后获得每层切片的轮廓数据信息，确定截面轮廓走向。算法的实施步骤如下：
(1)导入STL模型文件计算出模型需要的最大空间；
(2)运算出三角面片在Z轴坐标的最大值与最小值；
(3)确定分层的厚度Z；
(4)根据获取的各面片顶点坐标的最大值与最小值确立分层关系矩阵；
(5)对切平面建立有向加权图；
(6)选用递归搜索法求有向加权图中相交的的三角形，全部清除所有的相交边，将求到的交点放入轮廓线数据中。
(7)根据获得的轮廓数据，对截面轮廓走向进行直接确定；
(8)将切平面进行上移，如果切平面比模型最大高度还高，则进入(7)，否则进入(2)；
3.3 截面轮廓走向的确定
分层切片获得得轮廓线走向是不明确的，进行线宽补偿需要确定轮廓线的走向及内外边界。假设实体的外轮廓的逆时针方向为正方向，实体内轮廓的顺时针方向为正方向。STL文件内每个三角形切片数据中含其外法向量，所以在对STL文件进行切片的过程中，可以对轮廓环的走向进行直接确定。
在对分层算法描述中，可知对第一个三角形面片的分层过程中，任意选定三角形的一条边，接着沿着这个三角形面片的邻边三角形的方向搜索下去，一直到返回这个三角形。因此正确选择第一个三角形的边对得到截面轮廓方向是十分重要的，如图12所示，三角形F为第一个被切割的三角形。若得到交点P0，则轮廓的走向将会沿着D0方向，若得到P1点，那么轮廓将沿着D1的方向。本文为此选用如下方法来对截面轮廓走向的确定，判别函数如下：
F=(N×P0P1)×n
(12)
表达式中N为三角形的单位法向量，n为切片方向(Z轴上的单位向量)，n=[0,0,1]。
若F>0，选取P1为交点，截面轮廓的方向为D0；若F<0，选取P0为交点，截面轮廓的方向为D1。
4 实验结果
将本文提出的基于分组排序的有向加权图递归分层算法与两种常用的算法进行比对，分别是基于STL模型几何特征分类的算法和基于STL模型拓扑结构信息的分层算法。在本文实验中简称为算法1和算法2。
实验从模型分层时间、内存空间和体积误差三个方面对算法进行评估，3种算法应用于6个复杂程度不同的模型，STL模型如图所示。依次编号为1～6，各个模型包含的三角形面片的个数如表1所示。实验环境为OpenGL，算法语言使用C++[10]。
表2列出了模型分层厚度为0.01mm时3种算法对6个实验模型得出的模型分层时间、内存空间和体积误差，因为模型复杂程度的不同，各角度实验数值相差也比较大。
图13 6个STL模型
表2 6个模型在3种算法下的结果
图14为3种算法的分层时间对比曲线，从图中可以看出本文算法在分层运算效率方面优势明显，耗时相对算法1与算法2大幅减少，仅仅为算法2的18%左右，对于一些结构简单的STL模型，本算法只需几十甚至几百毫秒，面片数在2×104的模型只需要十几秒，适用性比较强。相比较而言，算法1比较适用于结构简单的模型，但对于三角形面片数在2×103以上的STL模型，分层需要的时间上升，无法进行应用。相对于算法1，算法2虽然在分层时间上有所减少，但是在建立拓扑数据过程耗时，且占用内存较大。对于面片数在2×104以下的模型，可以在20s以内很快完成分层，但对于复杂程度较大的模型，则需要很长时间才能完成。
图14 三种算法分层时间
图15给出的是本算法与算法1、算法2在减少体积偏差方面的比较。相对于算法1而言，本文算法平均可以使体积偏差减少大约3.6%的体积偏差，对模型2、5甚至达到了7%左右,但是在对模型10处理时出现了稍微的反复。与算法2相比较，本文算法平均可以使体积偏差减少大约1.16%，除了个别模型(模型6)。下降的幅度都相对较少，大约只有0.69%。该实验结果是在预期范围内的，体积偏差虽然变大，但是分层效率明显提高。
(a)与 算法1相比较 (b)与算法2相比较图15 本算法与算法1、算法2的精度性能比较
5 结论
本文提出的一种基于STL模型的快速分层算法即分组排序的有向加权递归算法。经过理论分析与实验结果对比，可以得到以下结论：
(1)通过对3D打印中STL模型文件进行分析，建立有向加权图数据结构，该拓扑结构找到邻接三角形记录其权值数据信息，通过权值信息直接找到边，进而求得边与截面的交点。该数据结构建立耗时短，分层效率高。
(2)通过对递归切片中出现的三角形“点切”问题的分析，在调用的递归函数中可以自动进行判断，完成搜索任务，进而避免摄动误差，达到分层的智能化与集成化。
(3)本文所有算法试验都是以正确STL文件为基础，对于部分残缺的STL模型在进行算法试验之前必须对模型进行修补，才可以生成完好的轮廊。对于如何处理有缺陷的STL模型软件也在开发之中。
[1] 朱晓鹏.激光熔覆再制造过程中的分层切片方法[D].上海:上海交通大学，2013.
[2] 黄建.数控加工空间运动平滑路径的规划[D].扬州: 扬州大学，2013.
[3] 刘斌，黄树槐.快速原型制造技术中实时切片算法的研究与实现[J].计算机辅助设计与图形学学报，1997,9(6) :488-493.
[4] 王春香 郝志博. 快速成型技术STL模型等厚分层算法研究[J]. 机械设计与制造,2014(4):133-136.
[5] 张嘉易，刘伟军，王天然,等.快速成型数据处理系统研究[J].机械设计与制造，2004(1) :38-40.
[6] Zhang L C,Han M , Huang S H. An effective error-tolerance slicing algorithm for STLfiles[J].The International lounutl of Advanced Manufacturing Technology,2002,20(5)；363-367.
[7] 赵吉宾,刘伟军.快速成形技术中基于STL模型的分层算法研究[J].应用基础与工程科学学报，2008,16(2):224-233.
[8] 朱经纬,王乘,蒙培生.基于控制点误差控制的网格简化算法[J].计算机应用，2007,27(5)：1150-1152.
[9] 王春香,郝志博,陈浩宏.快速成型中基于MATLAB软件的STL模型的分层优化[J]. 机床与液压，2014,42(21):113-117.
[10] 罗楠,王泉.一种快速3D打印分层方向确定算法[J].西安交通大学学报,2015,49(5):140-146.
(编辑李秀敏)
ResearchonaFastHierarchicalAlgorithmfor3DPrinting
LIU Da-wei1，WANG Su-zhou2
(1. College of Automation，Nanjing Institute of Technology，Nanjing 211167,China；2.College of Electrical Engineering and Control Science，Nanjing Tech University,Nanjing 211816,China)
Through the analysis of the hierarchical rule STL data 3D printing model weighted directed graph data structure, the data structure found in the neighboring triangle also records the weight information, using depth first traversal method graph, establish recursive search function, for the triangle "cut" the problem of recursive slices, put forward a fast algorithm based on STL model is a sorting algorithm to weighted recursive. This algorithm based on triangle sorting, directed weighted graph recursive search, obtain the intersection between triangles arranged orderly, in OpenGL environment to achieve the automatic generation of contour, according to the first triangle data of each contour cutting, to determine the profiles. The results show that the algorithm can reduce the time of establishment of the topology relation between patches, simple, stable and reliable.
3D printer；hierarchical algorithm；STL model
TH164;TG506
：A
1001-2265(2017)09-0050-05
10.13462/j.cnki.mmtamt.2017.09.013
2016-11-26；
：2017-01-08
刘大伟(1980—)，男，安徽萧县人，南京工程学院实验师，硕士，研究方向为3D打印机的研究，(E-mail)zdhxldw@njit.edu.cn。
