一种平台化的树形支撑结构生成算法*

王燕宁，赵祖烨，张军飞

0 引言

自20世纪80年代以来，3D打印发展迅速，出现了如熔融沉积成型（Fused Deposition Model⁃ing，FDM）、选择性激光烧结（Selective Laser Sin⁃tering，SLS）、选择性激光熔化（Selective Laser Melting，SLM）、光固化成型（Stereo Lithography Apparatus，SLA）和分层实体制造（Laminated Object Manufacturing，LOM）等众多3D打印工艺。

其中，FDM、SLM、SLA等工艺在加工过程中需要添加支撑结构。在SLM工艺过程中，热应力超过材料强度时发生的塑性变形以及逐层铺粉时的横向扰动等因素都会导致成形质量下降，因此需要设计支撑结构进行部分热量传导和零件固定。FDM工艺中，每个层面都是在上一层上堆积而成，上一层对当前层起到定位和支撑的作用。当前层的形状发生较大变化，如出现悬臂结构或较大倾斜面时，上层轮廓就不能给当前层提供充分的定位和支撑，这时就需要设计一些辅助结构用于支撑[1-2]。SLA工艺以光敏树脂为原料，采用计算机控制下的激光束以预定原型各分层截面的轮廓为轨迹点扫描，使被扫描区的树脂薄层产生光聚合反应后固化形成一个薄层截面[3]，上一层对当前层起到定位和支撑的作用，当截面形状变化很大时需要添加支撑结构。可见，支撑结构的生成是3D打印成型工艺中的一项关键技术。

目前支撑结构的类型主要有：点支撑、线支撑、块状支撑、柱状支撑[4]、网状支撑[5]、肋状支撑和锥形支撑等。树形支撑相比其他类型的支撑，所消耗的支撑材料更少，达到了节省材料降低成本的目的；同时，对于支撑体的打印时间减少，达到节省时间、降低成型周期的目的。在文献[6]中通过大量实验得出当树形支撑的倾斜角小于临界角度时，可以达到支撑效果。证明了树形支撑在支撑耗材比块状支撑、网状支撑、柱状支撑等其他支撑类型更少、打印时间更少的情况下，实体打印效果不受影响。故本文对树形支撑结构进行深入研究，提出一种自上而下的树形支撑结构生成算法。

1 树形支撑结构生成问题简述

树形支撑是一种类似树枝形状的支撑结构，与支撑面接触部位采用众多子枝干提供支撑，子枝干通过连接节点汇聚，为3D打印过程中的悬空区域提供支撑的支撑结构。相较于柱状支撑及网格支撑，树形支撑由于子枝干的汇聚在节省材料及打印时间上有一定的优势。

图1为本文算法生成的树形支撑结构图，为了节省支撑耗材，树形支撑结构长度应尽量小。因此，在某种程度上树形支撑的构建类似于Eu⁃clidean Steiner最小生成树（ESMT）问题。ESMT的目标是找到输入点集中各点连接距离之和最短的长度。而树形支撑结构是在三维空间中构建，且需满足临界倾角约束条件，因此该问题复杂程度至少是NP难度[6]。

图1 树形支撑结构图

本文采用的树形支撑生成算法为一种自上而下的生长方式，在识别的待支撑区域上拾取支撑点，通过子枝干节点搜索连接距离最短的连接节点，连接子枝干与连接节点，连接节点成为新的子枝干节点，依次迭代，直到搜索结束条件，构建整体支撑结构。支撑算法的研究主要分两部分内容：待支撑区域的识别和支撑体的生成。具体树形支撑生成流程如图2。

图2 算法流程图

2 待支撑区域识别及待支撑点提取

2.1 待支撑区域识别

目前，STL文件为3D打印领域中事实上的工业标准，它存储的是离散的三角形面片顶点坐标和指向实体外方向的单位法向矢量。支撑区域可以通过三角面片外法矢量与Z轴夹角，与临界倾角α的大小关系来判断。临界倾角α与材料属性、工艺类型、机器型号等因素相关，表示实体区域可以实现自支撑的最大角度。

根据三角面片外法矢量与Z轴夹角来判断待支撑区域，一般需要支撑的部位主要有两种：一种是被支撑面与Z轴垂直；另一种是被支撑面与Z轴的夹角等于或者小于临界倾角α。待支撑区域识别，本文采用基于STL格式的支撑区域识别算法[7]。

2.2 待支撑点提取

完成待支撑区域识别后，进行待支撑点的提取。待支撑区域实则是三维坐标点集，即三维凸包[8]。三维凸包的点采样一般采用栅格法。先完成待支撑区域在XOY平面内的投影，对待支撑区域的XOY平面投影进行网格划分，以划分的每个网格中心点为射线的起点沿Z轴正向与待支撑区域三角面片求交，所求交点即待支撑点。

3 树形支撑结构生成

3.1 树形支撑节点搜索原理

获得待支撑点后进行树形支撑节点搜索和支撑结构生成。树形支撑节点需满足临界倾角约束条件：（1）树形支撑连接枝干之间的夹角不大于倾角α；（2）新支撑点的Z坐标大于等于基底Z坐标。树形支撑节点搜索原理如图3所示，为减少支撑材料，连接相邻的待支撑点距离和应在满足临界倾角约束条件下尽量小。区域c中的点均满足临界倾角约束，点q为连接待支撑点p1和p2距离和最短的连接点。树形支撑节点q在圆锥体c1和c2的对称面上，同时也在圆锥体c1和c2的圆锥面上。根据联立方程组，即可求解树形支撑节点q。

3.2 树形支撑结构生成流程

树形支撑生成流程采用贪心算法和迭代的思想，选取支撑节点连接长度最短的连接方式并生成新的支撑节点。对每个当前支撑点求解连接距离之和最短的连接方式，以逼近树形支撑结构构建最优解。树形支撑结构生成流程如下所述。

（1）新支撑点生成

获得原始待支撑点后，自上而下生成新的支撑点，利用临界倾角约束条件，生成树形支撑结构。

1）逐步求得与当前点生成新支撑点连接距离最短的点，生成新支撑点与树形支撑的局部连接枝干；

2）对于剩余的独点，遍历所有的下一层新支撑点，找到与独点连接距离最短的新支撑点，并判断是否满足临界倾角约束条件，如果满足则加入到树形支撑的连接枝干中，若不满足则将独点加入到下一层新支撑点中。

（2）将获得的下一层新支撑点迭代步骤（1）中的方法，继续求解，直到新一层支撑点个数小于等于1。

图4为采用本文方法生成的门把模型的树形支撑结构图。

图3 支撑节点搜索原理图

图4 门把树形支撑结构图

4 树形支撑结构工艺路径生成

4.1 SLC文件格式

SLC文件格式是Materialise公司为获取快速成型三维模型分层切片后的数据而提出的一种数据存储的文件格式。SLC数据模型对三维模型的轮廓表达采用的是2.5D模式，最终形成的三维模型是沿着Z轴方向由一系列内外轮廓包围形成的小实体叠加而成的[9]。SLC格式使用的实体有轮廓边界、轮廓层、直线段和多义段。其中轮廓边界是值按逆时针排序的外边界与按顺时针排序的内边界、轮廓层是指由实体材料的内外边界线所组成的部分。直线段指的是位于二维平面上的两点间的连线。

4.2 Clipper库处理树形支撑结构

Clipper是一种开源的二维图形裁剪库，可对平面多边形进行布尔运算（交、并、差、异或）。由树形支撑结构的骨干结构转化为工艺路径，具体流程如图5。

图5 支撑结构工艺路径规划流程图

首先根据支撑结构骨干线，结合圆柱方程构造树形支撑结构三维数据结构，然后沿着Z轴方向切片，对于给定Z值的切片需要进行轮廓的布尔运算，采用Clipper库进行布尔运算得到最终的切片轮廓。得到切片轮廓后，进行路径填充，即可得到树形支撑结构的工艺路径。图6为图1的树形支撑结构SLC工艺路径。

5 结论

图6 SLC工艺路径图

本文提出了一种树形支撑结构生成算法，相比传统的支撑结构，树形支撑结构在节省材料使用量和支撑加工时间上具有优势。目前，本文关注点主要在树形支撑结构生成方面，对于具体工艺的支撑优化工作较少。例如，支撑截面形状、截面大小对于支撑稳定性的影响，如何通过支撑避免制件出现应力变形等。因此，未来的工作将主要对此进行深入研究。

参考文献：

［1］沈振宏，戴宁，李大伟，等.基于临界倾角约束的树形支撑结构生成算法［J］.中国机械工程，2016（8）：1107-1112.

［2］姜耀林，邵中魁.3D打印在快速熔模精密铸造技术中的应用［J］.机电工程，2017（1）：48-51.

［3］刘汝虎.光固化快速原型制造数据预处理关键技术研究与实现［D］.南京：南京航空航天大学，2008.

［4］董学珍，莫健华，张李超.光固化快速成形中柱形支撑生成算法的研究［J］.华中科技大学学报（自然科学版），2004（08）：16-18.

［5］钱波，莫健华，张李超.光固化快速成形中网形支撑生成算法的研究［J］.锻压装备与制造技术，2005（04）：122-124.

［6］ VANEK J，GALICIA J A G，BENES B.Clever Sup⁃port：Efficient Support Structure Generation for Digital Fabrication ［J］.Computer Graphics Forum， 2014，33（5）： 117-125.

［7］钱波，张李超，史玉升，等.基于STL模型的表面区域递归拾取算法［J］.华中科技大学学报（自然科学版），2008（09）：90-93.

［8］周培德.计算几何/算法设计与分析/中国计算机学会学术著作丛书：算法设计与分析［M］.北京：清华大学出版社有限公司，2005.

［9］吴懋亮，华麟鋆.SLC文件的扫描路径生成方法［J］.机械与电子，2010（11）：18-20.