面向机械臂3D 打印的曲面分区算法

张帆， 王克鑫， 赵圆圆， 魏培祥， 谭跃刚

（武汉理工大学机电工程学院， 湖北武汉 430070）

0 前言

传 统 熔 融 沉 积 （ Fused Deposition Modeling，FDM） 3D 打印采用三自由度叠加成型的方式， 模型只能沿着固定的沉积方向堆积， 模型悬空部分需要打印支撑结构， 在生长方向上存在天然的性能缺陷， 制约了打印效率和性能［1］。 机械臂具有多自由度的特性， 能够灵活构建空间中任意无干涉曲线的运动路径， 将机械臂运用到3D 打印领域， 可以改善传统层式打印产生的阶梯效应， 减少打印模型悬空部分的支撑约束， 改进沉积方向上的性能不足， 从而提高3D打印的质量和效率［2］。

三维模型切片处理是3D 打印的前提。 传统三轴打印的切片处理方式是垂直于Z轴、 平行于XOY平面进行平面分层， 具有生长方向单一性的缺点。 机械臂的多自由度特性可以在打印过程中改变打印方向，支持曲面分层处理［3］。 但是对于某一部分有多条互不连通的支柱结构或外表面层曲率变化较大（凹凸形态较明显） 的模型， 经过曲面分层处理之后会出现大量多岛屿状曲面层， 即该曲面层由若干个互不相连的独立区域组成。 这种曲面的复杂性具体表现在2 个方面： （1） 从整体来看， 曲面层不具备整体相连的轮廓信息， 即无法用一条封闭轮廓环表示边界； （2）从局部来看， 各区域相互独立（各自具有完整轮廓）并且两两之间存在没有数据填充的空白区。 对于曲面分层后的路径规划而言， 填充处理不仅需要识别待规划层的整体轮廓信息生成最大边界路径， 以及获取轮廓内部的点面信息生成内部填充路径， 而且需要识别非打印区域（无数据空白区） 的存在以确定从当前子区域到下一个子区域的待跳转点［4－5］。 如果不做分区处理而直接进行路径规划则会出现以下情况： （1）由于整个曲面层边界不是以一条封闭轮廓环存在， 而是由多个不相连的小轮廓环组成， 基于轮廓环一类的路径只会获取到其中一个独立区域的轮廓信息进行规划， 影响了打印路径的完整性； （2） 由于空白区域特征无法识别， 获取不到待跳转点， 基于扫描面一类的路径规划会将待跳转的2 个边界点通过直线相连，即： 两独立区域的跳转部分（从一个区域至另一个区域的2 个跳转点） 通过直线填充连接起来， 影响打印路径的正确性。

目前， 国内外对于曲面分区的研究分为2 种：（1） 将获取到的曲面拟合为平面， 建立三维曲面和二维平面的联系， 然后在平面上进行分区处理， 最后通过映射关系重建原曲面。 如张盼盼［6］提出将原曲面直接投影到XOY平面并进行拓扑分片、 之后将所分的平面子片逆投影回原曲面的方法， 这种方法无法完全获取XY值相同但Z值不同的特征点， 会导致在投影过程中丢失三维点信息； BRUNO 等使用了LCMS算法展平目标曲面， 然后进行平面分片和逆映射回曲面的处理［7］， 这种算法虽然可以很好地将曲面保角映射至平面， 但是在分区处理后逆映射回曲面的过程中会产生新的三维点坐标， 导致原曲面一定程度上失真。 因此， 将三维曲面进行降维处理后再升维的方法对于曲面分区具有一定的局限性。 （2） 直接提取曲面信息进行特征识别进而作分区处理。 如ATKAR等［8］采用基于RMS 高斯曲率的Watershed 算法以及拓扑几何的方法进行分区， 但是这种方法会将目标曲面分为大量曲率变化不大、 可近似平面的子区域， 算法流程过于复杂而且分得的区域数量冗余；VAN TUONG、 POKORNY＇［9］提出基于曲面分片加工的思想， 即首先自适应地获取聚类中心点， 并借助区域生长算法将曲面划分为点云密度大致相等的子曲面，这种方法对于只含有一个单连通区域的曲面划分精确， 但是对于含有若干个岛屿曲面特征的模型分区并不适用； THEOLOGOU 等［10］提出了基于模糊聚类和最小割的层次化三维网格分割算法， 并根据划分的网格组成相应子区域， 但是这种方法需要对已有点云进行K－means聚类， 通过事先设置分区数量获取对应的聚类阈值以达到分区目的， 算法迭代步数多且需要提前设置聚类阈值， 对于3D 打印中出现的曲面层适用性不强； KUMAZAWA 等［11］提出基于顶点曲率特性对复杂曲面进行分区的算法， 但这种方法太依赖内部三维点的相互关系， 无法充分考虑边界轮廓点的特征信息， 导致分区后处于边界的区域轮廓信息不完整。 李慧贤等［12］提出一种基于扫描矢量的分区算法， 即在扫描矢量生成的同时对子区域进行分割， 但是此方法需要获取一条封闭的轮廓信息， 难以处理同一层曲面上有2 个及以上互不连通的单独子区域。

综上所述， 传统的2 种分区思想并不能达到预想的分区效果（即划分后的独立子区域既保证本身具有独立完整的轮廓信息， 又使得内部点面信息不失真， 通过所有子区域简单叠加的方式生成原曲面）。因此， 在分区前后曲面信息不失真的前提下， 需要尽可能地划分适合路径规划的子区域。

1 面向机械臂3D 打印连续路径规划流程

面向机械臂3D 打印连续路径规划的软件全流程主要分解为模型导入、 曲面切片分层、 路径规划以及G 代码生成。 首先导入stl、 obj 等实体模型文件， 之后经过模型体素化、 体素化分层等切片处理步骤得到每一层的曲面信息， 再经过螺旋偏置、 直线填充等路径规划， 最后经过数字化处理生成G 代码。 其总体处理流程如图1 所示。

图1 机械臂3D 打印切片流程Fig.1 Flow of 3D printing slice of manipulator

为了实现机械臂无支撑3D 打印， 曲面切片分层必不可少。 该部分主要包括模型体素化、 体素化分层、 曲面层生成3 个部分， 经过其处理可以将三维实体模型分解成若干空间有序的三维曲面。 具体流程如图2 所示。

图2 曲面分层流程Fig.2 Surface layering flow： （a） stl model； （b） voxel model； （c） surface layering； （d） surface layer

（1） 模型体素化。 模型的体素化过程实质是三维栅格化， 即通过定位模型边界在三维栅格空间中的位置， 进而确定边界体素信息和内部体素信息（体素块的中心点）。 首先将模型的三维坐标转化为空间体素坐标， 获取基础信息； 然后沿着Z向通过逐层切片的方式获取截面轮廓， 经过截平面的离散化得到一定数量的三维点数据； 最后以离散点为中心定义体素块大小。 体素化后得到的体素模型既包含表面信息以及内部信息， 而且能够表现出模型的三维结构。

（2） 曲面分层。 曲面分层可以采用生长线的方式进行处理［13］。 首先分析模型文件， 找到最佳打印方向作为生长线方向。 然后根据模型大小计算出最小包围盒， 以此确定生长线的起始和终止坐标， 并且将对应的两点相连即为曲面分层所需的生长线。 最后将所有获取的生长线进行体素化处理， 分成若干个体素块， 其精度与模型体素块保持一致， 并且提取出相应的体素块， 获取起、 止体素块的坐标。 每一层根据坐标信息进行划分， 从而形成由生长线体素点、 内部体素点和边界体素点组成的点云数据， 进而形成有序曲面。

2 基于曲面分层的多岛屿分区算法

2.1 曲面多岛屿层问题的提出

经过体素分层生成有序列的若干曲面（三维离散点和面片信息组成的obj 格式文件）， 研究发现其中一部分曲面具有特殊性， 这种曲面从整体来看由多个独立岛屿区域组成， 不能提取统一封闭的边界； 从局部来看每一个独立区域拥有其轮廓边界和内部信息， 具体表现如图3 所示。

图3 多岛屿曲面层Fig.3 Multi－island surface layer： （a） surface layer model；（b） multi－island surface layer

在切片处理的过程中， 特殊曲面层的出现对曲面上的路径规划有很大影响。 对于扫描面的路径规划而言， 如果一个扫描面同时穿过多个独立子区域， 这些子区域间的无数据空白部分不能较好地识别， 会导致两跳转点形成直接连线［14－15］［如图4 （a） 所示］； 而对于轮廓环的路径规划方法而言， 由于多岛屿曲面层中轮廓信息是由若干个不连续的轮廓环组成， 这种规划方式只能识别到一个区域， 另外的若干个区域信息就会丢失， 也导致了路径规划的异常［16］［如图4 （b）所示］。 因此曲面分区在切片流程中尤为重要。

图4 分区前直接路径规划示意Fig.4 Schematic of direct path planning before zoning：（a） based on scanning plane （line）； （b）based on contour ring

2.2 基于广度优先搜索的分区算法

针对分区的必要性和传统分区方式的局限性， 文中提出了基于广度优先搜索的曲面岛屿分区算法。 分区是在曲面分层之后进行的， 分区算法输入的是一层具有点和面片信息的obj 文件， 经过算法处理， 输出若干个已经完成分区的obj 文件， 并且可以通过处理后的若干个文件复原原始obj 文件信息， 从而保证分区后各个区域中信息数据的准确性。 算法主要流程如图5 所示。

图5 曲面分区流程Fig.5 Surface zoning process

步骤一， 判断是否需要分区处理。

（1） 遍历当前层中的点（｛Vi｝i＝1，…，n）和面片（｛Fj｝j＝1，…，m）并记录， 同时创建一个大小为n的访问列表is＿Visit， 内部元素初始化值为0；

（2） 从Vi中选取第一个点并在｛Fj｝中获取对应点的索引位置， 根据索引位置遍历出与选取点相邻的其余点信息， 再以新获取的2 个点为新的当前点继续重复遍历， 将所有遍历到的点以及取出的第一个点的索引对应在is＿Visit 列表元素设置为1。

（3） 当遍历结束后， 如果访问列表中不存在0值， 则说明当前层已经是单连通区域， 无须分区； 如果列表中依然存在0 值， 说明至少存在2 个岛屿区域， 需要进行分区处理。

步骤二， 新区域三维点信息生成。

（1） 确定可以划分出的单连通区域数量。 经过步骤一确定需要进行分区操作后， 遍历当前情况下的访问列表is＿Visit， 随机获取一个元素值为0 的索引值， 并且在｛Vi｝中定位到具有相同索引的点P， 遍历｛Fj｝获取到点P所在的面片， 重复步骤一中操作（2）， 但是新遍历到的点对应在is＿Visit 列表元素不再设置为1， 而是可以提前建立一个变量L， 初始值为0， 每经过一次is＿Visit 列表的访问，L相应递增并将此次访问过的is＿Visit 列表中索引对应的元素设置为L， 其中L的变化如公式（1） 所示。 最终当is＿Visit 访问列表中不存在0 时， 分区结束， 对应的L值就是需要分区的数量。

L＝L＋1 （1）

（2） 确定需要分出的单连通区域内部点信息。根据操作（1） 中所得到的L值， 提供L个暂时数据为空的列表（｛Pi＿List｝i＝1，…，L）， 每个列表用于存储分区后的所有点。 遍历is＿Visit 访问列表， 此时列表元素为｛1，2，…｝， 将具有相同元素的索引值提取（这些索引值就是对应在obj 文件里的点的编号）， 并将其按照遍历顺序依次添加到已经设置好的点列表PList中， 至此L个列表中存储的就是每个分区所包含的所有点信息。 其中三维点的划分如公式 （2）所示。

步骤三， 新区域面片信息生成。

经过步骤二中的区域划分， 已经将对应区域的离散点全部填充进去， 接下来就是要进行面片信息的填充从而形成完整的曲面信息。 面片是由顶点相连组成， 其中存储着各个点的索引， 而每个点是三维空间中的离散点， 这种存储方式以精简的数据结构可以推导出法线、 曲率和面积等各种面片信息。 当把三维点提取到一个区域中时， 对应的面片信息需要跟随点的变化而更新。

（1） 确定三维点提取前后在原区域和当前区域中索引对应关系。 按顺序遍历点列表（｛Pi＿List｝i＝1，…，L）， 列表中的每个元素值是原区域中的索引信息， 而元素值对应在列表中的索引下标是将点放在新区域下的索引信息， 这两个索引信息相互对应， 使用以PKey－PValue键值对的形式存放（PKey表示三维点在原区域中索引位置；PValue表示三维点在分区后新区域中索引位置。 其中PKey是不重复的，PValue是有重复的）。

（2） 新区域面片信息生成。 遍历原始面片信息，记录原始点在面片信息中的索引值并与PKey进行比对， 当查找到相同PKey值则获取对应的PValue值， 并且把原面片信息中当前点索引值替换为PValue值（每通过一次对比就移除当前PKey－PValue以减少时间复杂度）。 当遍历结束时， 新区域中所有的面片信息就会对应更新完成。 其中PKey、PValue和遍历列表中的索引i三者的变换关系如公式（3） 所示：

步骤四， 分区完成。

完成分区。 将步骤二和步骤三中生成的点云信息和面片信息对应组合生成新的曲面， 这些若干个曲面就是岛屿分区算法后产生的新区域， 其中每个新曲面和原始曲面含有一样的数据信息。 在移除PKey－PValue值之前复制同样的键值对copy＿KV 进行保存， 经过分区后的新面片信息可以通过copy＿KV 中对应的信息重新组成原始面片， 从而保证分区的准确性。 至此多岛屿状的曲面层完成了分区， 可以在每个区域分别进行路径规划。

3 实验仿真及分析

在面向机械臂无支撑3D 打印的过程中， 某一部分由多条互不连通的支柱结构（图6 中模型1 和模型2 的下半部分） 或外表面凹凸起伏变化较大（模型1的上半部分） 的模型经过曲面分层处理之后会出现多岛屿状曲面（图7）。

图6 实验测试模型Fig.6 Experimental test model： （a） model 1； （b） model 2

图7 测试模型中的曲面层Fig.7 Surface layer in test model： （a） model 1；（b） model 2

3.1 未分区处理时仿真实验分析

选取模型1 中的2 个曲面层进行路径规划实验，2 个曲面层都无法提取统一封闭的整体轮廓信息（独立子区域拥有各自轮廓）。 其中对图8 所示曲面使用基于扫描线的路径规划方式填充， 对图9 所示曲面使用基于轮廓环的螺旋偏置路径规划方式填充。

图8 分区前直线路径规划Fig.8 Straight line path planning before zoning： （a） surface layer； （b） data surface layer； （c） path planning；（d） path planning completed

图9 分区前螺旋偏置路径规划Fig.9 Spiral offset path planning before zoning： （a） surface layer； （b） data surface layer； （c） path planning；（d） path planning completed

如图8 所示： 当对图8 （a） 中的曲面层使用基于扫描线的路径规划方式填充时， 由于若干不连续区域在扫描线方向上重合， 使得规划过程中无法识别两区域间没有数据填充的非打印部分， 导致规划第一块区域时从重合部分开始就直接连线到第二个区域， 并从第二个区域开始继续进行扫描填充， 具体表现在图8 （c） （d） 中。

如图9 所示： 当对图9 （a） 中4 块独立岛屿状区域组成的曲面层进行基于轮廓环的螺旋偏置路径规划时， 由于这种路径规划的方式是首先获取曲面层中一个点， 然后遍历与该点相连的所有三维离散点， 进而获取到该点所在区域的边界， 所以对于图9 中无法提取统一的整体轮廓信息（4 个独立子区域拥有各自边界） 的曲面层， 螺旋偏置路径只能识别到其中一个封闭的独立子区域的边界进行规划， 具体表现在图9 （c） （d） 中。

由以上结果可以验证， 类似于图8 和图9 特征的曲面不分区而直接进行路径规划会出现以下问题： （1）两独立跳转区域之间存在连线的不合理性； （2） 所有区域无法完全识别。 因此， 对多个独立子区域共同组成的曲面层进行路径规划前需先进行曲面分区处理。

3.2 传统分区方法仿真实验分析

如图10 所示： 传统的建立空间和平面关系的分区方式可以将多岛屿曲面层划分为独立的具有整体轮廓的子区域， 但是图10 （a） 中待分区曲面经过投影或映射至平面分区然后逆映射回曲面处理会得到图10 （c）中结果， 同时对比图10 （a） （c） 和图10 （b）（d） 明显看出： 两独立子区域相对于原曲面区域出现了信息缺失的问题； 另外对比图10 （a） 和图10 （d）也可以看出： 分区后的子区域无法完整地重组回原曲面。 这种内部信息缺失的问题使路径规划过程中获取路径点信息不完整， 最终导致打印错误。

如图11—12 所示（图11 属于模型1 的两层曲面， 图12 属于模型2 的两层曲面）， 不同颜色部分即为分区后的独立子区域， 采用基于曲面特征信息分区的方法将已经满足路径规划条件的区域（拥有封闭轮廓环的单连通区域） 继续进行划分（如图11 （b）和图12 （a） （b） 所示）。

图11 基于曲面特征信息的分区（模型1）Fig.11 Partition based on surface feature information （model 1）： （a） the 56th layer； （b） the 6th layer

图12 基于曲面特征信息的分区（模型2）Fig.12 Partition based on surface feature information （model 2）： （a） the 41th layer； （b） the 37th layer

当继续划分的区域曲率变化较大或凹凸状较多时， 划分后的子区域（根据顶点曲率、 高斯曲率等曲面特征参数划分） 中会出现内部有多个孔的复连通区域（如图11 （a） 的绿色部分： 这种复连通区域拥有一个封闭外轮廓以及若干内轮廓， 基于轮廓环的路径规划无法识别多轮廓边界的输入， 所以需要进一步分区处理）， 此分区方法使得划分后的子区域更加复杂而且数量更多， 反而不利于路径规划的完成。

可见， 传统的2 类分区方式存在划分子区域不合理、 子区域部分点面信息丢失等问题， 因此用作机械臂3D 打印中曲面路径规划前的分区处理方式均不合适。

3.3 基于广度优先搜索的分区方法仿真实验分析

分区是为了达到正确规划路径的目的， 需要考虑划分后子区域的完整性以及合理性， 因此采用文中提出的分区方式对由若干独立子区域组成的曲面层进行处理。 由于模型1 中的曲面层曲率变化更为明显而且处理起来相对复杂， 因此可以更好地证明分区算法的通用性， 所以选用模型1 中的两层曲面进行仿真分析， 并使用不同的路径规划方式验证算法的适用性。

如图13—14 （选用曲率更为明显的模型1 中的2个曲面层） 所示： 图13 是经过文中提出的分区方式处理后进行的路径规划， 对比图8 （c） （d） 可以明显看出： 消除了两独立区域之间的连线并且填充路径更加完整； 对比图14 和图9 （d） 可以看出： 经过分区处理后的独立子区域被全部识别， 并进行了完整的路径规划。

图13 分区后直线路径规划Fig.13 Straight path planning after zoning： （a） original surface layer； （b） partition； （c） subregion； （d） path planning； （e） planning completed

图14 分区后螺旋偏置路径规划Fig.14 Spiral offset path planning after zoning：： （a） surface layer； （b） partition； （c） regional 1 planning； （d） regional 2 planning； （e） regional 3 planning； （f） regional 4 planning

另外对比图13 与图10 （a） （b） 、 图11 （a） 以及图14 与图11 （b） 可以看出： 多岛屿曲面经过基于广度优先搜索的分区方法可以有效地将具有单独轮廓的独立子区域划分出来， 并且可以提取各自的轮廓信息以及内部信息以处理路径规划。 通过路径规划结果也可以明显看出： 经过文中算法处理后的区域相对于传统方法处理后的区域在合理性以及完整性上都得到了保证。

3.4 打印实验

由于篇幅限制， 文中只对模型2 进行打印实验。对于模型2 而言， 无论如何放置， 传统的三轴打印机在悬空部分都会产生支撑， 影响打印的效率， 如图15 所示。

图15 传统三轴3D 打印支撑示意Fig.15 Traditional three－axis 3D printing support： （a）the right side of model 2； （b） the opposite side of model 2

当使用机械臂3D 打印时， 通过曲面的切片方式以及机械臂的多自由度协作可以有效地避免支撑的产生， 将3D 打印切片生成的对应G 代码文件导入仿真软件中预览， 具体如图16 所示。 在确保分区及路径规划无误后， 将G 代码文件导入机械臂3D 打印机执行。 执行实验中使用SR20⁃1700 型号的STEP 工业臂，成型材料使用碳纤维， 选用的线宽和层高均为1 mm，内部填充比例为0.8， 丝材半径为0.875 mm， 打印喷头温度为235 ℃， 底床温度为75 ℃， 具体打印过程如图17 所示， 打印完成如图18 所示。 最终实验成功执行。

图16 曲面层仿真打印路径Fig.16 Print path surface layer simulation： （a） the 37th layer of model 2； （b） the 41th layer of model 2

图17 机械臂3D 打印过程Fig.17 3D printing process of manipulator

4 结语

文中提出了面向机械臂3D 打印的曲面多岛屿复杂模型的分区方法， 实现了对多岛屿曲面层模型的完整打印。 相比传统分区思想无法解决点面信息丢失以及分区后子区域不适用于路径规划的问题， 通过广度优先搜索思想的分区方法将若干独立子区域分别提取划分， 保证分区的合理性， 并且通过原始曲面层的点面对应关系对提取的面片信息进行更新， 保证分区后子区域点面信息的完整性。 通过大量的实例测试以及仿真对比， 验证了文中分区方法的有效性。 此方法为利用多自由度机械臂实现拥有多岛屿曲面层特征的复杂模型3D 打印提供了基础。 但是， 通过分析发现文中方法对曲面层中带有孔洞的复连通区域分区效果并不理想， 后续将通过孔洞识别与边界划分相结合的方式进一步研究复杂曲面的分区。