曲面特征恢复的三角网格模型孔洞修补算法

贺 强，张树生，白晓亮

(西北工业大学 现代设计与集成制造教育部重点实验室，710072 西安，hqcq@mail.nwpu.edu.cn)

曲面特征恢复的三角网格模型孔洞修补算法

贺 强，张树生，白晓亮

(西北工业大学 现代设计与集成制造教育部重点实验室，710072 西安，hqcq@mail.nwpu.edu.cn)

为了恢复三角网格模型中的孔洞处的真实形状，提出一种曲面特征恢复的孔洞修补算法.首先对模型中检测出的孔洞进行三角化并细分，完成孔洞的粗修复.然后利用高斯球确定孔洞的邻域及其曲面类型，对二次曲面类型的孔洞邻域进行非线性最小二乘拟合以获得曲面代数方程，对自由曲面类型的孔洞邻域则进行B样条曲面拟合.最后根据孔洞邻域的曲面方程获得孔洞内新增顶点在曲面上的精确位置，完成孔洞修复.实验结果表明，该孔洞修补算法不仅能完成孔洞区域的三角形填充，还能准确恢复出孔洞区域的曲面特征.

高斯球;孔洞邻域;曲面特征;孔洞修补

由于物体表面的反射属性、结构闭塞等因素的影响，测量获得的三角网格模型中不可避免地存在孔洞.孔洞不仅影响模型的外观，而且不利于后续的几何处理.为了获得完整的网格模型，孔洞修补尤为关键.经过大量研究，出现了基于网格和基于体数据2类具有代表性的孔洞修补算法.基于网格的修补算法［1－8］首先寻找网格模型中的孔洞，然后对孔洞进行三角化并细分，最后对新增的网格顶点的位置进行光顺调整.基于网格的修补仅仅作用在孔洞及其邻域，可以保持远离孔洞区域的网格结构不变，修补后孔洞区域能与周围区域光滑融合，但这类算法对输入的模型有一定的质量要求且没有或较少考虑孔洞处的曲面信息，常常丢失孔洞处的曲面特征.基于体数据的网格修补算法［9－12］首先将网格模型转换为一种中间的体数据来表示，然后在体数据上进行修补操作.这类算法在处理三角面片自相交和重合的情况时比基于网格的算法更具优势，并能保证修复后输出的网格是封闭的，但输出的网格完全改变了原有模型中的连接关系，从而导致模型特征的丢失并会产生大量的、狭长的三角片.

上述算法较少或基本没有考虑孔洞处的曲面特征，因而在对含有大量二次曲面的工业产品外形上的孔洞进行修补时，虽然可以得到完整且光顺的模型，但同时会丢失孔洞处的曲面特征.为了恢复孔洞处的真实形状，本文提出一种曲面的特征恢复的孔洞修补算法.首先对模型中检测出的孔洞进行粗修复，然后利用高斯球确定孔洞邻域及其曲面类型，最后根据孔洞邻域的曲面信息对孔洞内新增顶点的空间位置进行调整，获得精确的修复结果.

1 孔洞的粗修复

对三角网格模型中检测出的孔洞，直接进行三角化处理，并根据孔洞周围网格的平均边长对孔洞区域内新增的三角形进行细分，这个过程称为孔洞的粗修复.

1.1 孔洞的识别

三角形网格模型是由一系列顶点和三角形构成.2个相邻三角形通常有1条公共边，称这样的边为网格的内部边，而网格模型中的边界边和孔洞边通常只属于1个三角形.根据这一性质，对封闭的网格模型，如果存在某条边仅属于1个三角形，则此边就是构成孔洞多边形的1条边.由这样的边首尾相连就形成了1个孔洞.对于非封闭模型，提取出的孔洞中还包括了模型的边界轮廓.一般而言，孔洞的边的数量都小于边界轮廓的边的数量.根据这一经验，对检测出的所有孔洞按照边数量排序，不修补边数量最大的孔洞.对于特殊情况，则需要用户交互选择模型轮廓，并将其从孔洞集合中剔除.

1.2 孔洞的三角化和细分

对孔洞多边形使用Delaunay方法直接三角化，完成孔洞区域的拓扑填充.对面积较大的孔洞，获得的修复网格与原始孔洞周围的网格的采样密度差异较大，这不仅影响了视觉效果而且破坏了孔洞区域及其邻域的拓扑一致性.为了获得与孔洞邻域网格密度相近的网格分布，本文对新增的三角形的边进行细分.细分的原理是首先计算孔洞周围(选择孔洞周围网格6～10层)三角形边长的平均值，然后检测孔洞内新增三角形的三边长，如果某边边长超过平均值，则将该边从中点处分裂，边分裂过程如图1所示.

图1 边分裂

图2表示了孔洞的粗修复过程.其中图2(a)是含有孔洞的三角网格模型，图2(b)是采用Delaunay三角化的结果，图2(c)是细分光顺的结果.

图2 孔洞的粗修复

2 孔洞邻域及其曲面特征

为了使孔洞修补的结果能较好逼近孔洞处的真实曲面，利用孔洞周围的网格(即确定孔洞的邻域)尤为关键.物体的外形通常都由大量的二次曲面和少量的自由曲面构成.在工业领域，这种情况尤为突出.鉴于高斯球［13－14］可以很好地识别二次曲面，本文利用三角网格模型良好的拓扑连接关系，向孔洞的周围逐层扩展，同时利用高斯球识别出扩展部分的曲面类型，并将曲面类型不一致的顶点剔除.孔洞邻域就是剩余的与孔洞处曲面类型一致的顶点的集合.

2.1 网格顶点的高斯映射

在完成孔洞的粗修复后，向孔洞周围扩展6～10层三角形，获得初步的孔洞邻域点集.高斯映射是将曲面上任意一点的单位法矢的起点移动到坐标原点的过程.曲面上的点进行高斯映射后所得的结果是单位球内的一个点集.这个单位球就是高斯球.由高斯映射的定义可知，网格顶点的法矢量即为其在高斯球上的坐标.

2.1.1 平面的高斯球

平面点的法矢量均相等，因此平面的高斯球应该是一个点，但实际应用中，由于法矢估算不准确或噪声等原因，平面网格在高斯映射后的点会聚集在一个点区域中，如图3(a)所示.

2.1.2 圆柱面的高斯球

圆柱面上任意点的法向量都应该与其轴线的单位矢量n垂直，因此圆柱面上任意一点的高斯球坐标都在过原点且法向为n的平面上，该平面可以表示为(n，0).实际应用中，圆柱面类型的网格顶点在高斯映射后的点集近似地聚集在一个环状区域而不是严格位于同一平面，如图3(b)所示.该区域可以被最小二乘法拟合成一张平面(n*，d)，d近似为0.

2.1.3 圆锥面的高斯球

圆锥上任意一点的法矢与轴线方向n的夹角与圆锥角的1/2 α互余.因此圆锥上任意点的高斯球坐标构成平面(n，sin α).由于网格噪声等原因，实际的圆锥网格高斯映射后的点集近似地聚集在一个环状区域而不是严格位于同一平面，如图3(c)所示.该区域可以被拟合成平面(n*，d).

2.1.4 球面的高斯球

球面上任意点的法向各不相同，因此球面上的点的高斯球坐标各不相同，如图3(d)所示.球面上各个点及其法矢量构成的直线之间的交点理论上应该都在球心处，而对实际应用中的球面网格则是在包含球心的一个点区域中，与平面的高斯映射类似.本文根据这个性质来识别球面.

图3 二次曲面的高斯球

2.2 孔洞邻域的确定

对初步的孔洞邻域点集进行高斯映射后，利用高斯球就可以对其进行精炼，进而得到孔洞邻域的曲面类型和邻域点集，孔洞邻域及其曲面类型的确定过程为:

HN为初步的孔洞邻域点集，其高斯球坐标形成的点集为C，建立两者之间一一对应的索引关系.首先利用通用点聚类法判断HN是否为平面，该过程为:计算C的中心点Pc，然后计算C中每一个点与Pc的距离，如果该距离小于给定的阈值，则保留该点，否则抛弃该点.完成上述操作后，减小阈值，递归调用上述过程，直至C中的所有点到Pc的距离都小于给定的全局阈值或迭代次数达到设定的上限.此时若C中点的数量与HN中点的数量之比大于设定的有效点集率，则HN是1个平面区域.

如果平面判定失败，则依次进行圆柱面、圆锥面的判定.此时需要判断C是否处于一块有效的平面区域，利用通用平面聚类法完成平面区域的判定.该过程为:对C中的点行最小二乘平面拟合，得到一个中心平面Pp.计算C中的点到平面Pp的距离，如果该距离小于给定的阈值，则保留该点，反之删除该点.完成上述操作后，减小阈值，递归调用上述过程，直至C中的所有点到Pp的距离都小于给定的全局阈值或迭代次数达到设定的上限.根据C中剩下的点，利用建立的索引关系，就可以得到HN中与孔洞区域曲面类型一致的顶点集合，即孔洞的邻域.

以上曲面判定都失败后，还需对HN进行球面的判定.利用HN中的顶点和C中的法矢量确定的直线的交点来判定球面.若是球面类型的网格，这些直线会相交于球心附近，形成一个点区域，对该点区域进行通用点集聚类即可确定孔洞的邻域.

若以上曲面类型的判定都失败，本文将这样的孔洞邻域归为自由曲面类型.孔洞邻域则为扩展部分的所有顶点.

2.3 孔洞邻域的曲面拟合

对平面孔洞，无需拟合平面(因为三角化后细分新增的顶点还是在平面上).对球面、圆柱面、圆锥面孔洞，则根据孔洞的邻域，使用非线性最小二乘拟合获得孔洞邻域的代数方程.该方程作为孔洞内新增顶点位置调整的依据;若孔洞邻域是自由曲面类型，本文采用文献［15］中的双三次B样条曲面拟合算法来确定孔洞邻域的潜在曲面.

球面的代数方为

式中:r为半径;(x0，y0，z0)为球心，是待求的参数.

圆柱面的代数方程为

式中:(x0，y0，z0)为待求的圆柱轴线上任意一点;(nx，ny，nz)为待求的圆柱的轴线方向;r为待求的截面圆的半径.

圆锥面的代数方程为

式中:α为待求的圆锥角的1/2;(x0，y0，z0)为待求的圆锥的顶点;(nx，ny，nz)为待求轴线方向.

本文采用 Levenberg-Marquardt［16］算法求解曲面方程中的待求参数.设:F(x)为二次曲面的代数方程;x={x1，x2，…，xn}为待求参数组成的向量.对曲面方程中待求参数进行泰勒展开得

设xk为第k次迭代获得的待求参数向量.该求解过程为

式中:δ为x中参数的偏差;J为m×n阶雅可比矩阵;m为孔洞邻域点的数量;μ＞0为用户设定的参数，初始设为 10－6.

上述过程首先需要设定待求参数即x0的初始估计值.对球面拟合，球心的初值设为孔洞邻域内任意2点和其法矢量构成的直线的交点，半径初值为其中1点到该交点的距离.对圆柱面拟合，利用任意2点及其法矢量，根据法矢量与轴线垂直的性质就可估算轴线，其中一点到轴线的距离即为半径.对圆锥面拟合，选择不在同一平面的3点及其法矢量，利用法矢量与轴线的夹角为圆锥角的1/2这个性质就可计算半径、轴线方向、圆锥角、圆锥顶点.

3 孔洞内新增顶点的位置调整

由孔洞粗修复产生的新增顶点，如果孔洞邻域曲面类型是平面，则无需进一步处理，修补完成.若是球面、圆柱面和锥面中的任何一种，则需要利用过程2中获得的代数方程计算新增顶点在曲面上的真实空间位置.对新增顶点pi=(xi，yi，zi)，其法矢量n=(nx，ny，nz)，得到过该点且方向为法矢量的直线方程为

式(6)与孔洞邻域曲面代数方程联立求解就得到孔洞内的新增点的空间坐标.若孔洞邻域是自由曲面类型，本文采用文献［15］的网格参数化算法对粗修复的网格进行参数化，获得孔洞处填充的顶点的参数值，再将参数值带入由孔洞邻域拟合得到的B样条曲面方程中就获得了孔洞处新增顶点的空间位置.

4 实验结果

在VS2005的环境下实现了算法，在主频1.8 G，内存512 M的PC机上运行程序，且采用VTK(Visualization Toolkit一个面向对象的可视化类库)显示孔洞模型及其修补结果.为了更好地说明孔洞修补过程，本文以图4的球面孔洞为例详述其修补过程.图4(a)是原始的球面孔洞模型，其真实球心坐标为(0，0，0)，半径为 8 mm.图4(b)是孔洞粗修复的结果即完成了孔洞多边形的三角化和细分.对孔洞邻域进行拟合得到的球心为(－0.000 422，0.000 116，－0.000 208)，半径为7.999 997 mm，与真实情况的差异非常小，因此利用拟合的结果能精确恢复孔洞处的曲面特征，如图4(c)所示.图5是圆锥面孔洞的修复，图6是自由曲面孔洞的修复，图7是多种曲面类型孔洞的修复.从多种曲面类型孔洞的修补实验可知，除了平面类型的孔洞，孔洞粗修复后产生的新顶点都偏离了其在曲面上的真实位置，而采用本文算法处理后，能精确地恢复孔洞处的曲面特征.

图4 球面孔洞及其修复

图5 圆锥面孔洞及其修复

图6 自由曲面孔洞及其修复

图7 机械零件模型中的孔洞及其修复

5 结论

1)通过提取孔洞多边形，孔洞三角化和细分完成了孔洞区域的拓扑填充.

2)利用高斯映射确定了孔洞邻域及其曲面类型，并利用非线性最小二乘拟合得到相关的曲面参数.

3)利用孔洞邻域的曲面信息，完成了孔洞区域曲面特征恢复的修补，实验结果证明了算法的有效性.

［1］LIEPA P.Filling holes in meshes［C］//Proceedings of Eurographics/ACM SIGGRAPH symposium on Geometry processing. Switzerland:Eurographics Association，2003:200－205.

［2］CHUI C，LAI M J.Filling polygonal holes using C1 cubic triangular spline patches［J］.Computer Aided Geometry Design，2000，17(4):297 －307.

［3］BRANCH J，PRIETO F，BOULANGER P.Automatic Hole-Filling of triangular mesh using local radial basis function［C］//Proceedings of the third International Symposium on 3D Data Processing，Visualization and Transmission.Washington，NC:IEEE，2006:727 －734.

［4］TEKUMALLA L S，COHEN E.A Hole-Filling Algorithm for Triangular Meshes［M］.USA:Technical Report UUCS-04-019，School of Computing University of Utah，2004.

［5］PERNOT J P，MORARU G，VERON P.Filling holes in meshes using a mechanical model to simulate the curvature variation minimization［J］.Computer ＆ Graphics，2006，30(6):892－902.

［6］JUN Y.A piecewise hole filling algorithm in reverse engineering［J］.Computer-Aided Design，2005，37(2):263－270.

［7］张丽艳，周儒荣，周来水.三角网格模型孔洞修补算法研究［J］.应用科学学报，2002，20(3):221－224.

［8］张洁，岳玮宁，王楠，等.三角网格模型的各向异性孔洞修补算法［J］.计算机辅助设计与图形学学报，2007，19(7):893 －897.

［9］DAVIS J，MARSCHNER S R，GARR M，et al.Filling holes in complex surfaces using volumetric diffusion［C］//Proceedings of First International Symposium on 3D Data Processing，Visualization and Transmission.Washington，NC:IEEE，2002:428－438.

［10］NOORUDDIN F S，TURK G.Simplification and repair of polygonal models using volumetric techniques［J］.IEEE Transactions on Visualization and Computer Graphics，2003，9(2):191 －205.

［11］JU T.Robust repair of polygonal models［J］.ACM Transaction on Graphics，2004，23(3):888 －895.

［12］BISCHOFF S，PAVIC D，KOBBELT L.Automatic restoration of polygon models［J］.ACM Transaction on Graphics，2005，24(4):1332－1352.

［14］丁展，陈志杨，张三元，等.基于Gauss Ball的二次曲面细分解与识别［J］.计算机辅助设计与图形学学报，2007，1(19):31－36.

［15］白晓亮.逆向工程中混合CSG/B－rep模型重构技术研究［D］.西安:西北工业大学，2005.

［16］MADSEN K，NIELSEN H B.Method for Non-Linear Least Squares Problems［M］.Copenhagen:Technical University of Denmark，1999.

A hole repairing algorithm based on surface feature recovery in triangular mesh model

HE Qiang，ZHANG Shu-sheng，BAI Xiao-liang

(The Key Laboratory of Contemporary Design and Integrated Manufacturing Technology，Ministry of Education China，Northwestern Polytechnical University，710072 Xi’an，China，hqcq@mail.nwpu.edu.cn)

In order to recover original shape of the holes in triangular meshes，a hole-repairing algorithm based on surface feature was proposed.First，the hole triangulation and subdivision were performed as coarse filling.Then，gauss ball was used to determine the hole neighbors and their surface types.Quadric surface equations were fixed by non linear least square.The hole neighbors of freeform were fitted by B spline surfaces.Finally，accurate positions of vertexes were acquired according to surface equations of the hole neighbors and the holerepairing was completed.The experimental results show that the presented hole repairing algorithm can not only fill the holes but also recover surface feature in the hole regions.

gauss ball;hole-neighbor;surface feature;hole-repairing

TP391

A

0367－6234(2011)11－0120－05

2010－01－10.

国家高技术研究发展计划资助项目(2007AA04Z137);

国家自然科学基金资助项目(60573177).

贺 强(1985—)，男，博士研究生;

张树生(1956—)，男，教授，博士生导师.

(编辑 张 红)