基于模拟退火的三维模型典型结构挖掘与相似性评价

张开兴　杭晟煜　王金星　宋正河　刘贤喜,3

(1.山东农业大学机械与电子工程学院， 泰安 271018； 2.中国农业大学工学院， 北京 100083；3.山东省园艺机械与装备重点实验室， 泰安 271018)

0　引言

随着产品数字化技术应用的不断深入，企业已积累的大量CAD设计成果为新产品的研制提供了宝贵的可重用设计资源。虽然产品在不断地更新换代，但全新的功能、结构和工艺设计只有约20%，其余80%的设计则可以通过直接重用或局部修改已有设计来完成，产品在功能、结构和工艺等方面具有很强的相似性和继承性。在企业的模型库中，设计人员往往根据不同的应用背景通过人工交互方式定义一些典型结构用于模型的设计重用。面对企业庞大的模型库，这种方法效率低下，受主观因素影响大，并且大量的典型结构往往隐含在外形完全不同的CAD模型中，设计人员很难发现。因此，如何从海量的产品模型中快速、有效地挖掘出需要的典型结构，并对其加以重用已成为产品开发各环节的一个迫切需求。

迄今为止，已有多种数字化设计重用方法在机械产品设计中得到广泛应用，如基于实例推理的设计、基于模块化的设计、基于检索的设计等，可有效提高产品设计效率和质量。基于实例推理的设计是通过访问知识库中过去同类问题的求解从而获得当前问题解决方法的一种推理模式。张田会等[1]提出基于规则和实例的推理方法，提高夹具设计知识重用率和设计效率；王儒等[2]将设计知识融入到基于实例推理活动中，实现知识的辅助决策。基于模块化的设计是对不同功能、性能和规格的产品进行划分并设计出一系列的功能模块，通过模块的选择和组合来构成不同的产品。BRIERE等[3]采用基于结构的模块化设计方法对产品变体及特有部件进行系统性设计；郏维强等[4]提出了基于模糊关联分析与求解的复杂产品模块化设计方法处理产品设计过程中不确定信息的转化与传递。基于检索的设计主要通过建立三维零件CAD模型库，设计一定的匹配算法，在模型库中寻找与设计需求相似度最高的已有零部件进行设计重用。经典方法有OSADA等[5]提出的基于形状分布算法的检索方法，通过比较模型随机点之间距离(D2)统计特征的形状分布曲线实现模型的相似性评价；陶松桥等[6]通过求解模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵，实现对不同近似程度的相似模型的检索；TSAI等[7]将加工要求、质量、材料等工程语义信息数字化，提出基于模糊集的三维CAD模型相似性评价。在农业机械产品设计领域，基于实例推理、基于模块化以及基于检索的数字化设计重用方法引起众多科研人员的日益重视，宋正河等[8]提出基于推理知识的联合收获机械快速设计方法；陆长明等[9]针对小型农业作业机械，提出基于模块化的快速设计和变异设计方法；张开兴等[10]提出融合语义的三维CAD模型局部结构检索方法。

由于机械产品CAD模型包含较多几何及拓扑信息，基于实例推理和基于模块化的设计重用方法可靠性不高，同时由于在现代设计中三维CAD模型设计信息的复杂化，传统的基于检索的数字化设计重用方法不再适用，而启发式算法由于具有能够进行大量复杂信息快速准确处理的特点而在机械产品数字化设计领域有越来越多的应用。李海生等[11]采用遗传算法进行多特征融合权重优化，提出基于融合特征的非刚性三维模型检索算法；高雪瑶等[12]使用蚁群算法搜索源模型与目标模型之间的最优面匹配序列，以最优面匹配序列为基础来计算两个模型之间的相似性；王玉等[13]通过构造CAD模型属性邻接图，借助神经网络进行CAD模型的自动聚类。

总体来说，现有的数字化设计重用技术主要针对产品零部件级，产品研制中大量的设计重用则是在更细观的零部件内部特征和典型结构上，相似性判定以定性和文本属性匹配为主，且可重用设计信息的确定也非常依赖于人的经验和知识，产品数字化设计重用的粒度粗、精度差、智能化水平低。基于此，本文提出基于模拟退火算法的三维模型典型结构挖掘与相似性评价方法。

1　模型表示与属性邻接图构建

1.1　CAD模型的B-rep表示

在CAD系统中，三维实体CAD模型的精确表示通常有2种方法[14]：①边界表示法(Boundary representation，B-rep)。②构造实体几何表示法(Constructive solid geometry，CSG)。目前实际应用中的CAD系统零件的模型文件都保存有对应的B-rep信息，并且已成为国际标准的STEP文件格式也支持模型的B-rep表示。此外，不同CAD造型系统的零件模型都可方便地转换为STEP中的B-rep格式。因此，本文算法中采用CAD模型的B-rep表示。

模型的B-rep表示是把模型定义为封闭的边界表面围成的有限空间，通过面、环、边、点来定义模型的几何及拓扑结构。B-rep表示方法详细记录了构成形体的所有元素的几何信息及其拓扑信息，以便直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于面、边、点为基础的各种几何运算和操作。其优点在于：表示形体的点、边、面等几何元素是显式表示的，比较容易确定几何元素间的连接关系；且对模型的B-rep表示可以有多种操作和运算。

1.2　CAD模型的属性邻接图构建

属性邻接图从图的概念推广而来，是一种用于描述零件几何、拓扑信息的图结构，其定义如下：

定义1：属性邻接图。G=(V,E,α,β)，其中，V是一个包含有限元素的非空集合，其元素称为节点，且V≠∅；E⊆{(u,v)|u,v∈V}，是一个以不同节点的无序对作为元素的有限集合，其元素称为边(不考虑节点含有直接与自身相连的边)；α：V→WV是一个从节点集合到其属性集合的映射，WV是节点的属性集合；β：E→WE是一个从边集合到其属性集合的映射，WE为边的属性集合。

对于CAD模型的属性邻接图，模型中的每个面fi都有唯一的节点Vi与之相对应，模型中面的属性集合WV包括面的类型、面的指向、面的相对面积等。E为面之间的邻接关系，对于模型中任意2个面fi和fj，如2个面之间具有邻接关系，则有唯一的一条边Eij与之对应，模型中边的属性集合WE包括边的类型、邻接面之间的夹角、公共边的凹凸性等。表1为面节点和边的属性[15]。

表1　CAD模型属性及说明Tab.1　Attribute of CAD model and its instruction

(1)面的类型：本文中将CAD模型的面分为平面类、圆柱面类、圆环面类、圆锥面类、球面类和自由曲面类等。

(2)面的指向：在CAD模型中，面的指向对2个曲面的方向性有较大影响。例如圆柱面和圆柱孔，凸台和凹槽，虽然面的形状相同，但在CAD模型中所要表达的形状并不相同，因此有必要用面的指向加以区分。在几何内核中对CAD模型面的指向定义为面的方向和表面方向之间的关系，表面的方向总是从中心或轴向指向外的，而面的方向总是从模型实体指向外的。当面和曲面的方向相同时，面的指向为true，不同时为false。如图1所示圆柱面f1的指向为true，圆柱孔f2的指向则为false，通过判断面的指向可以有效地对这类相似的曲面进行区分。

图1　CAD模型面的指向示意图Fig.1　Graph of direction of surface in CAD model

(3)面的相对面积：一个面在CAD模型中所占面积的大小，对人的视觉认知及加工过程中有着重要的影响，因此面的相对面积也是面的一个重要属性。在CAD模型中，某个面fi的面积为Si，其所有邻接面集合为FA={f1,f2,…,fk}，则该面的相对面积Sei为

(4)边的类型：本文中将CAD模型的边分为直线、圆形曲线、椭圆形曲线、双曲线、抛物线和其他曲线等。

(5)邻接面夹角：面之间的夹角计算是一个较为复杂的问题，这里仅考虑3种情况：① 2个相邻接面都为平面，面之间的夹角用2个面的法向夹角计算。② 一个面为平面，另一个面为二次曲面，平面取法向，二次曲面取轴向。③ 2个面都为二次曲面，面之间的夹角用两曲面的夹角计算。对于不规则的曲面不予考虑，则边的邻接面夹角θ为

(6)边的凹凸性：对于边的凹凸性判断，可利用文献[16]计算。但是由于这些文献一般将边的凹凸性分为凹边和凸边，但对于2个相切邻接面边的凹凸性判别现有方法有时会存在判别错误，因此本文将边的凹凸性分为凸边、凹边和平滑边。如图2所示对模型边的凹凸性判断结果为：边l1为凸边，l2为平滑边，l3为凹边。

图2　CAD模型边的凹凸性示意图Fig.2　Graph of concavity and convexity of edge in CAD model

本文将STEP文件表达的B-rep模型读入以Open CASCADE[17]为几何造型核心的原型系统，遍历B-rep模型的每个面，将该面添加到模型的面集合FS={fi}，1≤i≤m，其中m为模型中面的数目；遍历面集合FS中的每个面fi，同时在属性邻接图中创建一个与该面对应的图节点，并提取该面的属性作为其对应节点的属性；对于FS中的每2个面fi与fj，计算它们之间的连接关系，若两面相邻接，则在属性邻接图中对应的两节点间构建一条边，该边的属性由边的类型、面之间的夹角及边的凹凸性决定。图3所示为CAD模型及其属性邻接图，CAD模型的属性图记录了模型几何和拓扑信息，涵盖的信息量大，与STEP文件记录的B-rep模型的几何拓扑信息相比，属性邻接图记录模型的信息形式简洁，表达直观，可读性强。

图3　CAD模型及其对应的属性邻接图Fig.3　CAD model and its attribute adjacency graph

2　三维模型典型结构挖掘与相似性评价

典型结构是指模型中包含的具有重用价值的局部区域，这些局部区域主要是设计领域常见的凸台类(Boss)、型腔类(Pocket)、台阶类(Step)、孔类(Hole)和槽类特征(Slot)，以及由这些基本特征组合、或按一定规律排布而成的复合特征，具有一定的复杂性。图4所示为假定一个典型结构以及含有该典型结构的CAD模型属性邻接图，圆、正方形和三角形分别表示属性不同的节点，在图4b属性图表示的CAD模型中挖掘图4a属性图表示的典型结构其实质是在大图中寻找子图。

图4　典型结构及包含该典型结构CAD模型属性邻接图Fig.4　Attribute adjacency graphs of typical structure and its CAD model

那么，可以将CAD模型典型结构的挖掘问题通过属性邻接图转换成检测典型结构与CAD模型的属性邻接图之间公共子图的问题来解决。在此，先给出公共子图和最大公共子图的定义：

定义2：公共子图。给定图G、Gα和Gβ，若图G与图Gα子图同构，同时，图G也与图Gβ子图同构，则称图G是图Gα和图Gβ的公共子图，记作cs(Gα,Gβ)。

定义3：最大公共子图。给定图Gα和Gβ，若图G是图Gα和图Gβ的公共子图，且不存在图G′，图G′也是图Gα和图Gβ的公共子图，图G′的节点个数大于图G，则称图G是图Gα和图Gβ的最大公共子图，记作mcs(Gα,Gβ)。

2.1　关联图构建

给定两属性邻接图G1、G2，节点集V1、V2，设二者的关联图为HV，则构建关联图的具体算法步骤如下：

(1)对图G1中的任意一个节点vi∈V1(1≤i≤n)，遍历图G2中每一个节点uj∈V2(1≤j≤m)，组成节点对(vi，uj)，若vi与uj具有相同的属性值，则将(vi，uj)加入关联图HV的节点集VH作为其一个节点。

(2)任取关联图HV中的2个节点uH=(u1，u2)和vH=(v1，v2)，若u1≠v1，u2≠v2，且图G1中的边e1=(u1，v1)与图G2中的边e2=(u2，v2)具有相同的属性值或图G1中的节点u1和v1，图G2中的节点u2和v2各不相邻，则构造一条边eH=〈uH，vH〉，并加入到关联图HV的边集EH中作为其一条边，其中，第1种类型的边称为连通边，第2种类型的边称为非连通边。

图5a所示为根据图4中2个属性邻接图构建的关联图，图中数字代表图节点标号，根据步骤(1)，查找节点类型相同的顶点对集合，关联图由节点NaA、NaB、NaG、NbD、NbF、NdA、NdB、NdG、NcC和NcE组成；根据步骤(2)，根据各节点边的属性对关联图的10个顶点对进行连接，连通边用实线表示，非连通边用虚线表示。红色圈内的顶点集合即为关联图的最大团，局部结构挖掘问题就转换成检测关联图中最大团问题。为了求解问题的方便，构建关联图的邻接矩阵，如图5b所示，矩阵中数字0代表节点之间没有连通关系，数字1代表节点之间是非连通关系，数字2代表两者之间是连通关系。

图5　关联图及其邻接矩阵Fig.5　Association graph and its matrix

2.2　基于模拟退火算法的典型结构挖掘方法

最大团问题是图论中的一类经典组合优化问题，其求解算法目前主要分为精确算法和启发式算法。精确算法最常用的是枚举算法[18-19]；由于最大团问题的算法复杂度比较高，因此现在更多的研究均倾向采用高效率的启发式算法。因此，本文将利用模拟退火算法来求解最大团问题，先给出极大团与最大团的定义：

定义4：极大团、最大团。对于给定图G=(V，E)。其中，V={1，2，…，n}是图G的顶点集，E⊆V×V是图G的边集。G的团就是一个两两之间有边的顶点集合。如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为G的极大团。顶点最多的极大团，称之为G的最大团。

由最大团的定义可知，最大团问题的可行解是一个满足一定约束条件的顶点集合，为了与解的表示相一致，提高算法效率，本文以能够检索CAD模型中典型相关结构信息的关联图的矩阵G作为输入(矩阵大小为n)；同时为了增强返回模型的多样性以方便灵活地进行不同设计阶段的设计重用工作，以挖掘出的子结构矩阵即关联图矩阵中的极大团S为输出(为保证所挖掘的子结构具备一定工程意义，规定子结构矩阵大小k最小值为3)。在本文模拟退火算法中，初始温度T设定为1 000，终止温度Tend设定为0.1，温度变化系数r是0.99，目标函数为Fit(S)=k(k-1)-Mij以计算子图的适应度f，函数中的Mij为求解某最大团中元素不为0个数之和，当寻找到目标最大团时，函数适应值是0。本文模拟退火算法的具体步骤如下：

(1)根据子图大小k，利用Swap函数从容器中随机选取节点构成初始子图Sinitial，同时利用目标函数函数Fit(S)=k(k-1)-Mij计算初始子图的适应度finitial，剩余n-k节点构成剩余子图Sremainder。

(2)进入循环，结合Swap函数从当前初始子图中任意选取节点u，利用Cald函数计算u在Sinitial中顶点的度du，从剩余子图Sremainder中任意选取一个节点v，计算v替换u之后在Sinitial中顶点的度dv，如果dv值不小于du，就接受新结构，而如果dv小于du，从剩余子图Sremainder中重新任意选取节点，且若重复8n次后dv仍小于du，则新结构度不满足要求。

(3)计算新结构的适应值fnew，如果finitial≤fnew，接受此结构，如果finitial>fnew，则以一定概率接受此结构。

(4)算法温度T以一定速率r递减，循环执行步骤(2)，直至寻找到目标适应值f的结构或者温度达到终止点Tend之后，程序退出，完成此次典型结构挖掘。

本文模拟退火算法的伪代码如表2所示。

表2　模拟退火算法伪代码Tab.2　Pseudo code of simulated annealing algorithm

2.3　相似性计算

在利用模拟退火算法查找关联图中最大团的过程中，只需要查找到极大团即可，查找出的极大团对应于典型结构和CAD模型所共同包含的公共子图，因此采用极大团的节点个数除以典型结构面的个数来描述局部相似性，即

式中Sc——局部相似度

Nm——所有极大团节点的个数

N——典型结构中面的个数

S越大表示2个模型局部相似性越高。

3　算法验证与讨论

为了验证算法的有效性，以Microsoft Visual Studio 2010为集成开发环境，Open CASCADE为几何造型平台，实验中所使用的模型主要来自于普渡大学的ESB[20]模型库和项目组成员根据国家科技支撑计划项目“农机专业底盘数字化设计技术研究与示范”和国家重点研发计划项目“丘陵山地拖拉机关键技术研究与整机开发”与“农机装备智能化设计技术研究”构建的农业机械装备模型库。

3.1　基于模拟退火算法的典型结构挖掘实例

表3所示的是基于模拟退火算法在图4b的CAD模型中挖掘图4a的典型结构的执行过程。算法共执行311次，以一定概率跳出当前可能局部解的次数为129次，由于新结构度不满足要求，执行8n次后退出的次数是163次；适应度从最初10开始，有不断减小且趋于稳定的趋势；从全局上讲，由于算法以一定概率接受适应度变大的局部典型结构，部分区域适应度波动较大；当适应度变成0，找到该典型结构。

表4所示为从模型中选取红色标记的典型结构对其进行挖掘，并在模型库中得到的返回模型。可以发现，本文算法可以将带有该局部结构的模型从模型库中全部检索出来，去掉了一些基本相同的模型，选取了15个具有代表性的模型进行了显示。从返回模型中可以看出，典型相关结构往往隐藏在外形各不相同的三维CAD模型中，而本文算法可以有效地将隐含典型结构的CAD模型推送给设计人员，以供设计人员参考。

3.2　算法性能对比与评价

表5展示了本文算法与蚁群算法[21]和遗传算法[22]在通用领域ESB模型库中，以盘形结构为测试对象的典型结构挖掘能力比较，去掉无关模型后，将返回模型按相似度进行排序。从挖掘结果分析，相对于蚁群算法，本文算法以极大团作为输出结果，而这种“模糊模式”的挖掘特性可以返回多层次相似度的模型，并且由于本文算法保证最大公共子图是连通的，典型结构的挖掘结果更符合人的相似性感知，例如表5蚁群算法第2及第6返回模型不符合视觉相似性；相对于遗传算法，本文算法的返回模型数量多，并且具有较高的复杂度，便于设计人员进行深度挖掘。

表3　模拟退火算法执行过程Tab.3　Process of simulated annealing algorithm

表4基于模拟退火算法典型相关结构检索结果
Tab.4Retrievalresultsoftypicalstructurebasedon
simulatedannealingalgorithm

表6和表7展示了本文算法与蚁群算法和遗传算法在农业机械装备模型库中，以稻麦收获机械底盘红色标记的转向油缸和制动机构典型结构为测试对象的挖掘能力比较，去掉无关模型后，将返回模型按相似度大小进行排序。从返回模型中可以发现，对于农业机械复杂零部件，本文算法相比蚁群算法和遗传算法，其返回模型相似度与复杂度层次多样，种类丰富全面，具有很大的灵活性，方便设计人员进行不同阶段的设计工作。

表5盘形结构挖掘的算法性能比较
Tab.5Comparisonofdisktypicalstructureminingabilitybasedonthreealgorithms

表6　转向油缸典型结构挖掘的算法性能比较Tab.6　Comparison of steering cylinder case typical structure mining ability based on three algorithms

表7　制动机构典型结构挖掘的算法性能比较Tab.7　Comparison of brake mechanism case typical structure mining ability based on three algorithms

为了充分对比3种算法的性能，本文分别对通用领域ESB模型库和农业机械装备模型库中的CAD模型进行统计测试，获得了平均查全率-查准率(Precision-Recall，PR)曲线，理想检索结果的曲线应该是一条查准率恒等于1的平行直线，位置靠上的曲线具有较高精度，代表着较好的检索结果。从PR曲线显然可以看出，本文算法的检索性能明显高于蚁群算法和遗传算法，如图6所示。

图6　平均查全查准率曲线Fig.6　Precision-recall curves

本文算法的时间复杂度主要集中在利用模拟退火算法查找最大团。实验所用测试机CPU为Intel Pentium 4 CPU 3.06 GHz，内存4 GB。本文算法、蚁群算法和遗传算法对单个模型的平均处理时间分别为0.136、0.251、0.303 s，由此可以看出，本文算法的时间效率高于其他2种算法。

4　结束语

提出了一种基于模拟退火算法实现三维CAD模型典型结构挖掘与相似性评价的方法，即利用模拟退火算法检测产品CAD模型属性邻接图之间所构造关联图的最大团，以有效挖掘模型中的典型结构并完成相似性评价，解决了目前产品数字化设计中的面向产品特征级和局部结构级的设计重用粒度粗、精度差、智能化水平低的问题。实验结果表明，本文方法具备较优的典型结构挖掘能力，算法运行效率高，便于设计人员进行CAD模型设计重用工作。

1张田会, 张发平, 阎艳, 等. 基于本体和知识组件的夹具结构智能设计[J]. 计算机集成制造系统, 2016, 22(5): 1165-1178.

ZHANG Tianhui, ZHANG Faping, YAN Yan, et al. Intelligent fixture configuration design based on ontology and knowledge components[J]. Computer Integrated Manufacturing Systems, 2016, 22(5): 1165-1178.(in Chinese)

2王儒, 王国新, 阎艳, 等. 支持产品智能化设计的知识服务方法研究[J]. 兵工学报, 2016, 37(11): 2101-2113.

WANG Ru, WANG Guoxin, YAN Yan, et al. Knowledge service method for supporting product intellectualized design[J]. Acta Armamentarii, 2016, 37(11): 2101-2113.(in Chinese)

3BRIERE C A, RIVEST L, DESPOCHERS A. Adaptive generic product structure modeling for design reuse in engineer-to-order products[J]. Computer in Industry, 2010, 61(1): 53-65.

4郏维强, 刘振宇, 刘达新，等. 基于模糊关联的复杂产品模块化设计方法及其应用[J]. 机械工程学报, 2015, 51(5): 130-142.

JIA Weiqiang, LIU Zhenyu, LIU Daxin, et al. Modular design method and application for complex product based on fuzzy correlation analysis[J]. Journal of Mechanical Engineering, 2015, 51(5): 130-142.(in Chinese)

5OSADA R, FUNKHOUSER T, CHAZELLE B, et al. Shape distributions[J].ACM Transactions on Graphics, 2002, 21(4): 807-832.

6陶松桥, 王书亭, 郑坛光, 等. 基于非精确图匹配的CAD模型搜索方法[J]. 计算机辅助设计与图形学学报, 2010, 22(3): 545-552.

TAO Songqiao, WANG Shuting, ZHENG Tanguang, et al. CAD model retrieval based on inexact graph matching[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(3):545-552.(in Chinese)

7TSAI C Y, CHANG C A. A two-stage fuzzy approach to feature-based design retrieval[J]. Computers in Industry, 2005, 56(5): 493-505.

8宋正河, 毕淑琴, 金晓萍, 等. 履带式收获机械传动系快速设计推理方法[J/OL]. 农业机械学报, 2013, 44(增刊2): 268-272.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=2013s250&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.S2.050.

SONG Zhenghe, BI Shuqin, JIN Xiaoping, et al. Rapid design reasoning method for crawler harvester transmission system[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(Supp.2): 268-272.(in Chinese)

9陆长明, 张立彬, 蒋建东, 等. 基于模板重构的小型农业作业机变异设计方法[J]. 农业工程学报, 2009, 25(10): 101-106.

LU Changming, ZHANG Libin, JIANG Jiandong, et al. Variantional design of small agricultural machinery based on templates reconfiguration[J]. Transactions of the CSAE, 2009,25(10):101-106.(in Chinese)

10张开兴, 杭晟煜, 赵秀艳, 等. 面向设计重用的三维CAD模型局部结构检索方法[J/OL]. 农业机械学报, 2017, 48(7): 405-412.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20170752&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2017.07.052.

ZHANG Kaixing, HANG Shengyu, ZHAO Xiuyan, et al. Effective subpart retrieval method of 3D CAD models for design reuse[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7): 405-412.(in Chinese)

11李海生, 孙莉, 吴晓群, 等. 基于模型内二面角分布直方图的非刚性三维模型检索[J]. 计算机辅助设计与图形学学报, 2017, 29(6): 1128-1134.

LI Haisheng, SUN Li, WU Xiaoqun, et al.Non-rigid 3D shape retrieval based on inner dihedral angle histogram[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(6): 1128-1134.(in Chinese)

12高雪瑶, 李慧楠, 张春祥, 等. 基于蚁群搜索的三维CAD模型相似性计算[J]. 西南交通大学学报, 2017, 52(2): 416-423.

GAO Xueyao, LI Huinan, ZHANG Chunxiang, et al.Similarity calculation of 3D CAD model based on ant colony searching[J]. Journal of Southwest Jiaotong University, 2017, 52(2): 416-423.(in Chinese)

13王玉, 马浩军, 何玮, 等. 机械三维CAD模型的聚类和检索[J]. 计算机集成制造系统, 2006, 12(6): 924-928.

WANG Yu, MA Haojun, HE Wei, et al.Clustering & retrieval of mechanical 3D CAD models[J].Computer Integrated Manufacturing Systems, 2006, 12(6): 924-928.(in Chinese)

14孙家广. 计算机图形学[M]. 3版. 北京: 清华大学出版社, 1998.

15王洪申，张树生，白晓亮, 等. 三维CAD模型局部结构检索属性图算法[J]. 计算机辅助设计与图形学学报, 2008, 20(3):316-320.

WANG Hongshen, ZHANG Shusheng, BAI Xiaoliang, et al.A partial retrieval algorithm of 3D CAD models based on attributed graphs[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(3):316-320.(in Chinese)

16刘雪梅, 张树生, 崔卫卫, 等. 逆向工程中基于属性邻接图的加工特征识别[J]. 计算机集成制造系统,2008,14(6):1162-1167.

LIU Xuemei, ZHANG Shusheng, CUI Weiwei, et al.Machined features recognition based on attributed adjacency graph in reverse engineering[J]. Computer Integrated Manufacturing Systems, 2008,14(6):1162-1167.(in Chinese)

17Open CASCAD technology [EB/OL]. (2006-5-10). http:∥www.epencascade.org.

18BORN C, KERBOSCH J. Algorithm 457: finding all cliques of an undirected graph [J]. Communications of the ACM, 1973, 16(9):575-579.

19KOCH I. Enumerating all connected maximal common subgraphs in two graphs [J]. Theoretical Computer Science, 2001, 250(1):1-30.

20JAYANTI S, KALYANARAMAN Y, IYER N, et al. Developing an engineering shape benchmark for CAD models [J]. Computer-Aided Design, 2006, 38(9): 939-953.

21FENET S, SOLNON C. Searching for maximum cliques with ant colony optimization[J].Application of Evolutionary Computing, LNCS,2003,26(11):236-245.

22李亮, 张树生, 白晓亮, 等. 基于遗传算法的三维CAD模型多特征融合和检索[J]. 制造业自动化, 2013(3): 78-81.

LI Liang, ZHANG Shusheng, BAI Xiaoliang, et al. 3D CAD model retrieval using a genetic feature combination method[J]. Manufacturing Automation, 2013(3): 78-81.(in Chinese)