基于层次图匹配的三维CAD模型表征方法

丁博++石熙++李峰

【摘 要】 由于三维CAD模型具有十分复杂的几何形状和拓扑结构，如何准确的描述三维CAD模型，从而提高三维CAD模型的检索效率，成为当前迫切需要解决的问题。本文提出了一种基于层次图的三维CAD模型表征方法，层次图中包含了特征依赖图和属性邻接图所描述的模型信息，因此，形状特征描述符和拓扑关系描述符都可以在层次图中提取，描述符的提取方便、准确。同时，多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节，提高了三维CAD模型表征的准确性和灵活性。

【关键词】 三维CAD模型表征 层次图 特征依赖图 属性邻接图

随着计算机技术和计算机图形学的不断发展，三维CAD已经渗透到工业生产中的各个方面，成为记录和表达工程设计的主要载体[1]。有关研究表明，新产品开发中重用现有的或供应商提供的零部件占40%，修改后重用的零部件占40%，完全全新设计的零部件仅占20%[2]。据估计变型设计或自适应设计约占到其中的90%，这表明大多数的设计工作可重用以前的产品设计知识。根据产品之间的相似性，最大限度地重用已有的设计资源来开发新产品，不仅可以降低产品成本，缩短设计时间，而且还可有效的提高产品可靠性，保证产品质量[3]。因此，准确的表征三维CAD模型是实现三维CAD模型检索的先决条件。

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型检索，提高了三维CAD模型的搜索效率。

1 相关知识介绍

目前，基于参数化的特征造型技术已经非常成熟，大部分数字化造型设计软件都采用了特征造型方法。特征造型系统的体系结构是一种三层结构：底层是数据模型，由特征依赖图（Feature Dependency Graph， FDG）表示，中间层是细胞元几何模型，最上层是视图模型[4]。

1.1 特征依赖图

特征依赖图（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征间的依赖关系，提供了造型的高层结构[5]。特征依赖图的形式化定义为：，其中，V={1，2，…，n}是特征依赖图的节点集合；是特征依赖图的边集；是一个从节点集合到其属性集合的映射，其中是节点的属性集合；是一个从边集合到其属性集合的映射，其中为边的属性集合。图1是一个CAD模型，图2是它的特征依赖图表示。

1.2 细胞元模型

在CAD系统中，细胞元模型表示CAD模型的几何信息，主要采用边界表示（Boundary Representation，B-Rep）方法。三维CAD模型的属性邻接图（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通过提取CAD模型中的B-Rep信息，将CAD模型转化为属性邻接图。图3为图1的属性邻接图。

2 基于层次图的三维CAD模型表征

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节。

本文通过构建层次图实现三维CAD模型的多层次描述，层次图中包含了特征依赖图和属性邻接图所描述的模型信息。图4是图1所示CAD模型的层次图。基于层次图进行三维CAD模型检索时，始终以粗层次信息为主导确定匹配的整体走势，以细层次信息为辅助调整匹配的局部细节，这种匹配方案既符合人类的认知过程，又能够保证模型多个层次间匹配的一致性。

定义1层次图（Hierarchical Graph， HG）是由五元组表示的一棵树：

其中V为树的特征节点集合；为树的边集合，其元素为有序节点对，由父节点指向子节点；是一个从节点集合到属性邻接图集合的映射，对每一个节点，存在，表征节点v对应的属性邻接图；是一个从节点集合到其属性集合的映射，Wv是节点的属性集合；是一个从边集合到其属性集合的映射，其中WE为边的属性集合。

层次图与一般的图不同，图中的每一个节点对应一个属性邻接图，故层次图结构中存在两种类型的节点，即属性图中的节点和层次图自身的节点。相应地，边也有属于内部属性邻接图的边和对应层次图的边。在检索的过程中，不仅仅要考虑其层次图自身的节点以及边的匹配，还要考虑其节点内部属性邻接图中节点及边的匹配，二者间相互关联，彼此影响。

2.1 形状特征的提取

为了有效地支持粗粒度的三维CAD模型检索，我们在特征依赖图中将提取相关的属性，包括：“特征类型”、“依赖关系”和“层次”， 特征类型指的是层次图中特征的类型；依赖关系是指特征间必须满足的依存关系；层次记录了特征所属的层次。

2.2 拓扑关系的提取

拓扑关系是指CAD模型的点、线、面、环之间的连接关系。三维CAD模型的拓扑关系从属性邻接图中提取，属性邻接图的形式化定义为：，其中，V={1，2，…，n}是属性邻接图的节点集合，是属性邻接图的边集。B-Rep模型中的每一个面都有唯一的顶点Vi相对应，因此，顶点Vi的属性即为模型中面的属性，面的属性包括：面的几何类型、面的凹凸性、外环边的数量、外环边的几何类型和外环边的凹凸性等信息。E为面的邻接关系，任意两个面都有唯一一条边与之对应。边的属性包括：边的凹凸性和边所连接的面类型等信息。

3 结语

本文提出了一种基于层次图的三维CAD模型表征方法。层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型表征，该方法描述三维CAD模型正确、灵活，为三维CAD模型检索提供了有利的先决条件。

参考文献：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，张树生.基于特征邻接图的三维CAD模型检索算法[J].机械科学与技术，2012，31（4）：583-587.

[3]潘翔，张三元，叶修梓.三维模型语义检索研究进展[J].计算机学报，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint

【摘 要】 由于三维CAD模型具有十分复杂的几何形状和拓扑结构，如何准确的描述三维CAD模型，从而提高三维CAD模型的检索效率，成为当前迫切需要解决的问题。本文提出了一种基于层次图的三维CAD模型表征方法，层次图中包含了特征依赖图和属性邻接图所描述的模型信息，因此，形状特征描述符和拓扑关系描述符都可以在层次图中提取，描述符的提取方便、准确。同时，多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节，提高了三维CAD模型表征的准确性和灵活性。

【关键词】 三维CAD模型表征 层次图 特征依赖图 属性邻接图

随着计算机技术和计算机图形学的不断发展，三维CAD已经渗透到工业生产中的各个方面，成为记录和表达工程设计的主要载体[1]。有关研究表明，新产品开发中重用现有的或供应商提供的零部件占40%，修改后重用的零部件占40%，完全全新设计的零部件仅占20%[2]。据估计变型设计或自适应设计约占到其中的90%，这表明大多数的设计工作可重用以前的产品设计知识。根据产品之间的相似性，最大限度地重用已有的设计资源来开发新产品，不仅可以降低产品成本，缩短设计时间，而且还可有效的提高产品可靠性，保证产品质量[3]。因此，准确的表征三维CAD模型是实现三维CAD模型检索的先决条件。

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型检索，提高了三维CAD模型的搜索效率。

1 相关知识介绍

目前，基于参数化的特征造型技术已经非常成熟，大部分数字化造型设计软件都采用了特征造型方法。特征造型系统的体系结构是一种三层结构：底层是数据模型，由特征依赖图（Feature Dependency Graph， FDG）表示，中间层是细胞元几何模型，最上层是视图模型[4]。

1.1 特征依赖图

特征依赖图（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征间的依赖关系，提供了造型的高层结构[5]。特征依赖图的形式化定义为：，其中，V={1，2，…，n}是特征依赖图的节点集合；是特征依赖图的边集；是一个从节点集合到其属性集合的映射，其中是节点的属性集合；是一个从边集合到其属性集合的映射，其中为边的属性集合。图1是一个CAD模型，图2是它的特征依赖图表示。

1.2 细胞元模型

在CAD系统中，细胞元模型表示CAD模型的几何信息，主要采用边界表示（Boundary Representation，B-Rep）方法。三维CAD模型的属性邻接图（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通过提取CAD模型中的B-Rep信息，将CAD模型转化为属性邻接图。图3为图1的属性邻接图。

2 基于层次图的三维CAD模型表征

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节。

本文通过构建层次图实现三维CAD模型的多层次描述，层次图中包含了特征依赖图和属性邻接图所描述的模型信息。图4是图1所示CAD模型的层次图。基于层次图进行三维CAD模型检索时，始终以粗层次信息为主导确定匹配的整体走势，以细层次信息为辅助调整匹配的局部细节，这种匹配方案既符合人类的认知过程，又能够保证模型多个层次间匹配的一致性。

定义1层次图（Hierarchical Graph， HG）是由五元组表示的一棵树：

其中V为树的特征节点集合；为树的边集合，其元素为有序节点对，由父节点指向子节点；是一个从节点集合到属性邻接图集合的映射，对每一个节点，存在，表征节点v对应的属性邻接图；是一个从节点集合到其属性集合的映射，Wv是节点的属性集合；是一个从边集合到其属性集合的映射，其中WE为边的属性集合。

层次图与一般的图不同，图中的每一个节点对应一个属性邻接图，故层次图结构中存在两种类型的节点，即属性图中的节点和层次图自身的节点。相应地，边也有属于内部属性邻接图的边和对应层次图的边。在检索的过程中，不仅仅要考虑其层次图自身的节点以及边的匹配，还要考虑其节点内部属性邻接图中节点及边的匹配，二者间相互关联，彼此影响。

2.1 形状特征的提取

为了有效地支持粗粒度的三维CAD模型检索，我们在特征依赖图中将提取相关的属性，包括：“特征类型”、“依赖关系”和“层次”， 特征类型指的是层次图中特征的类型；依赖关系是指特征间必须满足的依存关系；层次记录了特征所属的层次。

2.2 拓扑关系的提取

拓扑关系是指CAD模型的点、线、面、环之间的连接关系。三维CAD模型的拓扑关系从属性邻接图中提取，属性邻接图的形式化定义为：，其中，V={1，2，…，n}是属性邻接图的节点集合，是属性邻接图的边集。B-Rep模型中的每一个面都有唯一的顶点Vi相对应，因此，顶点Vi的属性即为模型中面的属性，面的属性包括：面的几何类型、面的凹凸性、外环边的数量、外环边的几何类型和外环边的凹凸性等信息。E为面的邻接关系，任意两个面都有唯一一条边与之对应。边的属性包括：边的凹凸性和边所连接的面类型等信息。

3 结语

本文提出了一种基于层次图的三维CAD模型表征方法。层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型表征，该方法描述三维CAD模型正确、灵活，为三维CAD模型检索提供了有利的先决条件。

参考文献：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，张树生.基于特征邻接图的三维CAD模型检索算法[J].机械科学与技术，2012，31（4）：583-587.

[3]潘翔，张三元，叶修梓.三维模型语义检索研究进展[J].计算机学报，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint

【摘 要】 由于三维CAD模型具有十分复杂的几何形状和拓扑结构，如何准确的描述三维CAD模型，从而提高三维CAD模型的检索效率，成为当前迫切需要解决的问题。本文提出了一种基于层次图的三维CAD模型表征方法，层次图中包含了特征依赖图和属性邻接图所描述的模型信息，因此，形状特征描述符和拓扑关系描述符都可以在层次图中提取，描述符的提取方便、准确。同时，多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节，提高了三维CAD模型表征的准确性和灵活性。

【关键词】 三维CAD模型表征 层次图 特征依赖图 属性邻接图

随着计算机技术和计算机图形学的不断发展，三维CAD已经渗透到工业生产中的各个方面，成为记录和表达工程设计的主要载体[1]。有关研究表明，新产品开发中重用现有的或供应商提供的零部件占40%，修改后重用的零部件占40%，完全全新设计的零部件仅占20%[2]。据估计变型设计或自适应设计约占到其中的90%，这表明大多数的设计工作可重用以前的产品设计知识。根据产品之间的相似性，最大限度地重用已有的设计资源来开发新产品，不仅可以降低产品成本，缩短设计时间，而且还可有效的提高产品可靠性，保证产品质量[3]。因此，准确的表征三维CAD模型是实现三维CAD模型检索的先决条件。

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型检索，提高了三维CAD模型的搜索效率。

1 相关知识介绍

目前，基于参数化的特征造型技术已经非常成熟，大部分数字化造型设计软件都采用了特征造型方法。特征造型系统的体系结构是一种三层结构：底层是数据模型，由特征依赖图（Feature Dependency Graph， FDG）表示，中间层是细胞元几何模型，最上层是视图模型[4]。

1.1 特征依赖图

特征依赖图（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征间的依赖关系，提供了造型的高层结构[5]。特征依赖图的形式化定义为：，其中，V={1，2，…，n}是特征依赖图的节点集合；是特征依赖图的边集；是一个从节点集合到其属性集合的映射，其中是节点的属性集合；是一个从边集合到其属性集合的映射，其中为边的属性集合。图1是一个CAD模型，图2是它的特征依赖图表示。

1.2 细胞元模型

在CAD系统中，细胞元模型表示CAD模型的几何信息，主要采用边界表示（Boundary Representation，B-Rep）方法。三维CAD模型的属性邻接图（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通过提取CAD模型中的B-Rep信息，将CAD模型转化为属性邻接图。图3为图1的属性邻接图。

2 基于层次图的三维CAD模型表征

本文提出了一种基于层次图的三维CAD模型表征方法，在层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。多层次的模型描述符不仅可以描述造型的总体形状，还可以描述造型的局部细节。

本文通过构建层次图实现三维CAD模型的多层次描述，层次图中包含了特征依赖图和属性邻接图所描述的模型信息。图4是图1所示CAD模型的层次图。基于层次图进行三维CAD模型检索时，始终以粗层次信息为主导确定匹配的整体走势，以细层次信息为辅助调整匹配的局部细节，这种匹配方案既符合人类的认知过程，又能够保证模型多个层次间匹配的一致性。

定义1层次图（Hierarchical Graph， HG）是由五元组表示的一棵树：

其中V为树的特征节点集合；为树的边集合，其元素为有序节点对，由父节点指向子节点；是一个从节点集合到属性邻接图集合的映射，对每一个节点，存在，表征节点v对应的属性邻接图；是一个从节点集合到其属性集合的映射，Wv是节点的属性集合；是一个从边集合到其属性集合的映射，其中WE为边的属性集合。

层次图与一般的图不同，图中的每一个节点对应一个属性邻接图，故层次图结构中存在两种类型的节点，即属性图中的节点和层次图自身的节点。相应地，边也有属于内部属性邻接图的边和对应层次图的边。在检索的过程中，不仅仅要考虑其层次图自身的节点以及边的匹配，还要考虑其节点内部属性邻接图中节点及边的匹配，二者间相互关联，彼此影响。

2.1 形状特征的提取

为了有效地支持粗粒度的三维CAD模型检索，我们在特征依赖图中将提取相关的属性，包括：“特征类型”、“依赖关系”和“层次”， 特征类型指的是层次图中特征的类型；依赖关系是指特征间必须满足的依存关系；层次记录了特征所属的层次。

2.2 拓扑关系的提取

拓扑关系是指CAD模型的点、线、面、环之间的连接关系。三维CAD模型的拓扑关系从属性邻接图中提取，属性邻接图的形式化定义为：，其中，V={1，2，…，n}是属性邻接图的节点集合，是属性邻接图的边集。B-Rep模型中的每一个面都有唯一的顶点Vi相对应，因此，顶点Vi的属性即为模型中面的属性，面的属性包括：面的几何类型、面的凹凸性、外环边的数量、外环边的几何类型和外环边的凹凸性等信息。E为面的邻接关系，任意两个面都有唯一一条边与之对应。边的属性包括：边的凹凸性和边所连接的面类型等信息。

3 结语

本文提出了一种基于层次图的三维CAD模型表征方法。层次图中可以提取两种模型描述符：形状特征描述符和拓扑关系描述符。形状特征描述可以有效描述三维CAD模型的整体形状，拓扑关系描述符用来描述三维CAD模型的局部细节，从而实现了粗粒度和细粒度两个层次的三维CAD模型表征，该方法描述三维CAD模型正确、灵活，为三维CAD模型检索提供了有利的先决条件。

参考文献：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，张树生.基于特征邻接图的三维CAD模型检索算法[J].机械科学与技术，2012，31（4）：583-587.

[3]潘翔，张三元，叶修梓.三维模型语义检索研究进展[J].计算机学报，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint