随着CAD/CAM技术的发展和在工程中的普及, 三维CAD模型在设计和加工中的重用问题日显突出, 三维模型的相似性评价是模型检索和重用的核心技术, 受到广泛关注, 学者们对三维CAD模型的相似性比较方法进行了较深入的研究, 如Hilaga等^[1]提出基于Reeb图的三维网格模型拓扑匹配方法; Bespalov等^[2]对网格化处理的CAD模型进行形状检索, 发现机械零件拓扑结构的微小变化会引起相似度的巨大差异; Bespalov等^[3]提出基于尺度空间分解的层次特征分割方法, 用于三维CAD模型的局部相似性比较。由于工程特性或美观的需要, 自由曲面在工业产品中应用越来越多, 自由曲面造型复杂、加工困难, 重用自由曲面设计模型和数控加工规划具有更好的工程意义, 这使得评价自由曲面相似性显得尤为迫切。You等^[4]构建拓扑图, 通过检测独立最大团方法, 计算汽车覆盖件曲面模型的相似性; 王洪申等^[5]采用区域生长法对STL格式的自由曲面进行分割构建拓扑结构, 利用赋权二分图最优匹配算法进行相似性比较; Fu等^[6]研究鼠标、相机等自由曲面模型的相似性, 提出基于高斯曲率积分的相似性比较方法; 王洪申等^[7]提出距离-曲率形状分布的方法, 以距离-曲率矩阵的相似度得到曲面模型的相似性描述; 张开兴等^[8]从曲率云图中提取特征点的类Sift算子, 通过比较局部特征的相似性实现2个曲面相似性的评价。Li等^[9-10]运用层次分割图(HPG)表达注塑模具, 并基于HPG图运用子图同构算法计算模具间的相似性。Huang等^[11]提出一种以加工重用为目的的自由曲面相似性评价与检索方法。首先对曲面进行内容编码, 初步过滤掉不匹配的对象, 然后用D2算法^[12]和子图同构算法评价自由曲面的相似性。已有研究都是通过设计抽象的几何描述子来表达自由曲面的几何特征, 而在将自由曲面表达成几何描述子的过程中, 不可避免地丢失了部分自由曲面的几何特征, 从而限制了对曲面的几何形态描述能力。为了能以更细的粒度描述自由曲面的几何特征, 又能满足检索对计算速度的需要, 本文依据曲面曲率, 提出适用于单曲率特征自由曲面相似性比较算法。该算法首先调整三维曲面的姿态, 使相比较的曲面的Z轴方向一致, 然后将待比较曲面做切片处理提取曲面上的截交线, 以截交线上一系列点的曲率为依据判别相应曲线的相似性, 将2个曲面的相似性度量转换为2簇平面曲线的相似性比较, 以降维思想简化曲面相似性评价问题。

1 单曲率特征自由曲面的含义

曲面上点的曲率信息是曲面形状描述中极其重要的一个属性, 能够可靠地反应曲面的形状特征。由微分几何知, 曲面上某点处的2个主曲率为k₁, k₂, 它们的乘积称为曲面该点处的高斯曲率, 常以K表示, 它们的平均数称为曲面该点的平均曲率, 常以H表示。根据曲面上点的高斯曲率和平均曲率将自由曲面的特征定义为如下A, B, C 3类(如图 1所示), 本文研究的“单曲率特征的自由曲面”定义为:曲率特征单一, 只有凸特征或凹特征或鞍型特征的简单自由曲面。

A类:K>0, H < 0的曲面称为单一凸自由曲面, 如图 1a)所示;

B类:K>0, H>0的曲面称为单一凹自由曲面, 如图 1b)所示;

C类:K≤0的曲面称为单一鞍型自由曲面, 又叫双曲抛物面, 如图 1c)所示。

本文约定:类型相同单特征自由曲面才有评价相似性意义, 如果曲面类型不同则认为不具有相似性。

2 单曲率特征自由曲面的相似性比较算法

本文研究的是B样条表达的自由曲面的相似性评价算法, 所设计算法的总体思路如图 2所示, 将一个自由曲面描述为一簇平面曲线的集合, 2个自由曲面之间的相似性可以通过曲面上对应的2簇曲线的相似性来衡量。曲面上点的曲率信息能形象地描述曲面形状, 本文设计的算法以点的曲率为核心参数, 计算2个曲面上已提取的对应曲线的相似值, 用所有相似值的平均值来评估2个单曲率特征自由曲面的相似性。

2.1 曲面做Z轴对齐处理

调整曲面模型在欧氏空间的摆放位置, 将曲面的Z轴对齐。如图 3a)所示, 两凸曲面在空间的摆放位置不统一, 2个面上各点法矢矢量和分别为N₁, N₂, 由于曲面的位置不一致, 可能无法得到正确相似性比较结果；通过对齐处理，如图 3b)所示, 使两曲面的法矢矢量之和的方向一致, 均指向Z坐标轴的方向, 即两曲面的Z轴对齐, 此时曲面做截切处理, 一一对应的截交线更能反映曲面的真实相似度, 提高算法的精度。具体实现过程如下:

1) 设S={S₁, S₂}表示待比较相似性的同类单曲率特征的一个自由曲面集, 首先依据曲面点的曲率值大小(不考虑正负号, 只考虑数值的大小), 分别在曲面S₁和S₂上遍历取点P_i(i=1, 2, …, n)。曲率值大反映曲面的弯曲程度大, 取分布较密集的点才能更准确地表达曲面的真实形状; 曲率值小反映曲面的弯曲程度小, 可以取分布较稀疏的点。遍历取点的步骤如下:

步骤1   输入参数化(u∈[0, 1], v∈[0, 1])的曲面, 在曲面上沿u, v方向按等参数间隔均匀取点, 点数为100×100, 计算所有点的曲率的平均值并找到最小曲率k_min和最大曲率k_max;

步骤2  选定一个搜索起点P₁(本文设起点为u=0, v=0处的点);

步骤3   固定起点的u参, 根据与起点曲率k的大小, 在v参方向以参数距离Δv寻找下一个曲面点, 直到v参方向的数值越界;

1) 依据前面所述, 曲面上分布点的曲率较大时，所取的点比较密集，反之则所取的点比较稀疏, 因此当k≠0时, 设

(1)

式中，a₁, a₂, b₁, b₂是设定的计算参数，且a₁≠0, a₂≠0, b₁≠0;

公式(1)中：时设Δv=Δv₁, 则

(2)

时, 设

(3)

根据曲面参数v的取值范围, 确保大曲率( ≤k_max)点的参数距离始终小于小曲率(k_min≤k≤ )点的参数距离, 可得

(4)

由公式(2)~(4)解得

(5)

公式(5)中, 在给定范围内先确定参数a₁, a₂的取值, 再由a₁, a₂确定参数b₁, b₂的取值。将a₁, a₂, b₁, b₂值带入到公式(1)中即可确定每次取点的Δv的值；

2) 当k=0时, 取Δv=b₁, 此处b₁与1)中的意义相同，且b₁≠0;

步骤4   固定起点的v参数, 在参数曲线v=0上以同样方法计算参数距离Δu寻找下一个v参数线的起点, 再重复步骤3，找到该v参数线上相应的曲面点;

步骤5  重复步骤4, 直到u参数线方向的数值越界，即可按曲率大小搜索到整个曲面上的点。

计算已搜索点的法向量N_i, 所有法向量求和, 然后按照和法矢的方向, 把曲面与三维笛卡尔坐标系中的Z轴对齐, 使得曲面的和法矢N与单位向量V=(0, 0, 1)平行, 即曲面的和法矢方向和Z轴一致。

本文输入图 4所示的凸曲面, 计算公式(5), 取a₁=10^-4, b₁=0.03, a₂=0.02, b₂=0.002, 4个参数值带入公式(1)找到曲面上的所有点(图 4中的黑色十字交叉点)。

2.2 调整曲面大小

在工程中, 有时讨论自由曲面的相似性并不考虑曲面的大小, 为了消除曲面尺度对相似性评价的影响, 此时需要对曲面进行比例缩放。曲面满足Z方向的对齐后, 对其中一个单曲率特征的自由曲面(本文选曲面S₂)做比例缩放变换以调整大小, 使两曲面在Z坐标轴的方向具有相同的曲面高度, 用相同数目的等距平面分别截切2个曲面, 处理结果如图 5所示(XOZ面内的实体投影图, 其中黑色线条是截切处理后生成的截交线)。图 5a)的2个凸特征自由曲面S₁和S₂的形状相似、大小差异明显, 工程应用中需要考虑曲面大小尺度对相似性评价的影响时, 曲面不缩放, 直接对其进行截切处理, 计算曲面的相似度量值(相似值为0.491), 用于评价考虑曲面大小时的相似性; 若将曲面缩放, 消除两曲面的大小差异, 如图 5b)所示, 使两曲面在Z方向具有相同的高度范围, 相应的相似度量值为0.126, 符合人的感官判断, 这种情况适用于工程应用中不考虑曲面大小时的相似性评价。

2.3 曲面做截切处理

三维自由曲面模型的表面形状较复杂, 微小变化会引起曲面的不同, 直接比较其相似性有一定的难度。而曲面做平面截切处理可将三维空间曲面形状的描述问题转换为二维平面曲线的形状描述问题, 简化曲面相似性的比较。因此以降维的思想, 用垂直于Z轴的相同数量(设为m)的等距平行平面T={T_i}(i=1, 2, …, m)分别截切曲面S₁和S₂, 在曲面S₁和S₂上生成各自的等高线, 得到一一对应的平面曲线(如图 5所示)。设M₁, M₂分别是曲面S₁和S₂上分布的截交线集合, 则:

2.4 计算曲线的相似性

通过对曲面的截切处理, 得到能反映单曲率自由曲面特性的一系列平面曲线, 为了准确描述曲线特征、合理表征曲线的相似性, 以曲率为变量, 用两曲线曲率的Earth Mover′s Distance(EMD)值描述其相似性。EMD, 也叫推土机距离, 是一种距离度量的定义, 能通过一次线性规划计算出2个大小不同(或相同)的几何或向量的距离。对于2条曲线, 其形状大小越相近, EMD值越小, 相似度越高; 反之, 则表示其差别越大; 形状大小完全相同时, EMD恒为0。

1) 曲线相似性评价

接2.3节, 在第一个交线集M₁的每条曲线Curve_i上沿曲线方向等弧长取点集P_i={P_i1, P_i2, …P_in}(本算法设定n=100), 计算P_i中每个元素对应的曲率值K_i={k_i1, k_i2, …k_in}; 在第二个交线集M₂的每条曲线Curve′_i上按同样的方法取点集P′_i={P′_i1, P′_i2, …P′_in}(本算法设定n=100), 计算P′_i中每个元素对应的曲率值K′_i={k′_i1, k′_i2, …k′_in}。此处的曲率用相对曲率, 即带有符号(正、负)的曲率值, 符号的规定如下:曲线沿正向前进时逆时针转, 曲率取正, 曲线沿正向前进时顺时针转, 曲率取负, 即沿着曲线的正向找到一点切矢到下一点切矢转过的角度, 角度逆时针曲率为正, 角度顺时针曲率为负。然后依次输入有符号的K_i和K′_i中的对应元素, 计算曲线Curve_i和Curve′_i的EMD值E_i, 记为:

(6)

公式(6)的E_i代表第i对曲线相似的度量值。

2) 曲线相似性算法验证

为了验证2条平面曲线的相似性评价算法, 设定2组曲线:Ellip1、Ellip2、Ellip3和Curve1、Curve2、Curve3、Curve4, 同组曲线中, 第一组为椭圆曲线, 第二组为B样条曲线(包括开曲线和闭合曲线), 其中Curve1、Curve4是形状大小相同、位置不同的B样条闭合曲线, 如图 6~图 9所示。

分别在每条曲线上沿曲线方向等弧长取相同数量(设为n)的点, 并计算各点的曲率(相对曲率), 作为EMD度量的参数, 依次计算两两曲线的EMD值, 为直观反映曲率大小的变化, 在平面坐标系中绘制曲率分布线。由于不同曲线之间存在长度上的大小差异, 因此需要对曲率分布线的尺度进行归一化, 本文实例以曲线上等弧长的长度作为曲率线横坐标的间隔, 其中横坐标代表所取点的数量(坐标原点是第一个点), 纵坐标代表点的曲率值。

曲线的类型、相关数据及图形、对应的曲率线如图所示, 图中取点数量n=100时曲线所对应的曲率线, 曲线发生微小变化, 则曲率线产生局部差异。计算同一曲线类型中两两对应曲线的EMD值度量其相似性, 结果如表 1所示。曲线图形是形状有微小差异的平面曲线, 根据人的直观视觉判断, 图 6中椭圆曲线Ellip1、Ellip2的形状大小最相近, Ellip2、Ellip3次之, Ellip1、Ellip3的形状相差最大, 计算结果，两两曲线的相似程度E_ij满足关系:E₁₂(Ellip1, Ellip2)>E₂₃(Ellip2, Ellip3)>E₁₃(Ellip1, Ellip3)，结论与人的感知相同。图 7和图 8中B样条曲线相似程度E_ij也满足如上关系式，结论与人的感知相同。图 9所示的闭合曲线，Curve1、Curve4的形状大小完全相同，但位置不同，评价的相似值恒为0，评价结果与实际相符，表明选用EMD距离描述平面曲线相似性时，无需考虑曲线在平面内的方位。表 1数据显示：无论描述椭圆曲线还是B样条曲线，两两曲线的相似度量值随着形状差异的增大呈递增趋势，符合人的感官判断，满足各曲线间实际的相似关系，所以在应用中，EMD距离适用于平面曲线的相似性比较。

2.5 计算曲面的相似度量值

三维曲面的表面形状映射为一组二维曲线, 2个相比较的三维曲面的相似性度量转化为对应的2组平面曲线的相似性度量。用2.4节公式(6)计算对应曲线的相似值并求和即为两曲面的相似值。由于曲面做平面截切处理时, 截切平面的数目变化会影响截交线相似性的总和, 为了避免该问题, 对曲线相似度量值的总和求平均值, 以该平均值作为曲面的相似性评价指标, 记作:

(7)

式中，E_i表示第i条曲线的相似值, m表示两曲面分别垂直于Z轴被等距截切后所得的平面截交线的数量, 表示两曲面相似性的评价值。

3 实验与讨论

基于OCC(Open CASCADE)开源3D建模库, 以Microsoft Visual Studio 2010为集成开发环境, 分别用第一节中定义的A, B, C 3类单曲率特征自由曲面验证本文相似性评价算法。主要验证以下属性:(1)自由曲面绕Z轴任意旋转对相似性评价结果的影响; (2)曲面的缩放操作对相似性评价结果的影响; (3)截交线的数量对相似性评价的影响。根据以上实验目的, 对每类(A, B, C类)单曲率自由曲面构造2个B样条曲面, 并分别设计3组实验, 组号分别记为X-Ⅰ、X-Ⅱ、X-Ⅲ(X取A, B, C)。实验方法:X-Ⅰ组在曲面相似性比较中, 不对曲面进行缩放操作, 相比较的曲面位置是对齐的; X-Ⅱ组曲面不缩放, 同时曲面S₂绕Z坐标轴做旋转变换; X-Ⅲ组对曲面进行缩放。对每组实验分别用10种截切间距截切曲面, 由公式(7)计算两曲面的相似度量值, 在实验中, 曲面的每条截交线上参与计算的点均取100个。

3.1 曲面的相似性评价实验数据

图 10~图 12为单曲率特征自由曲面的3种基本类型曲面实验图例, 表 2~表 4是实验所得的数据。

3.2 相似性评价实验分析与讨论

通过对表 2~4中的实验数据分析可知, 本文算法具有如下属性:(1)当截面间距相同时, X-Ⅰ组与X-Ⅱ组的值相同, 表明评价结果与曲面绕Z轴旋转位置无关; (2)X-Ⅰ组和X-Ⅲ组数据对比可知, 曲面缩放和不缩放, 对相似性指标的数值有影响, 但从图 13~15可以看出, X-Ⅰ组和X-Ⅲ的EMD分布图线变化关系一致, 表明本文算法对曲面缩放和不缩放的相似性比较对相似性的变化趋势没有影响; (3)对曲面的截切数量(截切间距不同)会对相似性数值产生影响, 但随着截切间距缩小, 相似性评价指标收敛于定值(见图 13~15的EMD分布线图); 此外, 当截面间距变化时, 相对X-Ⅰ组结果, X-Ⅲ组的数值更小, 数值也更稳定。由算法的描述可知, 算法的时间复杂度为O(m)(m为曲面的截面数目)。

4 结论

曲率是曲面的重要微分几何特性, 其大小与自由曲面模型在欧氏空间的摆放位置无关, 本文利用曲率的这种属性设计了单曲率自由曲面相似性评价算法。首先运用降维思想, 用垂直于Z轴的平面对单曲率特征的B样条曲面做截切处理, 得到曲面与截面的交线信息, 将三维空间模型转换为较简单的二维平面图形的集合, 然后以EMD距离度量平面曲线的相似性, 由此反映自由曲面的相似性, 方法可靠, 便于计算, 对考虑曲面大小和不考虑曲面大小的情况都适用。通过大量的实验验证, 设计的算法简单可行, 并具有如下属性:(1)对相比较的2个自由曲面仅需对齐一个坐标轴; (2)算法既适用于考虑大小的曲面相似性评价, 也适用于不考虑大小的曲面相似性评价; (3)相似性评价指标收敛。