苗鳳金,邵云鵬,祝錫晶,成 全,張 洪

(中北大學(xué) 機(jī)械與動(dòng)力工程學(xué)院,太原 030051)

基于改進(jìn)算法的MBD模型信息提取方法與運(yùn)用*

苗鳳金,邵云鵬,祝錫晶,成 全,張 洪

(中北大學(xué) 機(jī)械與動(dòng)力工程學(xué)院,太原 030051)

為了更高效地提取MBD模型工藝信息,提出基于改進(jìn)遞歸深度優(yōu)先遍歷算法的MBD模型工藝信息的提取方法,詳細(xì)介紹了此方法的應(yīng)用過程。該方法以Visual Studio2012為平臺(tái),將模型的組成信息和工藝信息存入多叉樹中,通過構(gòu)建和遍歷多叉樹,運(yùn)用層級(jí)控制,可以只遍歷任意一段子樹并輸出其信息,避免了遍歷全部信息的情況。借此不同職位工作者根據(jù)自身需求,可只遍歷和輸出所需內(nèi)容。最后輔以實(shí)例驗(yàn)證了該方法的可行性,并且越是復(fù)雜的模型,其優(yōu)越性越明顯。

提取;改進(jìn);深度優(yōu)先遍歷算法;篩選

0 引言

MBD(Model-based-definition)技術(shù)首先在航空領(lǐng)域被提出，而后迅速發(fā)展。它將工程信息全集合到一個(gè)三維模型中，使傳統(tǒng)的二維工程圖和三維模型結(jié)合的方式發(fā)展為產(chǎn)品的整個(gè)生命周期都只使用一個(gè)集成的三維模型的模式。由于不同的平臺(tái)都可以通過這一個(gè)模型來各自傳遞信息，所以實(shí)現(xiàn)了設(shè)計(jì)、工藝、制造、檢驗(yàn)等環(huán)節(jié)的高度集中[1]。

MBD的工藝信息涵蓋了產(chǎn)品生產(chǎn)制造中的所有工藝信息，這與傳統(tǒng)的三維模型相比，其信息量是非常巨大的，另外越是結(jié)構(gòu)復(fù)雜的產(chǎn)品，其包括的信息越多。在對(duì)其進(jìn)行三維標(biāo)注的時(shí)候就越容易出現(xiàn)各種問題，如標(biāo)注重疊、混亂等，導(dǎo)致工作者無法直觀識(shí)別標(biāo)注的信息。雖然現(xiàn)今對(duì)于MBD工藝信息模型的標(biāo)注有部分研究，但需要標(biāo)注的信息量隨著三維模型的復(fù)雜程序增加也在加大，所以仍然會(huì)有標(biāo)注混亂現(xiàn)象出現(xiàn)，如圖1所示。

圖1 三維模型標(biāo)注混亂現(xiàn)象

為了避免這種現(xiàn)象，可以使三維模型信息進(jìn)行層次化表達(dá)。三維模型的層次化表達(dá)，就是對(duì)工藝信息分類處理，以圖像或圖形的方式對(duì)處理過的信息進(jìn)行相應(yīng)表達(dá)，這樣的表達(dá)方式較為清晰，所以使用者可以方便閱讀和查看對(duì)應(yīng)的信息，三維模型的層次化表達(dá)對(duì)計(jì)算機(jī)圖形處理有很高的要求[2]。其可以將要表達(dá)的信息在模型中顯示，隱藏不需要的信息，從而使三維模型的標(biāo)注更加合理，有利于信息查看。

針對(duì)三維模型方面，已有一些學(xué)者做了相應(yīng)研究。趙鳴等[3]介紹了一種基于體分解的最大加工特征識(shí)別及工藝路線生成方法，Balic J等[4]介紹了一種從模型中提取信息的方法，Huang R等[5]介紹了一種從模型中提取子部件的方法，王煜[6]等介紹了輕量化模型的非遞歸深度優(yōu)先遍歷算法的信息提取方法和三維模型可視化技術(shù)。已有文獻(xiàn)中較少有信息提取方法，其中，王煜在信息提取中的非遞歸深度優(yōu)先遍歷算法每次都需遍歷所有信息，而不同職位的工作者所需信息不同，也許只需要其中部分信息，遍歷所有信息會(huì)增加查找信息時(shí)間，而在過多的信息中查找所需內(nèi)容也較容易出錯(cuò)，為了改進(jìn)其算法，提出本文方法。

本文提出將MBD模型的所有非幾何信息不在模型中顯示出來，而是將其信息按層級(jí)依次存儲(chǔ)在多叉樹中，而當(dāng)工作者需要其信息時(shí)，只需遍歷多叉樹，便可得到其信息。這樣的信息標(biāo)注與模型的分離方法在某種程度上實(shí)現(xiàn)了模型的輕量化，也避免了上述的模型標(biāo)注信息混亂問題和內(nèi)容過多對(duì)計(jì)算機(jī)的運(yùn)行內(nèi)存要求高的問題。

1 遞歸深度優(yōu)先遍歷算法

1.1 遞歸

在利用算法設(shè)計(jì)來解決問題中，遞歸[7-8]是一種較為常用的方法。

1.2 深度優(yōu)先遍歷算法

樹的每個(gè)節(jié)點(diǎn)可以有兩個(gè)以上的子節(jié)點(diǎn)，稱為m階多叉樹，也稱m叉樹。由于深度優(yōu)先搜索的E-節(jié)點(diǎn)是分多次進(jìn)行擴(kuò)展的，所以它可以搜索到所有已有的節(jié)點(diǎn)。

下面以一個(gè)例子來說明如何使用深度優(yōu)先遍歷[9-10]算法來遍歷一個(gè)多叉樹并得到其中信息。

算法的整個(gè)遍歷搜索區(qū)大約可分為四個(gè)信息層，分別為三維模型(第一層)、結(jié)構(gòu)分類(第二層)、部件組成(第三層)、零件組成(第四層)，為描述方便，可將各個(gè)層級(jí)的節(jié)點(diǎn)分別命名為源點(diǎn)V、根節(jié)點(diǎn)Pi、子節(jié)點(diǎn)Mi和葉節(jié)點(diǎn)Si。運(yùn)行算法時(shí)，程序會(huì)按指定路徑對(duì)每個(gè)節(jié)點(diǎn)都進(jìn)行一次且只進(jìn)行一次訪問。這種搜索方法就稱為深度優(yōu)先搜索(Depth-FirstSearch)，該方法優(yōu)先對(duì)縱向的節(jié)點(diǎn)進(jìn)行搜索訪問，并從中提取對(duì)應(yīng)的工藝信息。如圖2所示，具體步驟路線如下：

圖2 三維模型信息層次組成的多叉樹結(jié)構(gòu)

(1)訪問初始源點(diǎn)V，提取其中寫入信息，并將其節(jié)點(diǎn)設(shè)置為已訪問；

(2)遍歷與其相鄰節(jié)點(diǎn)P1，提取其節(jié)點(diǎn)內(nèi)容，并將其設(shè)置為已訪問；

(3)根據(jù)標(biāo)識(shí)訪問其關(guān)聯(lián)鄰接點(diǎn)M1，遍歷其部件部分并得到其中信息，將其設(shè)為已訪問；

(4)繼續(xù)訪問M1鄰接點(diǎn)S1，得到其內(nèi)容并將其設(shè)為已訪問；

(5)然后依次遍歷M1子節(jié)點(diǎn)下的S2到最后一個(gè)Si，并得到其中寫入內(nèi)容；

(6)重復(fù)步驟(4)、(5)，分別遍歷各部件組成和零件組成的節(jié)點(diǎn)，得到其信息，回到(2)繼續(xù)循環(huán)，一直到所有與起始源點(diǎn)相通的節(jié)點(diǎn)都被遍歷到為止，然后結(jié)束程序，輸出結(jié)果。

2 改進(jìn)的遞歸深度優(yōu)先遍歷算法

為了實(shí)現(xiàn)只遍歷部分節(jié)點(diǎn)得到其內(nèi)容的目的，在深度優(yōu)先遍歷算法的基礎(chǔ)上，加入了層級(jí)管理控制，通過控制層級(jí)來控制得到的輸出信息。圖3為技術(shù)路線圖。

2.1 多叉樹的構(gòu)建

多叉樹中的節(jié)點(diǎn)有兩個(gè)域，分別用來表示節(jié)點(diǎn)名及一個(gè)數(shù)組，其中數(shù)組存儲(chǔ)了該子節(jié)點(diǎn)的地址。一個(gè)多叉樹的建立，輸入格式為AB，其中A表示節(jié)點(diǎn)名，而B則表示該節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)。根據(jù)用戶需求，可自定義輸入信息，首先建立一個(gè)新節(jié)點(diǎn)，而后根據(jù)B值進(jìn)行深度優(yōu)先遍歷的調(diào)用，輸入節(jié)點(diǎn)的順序就是深度遞歸遍歷的順序。下面以一個(gè)例子簡單說明多叉樹存儲(chǔ)數(shù)據(jù)的過程。

圖3 改進(jìn)算法技術(shù)路線圖

如圖4所示，為一個(gè)多叉樹結(jié)構(gòu)，若要將此多叉樹構(gòu)造出來，可先建立一個(gè)文本文檔，在其中編寫文本來實(shí)現(xiàn)內(nèi)容的存儲(chǔ)。文本結(jié)構(gòu)如下：

V3P1P2P3

P1 3M1M2M3

P2 3M4M5M6

P3M7M8M9

圖4 多叉樹的數(shù)據(jù)結(jié)構(gòu)

可以看到文本中共有四行字母數(shù)字組合，第一行首字母V為源點(diǎn)名，第二個(gè)數(shù)字為與其鄰接的根節(jié)點(diǎn)的數(shù)量，接著的字母為各個(gè)根節(jié)點(diǎn)名。第二、三、四行同理。這樣就完成了圖4多叉樹數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)，其文本文件可供程序調(diào)用。

2.2 層級(jí)管理控制

為了使不同層級(jí)的信息層次性更加明顯，通過增加空格來達(dá)到目的。從源點(diǎn)開始，每降低一層，則在輸出時(shí)，其對(duì)應(yīng)的節(jié)點(diǎn)信息均比上級(jí)信息靠后3個(gè)字符位。這樣，工作者查看時(shí)便能直觀的看出不同節(jié)點(diǎn)信息的層級(jí)和從屬關(guān)系。

在信息提取時(shí)，使用者只需改變所需節(jié)點(diǎn)名稱，便可只提取其對(duì)應(yīng)節(jié)點(diǎn)下的所有節(jié)點(diǎn)信息。

3 程序運(yùn)行實(shí)例

由于本人對(duì)功率超聲珩磨裝置較為熟悉，所以在此以這套裝配體為例，實(shí)現(xiàn)改進(jìn)遞歸深度優(yōu)先遍歷算法對(duì)其信息的遍歷與輸出。

功率超聲珩磨裝置主要是在普通珩磨裝置中加入了超聲振動(dòng)系統(tǒng)，使油石座產(chǎn)生縱向振動(dòng)，達(dá)到需求的振幅，并能實(shí)現(xiàn)機(jī)床旋轉(zhuǎn)磨削時(shí)的自動(dòng)加壓，達(dá)到超聲珩磨效果。圖5為其裝置示意圖。

1.擋圈 2.珩磨頭體 3.油石 4.油石座 5.撓性桿 6.定心圓盤 7.振動(dòng)圓盤 8.連接體 9.接線柱 10.集流環(huán)與碳刷 11.提手 12.換能器外套筒 13.換能器 14.變幅桿 15.珩磨桿 16.中心頂桿 17.漲芯軸 18.導(dǎo)向條圖5 功率超聲珩磨裝置的機(jī)構(gòu)示意圖

圖6為功率超聲珩磨裝置的層級(jí)劃分多叉樹。由于條件限制，不能把所有的信息都放在一張圖中，圖6為前三層級(jí)的劃分圖。

圖6 功率超聲珩磨裝置前三層信息圖

第三層級(jí)的每一個(gè)結(jié)構(gòu)都有對(duì)應(yīng)的工藝信息，以其中一個(gè)換能器為例說明其第四層結(jié)構(gòu)，如圖7所示。

首先遍歷整個(gè)裝配體的所有信息，輸入結(jié)果如圖8所示。

圖7 換能器的工藝信息

若因職位不同，并不需要所有的信息，只需要部分信息時(shí)，只遍歷部分子樹，然后輸出其信息即可。比如只需要聲振系統(tǒng)的信息時(shí)，結(jié)果見圖9，其余同理。

如若只需要聲振系統(tǒng)中的變幅桿的工藝信息，則只遍歷變幅桿，如圖10所示，其余同理。

圖8 完整的遍歷信息

圖9 聲振系統(tǒng)的 遍歷輸出結(jié)果

綜上可知，運(yùn)用改進(jìn)的遞歸深度優(yōu)先遍歷算法來遍歷模型信息可以極大的減少不同職位工作者的工作量，這不只體現(xiàn)在遍歷輸出信息的過程，更是在工作者從大量信息中篩選出自己所需信息中得到淋漓盡致的體現(xiàn)。若模型較為復(fù)雜時(shí)，由于部件、零件很多，如果從全部信息提取自身所需內(nèi)容則耗時(shí)巨大，而這時(shí)，利用本文的改進(jìn)算法則可以直接提取所需內(nèi)容，避免了查找耗時(shí)，其算法的優(yōu)越性更加明顯。

圖10 變幅桿的工藝信息 遍歷輸出結(jié)果

4 結(jié)論

本文提出的改進(jìn)的遞歸深度優(yōu)先遍歷算法相比于非遞歸深度優(yōu)先遍歷算法，能根據(jù)自身需求，只得到部分所需信息，避免了每次均遍歷所有信息再從中自己查找的弊端。以功率超聲珩磨裝置的信息提取進(jìn)行算法驗(yàn)證，證明了其算法的優(yōu)越性，為復(fù)雜、大型模型提供了信息提取的思路。

[1] 莊乾宇.基于MBD的零件工藝信息模型建模方法研究與實(shí)現(xiàn)[D].太原:中北大學(xué),2016.

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

[3]趙鳴, 王細(xì)洋. 基于體分解的MBD工序模型快速生成方法[J]. 計(jì)算機(jī)集成制造系統(tǒng),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]王 煜,吉衛(wèi)喜,錢德成，等.MBD 模式下機(jī)械產(chǎn)品的三維輕量可視化研究[J].組合機(jī)床與自動(dòng)化技工技術(shù)，2015(5)：107-110,112.

[7]朱振元,朱承.遞歸算法的非遞歸化實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng)，2003，24(3)：567-570.

[8]王宏偉,趙國慶.遞歸算法的參數(shù)設(shè)置[J].電波科學(xué)學(xué)報(bào)，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

*基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(51365015)；江西省科技廳科技項(xiàng)目(20142BBE50058)

作者簡介：伍建軍(1974—)，男，四川營山人，江西理工大學(xué)副教授，博士，研究方向?yàn)楣I(yè)工程、質(zhì)量與可靠性研究,(E-mail)391485400@qq.com；通訊作者：廖泰健(1992—)，男，江西贛州人，江西理工大學(xué)碩士研究生，研究方向?yàn)橘|(zhì)量與可靠性研究，(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

國家自然科學(xué)基金項(xiàng)目(51275490);山西省自然科學(xué)基金(201601D011061);航空制造工藝數(shù)字化國防重點(diǎn)學(xué)科實(shí)驗(yàn)室開放基金(SHSYS2015003)；中北大學(xué)第十三屆研究生科技立項(xiàng)(20161314)

苗鳳金(1992—)，男，河北滄州人，中北大學(xué)碩士研究生，研究方向?yàn)榫芘c特種加工技術(shù)，(E-mail)15513039003@163.com。

TH166;TG506

A

編號(hào)：1001-2265(2017)05-0088-04 DOI:10.13462/j.cnki.mmtamt.2017.05.023