一种基于伞形搜索的树形支撑结构生成算法.doc

一种基于伞形搜索的树形支撑结构生成 算法王燕宁张李超rnsft史玉升华中科技大学材料学院材料成形与模具技术国家重点实验室广东技术师范学院摘要：和比目前成熟的支撑结构，树形支撑结构更节省材料，但其结构复杂多变一种 最优的树形支撑结构生成算法难度至少为NP难度对此，提出一种基于伞形搜 索的树形支撑结构生成算法通过伞形搜索算法快速求解满足临界倾角约束条件 的支撑节点，采用贪心算法和迭代的思路逼近最优解同时，在生成树形支撑结 构过程中用体素法对树形枝干与制件实体进行干涉判断，避免支撑与实体干涉， 保证支撑结构的合理性对比商用软件Meshmixer,所提算法在生成树形支撑结 构的合理性及算法生成时间上具有一定优势，且能处理带凸台结构复杂模型的 支撑结构问题关键词：3D打印；树形支撑结构;临界倾角约束;伞形搜索;体素化;作者简介：王燕宁（1993-）,女，湖北武汉人，华中科技大学硕士研究生，研 究方向：3D 打印、支撑结构;E-mail:1804575498@. com;作者简介：张李超（1975-），男，湖北武汉人，副教授，博士，硕士生导师， 研宄方向：快速成形及软件架构，通信作者；E-mail: clcganttcac@263. net;作者简介：陈森昌（1963-）,男，陕西西乡人，副教授，博士，研究方向：增材 制造技术，再制造技术;E-mail: 1299676191@. com;作者简介：胡汉伟（1992-）,男，湖北广水人，硕士研究生，研究方 向:CAD/CAM;E-mail:765599760@. com;作者简介：史玉升（1962-）,男，宁夏西吉人，教授，博士生导师，研宂方向: 快速成形技术，E-mail: shiyusheng@mail. hust. 。

收稿日期：2017-06-20 基金：国家863计划资助项目（2015AA042505）An Algorithm for Generating Tree-like Supporting Structure based on Umbrella-shape SearchWANG Yanning ZHANG Lichao CHEN Senchang HU Hanwei SHI YushengState Key Laboratory of Materials Processing andDie & Mould Technology, School of MaterialScience and Engineering，Huazhong University ofScience and Technology; Guang Dong Polytechnic Normal University;Abstract：Compared to the current mature support structure, the tree-like support structure saves material, but its structure is complex and changeable. An optimal tree-1 ike support structure generation algorithm is at least difficult to NP. A tree-like support structure generation algorithm based on umbrella-shape search was proposed. The support node satisfying the critical angle constraint was solved quickly by the umbrella search algorithm, and the optimal solution was approximated by greedy algorithm and iterative idea. At the same time, in the process of generating the tree-like support structure, the voxel method was used to judge the relationship between the tree branches and the parts, so as to avoid the support and the model interference and ensure the rationality of the support structure. Compared with the commercial software Meshmixer, the proposed algorithm has some advantages in generating the tree-like support structure and the generation time of the algorithm, and it is able to deal with the structure problems of complex models with convex structure.Keyword：3D printing; tree-like supporting structure; critical angle constraint; umbrella-shape search; voxelization;Received： 2017-06-200引言由于3D打印采用截面逐层堆叠方式来构建物体，因此对于一些3D打印工艺，如 熔融沉职型 FDM (Fused Deposition Modeling)、光固化成型 SLA (Stereo Lithography Appearance)、数字光处理型 DLP (Digital Light Processing)和 激光选区熔化SLM (Selective Laser Melting)等，需要在打印模型的悬空部 位下方添加支撑结构才能保证正常打印。

陈岩m指出支撑结构设计主要针对两 方面内容研宄：1、如何寻找添加支撑结构的部位;2、如何生成支撑结构对于内 容1，已经有很多成熟的方法，主要有W种一是Meshmixer和Magics等软件 釆用的基于三角面片外法矢量与水平面夹角来寻找添加支撑部位的方法1^11 另一种是根据对相邻切片的布尔运算结果进行分析本文重点研究内容2, 3D打印的支撑类型主要有:直壁支撑、斜壁支撑M、网形支撑III、块状支撑、 柱形支撑m等树形支撑较上述结构支撑在节省支撑耗材方面更具优势，本文 对树形支撑结构生成进行深入研宄，提出一种基于伞形搜索的树形支撑结构生 成算法0前，对于树形支撑结构，己有部分研究成果商用软件Mesh Mixer采用的树 形支撑生成算法，生成的支撑结构不对称且不稳定，有时会出现失败的现象 Varwk等m提出的树形支撑生成方法，支撑结构对称性较差且不稳定，支撑与 制件实体表面接触较多宋国华等U21捉出的树形支撑算法采用改进的L-系统 算法自下而上生成树状结构，这种自下而上的生成方法对于带凸台结构的模型 会出现支撑不全的问题魏潇然等Uil针对熔融沉积过程中结构不稳定，提出一 种以熔丝为支撑单位的树形稀疏支撑结构，虽然在耗材和打印时间上有所提高， 但是在算法计算时间上不具有优势。

针对上述问题，本文提出的树形支撑生成算法，通过伞形搜索算法求解树形支 撑节点，同时用体素法判断支撑结构与模型的位置关系，保证复杂模型的支撑 结构稳定合理，降低了算法时间复杂度1树形支撑结构生成问题简述图1为本文算法生成的树形支撑结构图，为了节省支撑耗材，树形支撑结构长 度应尽量小在果种程度上树形支撑的构建类似于Euclidean Steiner最小生成 树(ESMT)问题ESMT的0标是找到输入点集中各点连接距离之和最短的长度 而树形支撑结构在三维空间中构建，且需满足临界倾角约束条件，因此该问题 复杂程度至少是np难度m针对该问题，本文提出棊于伞形搜索的树形支撑结 构生成算法图2为带凸台结构模型图，对于这种模型或者类似模型，需对支撑与制件实体 进行干涉判断，合理处理支撑落脚点针对该问题，木文采用体素法对树形支撑 枝干与制件实体进行干涉判断与处理阁1树形支撑结构阁 下载原阁图2带凸台结构模型图 下载原图本文树形支撑结构生成流程如下，以三维模型文件作为输入，识别待支撑区域 并提取待支撑点，通过伞形搜索算法搜索支撑节点，生成树形支撑结构同时， 针对图2中出现的凸台结构，在生成树形支撑结构过程中，对树形支撑枝干与 制件实体进行干涉判断处理。

2待支撑区域识别及待支撑点提取2.1待支撑区域识别目前，STL文件为3D打印领域中事实上（de facto）的工业标准，它存储的是 离散的三角形面片顶点坐标和指向实体外方向的单位法向矢量支撑区域通过三 角面片外法矢量与Z轴的夹角，与临界倾角a的大小关系来判断临界倾角a, 与材料属性、工艺类型、机器型号等因素相关，表示制件实体可以实现自支撑的 最大角度根据三角面片外法矢量与Z轴夹角来判断待支撑区域，一般需要支撑的部位主 要有两种:一种是被支撑面与Z轴垂直;另一种是被支撑面外法矢量与Z轴的夹角 等于或者小于临界倾角a待支撑区域识别，本文采用基于STL格式的支撑区 域识别算法［12］2.2待支撑点提取完成待支撑区域识别后，进行待支撑点的提取待支撑区域实则是三维坐标点集, 即三维凸伍三维凸包的点采样一般采用栅格法如图3，先完成待支撑区域在 X0Y平面内的投影，对待支撑区域的X0Y平面投影进行网格划分，以划分的每个 网格中心点为射线的起点沿Z轴正向与待支撑区域三角面片求交，所求交点即 待支撑点3树形支撑结构生成获得待支撑点后，进行树形支撑节点搜索，具体原理如图4所示树形支撑节点 需满足临界倾角约束，即树形支撑各连接枝干与Z轴的夹角不大于临界倾角 a.o Vanek等M对于临界倾角约束条件进行了实验证明。

阁4中，以待支撑点 pl、p2为圆锥体顶点，临界倾角a为圆锥半顶角，构建圆锥体cl、c2易知，W 圆锥体cl与c2相交区域c内的点都满足临界倾角约朿条件为了节省支撑耗材 及支撑打印吋间，所构建的树形支撑结构长度越短越好，故求解满足临界倾角 约束条件且连接点pi和p2距离之和最短的点q是树形支撑结构生成算法的关 键本文采用伞形搜索算法进行求解图4树形支撑节点搜索原理图 下载原图Pl、P2为待支撑区域中的两待支撑点，cl、c2分别为以pi、p2为顶点的阙锥体， 为临界角，q点为cl与c2相交区域中连接pi、p2距离最短交点3.1伞形搜索算法图4中，区域c中的点均满足临界倾角约束条件，假设树形支撑节点q在圆锥体 cl和c2的对称面上，同时也在圆锥体cl和c2的圆锥面上证明分两步：1、证 明点q在圆锥体cl和c2的对称面上;2、证明点q在圆锥体cl和c2圆锥面上证明一，如阁5 (a)，空间内任意一点P2，都可以在平面M ul M 2N 2上找到其投影点P连接P, M ：、P, M 2、P2 M卜P2 M 2因 垂直于平面M M2 N 2，故 垂直于\1，和M 2因斜边长度大于直角边，故P2 \1々P: M ：，P2 M 2>P. M 2o所以，P2 M i+P2 M 2〉P, M冲，M 2。

故连接点M，和点M 2距离最 短的点必在平面M :义M 2N 2上如图5 (b)，连接两圆锥面顶点距离之和最 短的点必在两圆锥的对称而上证明二，如阁6，在平面Nh N： 。