基于面拓扑关联约束的三维实体模型检索方法

摘要

本发明公开了一种基于面拓扑关联约束的三维实体模型检索方法。该方法首先生成实体模型的平行、包含、共面及L型、T型、X型垂直或相交共六类面关系组成的模型面拓扑关联约束集，之后对实体模型中最常见的平行面对进行合并，以简化面拓扑关联约束集、并生成对应的六类归并面拓扑关联约束集。在检索三维实体模型时，以面拓扑关联约束集近似度计算来比较其拓扑及几何细节。本发明的有益之处在于，通过面拓扑关联约束的快速比较，可从全局拓扑关系及局部拓扑/几何细节两个层次，在大规模三维产品数据库中快速定位相似的三维实体模型，从而提高三维产品设计的复用水平。

说明书

技术领域

本发明涉及一种基于面拓扑关联约束的三维实体模型检索方法，且特别涉及一种通过六类面拓扑关系及在此基础上作平行面对归并后的归并面拓扑关联约束集比较的三维实体模型快速检索方法。

背景技术

在过去十年中，随着3D图形硬件成本的降低和技术的成熟，三维CAD设计技术在机械、制造、建筑、电子、化工、服装乃至广告等众多领域中得到快速发展和应用。据统计，近年来模具制造工业中3D CAD建模已占80％左右。

三维CAD实体模型在数量及复杂性上迅速增加的同时，三维产品数据的复用问题逐步出现。一般而言，设计者平均花费60％的工作时间用于产品信息的检索。Gunn则进一步指出，进行新产品设计时，仅约20％来自真正的创新，40％可从现有设计获取，另外40％则可在修改现有设计的基础上获得。Ullman认为，超过75％的新设计包含着对以往设计知识的复用。产品复用已成为CAD领域中的关键问题。三维形状检索(3D shape searching)是解决三维产品复用的有效途径。根据Kendall的定义，三维形状检索是指“在大型三维模型数据库中计算三维形状之间的相似度”。深入研究三维实体模型的检索机制，必然有助于促进三维CAD技术深化应用、提高三维CAD设计的自动化水平、加快产品创新开发，具有重要的理论意义和实际应用价值。

发明内容

发明目的：本发明针对现有技术的不足，提供了一种基于面拓扑关联约束的三维实体模型检索方法。

技术方案：本发明公开了一种基于面拓扑关联约束的三维实体模型检索方法，该方法包括以下步骤：

步骤1，给定三维实体模型的产品数据库，输入待检索的三维实体模型；

步骤2，判断是否已从输入的待检索实体模型生成其对应的面拓扑关联约束的描述文件，若判断结果为是则转步骤12；

步骤3，若步骤2的结果为否，则读取实体模型的顶点、边、面、环等几何数据；

步骤4，生成该实体模型的面包含关系图R_IN，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面有包含关系；

步骤5，生成该实体模型的共面关系图R_I，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面共面、但无包含关系；

步骤6，生成该实体模型的面平行关系图R_P，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面互相平行、但不共面且无包含关系；

步骤7，生成该实体模型的模型面L型垂直或相交关系图R_L，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为L型垂直或相交关系；

步骤8，生成该实体模型的模型面T型垂直或相交关系图R_T，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为T型垂直或相交关系；

步骤9，生成该实体模型的模型面X型垂直或相交关系图R_X，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为X型垂直或相交关系；将模型面拓扑关联约束集G_TOPO＝{R_IN，R_I，R_P，R_L，R_T，R_X}写入相应的描述文件；

步骤10，遍历R_P中各节点，将相互重叠比例最大且距离最小的两个平行面合并为一个新的面对节点；

步骤11，若面包含关系图R_IN、共面关系图R_I、模型面L型垂直或相交关系图R_L、模型面T型垂直或相交关系图R_T、模型面X型垂直或相交关系图R_X中包含步骤10中被合并的两个平行面对，则从该关系图中以步骤10所生成的面对节点替换掉这两个面，并重建该面对节点与其它节点间的包含关系、共面关系、L型垂直或相交关系、T型垂直或相交关系、X型垂直或相交关系，得到归并后的归并面拓扑关联约束集G’_TOPO＝{R’_IN，R’_I，R’_P，R’_L，R’_T，R’_X}，并写入相应的描述文件；

步骤12，逐一取产品数据库中的三维实体模型及其对应的归并面拓扑关联约束集描述文件；

步骤13，比较待检索模型及产品数据库中模型的归并面拓扑关联约束集，并计算其相似度；

步骤14，按归并后面拓扑关联约束集相似度比较结果，比较其模型面拓扑关联约束集，以作进一步的几何细节的局部比较，提高三维检索的精确度；

步骤15，判断模型数据库是否遍历结束，若结果为否，则转步骤12；

步骤16，若步骤15的判断结果为是，则将各近似度从大到小排序后输出；

步骤17，返回本次检索结果；

步骤18，根据近似度比较结果是否为“1”判断所输入的待检索模型是否已加入产品模型数据库，若判断结果为是，则返回步骤1；

步骤19，若步骤18结果为否，则将所输入的实体模型、对应的模型面拓扑关联约束集及归并面拓扑关联约束集描述文件加入到产品数据库，并返回步骤1。

本发明中，待检索的三维实体模型及产品数据库中的三维实体模型应符合STEP标准，但对其坐标系定义、实体模型大小、旋转方向无特别要求。

本发明中，面拓扑关联约束分为两个层次：通过初始模型面拓扑关系分析生成的模型面拓扑关联约束集G_TOPO＝{R_IN，R_I，R_P，R_L，R_T，R_X}，及节点归并后生成的归并面拓扑关联约束集G’_TOPO＝{R’_IN，R’_I，R’_P，R’_L，R’T，_RX}；

本发明中，组成模型面拓扑关联约束集的六类面关系图R_IN、R_I、R_P、R_L、R_T、R_X中，节点对应于某模型面、边对应于某种拓扑关系；模型面的几何特征(如法向量、面积、形状等)则作为面关系图中节点的属性列出，以作三维检索时的几何细节比较或局部检索。

本发明中，组成归并面拓扑关联约束集的六类归并面关系图R’_IN、R’_I、R’_P、R’_L、R’_T、R’_X中，节点对应于一个符合相互投影面重叠比例最大、同时距离最小的平行面对，边对应于六类拓扑关系中的一种。

本发明中，某三维实体模型所对应的归并面拓扑关联约束集描述文件由XML定义。

本发明中，某三维实体模型所对应的模型面拓扑关联约束集描述文件由XML定义。

本发明中，根据归并面拓扑关联约束计算两个实体模型相似度的方法是：

Similarity(M，N)＝Similar(R’_P(M)，R’_P(N)/6+Similar(R’_L(M)，R’_L(N))/6

                 +Similar(R’_IN(M)，R’_IN(N))/6+Similar(R’_I(M)，R’_I(N))/6

                 +Similar(R’_T(M)，R’_T(N))/6+Similar(R’_XM)，R’_XN))/6

其中，M、N表示两个实体模型，Similar(R₁，R₂)为计算两个图最大匹配度的现存函数；Similarity()函数的取值范围为[0，100％]。

本发明中，进一步的几何细节的局部比较方法是取六类模型面关系图中的面几何属性作比较；其中面几何属性包括面的类型、面的法向量、面的周长与面积、面内边的数量。

本发明中，判断待检索模型是否已加入产品数据库的方法是：检查是否有与待检索模型相似度为100％的模型存在，若判断结果为是，则产品数据库中已加入，否则未加入。

有益效果：本发明方法从CAD数据表达及产品交换相关ISO标准STEP(Standard for the Exchange of Product Information)/IGES(Initial Graphics ExchangeStandard)出发，在兼容绝大多数主流CAD模型描述方式基础上，提取、分析三维实体模型几何形状描述，分别生成由包含、平行、共面、L型垂直或相交、T型垂直或相交、X型垂直或相交共六类面关系组成的模型面拓扑关联约束集；在此基础上对符合投影重叠比例及距离约束的平行面对作归并，生成归并面拓扑关联约束集。在检索三维实体模型时，以归并面拓扑关联约束集比较为出发点，快速计算模型间相似度；并可根据全局拓扑约束的不同，进一步比较面类型、法向量、边数等属性，作进一步的几何细节区分。

由于目前在三维设计领域，超过75％的新设计包含着对以往设计知识的复用，而设计者平均需花费60％的工作时间用于以往产品的检索。因此，通过面拓扑关联约束的快速比较，可从全局拓扑关系及局部拓扑/几何细节两个层次，在大规模三维产品数据库中快速定位相似的三维实体模型，从而提高三维产品设计的复用水平、加快产品创新开发能力，并有助于促进三维CAD技术深化应用。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明。

图1表示本发明的工作流程图。

图2为一个三维实体模型的实例。

图3为从该三维实体模型生成的模型面平行关系图R_p。

图4为从该三维实体模型生成的模型面L型垂直或相交关系图R_L。

图5为从该三维实体模型生成的模型面包含关系图R_IN。

图6为R_P中节点归并的例子。

图7为节点归并后生成归并面平行关系图R’_p。

图8为节点归并后生成归并面L型垂直或相交关系图R’_L。

具体实施方式

如图1所示，本发明公开了一种基于面拓扑关联约束的三维实体模型检索方法，该方法包括以下步骤：

步骤1，给定三维实体模型的产品数据库，输入待检索的三维实体模型；

步骤2，判断是否已从输入的待检索实体模型生成其对应的面拓扑关联约束的描述文件，若判断结果为是则转步骤12；

步骤3，若步骤2的结果为否，则读取实体模型的顶点、边、面、环等几何数据；

步骤4，生成该实体模型的面包含关系图R_IN，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面有包含关系；

步骤5，生成该实体模型的共面关系图R_I，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面共面、但无包含关系；

步骤6，生成该实体模型的面平行关系图R_P，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面互相平行、但不共面且无包含关系；

步骤7，生成该实体模型的模型面L型垂直或相交关系图R_L，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为L型垂直或相交关系；

步骤8，生成该实体模型的模型面T型垂直或相交关系图R_T，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为T型垂直或相交关系；

步骤9，生成该实体模型的模型面X型垂直或相交关系图R_X，该图中的一个节点对应于一个实体模型的面，一条边表示其所连接的两个模型面为X型垂直或相交关系；将模型面拓扑关联约束集G_TOPO＝{R_IN，R_I，R_P，R_L，R_T，R_X}写入相应的描述文件；

步骤10，遍历R_P中各节点，将相互重叠比例最大且距离最小的两个平行面合并为一个新的面对节点；

步骤11，若面包含关系图R_IN、共面关系图R_I、模型面L型垂直或相交关系图R_L、模型面T型垂直或相交关系图R_T、模型面X型垂直或相交关系图R_X中包含步骤10中被合并的两个平行面对，则从该关系图中以步骤10所生成的面对节点替换掉这两个面，并重建该面对节点与其它节点间的包含关系、共面关系、L型垂直或相交关系、T型垂直或相交关系、X型垂直或相交关系，得到归并后的归并面拓扑关联约束集G’_TOPO＝{R’_IN，R’_I，R’_P，R’_L，R’_T，R’_X}，并写入相应的描述文件；

步骤12，逐一取产品数据库中的三维实体模型及其对应的归并面拓扑关联约束集描述文件；

步骤13，比较待检索模型及产品数据库中模型的归并面拓扑关联约束集，并计算其相似度；

步骤14，按归并后面拓扑关联约束集相似度比较结果，比较其模型面拓扑关联约束集，以作进一步的几何细节的局部比较，提高三维检索的精确度；

步骤15，判断模型数据库是否遍历结束，若结果为否，则转步骤12；

步骤16，若步骤15的判断结果为是，则将各近似度从大到小排序后输出；

步骤17，返回本次检索结果；

步骤18，根据近似度比较结果是否为“1”判断所输入的待检索模型是否已加入产品模型数据库，若判断结果为是，则返回步骤1；

步骤19，若步骤18结果为否，则将所输入的实体模型、对应的模型面拓扑关联约束集及归并面拓扑关联约束集描述文件加入到产品数据库，并返回步骤1。

更具体地说，图1中的步骤1初始所输入的实体模型由STEP格式定义，且对实体模型大小、方向、角度无特殊要求。

步骤4-步骤9在读取模型几何数据后，生成六类面关系图R_IN、R_I、R_P、R_L、R_T及R_X，具体步骤是：1)遍历各模型面A，取实体模型中其它任一模型面B，若符合以下六类面拓扑约束关系，则将模型A及模型面B作为节点加入对应的面关系图，并连以一条边：

1)$R_{\mathrm{IN}}(A,B)=\{\forall a\in A,a\in B\};$

2)

3)

4)

5)

6

在图2给出的CAD实体模型示例中，若定义RIN(A)＝{B：rin(A，B)}，则图1的模型面拓扑关联约束集可描述如下：

R_P(F₁)＝{F₃}，R_P(F₂)＝{F₄}，

R_P(F₃)＝{F₁}，R_P(F₄)＝{F₂}，

R_L(F₁)＝R_L(F₃)＝{F₂，F₄，F₅，F₆}，

R_L(F₂)＝R_L(F₄)＝{F₁，F₃，F₅，F₆}，

R_IN(F₅)＝{F₇，F₉}，R_P(F₅)＝{F₆，F₈，F₁₀}，

R_L(F₅)＝R_L(F₆)＝{F₁，F₂，F₃，F₄}，

R_IN(F₆)＝{F₈，F₁₀}，R_P(F₆)＝{F₅，F₇，F₉}，

R_P(F₇)＝{F₈，F₉，F₁₀}，R_P(F₈)＝{F₇，F₉，F₁₀}，

R_P(F₉)＝{F₇，F₈，F₁₀}，R_P(F₁₀)＝{F₇，F₈，F₉}

图3为对应于图2所示三维实体模型的模型面平行关系图R_p，图4为从该三维实体模型生成的模型面L型垂直或相交关系图R_L，而图5为从该三维实体模型生成的模型面包含关系图R_IN。该实体模型中无满足共面、T型垂直或相交、X型垂直或相交关系的模型面，因此R_I、R_T及R_X均为空。

步骤10对符合投影重叠比例及距离的平行面对进行归并，生成归并后的面平行关系图R’_P。R’_P生成步骤如下：

(1)遍历R_P图各边。设当前边为e_i，取e_i连接的两个节点f_i1及f_i2，令

d(f_i1，f_i2)＝area(overlap(f_i1，f_i2))/min(area(f_i1)，area(f_i2))

计算d(f_i1，f_i2)并将其按由小到大次序分别加入节点f_i1及f_i2的面距离集(其中area(f_i)为面积，overlap(f_i，f_j)为重叠面)；

(2)遍历R_P图各节点。设当前节点为f_i。取f_i面距离集中最大值所对应的节点集S(f_i)，按如下优先次序选择其中某节点f_j生成候选面对<f_i，f_j>；

a)area(f_i)＝area(f_j)；

b)$\forall f_k\in S\left(f_i\right),\forall f_j\in S\left(f_i\right),\mathrm{dis}(f_i,f_j)\le \mathrm{dis}(f_i,f_k)$

其中dis(f_i，f_j)为面距离；

(3)遍历(2)生成的候选面对集，按如下方法对R_P图归并，得到对应的面拓朴关联图R’_P(R’_P初始为空)：

a)复制R_P图中的所有节点到R’_P图；

b)遍历R_P中所有边，若其所连接节点f_i及f_k属于候选面对集，则合并f_i及f_k得到新节点PF(f_i，f_k)，将PF(f_i，f_k)加入R’_P图；

c)遍历R’_P图中各节点，设已存在某节点PF_j(f_j1，f_j2)，若f_j1、f_i、f_j2与f_i之间在原R_P图中有边连接，则在R’_P图中在节点PF_j(f_j1，f_j2)及PF(f_i，f_k)之间添加一条边；

(4)遍历R’_P中各节点，计算其最大连通子图R’_Pmax，以R’_Pmax法向作为模型主方向。

其中，(1)、(2)生成候选面对集，(3)以候选面对集对R_P归并，得到R’_P；(4)计算最大连通子图以确定模型主方向。图6给出了对应于图3所示R_P中节点归并的过程，其归并结果R’_P在图7中显示。

步骤11在R’_P生成后，结合该过程中所涉及的归并节点，分别重新计算R_L，R_in，R_I，R_T，R_X，以生成R’_L，R’_in，R’_I，R’_T，R’_X。其中R’_L生成算法如下：

(1)R’_L置空；

(2)遍历R_L各节点。设当前节点为f_i。遍历节点f_i各边，若在R_L中存在两条边(f_i，f_j)及(f_i，f_k)(j≠k)，且f_j及f_k已在R’_P中合并，则：

a)在R’_L中添加新节点VF(f_j，f_k)；

b)若f_i不在R’_L图中：

i若f_i无法和任何已有节点合并，则添加新节点VF(f_i，^)；

ii否则若f_i可与R’_L图中节点VF(f_m，^)合并(即可构成R’_P中合并节点)，

合并成新节点VF(f_m，f_i)；

c)否则f_i已存在于R’_L图中，返回；

d)在R’_L图中上述两个对应节点间添加连接边；

图8给出了对应于图4的归并后的R’_L图。R’_in，R’_I，R’_T，R’_X可按类似方法生成。

步骤16-18比较实体模型并按近似度排序后输出。设Similar(A，B)为用于计算两个图A与B的相似度的现存函数，则三维实体模型近似度计算方法为：

Similarity(M，N)＝Similar(R’_P(M)，R’_P(N)/6+Similar(R’_L(M)，R’_L(N))/6

                 +Similar(R’_IN(M)，R’_IN(N))/6+Similar(R’_I(M)，R’_I(N))/6

                 +Similar(R’_T(M)，R’_T(N))/6+Similar(R’_XM)，R’_XN))/6

其中M、N为任意两个实体模型。将所输入的实体模型和产品数据库中各模型逐一比较并计算近似度后，按近似度值从大到小逐一排序，将对应模型输出。

本发明提供了一种基于面拓扑关联约束的三维实体模型检索方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部份均可用现有技术加以实现。