基于改进算法的MBD模型信息提取方法与运用*

苗凤金,邵云鹏,祝锡晶,成 全,张 洪

(中北大学 机械与动力工程学院,太原 030051)

基于改进算法的MBD模型信息提取方法与运用*

苗凤金,邵云鹏,祝锡晶,成 全,张 洪

(中北大学 机械与动力工程学院,太原 030051)

为了更高效地提取MBD模型工艺信息,提出基于改进递归深度优先遍历算法的MBD模型工艺信息的提取方法,详细介绍了此方法的应用过程。该方法以Visual Studio2012为平台,将模型的组成信息和工艺信息存入多叉树中,通过构建和遍历多叉树,运用层级控制,可以只遍历任意一段子树并输出其信息,避免了遍历全部信息的情况。借此不同职位工作者根据自身需求,可只遍历和输出所需内容。最后辅以实例验证了该方法的可行性,并且越是复杂的模型,其优越性越明显。

提取;改进;深度优先遍历算法;筛选

0 引言

MBD(Model-based-definition)技术首先在航空领域被提出，而后迅速发展。它将工程信息全集合到一个三维模型中，使传统的二维工程图和三维模型结合的方式发展为产品的整个生命周期都只使用一个集成的三维模型的模式。由于不同的平台都可以通过这一个模型来各自传递信息，所以实现了设计、工艺、制造、检验等环节的高度集中[1]。

MBD的工艺信息涵盖了产品生产制造中的所有工艺信息，这与传统的三维模型相比，其信息量是非常巨大的，另外越是结构复杂的产品，其包括的信息越多。在对其进行三维标注的时候就越容易出现各种问题，如标注重叠、混乱等，导致工作者无法直观识别标注的信息。虽然现今对于MBD工艺信息模型的标注有部分研究，但需要标注的信息量随着三维模型的复杂程序增加也在加大，所以仍然会有标注混乱现象出现，如图1所示。

图1 三维模型标注混乱现象

为了避免这种现象，可以使三维模型信息进行层次化表达。三维模型的层次化表达，就是对工艺信息分类处理，以图像或图形的方式对处理过的信息进行相应表达，这样的表达方式较为清晰，所以使用者可以方便阅读和查看对应的信息，三维模型的层次化表达对计算机图形处理有很高的要求[2]。其可以将要表达的信息在模型中显示，隐藏不需要的信息，从而使三维模型的标注更加合理，有利于信息查看。

针对三维模型方面，已有一些学者做了相应研究。赵鸣等[3]介绍了一种基于体分解的最大加工特征识别及工艺路线生成方法，Balic J等[4]介绍了一种从模型中提取信息的方法，Huang R等[5]介绍了一种从模型中提取子部件的方法，王煜[6]等介绍了轻量化模型的非递归深度优先遍历算法的信息提取方法和三维模型可视化技术。已有文献中较少有信息提取方法，其中，王煜在信息提取中的非递归深度优先遍历算法每次都需遍历所有信息，而不同职位的工作者所需信息不同，也许只需要其中部分信息，遍历所有信息会增加查找信息时间，而在过多的信息中查找所需内容也较容易出错，为了改进其算法，提出本文方法。

本文提出将MBD模型的所有非几何信息不在模型中显示出来，而是将其信息按层级依次存储在多叉树中，而当工作者需要其信息时，只需遍历多叉树，便可得到其信息。这样的信息标注与模型的分离方法在某种程度上实现了模型的轻量化，也避免了上述的模型标注信息混乱问题和内容过多对计算机的运行内存要求高的问题。

1 递归深度优先遍历算法

1.1 递归

在利用算法设计来解决问题中，递归[7-8]是一种较为常用的方法。

1.2 深度优先遍历算法

树的每个节点可以有两个以上的子节点，称为m阶多叉树，也称m叉树。由于深度优先搜索的E-节点是分多次进行扩展的，所以它可以搜索到所有已有的节点。

下面以一个例子来说明如何使用深度优先遍历[9-10]算法来遍历一个多叉树并得到其中信息。

算法的整个遍历搜索区大约可分为四个信息层，分别为三维模型(第一层)、结构分类(第二层)、部件组成(第三层)、零件组成(第四层)，为描述方便，可将各个层级的节点分别命名为源点V、根节点Pi、子节点Mi和叶节点Si。运行算法时，程序会按指定路径对每个节点都进行一次且只进行一次访问。这种搜索方法就称为深度优先搜索(Depth-FirstSearch)，该方法优先对纵向的节点进行搜索访问，并从中提取对应的工艺信息。如图2所示，具体步骤路线如下：

图2 三维模型信息层次组成的多叉树结构

(1)访问初始源点V，提取其中写入信息，并将其节点设置为已访问；

(2)遍历与其相邻节点P1，提取其节点内容，并将其设置为已访问；

(3)根据标识访问其关联邻接点M1，遍历其部件部分并得到其中信息，将其设为已访问；

(4)继续访问M1邻接点S1，得到其内容并将其设为已访问；

(5)然后依次遍历M1子节点下的S2到最后一个Si，并得到其中写入内容；

(6)重复步骤(4)、(5)，分别遍历各部件组成和零件组成的节点，得到其信息，回到(2)继续循环，一直到所有与起始源点相通的节点都被遍历到为止，然后结束程序，输出结果。

2 改进的递归深度优先遍历算法

为了实现只遍历部分节点得到其内容的目的，在深度优先遍历算法的基础上，加入了层级管理控制，通过控制层级来控制得到的输出信息。图3为技术路线图。

2.1 多叉树的构建

多叉树中的节点有两个域，分别用来表示节点名及一个数组，其中数组存储了该子节点的地址。一个多叉树的建立，输入格式为AB，其中A表示节点名，而B则表示该节点的子节点个数。根据用户需求，可自定义输入信息，首先建立一个新节点，而后根据B值进行深度优先遍历的调用，输入节点的顺序就是深度递归遍历的顺序。下面以一个例子简单说明多叉树存储数据的过程。

图3 改进算法技术路线图

如图4所示，为一个多叉树结构，若要将此多叉树构造出来，可先建立一个文本文档，在其中编写文本来实现内容的存储。文本结构如下：

V3P1P2P3

P1 3M1M2M3

P2 3M4M5M6

P3M7M8M9

图4 多叉树的数据结构

可以看到文本中共有四行字母数字组合，第一行首字母V为源点名，第二个数字为与其邻接的根节点的数量，接着的字母为各个根节点名。第二、三、四行同理。这样就完成了图4多叉树数据结构的存储，其文本文件可供程序调用。

2.2 层级管理控制

为了使不同层级的信息层次性更加明显，通过增加空格来达到目的。从源点开始，每降低一层，则在输出时，其对应的节点信息均比上级信息靠后3个字符位。这样，工作者查看时便能直观的看出不同节点信息的层级和从属关系。

在信息提取时，使用者只需改变所需节点名称，便可只提取其对应节点下的所有节点信息。

3 程序运行实例

由于本人对功率超声珩磨装置较为熟悉，所以在此以这套装配体为例，实现改进递归深度优先遍历算法对其信息的遍历与输出。

功率超声珩磨装置主要是在普通珩磨装置中加入了超声振动系统，使油石座产生纵向振动，达到需求的振幅，并能实现机床旋转磨削时的自动加压，达到超声珩磨效果。图5为其装置示意图。

1.挡圈 2.珩磨头体 3.油石 4.油石座 5.挠性杆 6.定心圆盘 7.振动圆盘 8.连接体 9.接线柱 10.集流环与碳刷 11.提手 12.换能器外套筒 13.换能器 14.变幅杆 15.珩磨杆 16.中心顶杆 17.涨芯轴 18.导向条图5 功率超声珩磨装置的机构示意图

图6为功率超声珩磨装置的层级划分多叉树。由于条件限制，不能把所有的信息都放在一张图中，图6为前三层级的划分图。

图6 功率超声珩磨装置前三层信息图

第三层级的每一个结构都有对应的工艺信息，以其中一个换能器为例说明其第四层结构，如图7所示。

首先遍历整个装配体的所有信息，输入结果如图8所示。

图7 换能器的工艺信息

若因职位不同，并不需要所有的信息，只需要部分信息时，只遍历部分子树，然后输出其信息即可。比如只需要声振系统的信息时，结果见图9，其余同理。

如若只需要声振系统中的变幅杆的工艺信息，则只遍历变幅杆，如图10所示，其余同理。

图8 完整的遍历信息

图9 声振系统的 遍历输出结果

综上可知，运用改进的递归深度优先遍历算法来遍历模型信息可以极大的减少不同职位工作者的工作量，这不只体现在遍历输出信息的过程，更是在工作者从大量信息中筛选出自己所需信息中得到淋漓尽致的体现。若模型较为复杂时，由于部件、零件很多，如果从全部信息提取自身所需内容则耗时巨大，而这时，利用本文的改进算法则可以直接提取所需内容，避免了查找耗时，其算法的优越性更加明显。

图10 变幅杆的工艺信息 遍历输出结果

4 结论

本文提出的改进的递归深度优先遍历算法相比于非递归深度优先遍历算法，能根据自身需求，只得到部分所需信息，避免了每次均遍历所有信息再从中自己查找的弊端。以功率超声珩磨装置的信息提取进行算法验证，证明了其算法的优越性，为复杂、大型模型提供了信息提取的思路。

[1] 庄乾宇.基于MBD的零件工艺信息模型建模方法研究与实现[D].太原:中北大学,2016.

[2]Rezayat M. Some aspects of product and process development in the 21st Centery [J]. Computer Aided Design,2000(32):83-87．

[3]赵鸣, 王细洋. 基于体分解的MBD工序模型快速生成方法[J]. 计算机集成制造系统,2014, 20(8): 1843-1850.

[4]Balic J, Klancnik S, Brezovnik S. Feature extraction from CAD model for milling strategy prediction[J]. Strojniski Vestnik-Journal Of Mechanical Engineering. 2008, 54(5):301-307.

[5]Huang R, Zhang SS, Bai XL, et al. An effective subpart retrieval approach of 3D CAD models for manufacturing process reuse[J]. Computers In Industry,2014, 67: 38-53.

[6]王 煜,吉卫喜,钱德成，等.MBD 模式下机械产品的三维轻量可视化研究[J].组合机床与自动化技工技术，2015(5)：107-110,112.

[7]朱振元,朱承.递归算法的非递归化实现[J].小型微型计算机系统，2003，24(3)：567-570.

[8]王宏伟,赵国庆.递归算法的参数设置[J].电波科学学报，2010,25(6)：1187-1191.

[9] Li ZJ,Garcia La,JJ. Finding multi-constrained feasible paths by using depth-first search[J]. Wireless Networks,2007, 13(3): 323-334.

[10] Kuo TC,Smith S,Smith GC,et al. A predictive product attribute driven eco-design process using depth-first search[J]. Journal Of Cleaner Production,2016, 112: 3201-3210.

(编辑 李秀敏)

收稿日期：2016-12-04；修回日期：2016-12-19

*基金项目：国家自然科学基金资助项目(51365015)；江西省科技厅科技项目(20142BBE50058)

作者简介：伍建军(1974—)，男，四川营山人，江西理工大学副教授，博士，研究方向为工业工程、质量与可靠性研究,(E-mail)391485400@qq.com；通讯作者：廖泰健(1992—)，男，江西赣州人，江西理工大学硕士研究生，研究方向为质量与可靠性研究，(E-mail)905447835@qq.com。

An Information Extraction Method and Application of MBD Model Based on Improved Algorithm

MIAO Feng-jin, SHAO Yun-peng, ZHU Xi-jing, CHENG Quan, ZHANG Hong

(School of Mechanical and Power Engineering,North University of China ,Taiyuan 030051,China)

To extract the technology information of MBD model, this paper proposes a method based on improved recursive depth-first search algorithm.It introduces the process of the method concretely.The method took the Visual Studio2012 as platform, and achieved the goal of traversing and output the information of arbitrary subtree through saving the composition and technology of the model into multi-tree, building and traversing multi-way tree, using the hierarchical control, which avoided the situation of traversing all information.In this way, different workers in diverse positions just traverse and output the content they need according to individual requirement.Eventually, an example was quoted to demonstrate the feasibility of the algorithm.More complicated the model is, more excellent it is.

extraction; improve; depth-first search; filtrate

1001-2265(2017)05-0085-03

10.13462/j.cnki.mmtamt.2017.05.022

2016-11-29；

2016-12-31

国家自然科学基金项目(51275490);山西省自然科学基金(201601D011061);航空制造工艺数字化国防重点学科实验室开放基金(SHSYS2015003)；中北大学第十三届研究生科技立项(20161314)

苗凤金(1992—)，男，河北沧州人，中北大学硕士研究生，研究方向为精密与特种加工技术，(E-mail)15513039003@163.com。

TH166;TG506

A

编号：1001-2265(2017)05-0088-04 DOI:10.13462/j.cnki.mmtamt.2017.05.023