面向无支撑3D打印的近似金字塔形状分解

周钰琛 黄嘉诚 岳兴春 彭勇 宋威

摘  要：FDM法是当前3D打印中应用最广泛的方法之一，该方法有许多优点，但也存在的需要添加支撑结构才能打印悬垂部分的缺点。针对该缺点，设计了一种近似金字塔形状分解的方法，通过采样平面对模型进行分区，构建点的分类投票矩阵，通过kd-tree加速的分区聚类算法对模型进行分解。结果表明，该分解方法能成功将原模型分解为若干不需要支撑即可进行3D打印的部分。

关键词：3D打印；无支撑；采样平面；DBSCAN聚类；投票矩阵

中图分类号：TP391  文献标识码：A    文章编号：2096-4706（2023）06-0149-05

Approximate Pyramid Shape Decomposition for Support-Free 3D Printing

ZHOU Yuchen1， HUANG Jiacheng1， YUE Xingchun1， PENG Yong1， SONG Wei2

（1.School of Internet of Things， Jiangnan University， Wuxi  214122， China;

2.School of Artificial Intelligence and Computer Science， Jiangnan University， Wuxi  214122， China）

Abstract： The FDM method is currently one of the most widely used methods in 3D printing. This method has many advantages， but also has the disadvantage of requiring the addition of support structures to print overhangs. Aiming at this shortcoming， a method of approximate pyramid shape decomposition is designed. The model is partitioned by sampling planes， the classification voting matrix of points is constructed， and the model is decomposed by the kd-tree accelerated partition clustering algorithm. The results show that this decomposition method can successfully decompose the original model into several parts that can be 3D printed without support.

Keywords： 3D printing; support-free; sampling plane; DBSCAN clustering; voting matrix

0  引  言

FDM（Fused Deposition Modeling）法，即熔积成型法是现在使用最为广泛的3D打印方法之一。FDM法的工作原理是通过加热的喷嘴将材料熔化并挤出，再将材料逐层放置于构建平台。每次只能放置一层材料，直至部件构建完成。FDM法具有打印机结构简单、成本低、成型速度快等优点，但对于平行于构建平台的模型悬垂部分，需要在打印时添加支撑结构并在打印结束后去除，耗费大量时间和材料。

无支撑打印的实现目前主要分为通过多轴机械臂实现和通过模型分割实现两个方面。多轴机械臂能从多个方向进行打印。王铮等[1]提出了通过多叉分解树进行多轴机械臂路径规划，从而削减支持的方法。张帆等[2]提出了一种基于EtherCAT的协同控制方法，控制多轴机械臂完成无支撑打印。

通过模型分割减少支撑甚至实现无支撑3D打印也一直是人们追求的目标。Yang等[3]提出了一种针对壳模型内部填充算法实现自支撑；黄常标[4]等人提出了基于边界的分割方法，实现模型Z的无干涉分解；Herholz等人[5]基于高度场实现模型无支撑分解；易兵等人[6]提出基于高斯映射法向聚类分割方法，将模型分解为各类特征形状；Wei等人[7]以骨架为基础，将薄壳模型分解可无支撑打印的部分。

本文基于多邊形凸分解思想，提出一种基于近似金字塔形状的模型分解方法，首先读入模型的STL模型并进行预处理，然后通过在平行于打印方向上生成一定采样平面，将模型中的点进行分类；再通过kd-tree加速的DBSCAN分区聚类算法将各个相同分类且连通的点聚合成块，每个块在打印方向上都是近似金字塔形状，每个块都不需要支撑便能使用FDM法进行打印。实验结果显示本方法达到了设计要求。

1  STL模型的读取和预处理

STL文件是当前3D打印领域被广泛使用的打印模型文件。STL文件包含多个三角形面片的定义，每个三角形面片的定义包括三角形各个定点的三维坐标及三角形面片的法矢量。本文中STL模型的读取和预处理主要包括根据STL文件建立半边数据结构、模型的封闭性检测和模型漏洞的填补，最后在STL模型内生成点云或者将STL模型进行体素化处理。

1.1  建立半边数据结构

半边数据结构是以边为中心的数据结构。该结构能够存储网格模型顶点、边、面间的拓扑关系，使得对网格模型的局部查找操作更加高效。半边数据结构由顶点（Vertex）、半边（HalfEdge）、边（Edge）、面（Face）和模型（Mesh）五部分构成。半边数据结构的类关系如图1所示。

1.2  模型的封闭性检测和漏洞填补

理想情况下，3D打印使用的STL网格模型应该是完全封闭的。但现实中因为各种原因，读入的STL网格模型可能存在表面孔洞，并不是封闭的，因此需要对网格模型进行封闭性检测，并对漏洞进行填补。

首先检测模型是否是封闭的。对网格模型的所有边进行检查，如果发现某一条边A只被一个网格面所包含，则认为这条边是一条边界边，在这条边的附近存在漏洞。利用半边数据结构，找到这条边A指向的顶点P，并检查P连接的所有边，找出与点P相连的下一条边界边A1，通过找出A1指向的顶点P1，以此类推。当第二次找到边A或者顶点P时，说明回到了起点，找到了一个漏洞，将所有找到的边和顶点作为漏洞轮廓的边集H和点集V记录下来。

之后对点集V进行Delaunay三角剖分，目的是在点集V内生成满足最大化最小角性质和最小化外接圆性质的三角形网格。实现模型漏洞的填补。

最后在封闭的STL模型内生成点云，也可以对STL模型进行体素化处理。本文选择的是生成点云的处理。

2  点的分类投票

在读入STL模型并进行相关预处理后，对模型内的点依据金字塔形状进行分类，构建分类投票矩阵。

2.1  近似金字塔形状

设一个多边形S有一底边（面）B（S），对多边形内部任意一点P，作P到P在B（S）上的垂直投影点P′的连线；若线段PP′完全在S内，则称S为近似金字塔形的多边形。设多边形S垂直于B（S）向上的方向为O（S），则多边形S内的每个点都必须从底边（面）B（S）上的某个点沿O（S）可见。与B（S）相对的边（面），在沿O（S）方向定义了一个能描述多边形S高度的函数，如图2所示。

从上述定义可以知道，如果多边形S是近似金字塔形的，则使用FDM法打印该多边形时，只要将底面B（S）选作构建平台，则不需要添加额外的支撑结构即可完成打印，因为S中不存在平行于B（S）的悬垂部分。

最理想的分解目标是找到使得金字塔形状最少的模型分解结果。然而该目标的实现非常困难。文献[8]中Fekete和Mit-chell证明了该类形状分解问题在3D空间内是NP-hard问题，即难以为该目标找到一个多项式时间复杂度的算法；该目标可能没有多项式时间的解，同时未必可以在多项式时间内验证一个解的正确性。

因此本文的方法旨在产生一种模型分解结果，同时让分解的数量尽可能少，但不验证分解的结果是否使得金字塔形状最少。

2.2  点的分类投票

模型的打印方向一般为Z方向，因此垂直于Z方向产生若干平行于XOY平面的采样平面。设采样平面集D{D0，D1，D2，…，DN}，D内的点按Z坐标由小到大的顺序排列。产生采样平面的目的是作为近似金字塔形状的底面，让模型内的点都能被分类到以某个采样平面为底面的金字塔形状中。若模型内的点在以某个采样平面为底面的金字塔形状中，则称该点投票给该采样平面。

为了产生尽可能少的分解结果，沿Z轴正向和负向的两个方向考察模型S内的点P （xp， yp， zp），判断该点P沿这两个采样方向能否投票给某一采样平面。以点P为顶点，分别向Z轴正向和负向作射线，设正向射线与S的沿射线方向的第一个交点为Q （xQ， yQ， zQ），负向射线与S的沿射线方向的第一个交点为R （xR， yR， zR）。如图3所示。通过比较交点的Z坐标与各采样平面的Z坐标来判断点P能投票给哪些采样平面。

2.3  投票矩阵的构建

构造投票矩阵M=（bik）（n+1）（m+1），其中n为采样平面数量，m+1为点的数量，前n+1行表示对应下标的采样平面能接受哪些点的投票，第n+2行表示点P能投票的最远的采样平面。对于一个采样平面，若某点能向上投票给该平面，则在矩阵中将该行对应的列赋值为1，若能向下投票给该平面，则赋值为-1。每一列第n+2行的绝对值表示该列对应的点能投票最远采样平面在平面集D中的下标；符号代表投票方向，正号代表向上投票，负号代表向下投票。初始化令矩阵内所有元素值为0。如式（1）。对于交点Q，按下标由大到小的顺序，依次比较D内的平面Di与点Q的Z坐标。找到第一个平面Dg，使得ZDg≤ZQ，则认为平面Dg是点P向上投票的最远采样平面，计算点P到平面Dg的距离h1=ZDh-ZP，并让点P投票向上给所有位于点P和平面Dg之间的采样平面，即在投票矩阵中，让所有对应的bik=1。同样地，对于交点R，则按下標由小到大的顺序，依次比较平面Di与点R的Z坐标，当找到第一个平面Dh，使得ZDh ≥ZR，则认为平面Dh是点R向下投票的最远采样平面。如图4所示。计算点P到平面Dh的距离h2=ZP-ZDh，让点R向下投票给所有位于点R和平面Dh之间的所有采样平面，即在投票矩阵中，让所有对应的bik=-1。比较h1和h2，若h1＞h2，则认为平面Dg为点P的最远投票平面，且对应的b（n+1）k=g，g为平面Dg的下标。反之则认为平面Dh为点P的最远投票平面，并让对应的b（n+1）k=-h，h为平面Dh的下标。

（1）

3  DBSCAN聚类分解

对模型中的点进行分类并构造投票矩阵后，使用经kd-tree加速的分区DBSCAN聚类算法对点进行聚类。聚类的目的是找出一个连通的区域，该区域内的点能沿同一方向投票给同一采样平面，也就是说，该区域内的点能与同一采样平面构成一个连通的金字塔形状。

3.1  kd-tree加速的DBSCAN聚类算法

DBSCAN算法是一种基于密度的聚类算法，可以发现满足某一密度条件的任意形状的聚类。DBSCAN定义了两个关键参数：Eps邻域半径和Minpts最小点集。由这两个参数又定义了如下几个概念：

核心点：在其邻域半径Eps内点数目大于等于Minpts的点。

噪声点：在其邻域半径Eps内点数目小于于Minpts的点。

直接密度可达：若点p是核心点，点q在点p的Eps邻域内，则称点q到点p直接密度可达。

密度可达：设区域内一连串的点ci（i=1， 2， …，n），设a=c1，b=cn，若ci到ci-1均直接密度可达，则认为a和b密度可达。

DBSCAN聚类的思想是，首先找出一个核心点，将区域中所有与该核心点密度可达的点都聚为一类。之后找出下一个核心点，重复上述过程，直到区域中所有点都完成聚类。

传统的DBSCAN聚类算法在检查点Eps邻域内点的数量时采用暴力遍历的方法，效率比较低下，在区域内点的数量较多时严重影响运行速度。kd-tree是一种用于对多维空间数据进行划分和存储的二叉树数据结构。本文先对区域内的点建立kd-tree，并利用最高优先级的思想结合DFS深度优先搜索实现kd-tree内的最近邻查询，来加速DBSCAN算法的Eps鄰域检查。

3.2分区参数确定

为了使分解边界更加清晰，同时为了能自适应确定DBSCAN算法的Eps邻域半径和Minpts最小点集两个参数，减小人为选择参数对聚类结果的影响，依据k-dist图的思想，对模型内的点进行分区。以投票矩阵M作为分区依据，不论投票方向，将能投票到同一采样平面的点分在同一区，同一个点可以被允许存在于多个不同的分区中。对每一个分区，利用kd-tree快速计算分区内每个点与其第k近邻点之间的距离。区域内的点都是三维坐标点，k值取比维度高1，k=4，按距离由小到大的顺序对分区内的点进行排序。以排序后的点的序号为横坐标，点到第k近邻点之间的距离为纵坐标，画出k-dist图，如图5所示。从图可知，大部分点的第k近邻距离都比较接近，小部分点的第k近邻距离较大。利用4阶多项式（2）对k-dist图进行曲线拟合，利用式（3）计算二阶导数并获得曲线（x0， f （x0））拐点（x0， f （x0））。将 f （x0）作为该分区的Eps邻域半径，k值作为Minpts的值。

（2）

（3）

3.3  对模型内点聚类分解

使用上述改进DBSCAN算法对点进行聚类。基于贪心思想，为了获得尽可能少的分解结果，将核心点能投票的最远采样平面规定为参考平面，对应的投票方向为参考方向，目的是为了让聚类生成的金字塔形状拥有尽量大的高度。考察所有与核心点密度可达的点，将能够以参考方向投票给参考平面的点加入聚类，目的是获得尽量大的连通区域，将尽量多连通且能与参考平面构成金字塔形状的点加入聚类。具体步骤如下：

（1）遍历模型内的点，依据点能投票的最远参考平面获取对应分区的Eps和Minpts，并利用kd-tree判断当前点是否为核心点。发现一个核心点P后，建立一个新的簇C。并将点P标记为已处理。否则标记为噪声点。

（2）通过投票矩阵，检索投票矩阵中点P对于列的第n+2行的值，获取点P能投票的最远采样平面和对应的采样方向。作为当前聚类的采样参考平面和采样参考方向，分别设为平面D和方向O（P）。

（3）遍历点P的Eps邻域中的点，将所有能以方向O（P）投票给平面D的点加入簇C。

（4）考察簇C中除点P以外的点，通过kd-tree判断是否为核心点。若为核心点，则将该核心点Eps邻域内能以方向O（P）投票给平面D的点加入簇C，同时将该点标记为已处理。若为噪声点，则只标记为已处理。

（5）重复步骤（4），直到簇C内所有点都被考察且簇C不再扩展为止。此时簇C便是一个近似金字塔形状的聚类块。

（6）重复步骤（1）至（5），直到所有点都被处理为止，完成聚类。

聚类流程如图6所示。

4  分解结果

对分别包含20 000、50 000、100 000个点的模型，分别对其进行传统DBSCAN聚类、kd-tree加速的DBSCAN聚类和10个分区的kd-tree加速DBSCAN分区聚类，计算聚类完成所用的时间。如表1所示。可见经kd-tree加速的DBSCAN聚类算法能大幅加速聚类过程。分区聚类的聚类时间相比直接聚类有所增长，但也能自适应生成Eps和Minpts，免去了设定参数的步骤。

利用本方法对模型A、模型B进行近似金字塔形状分解，分解结果如图7～10所示。

相关聚类信息如表2所示。可以看到本方法能将模型垂直于打印方向的悬垂部分分解成块，且尽量使每一个块更大，来获得尽量少的分解结果，基本达到设计要求。

5  结  论

本文提出了一种用于STL模型的近似金字塔形状分解方法，目的是将STL模型分解成能够实现无支撑3D打印的部分。人为地在模型中划分出投票平面，将模型内的点依据投票平面进行分类，并使用kd-tree加速的DBSCAN聚类算法将各点聚类成块。实际结果表明，本方法能够将模型在一定方向上分割成可无支撑打印的部分，且尽量减少分割数量，基本达到设计要求。

本方法目前还存在分割结果受投票平面影响较大、各分割部分间边界不够平滑、分割数量依然可以优化等问题。后续工作将引入对模型表面的特征提取方法，合理划分投票平面；考虑使用Douglas Peucker算法对边界进行细化和拟合；建立一套评价方法，用于衡量分解数量是否尽可能少。进一步提升分解的质量。

参考文献：

[1] 王铮，赵东标.FDM五轴3D打印支撑消减算法研究 [J/OL].机械科学与技术：1-5（2022-05-17）.DOI：10.13433/j.cnki.

1003-8728.20200652.

[2] 张帆，肖述文，涂一文，等.多轴机械臂3D打印的运动-挤料协同控制方法 [J].机械设计与研究，2021，37（6）：141-147+154.

[3] YANG Y，CHAI S，FU X M. Computing interior support-free structure via hollow-to-fill construction [J]. Computers & Graphics，2017，70：148-156.

[4] 黄常标，刘斌，江开勇，等.基于边界分割的STL模型三维分段 [J].机械科学与技术，2014，33（6）：870-874.

[5] HERHOLZ P，MATUSIK W，ALEXA M. App-roximating Free-form Geometry with Height Fields for Manufacturing [J].Computer Graphics Forum，2015，34（2）：239-251.

[6] 易兵，刘振宇，谭建荣.基于高斯映射的CAD网格法向聚类分割方法[J].机械工程学报，2015，51（7）：115-123.

[7] WEI X，QIU S，ZHU L，et al. Toward support-free 3d printing：a skeletal approach for partitioning models [J].IEEE Trans Vis Comput Graph，2017，24（10）：2799-2812.

[8] FEKETE S P，MITCHELL J S B. Terrain decomposition and layered manufacturing [J].Int J Comput Geom Appl，2001，11（6）：647-668.

作者简介：周钰琛（1996—），男，仫佬族，广西柳州人，硕士研究生，主要研究方向：嵌入式系统设计与集成；彭勇（1964—），男，汉族，江苏南京人，硕士，副教授，主要研究方向：嵌入式系统设计与集成。

收稿日期：2022-10-27