基于二分法的3D打印切片数据精简

潘成钢，吴婷，陈廷豪，吴建，包涵，吴广庆

（嘉兴学院 机电工程学院，浙江 嘉兴 314001）

0 引言

3D打印技术出现于20世纪90年代中期，也称快速成型技术，可通过逐层打印高效地将数字化的三维模型构造成具体物体。3D打印将传统的减材制造模式转变为增材制造模式，不仅完全打破了物体结构复杂性的限制，也促进了个性化服务与生产社会化的发展，更加推动了3D数字化相关技术的发展与创新[1]，被广泛应用于工业设计、汽车、航空航天和医疗等领域[2]。

目前，3D打印处理的主流对象模型是STL三角网格模型，由于STL模型表面由大量三角面片组成，这些三角面片会导致模型的各层切片轮廓产生许多微小线段，大量的微小线段不仅会占用较大的存储空间，也会造成打印喷头的不断振动，最终影响3D打印的效率和平稳性[3]。因此，在打印加工前需要对这些切片轮廓进行优化精简处理，以提高模型制造的效率和精度。

数据精简是一种剔除冗余信息的数据处理方法，其目的在于尽可能利用最少的数据点完整而准确地表达物体的原有信息，并在此基础上达到更高的运行效率[4]。传统数据精简的方法包括最大（小）距离法、弦高法、角度偏差法和曲率法等。目前，已有众多学者改进了现有的数据精简算法，取得了一定的研究成果。俞毅等[4]提出一种改进的角度偏差数据精简方法，该方法利用数据点的曲率变化，将角度阈值变成一个能随数据点曲率自动调整的函数，并联合最小距离法设定距离阈值，对大于阈值的数据点进行保留。吴凤和等[5]通过分析物体轮廓曲线的曲率变化，提出一种曲率弦高精简方法，该方法通过相邻数据点间的曲率比，建立变化的弦高阈值函数，从而更好地保留曲率较大位置处的特征点。李新等[6]改进了传统的角度弦高联合方法，该方法将扫描线上某个数据点的角度和弦高都小于阈值的点判断为冗余点，并在进行下一个数据点的判断时，重新计算该冗余点到新基准的角度和弦高，以进一步精判断，从而防止累计误差的产生。Liu等[7]提出离散曲率光顺的方法，通过分析二维点集离散曲率和一阶曲率差分的性质来识别缺陷点，并通过构造能量函数来修改缺陷点的几何位置。

本文在已有数据精简方法的基础上，提出基于二分迭代的角度弦高数据精简方法。该方法以曲线上数据点之间的角度和弦高为依据，通过二分迭代，确定所需要保留的数据点，以此加快数据精简的效率。

1 算法原理

1.1 传统角度弦高法

角度法与弦高法通过确立测量点的基线，求得测量点与基线的角度和垂直距离，来衡量相邻轮廓数据点的方向和曲率变化程度。如图1所示，在判定一条轮廓上某点Pi是否为冗余点时，将其与前后的两点Pi-1、Pi+1相连，组成一个三角形，计算点Pi到基线Pi-1Pi+1的高hi及角度αi，若hi和αi小于设定的阈值，则可将Pi视为冗余点。在判断下一个点Pi+1时，为避免产生累积误差，若Pi为冗余点，则除了计算点Pi+1的弦高hi+1_1和角度αi+1_1，还应计算冗余点Pi到新基线的弦高hi+1_2和角度αi+1_2，若这些值均小于阈值，则Pi+1才能被视为冗余点。

图1 传统角度弦高法基本原理

可以看出，这种方法在计算待测点的角度和弦高时，需要利用待测点前后的数据点，因此需要反复计算待测点和冗余点到基线的弦高与角度。对于3D打印工艺而言，这一方法的计算量大，不适应具有大量切片与复杂轮廓的数据精简。

1.2 二分法

二分法，也叫折半查找法，是一种在指定数据区间内查找指定元素的搜索算法。它通过不断对分数据区间，将不可能的解集排除在外，来得到满足误差条件的近似解[8]。假设函数f(x)在区间[a, b]内单调递增，若需要查找指定元素X，使得f(X)=Y，则首先将区间[a, b]进行对分，从[a, b]的中点c开始搜索，若f(c)=Y，则查找成功，即c=X；若f(c)＜Y，则在前半段的区间[a, c]里查找；若f(c)＞Y，则在后半段的区间[c, b]里查找，重复上述步骤，直到找到近似解为止。

1.3 本文方法

3D打印切片层数较多，因此对切片轮廓数据的精简不仅要考虑到算法的运行效率，也要考虑到阈值参数的方便设定。基于误差拟合的方法耗时较多，而基于曲率的方法，不同轮廓曲率阈值的设定较为困难。因此，根据切片轮廓数据分布特点和减少计算过程迭代次数的原则，本文提出一种将曲线的角度、弦高与二分法相结合的方法，即二分迭代的角度弦高精简方法。该方法将切片轮廓数据上若干个连续数据点作为一个簇，在这个簇中计算各数据点的角度与弦高，通过对簇的点数不断进行二分迭代来确定保留的数据点。

对于切片轮廓上排列有序的数据点集，如图2所示，以某一点Pi为基点，将数据点{Pi, Pi+1,…, Pi+w-1}作为一个簇，以PiP(i+w-1)为基线，计算簇内的每个点到基线PiPi+w-1的角度和弦高，求出这些角度和弦高的最大值αmax、hmax。若hmax和αmax均 小于阈值，则Pi和Pi+w-1为保留点，并以点Pi+w-1为基点，继续进行下一个簇的判断；若hmax和αmax有一个大于阈值，则将此簇的点个数w通过二分法重新聚类，即

图2 本文方法精简原理图

其中，[]为向上取整运算，然后对二分后的簇内数据点的角度和弦高重新进行计算。

本文方法的整个流程如图3所示。

图3 本文算法流程图

步骤1：读取切片轮廓数据{P1,P2, …,PN}，设定角度阈值Δα和弦高阈值Δh，以及每组簇的初始点个数w0。

步骤2：选取轮廓数据中的第一个数据点P1为起点，定义i的初始值i=1。

步骤3：判断i＞Nw0+1是否成立，若成立，则令w=N-i+1，否则，令w=w0。

步骤4：将数据点{Pi,Pi+1,…,Pi+w-1}作为一个簇，并将线段PiPi+w-1作为基线，计算簇内的每个点Pj（j=i+1,i+2, …,i+w-2）到基线的角度αj和弦高hj。

步骤5：计算角度的最大值αmax=max{αj}和弦高的最大值hmax=max{hj}。

步骤6：判断αmax＜Δα和hmax＜Δh是否同时成立，若成立，则Pi和Pi+w-1为保留点，该簇内的其余点为冗余点，并令i=i+w-1后，转步骤7；否则，令w=[w/2]后，转步骤4。

步骤7：判断是否满足条件i＜N，若满足，转步骤3；否则，该层切片轮廓线上的所有数据点均处理完毕，将所有保留的数据点作为精简后的数据输出。

2 实例验证

为验证本文算法的有效性，选取一梅花形状的切片轮廓进行精简测试。原始梅花轮廓数据点共有628个点，通过控制每组簇内点个数w0、角度阈值Δα和弦高阈值Δh，从精简率、重构曲线平均误差等指标来对简化结果进行评价。

在每组簇内点个数w0=20，不同角度阈值Δα和弦高阈值Δh的参数条件下，精简效果如图4所示。从精简后的曲线图可以发现，本文方法能够在高曲率变化处保留较多的数据点，而且在低曲率片段中也能保留较多细节的特征点，可见本文方法能够利用较少的离散点较好地表示复杂原有轮廓信息，总体结果疏密有秩，精简效果较好。另外可以发现，随着Δα和Δh的减小，精简后的数据点会不断增多。当Δα=5°、Δh=0.05时，精简率为76%，重构曲线平均误差为0.012；当Δα=2°、Δh=0.02时，精简率为58%，重构曲线平均误差为0.0032。因此，通过控制Δα和Δh的大小，可以控制精简结果。

图4 数据精简效果对比

图5显示了在Δα=5°、Δh=0.05的条件下，簇内点个数w0大小的变化对精简率和算法执行时间的影响。可以看出，当3≤w0≤10时，精简率呈上升趋势，当w0≥15，精简率结果趋于稳定；而算法耗时随w0的增大而增大。因此，在实际应用中，考虑到算法的执行效率，w0取值范围在10～20时较为合适。

图5 簇大小对精简率和耗时的影响

3 结论

本文提出基于二分法的数据精简方法，有效实现了3D打印切片轮廓的数据精简。该方法以曲线上相邻点之间的角度与弦高为依据，通过簇内点数的二分法迭代来确定需要保留的数据点，完成数据的精简工作。实验测试结果表明，该方法能够较高效且稳定地完成切片轮廓的数据精简，其结果疏密有致，精简效果较好。