基于LibreCAD的電火花線切割CAM實(shí)體排序算法研究

沈桂旭，夏蔚文，陶旭牧野，趙萬(wàn)生

（上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海200240）

基于LibreCAD的電火花線切割CAM實(shí)體排序算法研究

沈桂旭，夏蔚文，陶旭牧野，趙萬(wàn)生

（上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海200240）

在電火花線切割CAM軟件的開(kāi)發(fā)過(guò)程中，針對(duì)DXF文件的實(shí)體排序問(wèn)題，提出了基于LibreCAD文件讀取的實(shí)體排序算法，可同時(shí)實(shí)現(xiàn)封閉圖形、非封閉圖形及多圖形文件的實(shí)體排序。通過(guò)分析DXF文件中實(shí)體自身的排序特點(diǎn)，提出了一種用于處理大數(shù)據(jù)量實(shí)體搜索的記憶搜索算法，基于前一步搜索的實(shí)體進(jìn)行區(qū)域內(nèi)智能搜索。經(jīng)過(guò)數(shù)值計(jì)算及實(shí)際測(cè)試對(duì)比，記憶搜索算法能實(shí)現(xiàn)高適應(yīng)性、高準(zhǔn)確率、高效率的實(shí)體搜索與排序。

電火花線切割加工；CAM軟件；DXF文件；實(shí)體排序；記憶搜索算法

電火花線切割常用于加工淬火鋼和硬質(zhì)合金等高熔點(diǎn)、高硬度的特殊金屬材料，在模具制造、刀具加工、精密復(fù)雜零件加工等領(lǐng)域得到廣泛應(yīng)用[1]。其中，往復(fù)走絲電火花線切割機(jī)床因其結(jié)構(gòu)簡(jiǎn)單、性價(jià)比高，在我國(guó)應(yīng)用廣泛。隨著智能制造深入發(fā)展，對(duì)傳統(tǒng)往復(fù)走絲線切割加工的控制技術(shù)也提出了更高的要求。在線切割數(shù)控編程中，多采用DXF文件寫入加工圖形，線切割CAM軟件通過(guò)處理DXF文件，獲取零件的幾何信息，規(guī)劃加工路徑，最后輸出加工G代碼，以實(shí)現(xiàn)零件的加工。CAM軟件的重要功能之一是對(duì)DXF文件中的實(shí)體按加工方向重新排序，將實(shí)體首尾相連。由于線切割加工圖形具有多樣性、復(fù)雜性的特點(diǎn)，且在幾何建模時(shí)的順序也可能隨機(jī)，故準(zhǔn)確、高效的實(shí)體排序算法顯得尤為重要，且能直接決定線切割CAM軟件軌跡規(guī)劃的準(zhǔn)確度和效率。

線切割圖形大多由直線和圓弧組成，讀取DXF文件中的實(shí)體段可獲取單個(gè)實(shí)體的起始與終止位置，從而進(jìn)行連接性判斷與排序。在線切割CAM軟件開(kāi)發(fā)過(guò)程中，相關(guān)科研機(jī)構(gòu)與學(xué)者也提出了相應(yīng)的實(shí)體排序算法。邢海蛟通過(guò)端點(diǎn)距離比對(duì)的方式，獲取與上一實(shí)體距離最近的實(shí)體，實(shí)現(xiàn)圖形中實(shí)體的連續(xù)排序[2]。張為民通過(guò)結(jié)點(diǎn)搜索的方式，遍歷所有實(shí)體對(duì)象，將搜索到的連續(xù)實(shí)體逐一存入結(jié)點(diǎn)，進(jìn)行封閉圖形實(shí)體的重新排序[3]。曹琨等通過(guò)傳統(tǒng)循環(huán)遍歷算法實(shí)現(xiàn)首尾相連實(shí)體的排序，并采用逐步從搜索列表中移除已排序?qū)嶓w的方式，在一定程度上提高了搜索與排序的效率[4]。

在線切割加工的軌跡規(guī)劃過(guò)程中，當(dāng)DXF文件中同時(shí)存在封閉與非封閉圖形時(shí)，傳統(tǒng)排序方式并未進(jìn)行區(qū)分處理，且對(duì)于大數(shù)據(jù)量的實(shí)體圖形，如何進(jìn)行高效完備的排序也非常關(guān)鍵。本文針對(duì)線切割加工軌跡規(guī)劃的這些特點(diǎn)，基于開(kāi)源軟件Libre CAD的DXF實(shí)體讀取API（application programming interface，應(yīng)用程序編程接口），設(shè)計(jì)了實(shí)體排序新算法，有效地進(jìn)行多圖形文件的單獨(dú)圖形實(shí)體排序，統(tǒng)一處理封閉、非封閉圖形的實(shí)體排序。通過(guò)分析DXF文件中原實(shí)體的排序特點(diǎn)，提出了記憶搜索的新算法，極大地提高了大數(shù)據(jù)量圖形（如數(shù)萬(wàn)個(gè)實(shí)體的圖形）的軌跡規(guī)劃效率。

1 LibreCAD與DXF文件讀取

LibreCAD是一款輕量級(jí)開(kāi)源CAD軟件，支持Windows、Mac 及 Linux 系統(tǒng)[5]，支持 DXF、DWG 等圖形文件的導(dǎo)入與讀取，具備豐富的平面圖形繪制功能。LibreCAD底層采用Qt C++編寫[6]，開(kāi)放二次開(kāi)發(fā)的編程接口，基于其提供的實(shí)體讀取API，可方便地實(shí)現(xiàn)對(duì)DXF文件中幾何實(shí)體數(shù)據(jù)信息的讀取。

DXF是一種用于二維圖形數(shù)據(jù)交換的標(biāo)準(zhǔn)文件格式，廣泛用于處理和記錄二維CAD數(shù)據(jù)，特別是在不同的CAD平臺(tái)之間進(jìn)行數(shù)據(jù)交換時(shí)起到了很好的橋梁作用。DXF文件是由可讀的ASCII字符組成的文本文件，其結(jié)構(gòu)見(jiàn)圖1，其實(shí)體段部分包含了圖形中所有幾何實(shí)體的信息[7]。通過(guò)LibreCAD源碼開(kāi)放的getAllEntities函數(shù)，可獲取DXF文件中所有的實(shí)體，并讀取實(shí)體段記錄的具體數(shù)據(jù)信息。

圖1 DXF文件結(jié)構(gòu)

2 多圖形實(shí)體排序算法

針對(duì)存在多個(gè)圖形的線切割圖形文件，若選擇某個(gè)圖形實(shí)體（Entity）對(duì)象（以下簡(jiǎn)稱“實(shí)體”）作為起始段，需從所有實(shí)體中將包含起始段實(shí)體在內(nèi)的獨(dú)立圖形搜索出來(lái)，并按加工順序?qū)?shí)體排序。

為了進(jìn)行連續(xù)實(shí)體搜索，需確定實(shí)體的端點(diǎn)坐標(biāo)，以用于判斷實(shí)體間是否連接。對(duì)于直線段，實(shí)體段中記錄了起點(diǎn)及終點(diǎn)坐標(biāo)等信息；對(duì)于圓弧，實(shí)體段中記錄了圓心坐標(biāo)、半徑、圓弧起始與終止角度、順逆時(shí)針等信息，由此可計(jì)算得到圓弧的起點(diǎn)及終點(diǎn)坐標(biāo)。

假設(shè)圓弧圓心坐標(biāo)為（X，Y），半徑為R，起始角為 α，終止角為 β，設(shè)圓弧起點(diǎn)坐標(biāo)為（X1，Y1），則：

設(shè)圓弧終點(diǎn)坐標(biāo)為（X2，Y2），則：

采用二元數(shù)據(jù)結(jié)構(gòu)對(duì)搜索到的實(shí)體進(jìn)行存儲(chǔ)，兩個(gè)數(shù)據(jù)位分別記錄實(shí)體對(duì)象及方向標(biāo)識(shí)。其中，方向標(biāo)識(shí)為布爾值，實(shí)體本身方向?yàn)閺钠瘘c(diǎn)到終點(diǎn)，當(dāng)實(shí)體方向與加工方向一致時(shí)，方向標(biāo)識(shí)為真，反之，方向標(biāo)識(shí)為假。按照加工方向搜索時(shí)，由方向標(biāo)識(shí)確定當(dāng)前實(shí)體參與搜索的端點(diǎn)，以便搜索下一實(shí)體。此外，方向標(biāo)識(shí)在生成加工代碼階段也起著重要作用。圖2是排序算法實(shí)現(xiàn)過(guò)程，通過(guò)不斷搜索與當(dāng)前端點(diǎn)連接的下一段實(shí)體，進(jìn)而實(shí)現(xiàn)完整圖形的搜索與實(shí)體排序。

圖2 排序算法實(shí)現(xiàn)過(guò)程

封閉圖形搜索的終止條件是：當(dāng)前搜索端點(diǎn)連接至起始實(shí)體。非封閉圖形搜索的終止條件是：未找到連接實(shí)體，即當(dāng)前搜索端點(diǎn)為斷點(diǎn)。達(dá)到任意終止條件，則單個(gè)圖形的所有實(shí)體排序完成，不再進(jìn)行實(shí)體搜索，由此實(shí)現(xiàn)多圖形文件中單獨(dú)圖形的實(shí)體排序。同時(shí)，根據(jù)終止條件類型可判斷當(dāng)前圖形的封閉性。

3 記憶搜索算法

線切割加工的復(fù)雜圖形通常由大量的直線或圓弧擬合而成，在規(guī)劃這類大數(shù)據(jù)量實(shí)體圖形時(shí)，傳統(tǒng)的遍歷算法效率低，會(huì)造成CAM軟件運(yùn)行卡頓甚至卡死的情況。通過(guò)分析發(fā)現(xiàn)，DXF文件中的幾何實(shí)體是按照?qǐng)D形繪制時(shí)的順序排列，對(duì)于大數(shù)據(jù)量實(shí)體圖形，尤其是區(qū)塊化明顯的圖形，區(qū)域內(nèi)的小線段往往連續(xù)繪制，在遍歷時(shí)最大程度上優(yōu)先搜索區(qū)域內(nèi)的連續(xù)實(shí)體，可極大地提高排序效率。

在搜索過(guò)程中采用記憶搜索算法，即每個(gè)搜索循環(huán)結(jié)束時(shí)，記錄當(dāng)次搜索到的實(shí)體在實(shí)體表中的序號(hào)，并從表中移除該實(shí)體；下一循環(huán)優(yōu)先從表中該實(shí)體原前、后相鄰的實(shí)體開(kāi)始搜索，找到相連實(shí)體則結(jié)束當(dāng)次搜索循環(huán)，否則依次遍歷實(shí)體，直至找到相連實(shí)體或達(dá)到終止條件。

假設(shè)某個(gè)區(qū)域內(nèi)的圖形為連續(xù)繪制，即該區(qū)域內(nèi)所有實(shí)體均與實(shí)體表中前、后實(shí)體相接，此時(shí)搜索與該實(shí)體n相連接的實(shí)體。傳統(tǒng)遍歷算法的搜索過(guò)程為：

實(shí)體1與實(shí)體n比對(duì)

實(shí)體2與實(shí)體n比對(duì)

……

實(shí)體n-1與實(shí)體n比對(duì)

實(shí)體n+1與實(shí)體n比對(duì)

……

若實(shí)體n-1與實(shí)體n按加工方向相連，該次搜索共比對(duì)n-1次；若實(shí)體n+1與實(shí)體n按加工方向相連，該次搜索共比對(duì)n次。

記憶搜索算法的搜索過(guò)程為：

實(shí)體n-1與實(shí)體n比對(duì)

實(shí)體n+1與實(shí)體n比對(duì)

……

若實(shí)體n-1與實(shí)體n按加工方向相連，該次搜索共比對(duì)1次；若實(shí)體n+1與實(shí)體n按加工方向相連，該次搜索共比對(duì)2次。

假設(shè)該區(qū)域內(nèi)實(shí)體總數(shù)s為10 000，選擇其中第n個(gè)實(shí)體開(kāi)始進(jìn)行排序，完成全部排序過(guò)程的總搜索次數(shù)記為Z。

若加工方向與原實(shí)體表排序方向相同，傳統(tǒng)遍歷算法有：

當(dāng)n=1或n=10 000時(shí)，搜索比對(duì)次數(shù)最少，為9999次；當(dāng)n=5000時(shí)，搜索比對(duì)次數(shù)最多，為25004999次。

而記憶搜索算法有：

若加工方向與原實(shí)體表排序方向相反，傳統(tǒng)遍歷算法有：

當(dāng)n=5000時(shí)，搜索比對(duì)次數(shù)最少，為2.5×107次；當(dāng)n=1或n=10 000時(shí)，搜索比對(duì)次數(shù)最多，為50005000次。

而對(duì)于記憶搜索算法有：

繪制由10 000條小線段順序連接擬合成的圓，以Qt C++編寫傳統(tǒng)遍歷搜索算法和記憶搜索算法測(cè)試程序。在表1所示的測(cè)試環(huán)境下，按圓的順、逆時(shí)針?lè)较蚍謩e進(jìn)行搜索與排序，進(jìn)行兩種算法的對(duì)比測(cè)試，搜索過(guò)程用時(shí)對(duì)比見(jiàn)表2。

表1 搜索算法測(cè)試環(huán)境

表2 順序連接圖形的不同搜索算法用時(shí)對(duì)比

從上述數(shù)值計(jì)算及實(shí)際測(cè)試對(duì)比中可看出，相比傳統(tǒng)遍歷搜索算法，記憶搜索算法具有以下特點(diǎn)：①顯著減少搜索次數(shù)，大幅提高搜索效率；②不受起始實(shí)體位置影響，受切割方向影響小，穩(wěn)定性較強(qiáng)；③實(shí)體數(shù)量增加，與傳統(tǒng)遍歷算法的搜索次數(shù)呈幾何增加不同，記憶搜索算法的搜索次數(shù)呈線性增加，具有較好的適應(yīng)性；④存在多個(gè)圖形時(shí)，能較好地避開(kāi)無(wú)關(guān)實(shí)體搜索，保證搜索效率。

在實(shí)際線切割加工中，大實(shí)體量圖形通常不會(huì)完全按照連接順序繪制，而是區(qū)域內(nèi)順序繪制，由多個(gè)圖形區(qū)域最終組成完整圖形。如圖3所示，“雙馬”圖形總計(jì)11 061段實(shí)體，為分區(qū)域連續(xù)繪制而成。以該圖形為例，對(duì)其進(jìn)行算法搜索效率對(duì)比，測(cè)試環(huán)境同表1所示。

圖3 “雙馬”圖形

選擇多個(gè)起始位置進(jìn)行測(cè)試，兩種算法搜索用時(shí)對(duì)比見(jiàn)表3?？梢?jiàn)，記憶搜索算法在處理更具一般性的圖形時(shí)，實(shí)現(xiàn)了區(qū)域內(nèi)的最優(yōu)搜索，保證了搜索效率。

表3 “雙馬”圖形的不同搜索算法用時(shí)對(duì)比

4 結(jié)束語(yǔ)

針對(duì)電火花線切割CAM軟件加工代碼生成的需要，提出了一種利用LibreCAD進(jìn)行文件讀取的DXF實(shí)體排序算法，同時(shí)提出了一種記憶搜索算法用于處理大數(shù)據(jù)量實(shí)體搜索。通過(guò)數(shù)值計(jì)算及實(shí)際測(cè)試對(duì)比，記憶搜索算法能實(shí)現(xiàn)高適應(yīng)性、高準(zhǔn)確率、高效率的實(shí)體搜索與排序。與傳統(tǒng)實(shí)體排序算法相比，記憶搜索排序算法具有以下優(yōu)點(diǎn)：①封閉、非封閉圖形可統(tǒng)一進(jìn)行搜索與排序；②可逐一處理多圖形文件中的單獨(dú)圖形實(shí)體搜索與排序；③大幅提高了實(shí)體搜索效率，避免了實(shí)體數(shù)量巨大時(shí)搜索次數(shù)的幾何增長(zhǎng)；④避免了起始加工位置不同或文件中存在多個(gè)圖形引起的搜索效率波動(dòng)。

記憶搜索算法已成功應(yīng)用于基于LibreCAD的線切割CAD/CAM軟件系統(tǒng)，對(duì)于包含大量幾何實(shí)體的DXF文件的線切割加工路徑規(guī)劃、加工G代碼生成任務(wù)，均具有快速、精準(zhǔn)的處理效果。目前，采用記憶搜索算法的線切割CAD/CAM軟件系統(tǒng)已可用于生產(chǎn)，具有線切割G代碼生成功能，并支持多次切割、變錐度切割、上下異形面切割、非封閉圖形切割等高端往復(fù)走絲電火花線切割加工所必備的高級(jí)處理功能。

[1]蔣秋生.高速走絲電火花線切割CAD/CAM系統(tǒng)關(guān)鍵技術(shù)研究[D].廣州：廣東工業(yè)大學(xué)，2005.

[2]邢海蛟.基于AutoCAD圖形數(shù)控切割的應(yīng)用研究[D].哈爾濱：哈爾濱理工大學(xué)，2015.

[3]張為民.電火花線切割CAD/CAM集成系統(tǒng)關(guān)鍵技術(shù)研究[D].杭州：浙江大學(xué)，2004.

[4]曹琨，范益民，羅凌，等.基于Linux的圖形交互線切割加工CAM軟件關(guān)鍵技術(shù) [J].電加工與模具，2010（2）：20-23.

[5]陳俊聰.基于Linux數(shù)控系統(tǒng)的CAD二次開(kāi)發(fā)研究與實(shí)現(xiàn)[D].廣州：華南理工大學(xué)，2016.

[6]趙永光.使用LibreCAD開(kāi)發(fā)紙包裝結(jié)構(gòu)輔助設(shè)計(jì)軟件的研究[J].印刷雜志，2016（11）：45-48.

[7]李芳珍，許倫輝.DXF文件格式及其外部接口的研究[J].兵工自動(dòng)化，2008，27（7）：83-85.

Study on Entity Sorting Algorithm for WEDM CAM Based on LibreCAD

SHEN Guixu，XIA Weiwen，TAO Xumuye，ZHAO Wansheng
（ State Key Laboratory of Mechanical System and Vibration，School of Mechanical Engineering，Shanghai Jiao Tong University，Shanghai 200240，China ）

In the development process of WEDM CAM，a new entity sorting algorithm based on LibreCAD file reading is designed to solve the entity sorting problem of DXF file which contains huge number of geometric entities.Through the new algorithm，the entity sorting of closed geometry file，nonclosed geometry file and multi-geometry files can be realized at the same time.Based on the analysis of the sorting characteristics of the entities in a DXF file，a memory search algorithm is proposed to deal with the large data volume entity search.Based on the previous search，the intelligent search is carried out.Through the numerical calculation and the actual test comparison，the memory search algorithm can achieve high adaptability，high accuracy and high efficiency entity search and sorting.

WEDM；CAM software；DXF file；entity sorting；memory search algorithm

TG661

A

1009－279X（2017）05－0022-04

2017-08-03

沈桂旭，男，1992年生，碩士研究生。