基于FDM的自适应分区路径规划算法研究

汪国强，石志良，熊林杰，蔡旺月

(武汉理工大学 机电工程学院，湖北 武汉 430070)

3D打印是一种依据物体的三维模型数据，利用成型设备以材料累加的方式制成实物模型的技术，具有广阔的应用前景[1]。FDM(fused deposition modeling)成型技术核心在于分层制造，通过材料沿规划轨迹的层层粘接叠加来实现三维实体的制造，合理的路径规划方法直接影响模型的加工效率及表面精度。路径规划技术在很多领域都具有广泛的应用，凡是可拓扑为点、线网络的规划问题基本上都可以采用路径规划的方法解决。

许多研究者对3D打印路径规划进行研究，Jin等[2]提出之字形路径填充，但会产生许多急转弯和阶梯效应，影响打印质量。Abdullah等[3]提出了一种基于蚁群优化技术的轮廓平行路径生成方法，生成一条清晰的刀具路径，该刀具路径可以在最少的时间下加工整个区域。文献[4]通过将任意复杂的域分解为更简单的域，并用螺旋曲线填充每个子区域。Zhao等[5]对上述算法做了进一步的改进，根据偏移曲线的位置将一个域分解为一组子区域。重新连接，每个子区域都填充有一条连续的费马螺旋曲线，最终可以获得一条全局连续路径。Ding等[6]将2D几何形状分解为一组凸多边形，并为每个凸多边形确定最佳倾斜度，并使用锯齿形和平行填充路径的组合来生成连续路径。通过连接所有子路径来形成最终路径。王美茜[7]以打印重叠率和轮廓面积误差作目标，对义齿轮廓的往复直线路径间距进行优化，提高了零件的精度。翟晓雅[8]提出了分形模型的分区路径规划算法，对3个不同区域采用不同的填充方式，并对区域间的填充连接进行优化，保证边界精度同时提高了打印效率。但他们并未从打印方向轮廓间的拓扑关系进行纵向路径规划。文献[9]提出多切片层细小区域扩充算法，实现细小区域在模型打印方向上的扩充，只适用于扩充后的单区段简单模型单独打印，未考虑不同区域打印干涉情况，且不适用于打印方向多区段并存的复杂模型。

当模型为多峰结构或多孔结构时，单层的轮廓数量较多，层次打印的方式会造成整体的打印路径上存在多次空走、喷头回抽，增加了制造成型时间，同时也会影响模型表面精度。笔者提出一种考虑打印头干涉影响的分区打印路径规划算法，依据多切片层轮廓沿打印方向邻接拓扑关系进行区域扩充，通过轮廓树的建立、分区轮廓组的构造与数据存储、打印过程干涉检测及规划，生成打印路径，减少空走次数和行程，保证打印安全可靠，提高打印效率和成型质量。

1 分区打印路径规划算法

算法的步骤为：①将模型切片得到的轮廓保存在相应的切片平面高度轮廓组中。②对相邻的切片层间的轮廓进行轮廓位置关系判别，建立轮廓树。③检测特征分区轮廓进行轮廓分区。④考虑单区段内轮廓间的打印干涉影响，自适应规划安全合理的打印路径。整体算法流程如图1所示。

图1 算法流程图

1.1 轮廓树的建立

在实际切片过程中，为保证打印模型的质量，通常设置的切片厚度较小，远小于三维模型打印高度，相邻切片层间同区域的轮廓沿打印方向位置临近，轮廓形状和大小呈现渐变特性，且能反映三维模型的上下依赖、附属关系等局部几何特性。上下切片层两轮廓的投影轮廓位置关系存在相离、相交和包含3种情况，其中，相交和包含两种符合轮廓渐变特征，可进行扩充。但可扩充上下轮廓和邻接切片层中存在轮廓分裂、合并及缺失的特殊轮廓，为处理该特殊轮廓，引入父子轮廓和特征分区轮廓的定义。

定义1：相邻切片中，沿打印方向的上层切片某一轮廓p和下层切片某一轮廓q，两投影轮廓属于相交或包含关系，则下层轮廓q为上层轮廓p的父轮廓，上层轮廓p为下层轮廓q的子轮廓。

定义2：相邻切片中，若某一轮廓p含多个父轮廓或多个子轮廓或无子轮廓，则称该轮廓p为特征分区轮廓。

在轮廓“父子”关系建立过程中，因模型的复杂性，在特殊区域切片时，会存在一个轮廓包含多个下级轮廓或多个上级轮廓。如图2(a)所示，为人体股骨头的模型，其竖截面如图2(b)所示，进行切片后，切片轮廓图如图2(c)和图2(d)所示，其中L1、L2、L3为相邻切片层截交面。L1切片轮廓为单轮廓，L2切片轮廓为双轮廓，且L2的两轮廓与L1的轮廓满足上述的包含或相交关系，L1轮廓包含多个子轮廓。

图2 股骨头相邻切片轮廓示意图

轮廓树的建立，需要对相邻切片层中父子轮廓进行判别，记录当前轮廓的父子轮廓信息，便于后续路径规划算法查找访问。同时，不同类型的特征分区轮廓会对打印路径规划造成影响，需要对特征分区轮廓类型制定标识符，建立特有的轮廓数据类型。该数据类型成员包括轮廓的轨迹点集、轮廓所在平面层数、轮廓位于该层切片轮廓组的序号、轮廓面积、下一层子轮廓的序号数组、上一层父轮廓的序号数组以及特征分区轮廓类型标识符，初始化时将该标识符设为flase。建立轮廓的数据类型，便可对位置关系进行判别，完善轮廓信息。

轮廓的位置关系可以利用轮廓的AABB包围盒碰撞检测方法[10]，快速筛选出可能的相交或包含轮廓，然后采用射线法[11]进一步判别某一轮廓内相交区域的点集，是否相交或包含在另一轮廓内。父子轮廓关系判别与特征分区轮廓判别步骤如下：

步骤一：获取当前第H层切片的所有轮廓LH{LoopH,1,LoopH,2,…,LoopH,n}，轮廓数量为n，与下一层第H+1层切片的轮廓LH+1{LoopH+1,1,LoopH+1,2,…,LoopH+1,m}，轮廓数量为m。

步骤五：检索第H切片层中每个轮廓的子轮廓数量，若数量为0，则说明该轮廓没有子轮廓，若数量为1，则含有一个子轮廓，若超过1个，则标记该轮廓为“多子轮廓”，同样地，检索第H+1切片层中每个轮廓的父轮廓数量，若超过1个，则标记该轮廓为“多父轮廓”。

1.2 分区轮廓组的构造与数据存储

在完成轮廓拓扑关系建立后，每个轮廓的父、子轮廓序号都被保存，并能检索。轮廓存在无子轮廓、多子轮廓和多父轮廓的复杂情况，将特征分区轮廓在轮廓树中的位置定义为“特殊节点”。对于轮廓沿打印方向的扩充分区处理，在分区过程遇到这种特殊节点时，需要以此轮廓为起始节点，至下一个特殊节点完成扩充，如图3所示，其中轮廓2和轮廓5为多子轮廓，轮廓13为无子轮廓，轮廓12为多父轮廓，3-5，4-10，6-13，7-9，12-15间的轮廓可以区域合并。

图3 依据拓扑关系建立的轮廓树

3D打印在分区打印过程中，与传统的层次打印方式不同，层次打印方式每一层高度值相同，喷头水平移动跨越空腔区域，并不会产生碰撞。但采取分区打印的方式，分区已打印的区域与待打印的区域打印的高度值并不相同，存在干涉问题。当检测到干涉现象发生时，不能沿当前轮廓的子轮廓向下继续打印，需跳转至干涉轮廓所在的区域，沿干涉轮廓的子轮廓打印。这要求打印轨迹不能按预先的分区，完整地打完该区域后跳转剩余区域，而是对待打印的轮廓进行实时“干涉检测”，干涉发生，则需重新规划轨迹。如图4所示，区域1与2距离太近，分区打印时，与打印机喷头的热熔腔产生碰撞，这种情况必须避免，区域1不宜打印太高。

图4 干涉现象

打印路径规划算法设计与分区轮廓组的构造方式密切相关，路径规划需要遵循三点原则：①当打印至不含子轮廓的轮廓处，需获取与该轮廓距离最近的未打印轮廓，将该轮廓设为打印轮廓，对其子轮廓进行干涉检查，完成后续打印；②当打印轮廓的子轮廓为多父轮廓时，需跳转至打印轮廓的兄弟轮廓所在轮廓组中未打印的轮廓；③当前打印轮廓的子轮廓与其余区域轮廓发生干涉，需跳转至干涉轮廓所在区域轮廓组中的最底层未打印轮廓，将该轮廓设为打印轮廓。

采用对特征分区轮廓分区的方法，记录并由低到高排列特征分区轮廓位于轮廓树的高度，将轮廓树上的轮廓按邻近的两特征分区轮廓高度差进行分割存储，在该区段内，任一轮廓存在子轮廓且唯一，从而可构建一系列同维的轮廓数组。最终将原始无序的多个区段划分为整齐分割的连续区段，仅对一个区段内多个轮廓组进行干涉判断，搜索范围降低，可提高干涉检查效率。具体分区轮廓组的构造与存储方法如下：

步骤一：定义一个特征分区轮廓整数型数组，获取第i层的切片轮廓，数量为n。

步骤二：取其中第k个轮廓，当k≥n时，切片层数i+1，跳转步骤一；当k

步骤三：进一步判断该特殊轮廓是否为“多父轮廓”，若为“多父轮廓”，则将当前“多父轮廓”的层数H-1存于特征分区轮廓数组中，若为其它特殊轮廓，则将该特殊轮廓所在层数H存于特征分区轮廓数组中，跳出循环，切片层数i+1。

步骤四：k值加1，跳转步骤二。

步骤五：完成上述步骤，即可获取所有特殊轮廓所在切片层的位置和特征分区轮廓数组中相邻两项间的层数，首项为扩充的最低层数m1，末项为扩充的最高层数m2，从整体切片轮廓中提取首项层数m1所在的切片轮廓。

步骤六：对该切片的每一轮廓，进行子轮廓查询，若子轮廓所在层数小于m2，则添加到该轮廓的子轮廓数组中，将查询到的子轮廓更新为打印轮廓，对该打印轮廓的子轮廓继续查找判断；若子轮廓所在层数大于等于m2则更新下一合并区域所在的层数段，跳转至步骤五。

轮廓树的分区处理如图5所示。N1为一维数组，N2为二维数组，起始为轮廓3和轮廓4所在层高，终止为轮廓5所在层高，储存两块合并区域轮廓，N3为三维数组，起始为轮廓6所在层高，终止为轮廓8所在层高，存储三块合并区域的轮廓。

图5 轮廓树的分区处理

完成轮廓树的初始区域划分后，仅需在区域内对轨迹进行规划，而不是全局规划处理，同时在多父轮廓所在的区段，需打印完所有当前层所有轮廓才能继续打印，满足原则②的要求，这种分区方法降低了干涉检查范围，提高计算效率。在区域内的轨迹规划，要依据之前提到的3个原则，减少空走路径。

1.3 打印过程干涉检测及规划

干涉检测算法广泛运用于数控加工领域，常用的方法有层次包围盒法和空间剖分法[12]。数控加工是基于去除材料的方式，在加工前，模型表面和轨迹线位置已知，刀具沿加工轨迹线更新刀具位置进行干涉判别，但3D打印属于增材制造技术，需要对其干涉情况进行具体分析，明确干涉检测对象与范围。

3D打印机打印头结构如图6所示，由热熔腔和喷嘴组成，热熔腔外部有套筒等辅助结构，为简便计算，将其简化为圆柱模型，喷嘴为圆锥或凸台结构，热熔腔的半径最大，在分区打印过程中最易发生干涉碰撞。

图6 打印头模型示意图

如图7所示，以复杂的圆弧空腔模型进行分析，t1等于t2并略小于R3，t3略小于R2，起始打印轮廓为区域1第0层，并沿其子轮廓不断向上打印，高度增高。干涉原因是由于沿未打印的低层轮廓中某段轨迹打印时会与已打印的高层轮廓发生碰撞，图7中区域1与区域2相距t1处的两轮廓发生热熔腔碰撞、区域2与区域3相距t3的两轮廓发生喷嘴碰撞。判断一个轮廓的子轮廓是否为规划路径的待打印轮廓，通过检测该轮廓与其余区域低于该轮廓高度的未打印轮廓组中是否存在一个打印点，使位于该点处的打印头与该轮廓轨迹在空间中发生碰撞。如存在，则发生干涉，该轮廓不允许打印，且干涉轮廓所在区域的最低层未打印轮廓为待打印轮廓；若不存在，则不干涉，即该轮廓为待打印轮廓。跨区路径的打印轨迹顺序按图7中①、②、③、④、⑤轨迹排列，打印至区域1第17层时，检测到与区域2第0层中存在轮廓点使热熔腔与第18层轮廓发生干涉，则打印至17层时跳转至区域2；打印至第3层时，检测到子轮廓与区域3发生喷嘴干涉，则跳转至区域3打印；打印至第11层时，区域3与区域2的高度差正好为热熔腔所在位置，由于t2小于t3所以干涉，转区域2打印；沿子轮廓不断向上堆积，区域2打印至顶部，与区域1中的18层轮廓发生干涉，转区域1，并完成区域1的打印；此时检测图7所示区段中仍有区域3未打印完全，则跳转至区域3的第12层轮廓，沿其子轮廓向上打印。

图7 轨迹规划示意图

判别当前轮廓的子轮廓与其它区域是否发生干涉采用K-D tree的范围查询。K-D tree是基于点区域划分的索引结构，每一个节点都代表一定的空间范围，具有占用存储空间小，搜索效率高的特点，非常适合点云模型的顶点检索。

首先，将当前高度以下其余区域的轮廓组向打印底面投影得到的点云作为查询集，当前轮廓点位查询点，设置查询的范围r，获得可疑干涉点，进一步计算干涉平面，判断是否发生干涉。具体步骤如下：

步骤一：根据打印机型号，获取打印头的规格参数(h1、h2、h3、R1、R2、R3)。

步骤二：将当前轮廓以及当前高度以下其余区域的轮廓组向打印底面进行投影，获得两投影点云T1、T2，并用K-D tree的形式进行存储。

步骤三：遍历点云T1的点，从T2点云中使用K-D tree的最近点搜寻方式，计算两两投影点云间的最近距离为d。

步骤四：比较d与R3的大小，若d大于等于R3，则不发生干涉；若d小于R3,则可能发生干涉，转步骤五。

步骤五：选择当前打印轮廓投影点云上的第i点qi，以K-D tree半径为R3的邻域搜寻方式对其余轮廓组投影点云搜索，获取邻域点集roundi。

步骤六：从邻域点集roundi中取第j个点，获取所在轮廓组的高度位置和所属轮廓，计算两原始轮廓的高度差Δh，将Δh与打印头各区段距喷嘴的高度进行比较，判断高度值较大的轮廓所在平面位于打印头的区段，计算实际的干涉检查半径r。若d大于等于r，则不发生干涉，j+1，重复步骤六；若d小于r，则干涉。若遍历完邻域内的所有点，都不干涉，则i+1，转步骤五。

通过上述的干涉检测算法依次检测当前打印轮廓与其余区域轮廓组的干涉情况，若发生干涉，则沿干涉区域的未打印的最低层轮廓为打印轮廓，循环更新，直至该区段所有轮廓完全遍历。对区段中规划排序的最后一个轮廓，判断有无子轮廓，若存在子轮廓，则以该轮廓为打印轮廓；若不存在子轮廓，则以该轮廓所在切片层内，搜索与该轮廓相距最近的轮廓为参考打印轮廓，判断有无子轮廓。若无子轮廓则继续搜索，直至区段中某一顶层轮廓存在子轮廓，将该轮廓设为打印轮廓，即可开始下一区段的打印工作。

2 实验结果与分析

2.1 结果分析

喷嘴型号为Makerbot Mk8，R1为0.6 mm，R2为4 mm，h1为4 mm，h2为4 mm，热熔腔无固定型号，形状尺寸各异，设定R3为30 mm，h3为30 mm，以人体手掌和手肘模型为例，设定切片的层厚为1 mm，对算法进行验证，并将得到的Gcode在CIMCO Edit 软件进行打印轨迹的三维模拟仿真，仿真结果如图8(b)所示。图8(a)为手掌的三维模型，完成切片和轮廓构建后，在构建轮廓树时会存在A～H 8个点所在高度切片轮廓的特殊节点，初始分区划分为9个区段。

图8 算法模型演示

手掌模型较为复杂，用于验证算法的有效性，整体的打印流程如图9中箭头所示。图9(a)中手掌主体和小拇指间距较近，会发生干涉，采用逐层跨区打印；图9(b)中小拇指的打印与其它区域不存在干涉，故可连续打印至节点C所在轮廓高度；跳转至临近的掌中区域连续打印,如图9(c)所示；发生干涉，跳转至大拇指区域连续打印直至与掌中区域发生干涉，如图9(d)所示；跳转至掌中区域，上层打印过程与其余区域不发生干涉，可连续打印至节点C所在轮廓高度，如图9(e)所示；则检测到C点高度以下的区段中，有剩余轮廓未打印，故转至大拇指区完成打印，如图9(f)所示。后续部分的打印也遵循算法规则，实时检测干涉，并跳转区域打印，先后完成小拇指、大拇指、无名指、食指和中指的打印，最终打印完成如图8(b)所示,其中手指间的路径为跨区空走路径。

2.2 数据分析与讨论

对手掌这类多峰模型的打印，以打印时间和空走次数作为评价指标，将分区打印方法与传统的层次打印方法进行比对，设定打印喷头空走移动速度为80 mm/s，将打印层厚做变量，运行对比结果如表1所示。

表1 路径规划方法比较

图9 手掌模型的分区打印过程

由表1知，随着层厚的降低，切片层数增多，传统的打印方式空走次数越多，同时空走的路径长度也越长，但分区打印算法几乎不受切片层厚影响，只有少许增加。增加的空走次数是由于切片层数增多，喷嘴的凸台和圆柱部分在手掌特征分区点A、B、D、E 4处造成不同区域间干涉次数增多，在这4处的临近区域内跨区打印次数会增多。因手掌呈张开状态，越往上层，邻近的手指间的间距越大，喷嘴干涉影响越小，热熔腔造成的干涉成为主要空走原因，当两邻近区域打印高度差累计到8 mm时，干涉可能发生，并空走跨区。这种情况的跨区与两邻近区域打印高度差值有关而与层厚无关，因此5个手指间的空走次数并没有大的变化，总体的打印路径长度也基本保持不变。当层厚为0.2 mm，达到一般桌面级3D打印机的打印精度时，对比两种方法可知，空走次数减少了96.7%，空走路径长度减少96.0%，缩短的打印时间为10分12秒。

3 结论

为提高3D打印的效率，减少打印头空走次数，提出了一种分区打印路径规划算法，依据邻接切片轮廓的拓扑关系，构建轮廓树，通过检测特征分区轮廓位置对轮廓树进行分区，采用K-D tree存储待打印轮廓与其它区域轮廓组的投影点云数据，进行实时干涉检测，寻求安全的打印路径，同时对干涉区域的轮廓利用K-D tree进行近邻点查询，缩短空走行程。该算法基于开源CloudCompare 软件开发出切片原型系统，实现对同一区域相邻层的连续打印以及不同区域间的跨区打印。以手掌模型为例，先后完成小拇指、大拇指、无名指、食指和中指的成型过程。新的路径规划方法与传统打印新的路径规划方法进行比对，空走次数和空走路径明显降低，验证了分区打印算法的有效和实用性。