CAD轻量化网格模型的特征识别

罗年猛，殷吉功，刘云华，朱 林

（华中科技大学 国家CAD支撑软件工程技术研究中心，湖北 武汉430074）

0 引 言

由于轻量化模型只有三角面片信息，缺乏几何特征信息，导致众多应用受到较大的限制，例如标注、测量、装配、工艺制作、模型重建等。为了解决上述问题，需要对轻量化模型进行特征识别。

目前国内外针对轻量化模型的特征识别已提出了很多算法，这些算法主要集中在2类模型上，一是通过三维测量点云构造的轻量化模型，它的特征识别算法有区域生长法、迭代聚类法、骨架抽取法、分水岭法、层次分解及合并法、谱分析法等，文献 ［1］中对各种分割算法进行了介绍；二是通过三维CAD转换的轻量化模型，它的特征识别算法有张量投票法［2］、 聚类法［3］、 分水岭法［4，5］、 混合方法［6，7］等。

针对CAD转换的轻量化模型，文献 ［3］通过把三角形划分为稀疏三角形和稠密三角形，针对这2部分分别运用不同的算法进行网格分割及特征识别。文献 ［4］改进了传统的分水岭分割算法，通过加点很好地解决了分水岭算法无法有效处理三角化不均匀的CAD网格模型的问题，并且支持过渡面的分割。文献 ［6］提出了一种特征的二次提取及表面分割混合算法，首先采用基于边的方法把平面和稀疏网格表面提取出来，然后采用基于顶点的方法，通过区域生长实现其它表面区域的分割及特征提取。文献 ［7］提出了一种方法能够自动识别CAD网格模型中的特征，该方法主要适用于包含自由曲面的钣金零件。文献 ［8］利用计算出来的曲率值及平面与二次曲面不同的性质逐类识别，并通过双三次B样条曲面拟合技术识别自由曲面。

本文针对CAD系统转换的轻量化模型中特征数据连续性的特点，提出一种新的快速特征识别算法。轻量化模型中特征数据的连续性是指组成一个特征的所有三角面片在轻量化文件中是连续分布的。由于CAD模型大部分是由平面和柱面、锥面、球面等二次曲面特征组成，所以本文首先对模型中的平面进行特征识别，再对被分割开的区域进行柱面、锥面、球面以及自由曲面的特征识别。该算法减少了三角面片的遍历次数，因此速度快、效果好。

1 算法概述

CAD轻量化网格模型由一个一个的特征组成，一个特征的所有三角形在轻量化文件中是连续的、线性的。轻量化文件可以看作以三角形为节点的链表，如图1所示。

轻量化文件也可以表示成

其中，S表示整个轻量化文件，Si、Sj（S1…Sn）表示轻量化文件中连续三角面片的组合，一个组合就是网格模型中的一个特征。在轻量化文件中一个特征最多只与前后两个特征相连，当在轻量化文件中准确识别其中一个特征后其它特征相应的也被准确的分割，由此可保证特征识别的准确性。

CAD系统导出的轻量化文件都可以作为本文的输入数据，文件格式可以是任何轻量化文件格式，如STL、STEP203、STEP214、X＿T等。图2中的模型是从Solidworks系统中导出的轻量化文件，文件格式为STL（ASCII形式），图中标示了轻量化文件和轻量化模型中的特征对应关系。

本文对导入的轻量化数据直接根据面片法向量和平均法向量进行平面识别，无需建立整体拓扑结构；然后根据高斯映射识别柱面和锥面特征；再对剩余的区域建立局部拓扑结构，利用最小二乘法进行分割；最后对分割后的区域根据高斯曲率识别球面特征。

2 特征识别算法

2.1 平面识别

在进行平面识别之前，先介绍以下基本概念及规则：

法向量F1：轻量化文件中的面片法向量；

法向量F2：根据三角面片的顶点计算出来的法向量，即平均法向量；

规则1：一个面片的F1向量与F2向量相等，误差在ε范围之内；

规则2：两三角面片F1向量相等，误差在ε范围之内；

规则3：两三角面片F2向量相等，误差在ε范围之内；

平面识别算法具体如下：

（1）从轻量化文件中的第一个面片开始，记录此面片为Previous，下一个面片为Current，依次遍历所有的面片；

（2）判断Previous面片是否满足规则1。若不满足转至（3）；否则把Previous面片归为平面区域Plane i，判断Previous与Current是否满足规则1、规则2和规则3。

1）如果满足，把Current面片归为Plane i；

2）否则，平面区域Plane i在Current面片处断开，到此一个平面特征识别完毕，继续查找下一个平面特征。

（3）若没有面片，算法结束；否则令Previous＝Current，继续下一个面片并记为Current，继续 （2）。

平面的识别是最简单的，也是最准确的。之前的文献对平面特征识别时只是利用规则2或者规则3进行识别，在CAD网格模型中不是很可靠。因为CAD模型中有很多的过渡特征，特别是机械模型，当平面与相对比较小的过渡圆角相连时，过渡线两侧的三角形法向量有可能相等（误差ε）。这种情况下识别出来的平面就没有严格的边界，实际上就是识别错误。而通过以上3条规则就可以很好地识别出来平面特征，保证有严格的边界。本文算法还可以区别多棱柱面和圆柱面，特别是当圆柱面剖分的精度比较粗糙时，剖分的结果和多棱柱三角化的结果完全一样，如图3所示。把面片1和面片2的法向量p1和p2单位化并平移到一点。当网格模型为多棱柱时，面片1和面片2的法向量关系为图 （a），即重合；当网格模型为圆柱时，面片1和面片2的法向量关系为图 （b）。由此即可分割棱柱面和圆柱面。

图3 圆柱和多棱柱中面片法向量比较图：左侧图形为多棱柱及圆柱三角化后的模型，其中多棱柱时面片1和面片2在一个侧面上，图 （a）和图 （b）为多棱柱和圆柱时面片1和面片2的法向量平移到一点的结果

这样把平面识别出来，平面的识别过程实际上也是分割其它区域的过程，同样把轻量化文件分割开。平面识别出来后其它区域就是不同的特征区域，或者是不同特征区域的组合。

2.2 柱面和锥面特征识别

对被平面特征识别后分割开的各个子区域分别进行柱面特征识别，识别柱面采用高斯映射的方法。把单个子区域三角形的面片法向量移动到原点，然后由原点和2个法向量的终点组成小三角形，这样依次进行，最终形成新的三角面片特征。在这些形成的新三角特征中按0中的算法查找平面特征，不同的是判断条件只有2个面片的平均法向量。这些平面特征中组成三角形的2个顶点 （3个点中除了原点）就是柱面特征的一部分。这样得到的一个平面特征就是原模型中的柱面特征。由于平面特征较容易识别，此方法通过转换把对柱面特征的识别转换为对平面特征的识别。这里的柱面泛指圆柱面、椭圆柱面。

对已剩下的各个子区域分别处理，把子区域中的三角面片进行高斯映射。如果高斯映射落在高斯球的小圆上，则说明这些三角面片组成的是锥面特征［8］。

2.3 其它特征识别

剩下区域的三角形比较密集、规则，可以应用曲率估计算法。首先建立局部区域的拓扑结构，拓扑采用半边结构，然后根据三角形的所有相邻三角形利用最小二乘法估算该三角形的曲率值，通过指定曲率值的阈值来进行区域划分，被划分的单独区域就是一个特征。

目前已有很多算法估算离散网格的曲率，但大多数都是估算三角形顶点的曲率值。而为了分割轻量化文件，要估计三角形的整个形态，然后在三角形之间进行分支，所以要计算三角面片的曲率。文献 ［9］对面片的曲率值估算的较准确，但是已知条件比较苛刻，需要知道面片的顶点法向量。文献 ［10］中描述了10多种曲率估计算法，及各种算法的理论背景、公式意义和适用范围。这里采用最小二乘法估算三角面片的曲率值。具体做法是，以三角面片的中心O为原点，建立局部二次曲面

如图4所示，h轴为三角面片在轻量化文件中的法向量方向，u、v相互正交。以三角面片的顶点和顶点的相邻点来拟合曲面S（u，v），用最小二乘法就可以得到曲面参数a、b、c、e、f、g。曲面在原点的曲率就是三角面片中心O的曲率，由曲面的第一、第二基本公式，有

再有K ＝k1k2，H ＝ （k1＋k2）／2，得

其中，k1为最大主曲率，k2为最小主曲率。

图4 局部坐标系

根据上述计算出的曲率值，通过指定阈值对区域进行分割，具体分割算法流程如图5所示。区域分割后根据高斯曲率和平均曲率是否为常值来进行球面特征的识别。其它区域认为是自由曲面特征。在实际情况中，有可能识别平面、柱面和锥面特征之后整个轻量化文件就已经被完全分割开，无需再对其进行分割。

3 实验结果及分析

本文算法已在本课题组开发的Intevue三维系统中实现，环境为Visual C＋＋2005和Hoops。图6为一简单的CAD轻量化网格模型，上部为半球面，下部为高度较小的柱面，本文可以很好的对其进行区域分割。图6中的图（a）为轻量化网格模型，图 （b）为模型面片图，图 （c）为特征识别结果，其中黄色区域为平面，蓝色区域为柱面，红色区域为球面。此模型对于文献 ［3］来说，由于柱面三角形和球面三角形在大小、形状上非常接近，在区分稠密三角形和稀疏三角形时无法自动把球面和柱面分开，导致此情况无法自动识别。

图6 零件轻量化网格模型

图7 （a）是文献 ［7］中的示例，本文对此模型的识别结果如图7（b）所示。该模型的识别过程比较简单，没有文献 ［7］中的算法那么繁琐。该模型共有13个特征：6个平面、5个柱面、1个锥面和1个环面，其在轻量化文件中的连接关系如图7（c）所示。平面特征识别之后剩下3个区域，再识别柱面之后就可把整个轻量化模型分割完毕。该轻量化网格模型只需分割平面和柱面，并不需要再对其它区域进行分割，只需判定其它区域具体的特征类型即可。特征识别结果：黄色区域为平面特征，红色区域为锥面特征，蓝色区域为柱面特征。图7中的 （b1）和 （b2）为分割后的局部放大图，从图中可知各个特征之间的是有严格边界的。图8是本文算法与文献 ［7］中算法的结果比较，其中图 （a）为本文算法特征识别结果，而图 （b）为文献 ［7］中的结果［3］。由结果可知本文算法比文献 ［7］中算法识别质量高。

图7 零件轻量化网格模型 （a）原模型；（b）特征识别结果，其中 （b1）、（b2）识别结果局部放大图；（c）特征数据连接关系

图8 零件识别结果比较

图9 为一支架零件模型，图 （a）为原模型，图 （b）为特征识别结果，各个特征之间用不同的颜色表示。1）、2）、3）为特征识别结果的局部放大图。图10展示了多个轻量化零件模型的特征识别结果。

图9 支架轻量化网格模型 （a）原模型，（b）特征识别结果，1）、2）、3）识别结果局部放大图

图10 轻量化网格模型的特征识别结果

本文算法与文献 ［8］中算法比较，本文算法的优势有：①本文算法无需在导入数据时就建立整个网格模型的三角形拓扑结构，只在识别三角形比较均匀的局部区域建立拓扑结构，此时三角面片数量已大幅减少，占用内存也较少；②在识别过程中比较次数较少，因为本文算法只需比较前后2个三角形即可，而后者要比较一个三角形的所有邻域三角形，增加了识别时间；③本文算法在准确识别平面特征的基础上已有完整的特征边，故跟平面相连的所有特征也有严格的边界。

4 结束语

本文利用CAD轻量化文件中特征数据的连续性，逐次分割轻量化文件。首先对较容易的平面特征进行识别，然后根据高斯映射和最小二乘法识别其它特征。通过本文算法可以快速准确地识别CAD模型中最常见的基本特征：平面、柱面、锥面、球面等特征。不足之处在于阈值的选择，不同的阈值区域分割的结果可能不同。如果出现阈值选择不当等问题，自动识别结果就不能满足要求，本文支持交互式调整或者交互式识别。但是交互降低了自动化程度，因此，阈值的自动化选择是下一步的重点研究工作。

［1］Alexander Agathos，Ioannis Pratikakis，Stavros Perantonis，et al.3Dmesh segmentation methodologies for CAD applications［J］.Computer Aided Design ＆ Applications，2007，4（6）：827－841.

［2］SHU Zhenyu，WANG Guozhao.Fast mesh segmentation algorithm based on tensor voting ［J］.Journal of Zhejiang University （Engineering Science），2011，45 （6）：999－1005 （in Chinese）.［舒振宇，汪国昭.基于张量投票的快速网格分割算法 ［J］.浙江大学学报 （工学版），2011，45 （6）：999－1005.］

［3］Dong Xiao，Lin Hongwei，Xian Chuhua，et al.CAD mesh model segmentation by clustering ［J］.Computers ＆ Graphics－Uk，2011，35 （3）：685－691.

［4］YANG Fanqin.Research on the approach to CAD mesh model segmentation ［D］.Hangzhou：Zhejiang University，2007（in Chinese）.［杨钒沁.面向CAD应用的三维网格分割算法研究 ［D］.杭州：浙江大学，2007.］

［5］QIAN Jiang，CHEN Zhiyang，YE Xiuzi.Noise robust watershed mesh segmentation algorithm ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2008，20 （3）：310－315（in Chinese）.［钱江，陈志杨，叶修梓.噪声鲁棒的分水岭网格分割算法 ［J］.计算机辅助设计及图形学学报，2008，20（3）：310－315.］

［6］DONG Fangmin，XIAO Renbin，ZHONG Yifang，et al.A hybrid approach to feature segmentation for triangle meshes of mechanical CAD model ［J］.China Mechanical Engineering，2007，18 （4）：382－387 （in Chinese）.［董方敏，肖人彬，钟毅芳，等.机械CAD三角网格模型的特征表面分割混合算法［J］.中国机械工程，2007，18 （4）：382－387.］

［7］Sunil V B，Pande S S.Automatic recognition of features from freeform surface CAD models ［J］.Compute Aided Design，2008，40 （4）：502－517.

［8］Wang Jun，Yu Zeyun.Surface feature based mesh segmentation［J］.Computers ＆ Graphics－Uk，2011，35 （3）：661－667.

［9］Zhihong M，Guo C，Yanzhao M，et al.Curvature estimation for meshes based on vertex normal triangles ［J］.Compute Aided Design，2011，43 （12）：1561－1566.

［10］QI Baoming.Curvatures estimation and the improvement of Taubin’s method on triangle mesh ［D］.Dalian：Dalian University of Technology，2008 （in Chinese）.［齐宝明.三角网格离散曲率估计和Taubin方法改进 ［D］.大连：大连理工大学，2008.］