基于子图同构的三维CAD 模型局部匹配探讨

李倩

摘要：为了有效解决结构匹配无法精确实施的问题，该文将从子图同构原理出发对三维CAD模型局部结构匹配算法进行探索。在该算法中通过对CAD模型的B-Rep信息的提取，用以面作为节点的属性连接图将其展现出来。局部匹配过程中用子图表示用户输入的局部结构，用大图表示带匹配的整体CAD模型。这样就可以通过寻找大图中同构子图解决检索局部结构的问题。根据CAD模型的面特征细分图顶点，并利用已匹配点之间的临界关系对搜索空间进行动态剪裁，这样同构匹配的迅速就会大大增加。

关键词：子图同构；三维CAD模型；局部匹配

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）13-0179-02

现阶段产品设计、产品制造、产品虚拟仿真等机械设计和制造环节中已经广泛运用了三维建模软件，这样企业内容的三维CAD模型数量就会迅速增加。设计人员在工作中常常需要参照企业已有模型进行新产品设计，通过相似形设计或改型设计能够有效带动设计效率的提升。然而，对于一些大型制造企业而言，由于具备庞大数量的CAD模型，怎样让设计人员从中找到所需要的模型就成为另一个必须解决的问题，本文将尝试通过三维模型检索解决这个问题。

1 CAD模型局部匹配总体思路

实际中，完全自动识别出直接给定任意的两个三维CAD模型相思局部结构还存在一定难度，但是还没有较好的方法能够解决这个问题，并且这样的需求在实际应用CAD领域还相对较少。相反设计人员在设计的过程中，往往非常关注零件上某一个局部结构，进而将具备该局部结构零件从已有产品模型中各发掘出来，并依次为依据和参考。这样设计人员就能够检索自己感兴趣的局部结构，一般通过以下两种方式输入：将已有CAD模型直接打开，然后拾取局部结构的多个面；利用建模工具对局部结构进行完全自定义。

为了实现局部匹配的目标，首先需要对属性邻接图进行设计，并对CAD模型中B-Rep信息进行提取，这样就能够用一个属性邻接图表示CAD模型。通过提取已经输入的局部结构B-Rep信息，就能够产生小属性邻接图，该图作为“子图”。同时还应当提取待匹配的模型库中的每一个整体三维CAD模型，这样就能够获得一个大属性邻接图，这样通过在大图中寻找子图就能够解决在整体三维CAD模型中检索制定局部结构的问题。

2 构建属性邻接图

由于多媒体可视化模型具有较低的精度要求，所以通过三维网络模型近似表示即可。但CAD具有较高的精度要求，所以在表示过程中通常运用B-Rep模型。B-Rep模型中的一个三维CAD模型包括n各三维空间曲面，多条边围成每个曲面，每个顶点确定每条边。通过对每个顶点、每条边、每个曲面的精确描述，整个三维CAD模型就能够准确的反映出来。通过将三维CAD模型中B-Rep信息转化为属性邻接图，其中每一个模型的面都存在对应图顶点，顶点具有面的几何属性。顶点之间的关系反映与模型中的面之间的关系，共面、垂直、平行、供边等是常见的关系。

3 局部匹配

1）图同构概述

看两个图之间是否存在一个映射是判断两个图是否同构的关键，这样两个图之间对应的不仅包括点还包括边。当前图同构问题计算还较为复杂，但是已经证明子图同构问题是一个NP问题，实际中包含四种求解方法，其中提出时间最长、且应用最广泛的就是ullmann算法。由CAD模型转换得到的一种特定的属性邻接图是本文研究的对象，所以必须充分运用CAD模型自身特征进行子图同构匹配算法的设计，进而推动算法匹配效率的提升[1]。

2）子图同构匹配算法思路

为了达到降低搜索空间杂复程度的目的，应当通过先验知识的运用尽可能增加M元素为0的个数，这样就需要细分图的顶点。实际当中从一定规则出发将图的顶点划分为若干个子集就是顶点细分，在同构中不可能匹配不同子集的顶点。可见不可能的顶点对应关系通过有效的定点细分，在一开始就能够得到有效的排除。本文算法在细分图的顶点时，主要考虑的是CAD模型的面的特征。CAD模型的面与CAD模型转换得到的属性邻接图顶点存在一一对应的关系，因此在进行顶点细分时可以运用CAD模型面的特征。

3）算法分析

因为子图同构的本质是NP完全问题，所以相应的都是复杂度高的求解算法，并且还具有算法性能不稳定的弊端。为了实现提升匹配效率，本文从两个方面进行了优化：首先在进行细分图顶点过程中充分的结合和考虑了CAD模型面的特征；在进行快速的剪枝搜索中运用已匹配上的顶点所组成的子图对应同构这一原理。属性邻接图是本文研究的对象，主要通过转化三维CAD模型的面后获得。应当以顶点对应模型的面的类型和面的特征出发，细分图顶点，这样初始时矩阵元素等于0的数量就会增加，搜索空间复杂程度相应的就会降低[2]。

4 试验及结果分析

为了在CAD模型局部检索中验证本算法的效果，本文进行了局部结构库和三维CAD模型库的构建。其中，三维CAD模型库中包含四百多个典型CAD模型，例如箱类、轴类、盘类等，这些模型具有不同的复杂程度，所具备的面数也在几个至几百个之间。局部结构库中既包含由几个面构成的孔、槽，也包括由数十个面构成的用户自定义结构，共囊括八十个典型结构。本文针对该模型和局部结构库的试验包括三个方面。

实验一。当待检索局部结构具有一定数量的面时，对待匹配的整体三维CAD模型的面数量进行调整，对匹配所需时间进行测量。研究整体三维CAD模型复杂度的增长匹配时间带来的影响是进行这项实验的目的，根据图1可知实验结果，其中整体三维CAD模型面的数量通过横轴表示，匹配所需时间t通过纵轴表示。局部结构面的个数、也就是图顶点个数表示为m，根据图1a可知如果整体三维CAD模型面数量控制在一定范围内，那么匹配时间t和面的数量之间体现为线性关系[3]。

实验二。当待匹配整体三维CAD模型具有确定数量的面时，对检索局部结构的面数量记性调整，进而测量匹配时间，研究局部结构复杂度的增长给匹配时间造成的影响是该项试验的目的。图1a为实验结果，其中局部结构面的数量由横轴表示，匹配所需时间由纵轴表示。整体三维CAD模型面的个数也就是大图顶点的个数由n表示。根据图1b可知，如果三维CAD模型面的数量不超过200时，局部结构复杂度和匹配时间存在线性关系。如果三维CAD模型面数量大于400时，局部结构越复杂匹配时间增长幅度越大[4]。

实验三。以试验一、二维基础，对比试验最著名的Ullmann算法和本文算法，两种算法的综合性能比较如下。如图1c、1d为试验结果，其中相同条件下Ullmann算法匹配时间与本文算法匹配时间的比表示为纵轴r。通过图1a、1c可知，本算法和ullmann算法在n和m较小的情况下具有相同的效率，但是本算法在n和m较大的情况下具有比ullmann算法更高的效率。例如在m=40、n=400时，ullmann算法完成一次匹配使用的时间，本文算法能够实现三百次匹配[5]。

5 结论

本文中的支持局部匹配的三维CAD模型检索算法，不同于基于统计特征提取的检索算法，它首先用属性邻接图替代CAD模型，然后用子图同构问题替代局部结构匹配问题。在对子图同构匹配算法进行设计时，首先根据CAD模型面的特征预先细分属性邻接图的顶点，这样初始搜索空间复杂度就会大幅降低。在进行动态搜索的过程中，应当以匹配上的顶点对组成的子图应对应同构这一原理出发，将不可能对应关系尽早排除掉，搜索进程就能够大幅提升，最终达到提升匹配迅速的目的。根据实验结果可知，精确的局部结构匹配能够通过这种算法得到有效实现，同时实际检索需求也能够得到充分满足。

参考文献：

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

[2] 王成，张树生，张开兴等.基于回转面归并的CAD模型局部检索算法[J].微处理机，2011，32（5）：53-57.

[3] 郑坛光.三维CAD模型检索技术研究[J].华中科技大学报2011，32（5）：3-7.

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

[5] 陶松桥.面向设计的三维CAD模型搜索技术研究[J].华中科技大学报，2012，20（3）：16-20.