付 鹏 苑伟政

西北工业大学陕西省微/纳米系统重点实验室,西安,710072

0 引言

三维CAD系统用实体模型表示产品,其模型表示由点、边、面等几何信息构成。CAPP和CAM 系统需要加工信息例如轴、孔、槽等来进行工艺推理和加工轨迹的生成。特征识别技术[1]从产品的实体模型出发自动识别出其中具有一定工程意义的几何形状(特征),并将其进一步转换为可用于后续加工的特征。特征识别技术已成为一体化CAD/CAM环境中必不可少的组成部分。

20世纪80年代以来,国内外许多学者对特征识别技术进行了研究,但主要集中在算法研究上,实现过程的论述较少。从已公开的资料来看,主要存在以下问题：

(1)算法方面,基于图的特征识别方法的研究较多,多采用属性邻接图方法[2]和凸壳(convex hull)方法[3]来处理相交特征,并将这些方法与其他方法结合,产生了多种混合特征识别算法[4-6]。上述算法的时间复杂度与零件复杂度相关,且难以有效地识别相交特征并提供相交特征的多重解释。

(2)研究往往针对某一特定的CAD系统,通过对该CAD系统的二次开发,实现特征识别。

(3)对特征识别的研究仍停留在特征的面表示层次。对于面特征的边界表示,尤其是特征识别中的面、边环、边的多态耦合性很少涉及。

笔者采用基于STEP的特征识别技术[7-8]识别来自不同三维CAD系统的模型,引入面向对象的方法,预定义二维面、边环、边等实体类以提高特征识别系统代码的重用性,并通过基于子图匹配和基面分解的属性邻接图分解方法来识别特征。

1 STEP模型的表示与基于STEP的特征识别过程

STEP模型采用B-Rep法和参数表示法的混合表示方法来表示。B-Rep法的拓扑表示规则如下：体是B-Rep表示的顶层对象,由壳包含而成;壳由一系列面连接而成;面由边界包含而成,边界具有方向性,其参数由边环给出;边环由有向边按照连接顺序构成,有向边的参数由边给出;边由点定义,通过起点和终点确定边的参数。高阶的较复杂物体必须建立在基本体基础上。对于自由曲线曲面,STEP采用参数表示法来描述。STEP应用NURBS方法来表达复杂的自由曲线曲面,该方法允许局部修改曲率,并能准确地描述几何基元。

本文所述的基于STEP的特征识别基于AP203协议,采用边界匹配方法来识别特征。识别过程由以下4个步骤组成：

(1)预定义特征类型,建立特征库。

(2)生成STEP模型拓扑几何结构树。

(3)识别STEP面和边环的类型并获取其几何参数。

(4)采用基于子图匹配和基面分解的属性邻接图分解方法识别预定义特征。

2 预定义特征的属性邻接图表示

属性邻接图[2](attributed adjacency graph,AAG)是目前广泛应用的特征识别方法,可表示用B-Rep法描述的零件的拓扑几何关系。在属性邻接图中,顶点表示模型中的面,顶点之间的弧表示两相交面的共有边,用顶点和弧的附加属性表来表示拓扑几何属性。采用属性邻接图时,特征定义规则的表示简单直观,便于进行特征拓扑几何构成的描述。

图1为4种常见特征的属性邻接图。笔者采用属性邻接图的特征表示方法,但引入面向对象方法采用了新的实现方式,可预定义二维面、边环、边等实体类,以类成员变量代替属性邻接图中的属性表。引入面向对象的方法,可以显著提高特征识别系统的代码重用性,便于实现特征识别系统的组件化,有利于实现面向不同应用的快速开发。

图1 常见特征的属性邻接图表示

图1 a和图1b所示为圆柱体与圆锥体特征,其组成中都包含两个圆形表面;图1c和图1d为长方体和开口直槽特征(都是由矩形平面组成)。预先定义圆形平面、矩形平面类及其低阶图素构成的方法,可以提高特征识别系统代码的重用性。图1a和图1b的圆柱和圆锥体特征的属性邻接图的图表示完全相同。对于预定义的圆柱体和圆锥体类来说,采用相同形式的属性邻接图可准确描述这两种特征,并可减少用于表示预定义特征的属性邻接图数量。

3 STEP模型拓扑几何结构树生成

STEP模型的拓扑几何结构为树状解构,如图2所示。

图2 STEP模型拓扑几何结构树示例

特征识别前需从STEP模型文件中解析数据,并按照STEP模型拓扑几何结构重新组织数据,生成STEP模型拓扑几何结构树。具体生成过程如下：

(1)建立STEP实体类型与C++结构的映射关系。分析STEP实体类型的数据定义,建立与之对应的C++结构。每个C++结构将定义的ID成员变量作为唯一标志,其他成员变量与STEP实体类型的参数一一对应。

(2)将STEP实体解析为对应的C++结构变量。笔者使用VC的CStdioFile∷ReadString函数读入STEP文件,解析获得实体类型,然后用switch case语句判断实体类型并将该实体的低阶实体行号和数据转换存入对应的C++结构链表。由于笔者开发的原型系统中解析的STEP实体类型数量较多,故在此仅给出解析流程,如图3所示。

图3 STEP实体解析流程

(3)生成STEP模型拓扑几何结构树。根据C++结构变量的ID成员变量,按照STEP模型拓扑结构逐层搜索,逐层添加构成高阶拓扑实体的低阶拓扑几何实体元素,生成模型的拓扑几何结构树。

4 STEP面和边环的类型识别及几何参数获取

可用于属性邻接图的面类,如矩形平面、圆形平面在STEP中未定义,面的类型是由边环类型和面几何参数共同确定的。例如,圆形边环与平面位置定位共同确定一个圆形平面,矩形边环与平面位置定位共同确定一个矩形平面等。边环类型,例如矩形边环、平行四边形边环、圆形边环等在STEP中也未定义,需要通过组成边环的边数量、边与边之间的几何关系等组合规则来识别。例如,由两条等半径半圆构成的边环即为圆形,由4条直线两两垂直构成的边环即为矩形,由4条直线两两平行且互不垂直构成的边环即为平行四边形等。因此,必须预定义边环类型的识别规则,识别出边环类型并获取参数后,结合面几何参数识别出可用于后续特征识别的面类型并获取其参数。

按照STEP模型的拓扑几何结构,自顶向下查找并识别出低阶类型,获取其几何参数后,根据低阶类型的不同组合可实现高阶类型的识别和几何参数的获取。笔者开发的原型系统可实现圆形平面、矩形平面、圆柱面等面类型的识别,由于具体的识别算法较为繁杂,笔者在此仅给出识别算法整体流程：

(1)遍历STEP模型面链表,读取STEP面结构对象。

(2)读取面对象的面几何参数变量,使用switch case语句判断面的几何参数类型,转入对应分支。

(3)读取面对象的面边界参数变量,获取构成边界参数变量的边环对象及边环的边数量的变量后,使用switch case语句判断边环的边数量,转入对应分支。

(4)读取边环对象的边类型数量的变量,使用switch case语句转入对应分支。获取边的类型和参数,并结合边与边的几何关系识别边环类型,解析边对象的参数获得边环参数。

(5)根据面几何参数和边环类型识别面的类型,解析获取几何参数。

5 基于子图匹配和基面分解的属性邻接图分解方法

复杂零件的属性邻接图中存在与预定义特征匹配的子图,通过子图匹配可以识别出零件所包含的特征。但是直接在零件属性邻接图中搜索子图是NP问题,算法复杂度与零件复杂度相关,因此在子图匹配前进行属性邻接图分解可降低算法复杂度。目前属性邻接图分解有多种方法[2-5],但这些方法无法有效解决相交特征的识别,且算法复杂、编程实现工作量较大。

在相交特征识别中,若一个面含有内环或者它的外环上含有凹边,则称其为基面,基面是体上连接特征的面即相交特征的相交面[9]。笔者提出了基于基面分解的属性邻接图分解方法,该方法的子图搜索算法时间复杂度仅与特征子图的复杂度相关,而与零件复杂度无关,因此可减少冗余计算量。算法流程简述如下：

(1)为面类设置基面标志变量。基面标志变量的设置规则由两部分构成：①多环判定中,多环为真,其他为假;②混合环和凹环判定中,混合环或凹环为真,其他为假。

(2)遍历面链表,读取面对象的基面标志变量,为真则获取基面。

(3)由基面开始采用深度优先算法进行图的遍历,生成子图。

(4)将子图与预定义属性邻接图匹配,识别预定义特征。

(5)解析特征参数,根据不同的特征与基面的相对位置,判断相交特征凸凹性。

图4为圆柱体与立方体相交而成的零件及其属性邻接图,其中,F3面包含2个边环,其基面标志为真。遍历面链表获取F3面,子图分解后如图5所示,分别与图1中圆柱体与立方体的属性邻接图表示匹配,该零件由一个圆柱体和立方体特征构成。

图4 圆柱立方体零件及其属性邻接图

图5 子图分解

笔者使用VC++6.0开发了基于STEP的特征识别原型系统,可识别圆柱体、圆孔、矩形槽等常见特征和部分复杂特征。

6 结束语

本文阐述了基于STEP的特征识别技术及其实现过程,采用属性邻接图表示预定义特征。引入面向对象方法可以简化属性邻接图的表示,提高特征识别系统的代码重用性,便于实现特征识别系统的组件化,有利于实现面向不同应用的快速开发。基于子图匹配和基面分解的属性邻接图分解方法,降低子图搜索算法复杂度,可识别多环相交特征和预定义混合环相交特征。今后的研究方向是提高对混合环相交特征和过渡特征的处理能力。

[1] 高曙明.自动特征识别技术综述[J].计算机学报,1998,21(3)：281-288.

[2] Joshi S,Chang T C.Graph-based Heuristics for Recognition of Machined Features from a 3D Solid Model[J].Computer-aided Design,1988,20(2)：58-66.

[3] Ferreira J C E,Hinduja S.Convex Hull-based Feature-recognition Method for 2.5D Components[J].Compute-aided Design,1990,22(1)：41-49.[4] Gao S,Shah J J.Automatic Recognition of Interacting Machining Features Based on Minimal Condition Sub-graph[J].Computer-aided Design,1998,30(9)：727-739.

[5] Rahmani K,Arezooa B.A Hybrid Hint-based and Graph-based Framework for Recognition of Interacting Milling Features[J].Computers in Industry,2007,58(4)：304-312.

[6] 王飞,张树生,白晓亮,等.基于子图同构的三维CAD模型局部匹配[J].计算机辅助设计与图形学学报,2008,20(8)：1078-1084.

[7] 杜娟,田锡天,朱名铨,等.基于 STEP和 STEPNC的AD/CAPP/CAM/CNC系统集成技术研究[J].计算机集成制造系统,2005,4(11)：487-491.

[8] Rameshbabu V,Shunmugam M S.Hybrid Feature Recognition Method for Setup Planning from STEP AP-203[J].Robotics and Computer-integrated Manufacturing.2009,25(2)：393-408.

[9] 徐世新.对一种特征识别算法的两点改进[J].北京航空航天大学学报,2000,26(4)：454-456.