第9期 2017年9月
组合机床与自动化加工技术
ModularMachineTool&Automatic ManufacturingTechnique
文章编号：10012265(2017)09005005
D0I:10.13462/j.cnki.mmtamt.2017.09.013
3D打印中一种快速分层处理算法的研究
刘大伟，王苏洲
No.9 Sep.2017
（1.南京工程学院自动化学院，南京211167;2.南京工业大学电气工程与控制科学学院，南京 211816)
摘要：通过对3D打印中STL数据模型分层规则的分析建立有向加权图数据结构，该数据结构在找到邻接三角形的同时也记录了其权值信息，运用图的深度优先遍历法，建立递归搜索函数，针对递归切片中出现的三角形“点切”问题，提出了一种基于STL模型的快速分层算法即分组排序的有向加权递归算法。此算法通过对三角形面片分组排序后，进行有向加权图递归搜素，获得三角形面片之间有序排列的交点，在OpenGL环境中实现了截面轮廊的自动生成，根据每个轮廊环切割的第一个三角形面片数据，确定截面轮廊的走向。实验结果证明该算法可以减少面片之间建立拓扑关系的时间，实现简单，稳定可靠。
关键词：3D打印；分层算法;STL模型
中图分类号：TH164；TG506
文献标识码：A
Research on a Fast Hierarchical Algorithm for 3D Printing
LIU Da-wei',WANG Su-zhou
(1. College of Automation,Nanjing Institute of Technology ,Nanjing 211167, China ;2. College of Electrical En-gineering and Control Science,Nanjing Tech University,Nanjing 211816,China)
Abstract : 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 aee recursive slices, put forward a fast algorithm based on STL model is a sorting algorithm to weighted recur-sive. This algorithm based on triangle sorting, directed weighted graph recursive search, obtain the intersec-tion between triangles arranged orderly, in OpenGL environment to achieve the automatic generation of con-tour, 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, sta-ble and reliable.
Key words: 3D printer;hierarchical algorithm; STL model
0引言
3D打印采用分层制造原理，以STL模型作为3D 打印的文件格式，但它无法直接作为3D打印的输人数据，必须通过分层软件对输人数据进行处理。基于 STL分层算法的关键步骤是在获取轮时，先判断三角面片和切平面的位置关系，若相交则求交。这种求交过程中，要追历所有三角形面片，而大部分三角形面片与切平面不相交，查找过程比较费时。并且每条边都要求交两次，交线排序过程也比较费时。为了提高分层效率，研究者对STL模型数据先进行预处理，其中主要分层算法有两类。
一是基于STL模型几何特征分类的算法。此算法收稿日期：2016-11-26；修回日期：2017-01-08
对STL文件的三角形直接进行分级分类，然后进行求交计算，但必须整理截面轮廓信息形成封闭的有向线段。利用三角面片存在的特点：在Z方向上如果三角面片越长，那么与其相交的切平面将会越多；三角面片在Z方向的最低点越是最低，与切平面相交将越快。但这种方法对三角面片类的划分指标是模糊值，因此难以完全杜绝位置关系的无效判断。
二是基于STL模型拓扑结构信息的分层算法。三角形面片在STL模型中毫无顺序，这一算法首先建立三角形面片的几何拓扑数据，在拓扑信息的基础上进行分层处理。如果没有建立拓扑信息，搜索三角形面片比较费时，但是建立拓扑信息后，能够搜索到构成该三角形面片的三个顶点和三条边，通过边的信息还可
作者简分势数据980—），男，安徽萧县人，南京工程学院实验师，硕士，研究方向为3D打印机的研究，（E-mail）zdhxldw@njit.edu.en。