点云特征型面的边界曲线拟合及曲面裁剪算法

陈华伟，袁小翠，伍 权，徐卫平

（1.贵州师范大学机电工程学院，贵州 贵阳 550025；2.南昌工程学院江西省精密驱动与控制重点实验室，江西 南昌 330099）

1 引言

对机械零件点云模型而言，经过分割的分片点云是零件模型表面特征型面的点云表达，对分片点云进行样条或NURBS等曲面拟合可以获得对应的曲面表达，从而为CAD软件所识别。分片点云是零件表面的特征型面，其曲面重构过程主要包括曲面拟合和边界裁剪两个过程，其中拟合曲面是特征型面的依托面，裁剪边界是特征型面的边界。曲面裁剪算法很多，但快速而准确的曲面裁剪是一个难点问题，很多商业软件中的裁剪算法仍然是商业机密[1]。算法研究上，文献[2]针对N边域问题，采用在域周围曲面上构造曲线，对周围曲面进行裁剪获得大四边域，对大四边域曲面进行重采样和曲面逼近，再对其进行裁剪得到裁剪曲面，该方法能保持各曲面间的G1连续；文献[1]使用参数变换和开花（Blossoming）工具对多项式曲面展开多项式曲线裁剪，通过区域分割，该算法能对复杂曲面进行裁剪；文献[3]将B样条曲面转换为阵列式T样条曲面，然后利用局部细分和控制点移除法得到裁剪曲面；文献[4]使用OpenGL实现了NURBS曲面裁剪算法，该算法只考虑了简单曲面；文献[5]通过UG二次开发实现了点云曲面拟合和边界裁剪算法，并对汽车顶盖模型进行了测试验证。对点云逆向建模应用而言，存在复杂曲面复杂边界，曲面裁剪应更多地考虑点云曲面重构和边界提取问题，而且，对于特征显著的机械零件曲面，还应优先考虑特征保留问题。

对此，将以机械零件模型的典型型面为研究对象，展开曲面裁剪方法研究，并重点研究裁剪边界的提取算法。边界裁剪法的输入是待裁剪曲面及其裁剪边界，在逆向建模中，两者均以点云型面为输入，通过几何拟合构造。研究思路，如图1所示。

图1 曲面边界裁剪的思路Fig.1 Flowchart of Surface Boundary Trimming

点云型面是特征型面的点云表达，其边界提取需经过边界点识别、边界点排序和边界点拟合三个步骤。拟采用文献[6]的场力法识别分片点云边界，但是场力法所提取的边界点是无序点，需要进行排序才便于曲线拟合。有界曲面的边界为闭合曲线，而复杂闭合曲线难以通过整体逼近获取，对此，拟采用分段拟合和拼接方式加以解决。提取边界线之后，即可进行曲面裁剪。

2 预处理

边界线提取是曲面裁剪的前提条件，点云边界提取质量直接影响曲面裁剪的效果。经过识别的边界点，构成了特征边界的线状点云表达，为获得高质量的点云边界，还需要经过去噪、排序、分段、拟合、拼接等多个步骤。

边界线进行提取之前应对边界点云进行去噪、排序等预处理操作，其目的是消减边界点识别中的误差，为边界线提取提供更好的线状点云质量。

2.1 近点移除

近点是指距离非常靠近的点，通常情况下，点云导入时只对重复点进行过滤，但不会过滤近点。大量近点的存在会降低点云处理效率甚至导致错误，线状点云处理中，近点的存在不仅降低了点云处理速度，还会导致后续排序、去噪、曲率计算、分段等功能出错，因此，必须事先去除近点。

设定距离值在距离误差ε范围内的点为近点，然后采用先标记后删除的方法删除近点。具体做法是：构造点云邻域，遍历每个点，计算邻域点至当前点的距离d，如果d<ε，则将邻域点标记为近点。遍历结束后，再一次性删除所有近点。

2.2 点云排序

采用最短距离法对无序边界点进行排序，并通过对边界点集构造邻域结构，限定在邻域内搜索最短距离点，从而提高点云排序搜索效率。

任选一点Pstart=P0∈V为排序起点，V为边界点集，置P0为当前点，其邻域记为Neib0，遍历Neib0内所以节点，将与P0距离最近的点作为下一排序点，记为P1。置P0=P1，Neib0=Neib1，重复上述过程。记排序后的有序点集为V′，直至V中的所有元素进入V′。考虑到曲面裁剪对闭合边界的要求，上述搜索排序完成后，还需追加Pstart至V′，即可保证有序点集V′表达了闭合边界。

2.3 去噪

线状点云排序后，在排序路径上，会出现一些锯齿尖点，如图2中的点3，这类点是边界点的噪声点。显然，噪声点直接影响线状点云曲率估算和曲线拟合的精度，应进行去除。尖点处边界方向会出现折回现象，因此可通过对边界方向连续性判断标记出边界尖点。程序实现中，使用方向夹角Ai的范围T进行限定，当Ai>T时，判定当前点Pi为噪声点，予以删除，具体实现见EdgePtDenoise函数。

图2 排序边界点集中的噪声Fig.2 Noise in the Point Cloud of Sorted Boundary

同时，噪声中尖点的存在，还会导致边界线的自交，如图3所示。在曲面裁剪算法中，自交边界是非法边界，将导致曲面裁剪失败。为此，采用修改方向夹角阈值T，多次调用去噪算法的方法规避这一问题。T<90°表示允许边界线中出现钝角，这也表示边界线只能为凸曲线；T=90°表示允许边界线中出现直角；T>90°表示允许边界线中出现锐角，即边界线中允许出现凹曲线，用户操作时，应根据当前点云边界的特点，设定合适的不同的T值，多次调用EdgePtDenoise函数，从而达到边界点集去噪的最佳效果，如图3所示。

图3 边界线的自交与多次去噪Fig.3 Self Intersection of Boundaries and Multi-step Denoising

3 曲线分段和拟合

曲线拟合中，控制点数难以确定，整体逼近或者拟合时，甚至出现奇异值致使曲线变形和打结，从而导致曲面无法裁剪。为了更准确地描述边界曲线，提高边界点拟合精度，应分段拟合边界线，然后拼接形成完整闭合边界曲线。曲线上的特征点是分段曲线的连接点，如果能够准确找到边界特征点，就能实现边界分段。

3.1 边界点集曲率估算

曲线在特征点处分段，特征点附近曲线会发生曲率突变。因此，进行边界点集分段的前提就是点集曲率的计算。采用多项式曲线拟合法估算离散点曲率，算法主要步骤为：

（1）构造邻域结构Neib。对排序点集，每个节点前和后各取k/2个点作为其邻域点，k为邻域点数量；

（2）对每个节点i，在对应邻域Neibi内拟合最小二乘平面PLi；

（3）Neibi内所有点向PLi投影得到投影点集

（5）多项式函数曲线在节点i处的曲率值作为节点i的曲率，其计算公式为

接下来，将提取曲率突变点。对所有节点曲率进行降序排列，设定突变点比例数r，将前N×（rN为节点数）个高曲率值对应的节点标记为曲率突变点。

3.2 边界分段与拟合

以曲率突变点为备选特征点，通过对突变点的左右曲线归属判断，去除伪特征点，最终在相邻曲线间保留一个特征点作为分段点。显然，分段点应该是距两曲线距离和最小的点，以此为准则提取曲线分段特征点，算法伪代码列于EdgePtSegment函数，该算法依次调用Preprocess、Compute和Postprocess子函数，分别为曲线分段的预处理、分段计算和后置处理三个部分，其中子函数内容以注释形式加以说明。

排序点集，如图4所示。其中点5可经过去噪处理去除，如果不做去噪处理，则会作为曲率突变点进入分段处理。点集［0，1，2］、［7，8，9］分别为左、右曲线点，中间点集［3，4，5，6］为备选分段点，点2为左曲线末点，其切向线为LL，点7为右曲线首点，其切向线为LR。通过计算中间点集中各点至LL和LR的垂直距离之和，可知点4具有最短距离值。点4作为左右曲线的特征分段点继续保留在中间点集，其左点3归入左曲线，右点5和6顺序归入右曲线。最终分段结果为左、右曲线点集分别为［0，1，2，3］、［5，6，7，8，9］。

图4 线性点集特征分段Fig.4 Feature Segmentation for Linear Point Cloud

分段后，对各分段点集分别拟合NURBS曲线，然后分段边界曲线进行C0拼接，形成闭合边界曲线。采用Piegl的NURBS曲线拟合和拼接算法[7]。

4 曲面裁剪

样条曲线、曲面均为双参数表示，分别记为 S（u，v）、C（u，v），但是两者的u，v参数是相互独立的，可通过投影计算，将C（u，v）投影至 S（u，v），从而获得 C 在 S上的投影曲线 C′，C′即为 S的裁剪曲线。具体做法是：（1）C的所有控制点P（ixi，yi，z）i向S投影，获得对应投影点；（2）置换 C 的所有控制点为新的控制点

曲面的裁剪和保留是由边界方向确定的，不失一般地，设定内、外边界分别为顺时针和逆时针方向，内外边界之间地曲面为保留曲面，其它部分曲面则予以裁剪。无孔洞的曲面只有外边界，无内边界。由于边界裁剪曲线C′的方向并未事先规定，因此应对其方向进行判定，对不符合方向规定的进行反向操作。

二维（u，v）点集的方向判断可直接使用多边形法，算法代码可参考文献[8]。该算法沿用三维点叉乘法，对二维点进行叉乘操作，统计叉乘结果符号，结果为正，则判定边界方向为逆时针，否则为顺时针。该算法适用于这里时，还需要注意以下两个问题：（1）直线段边界点集的叉乘结果趋于0，对方向判断无贡献。闭合边界的方向性并不由直线边界决定，因此，只需要对叉乘结果在0值误差范围内的共线点集予以过滤即可。（2）多边形法在点集为凸包时有效，但是如果点集中大部分分段为凹包点，则会导致判断错误。观察到特征点构成的多边形方向直接反映了边界的凸包性，代表了边界方向，因此以特征点集替换整体边界点集，既可规避局部噪声对凸包性的影响，又可最大程度上减少整体点集对边界方向判断的错误。如前述，对曲面进行外边界裁剪时，如果曲线为顺时针方向，则应对曲线进行反向。反向算法参考文献[7]，该算法的核心是对节点和控制点进行反向。

5 实验

在VC和OpenGL开发环境下开发实现了上述算法，其中NURBS曲线拟合、拼接、反向等算法均通过集成nurbs++开源算法库实现。NURBS曲线拟合算法中控制点数太少，曲线拟合误差大，控制点太多，在边界点集不光滑的情况下，易致曲线出现锯齿形状，为了保证曲线拟合的效果，算法将控制点数设置为输入点集数的1/3。模型实验中，固定或交互设定算法参数，其中距离误差ε=0.001，曲率突变比例r=0.1，即边界点集中10%的节点为曲率突变点，方向夹角阈值T根据边界点集特点设定。

以fandisk模型的顶面为例进行说明，如图5所示。该面的拟合面为平面，点云分割和面拟合在文献[9-10]中已有详细论述，此处不再赘述。经分割后的部分点云特征面，如图5（b）所示。提取的顶面点云边界，如图5（c）所示。点云边界排序后可串联为多边形边界，最短距离法进行边界点排序，能过滤部分离群点，但还是因非离群噪声点的存在而形成锯齿形边界，必须经过去噪处理后锯齿现象才能得到很好的去除。图5（d），图5（e）中非边界多边形上的点为离群点，边界多边形的1、2、3处分别给出了放大图，从中可以看到去噪前后的对比效果。图5（f）矩形框中的节点是从曲率突变点中识别的边界线特征点，该图也表达了边界分段的效果。图 5（g）中，1、4、6 分段处为凹曲线，3、5 分段处为直线段，只有2处为凸曲线段，为了规避密集点集的凹凸不确定性，采用边界特征点进行曲线方向的判断，图5（h）标号处为用于曲线方向判断的主要边界特征点。在获得满意的边界特征线之后，即可对拟合面进行裁剪，图5（i）显示了fandisk顶面的裁剪结果。根据以上算法，完成了对fandisk模型的主要特征型面边界的识别、分段拟合和曲面裁剪，如图 5（j）～图 5（l）所示。

图5 算法实例Fig.5 Case Study of the Algorithm

文献[5]给出的汽车顶盖曲面拟合和裁剪实例，如图6所示。该曲面只需要一个四边域即可裁剪车顶曲面（中间的曲面）。文献[4]也只是给出了简单边界圆形边界的裁剪实例。相比之下，fandisk实例点云曲面多且复杂，曲面边界凹凸不平，裁剪算法适应性更强。

图6 文献[5]中的实例Fig.6 Case Study in Literature[5]

6 结论

对边界点集进行预处理和分段拟合，可获得高质量的边界曲线，从而获得良好的曲面裁剪效果，论文通过算法和实例研究验证了这一思路。针对机械零件的复杂边界，应以特征识别为核心，重点识别边界线上的特征点，才能很好地进行边界线分段和拟合。拟合边界线的方向性也是曲面裁剪的一个关键，以特征点集替代整体点集进行方向判断的方法也取得了预想的结果。从图5（i）所示的裁剪结果看，曲面边界还是存在不光滑的现象，这是由于边界线未做平滑处理。从原理上看，前述算法同样适用于非平面曲面、多孔洞曲面等更复杂曲面的裁剪，这也是论文的下一步研究工作。