刀軌環(huán)無跳刀尖角垂線過渡連接算法

楊 峰 廖文和 戴 寧 張長東 郭保蘇 孫玉春

1.南京航空航天大學(xué)，南京，210016 2.上海電力學(xué)院，上海，200090 3.北京大學(xué)口腔醫(yī)學(xué)院，北京，100081

0 引言

隨著科學(xué)與技術(shù)的飛速發(fā)展，計(jì)算機(jī)輔助設(shè)計(jì)與制造（CAD／CAM）技術(shù)在航空航天、汽車等領(lǐng)域的應(yīng)用越來越廣泛。這些領(lǐng)域中需要加工的多為復(fù)雜型腔零件，零件的內(nèi)部往往存在一個(gè)或多個(gè)島嶼，因此環(huán)切不失為一種較好的加工選擇。環(huán)切刀軌的產(chǎn)生主要包括兩步：刀軌環(huán)的生成和刀軌環(huán)的連接［1－2］。刀軌環(huán)生成后是相互獨(dú)立的，直接加工會產(chǎn)生大量對實(shí)際加工沒有作用的走刀（如快速抬刀、快速下刀、快速移動(dòng)），影響加工效率，并且刀具的頻繁跳刀與突進(jìn)會在被加工模型的切削表面留下刀痕，影響加工質(zhì)量和刀具壽命，因此刀軌環(huán)如何高效地連接成環(huán)切刀軌顯得尤為重要［3］。

目前國內(nèi)外對刀軌環(huán)過渡連接的研究主要分為兩類。第一類是刀軌環(huán)幾何關(guān)系的構(gòu)建。Guyder［2］將刀軌連接看作是刀軌環(huán)的排序問題，其算法過于簡化，適用范圍有一定的局限性。Park等［4］在構(gòu)建刀軌環(huán)的同時(shí)生成多根節(jié)點(diǎn)刀軌樹，算法計(jì)算效率高，但是當(dāng)?shù)盾壄h(huán)的最大等距層數(shù)為n時(shí)，會產(chǎn)生n－1次的跳刀。文獻(xiàn)［5］中把多根節(jié)點(diǎn)樹轉(zhuǎn)化為單根節(jié)點(diǎn)結(jié)構(gòu)，實(shí)現(xiàn)了無跳刀連接，但是刀軌樹的轉(zhuǎn)化需要額外計(jì)算，增加了算法復(fù)雜度。Hao等［6］提出基于“刀軌環(huán)向量”遍歷刀軌環(huán)關(guān)系樹的方法，該方法可以實(shí)現(xiàn)無跳刀，但向量的維數(shù)會隨著等距環(huán)的個(gè)數(shù)增加，造成更多冗余的向量空間。張鳴等［7］構(gòu)建了一種稱之為區(qū)域樹的樹型數(shù)據(jù)結(jié)構(gòu)，能夠顯著減少跳刀次數(shù)但并不能總是實(shí)現(xiàn)無跳刀。Castelino等［8］為了減小刀軌總長度，引入旅行商問題，但是該方法僅適用于每個(gè)節(jié)點(diǎn)只遍歷一次，而且退刀點(diǎn)和下刀點(diǎn)重合的場合。第二類是過渡點(diǎn)連接方式的優(yōu)化。Kim等［9］通過計(jì)算父子關(guān)系環(huán)之間距離最小的點(diǎn)把兩個(gè)環(huán)連接起來，沒有從幾何角度考慮下刀起點(diǎn)的位置。Hinduja等［10］提出了基于Voronoi圖刀軌環(huán)過渡的7個(gè)準(zhǔn)則及刀軌優(yōu)劣評價(jià)標(biāo)準(zhǔn)，綜合考慮了加工中的幾何因素和物理因素，但其生成的刀軌還需要進(jìn)一步優(yōu)化才能用于實(shí)際加工中。

本文提出一種刀軌環(huán)過渡連接算法，該算法基于子域構(gòu)造區(qū)域等距環(huán)，根據(jù)環(huán)的等距關(guān)系構(gòu)建刀軌環(huán)數(shù)組，進(jìn)而生成單根節(jié)點(diǎn)關(guān)系樹，并根據(jù)樹中葉子環(huán)上點(diǎn)的尖角大小確定過渡點(diǎn)的位置，遍歷刀軌環(huán)樹實(shí)現(xiàn)無跳刀環(huán)切刀軌，最后通過實(shí)例驗(yàn)證了該算法的有效性。

1 刀軌環(huán)過渡連接算法基本流程

刀軌環(huán)過渡連接算法基本流程如圖1所示。首先進(jìn)行等距環(huán)的生成，輸入邊界輪廓并對其上的離散點(diǎn)進(jìn)行基于累積曲率的簡化、光順處理，通過計(jì)算邊界元素的角分線向量，把平面域邊界輪廓分解為隸屬于每個(gè)邊界元素的子區(qū)域，進(jìn)而基于子域生成等距環(huán)。然后進(jìn)入本文算法的核心部分（圖1虛線框部分），即實(shí)現(xiàn)尖角垂線過渡無跳刀刀軌。首先把生成的等距環(huán)根據(jù)等距關(guān)系構(gòu)建刀軌環(huán)數(shù)組，并根據(jù)數(shù)組中環(huán)的關(guān)系建立單根節(jié)點(diǎn)刀軌環(huán)樹，然后通過葉環(huán)上尖點(diǎn)垂線過渡的方式連接刀軌環(huán)，最后生成無跳刀環(huán)切刀軌。

圖1 刀軌環(huán)過渡連接算法流程圖

2 基于子域等距的刀軌環(huán)樹生成

2.1 基于子域構(gòu)造等距環(huán)

邊界輪廓的子域定義為隸屬于每個(gè)邊界元素的獨(dú)立子區(qū)域，子域的內(nèi)部節(jié)點(diǎn)是至少與邊界輪廓的三條邊界元素（或邊界的延長線）相切圓的圓心，每條邊界元素的等距線完全在其子域內(nèi)產(chǎn)生。先對離散刀軌環(huán)進(jìn)行子域分割（圖2a），再根據(jù)給定的等距距離，就可生成離散刀軌環(huán)的等距線，如圖2b所示。每個(gè)等距環(huán)都是多邊形，由相同等距距離的等距線依次連接而成，如圖2c所示。

2.2 刀軌環(huán)數(shù)組的建立

圖2 基于子域生成等距線

如圖3a所示，3個(gè)封閉環(huán)分別為被加工對象的邊界輪廓，等距過程中，約定內(nèi)環(huán)的方向?yàn)轫槙r(shí)針，外環(huán)的方向?yàn)槟鏁r(shí)針。圖3b中的內(nèi)部環(huán)是基于子域生成的等距環(huán)。邊界輪廓和等距環(huán)統(tǒng)稱刀軌環(huán)。刀軌環(huán)之間具有嵌套關(guān)系，本算法用數(shù)組表示刀軌環(huán)，并規(guī)定逆時(shí)針方向的等距環(huán)為外等距環(huán)，順時(shí)針方向的等距環(huán)為內(nèi)等距環(huán)。

本文參考文獻(xiàn)［6］定義了環(huán)的父子關(guān)系，即：當(dāng)沿逆時(shí)針走刀路環(huán)Li行進(jìn)時(shí)，如果刀路環(huán)Lj在左邊，且Li與Lj至少在一段區(qū)域內(nèi)相鄰（即兩者之間沒有其他刀路環(huán)，兩環(huán)之間的距離為ρ），則稱Li是Lj的父環(huán)。

刀軌環(huán)數(shù)組定義格式如下：

Struct Loop

｛

bool clockwise；

unsigned offsetnumber；

Loop＃PParent；

bool isvisited；

｝

其中，數(shù)組的第一個(gè)元素表示刀軌環(huán)的方向，如果該方向是逆時(shí)針則說明是外等距環(huán)（或外邊界輪廓），值為0；如果該方向是順時(shí)針則說明是內(nèi)等距環(huán)（或內(nèi)邊界輪廓），值為1。第二個(gè)元素表示等距環(huán)的等距次數(shù)，該值在等距過程中已經(jīng)記錄，邊界輪廓的等距值默認(rèn)為0。第三個(gè)元素指向當(dāng)前環(huán)的父環(huán)。第四個(gè)元素表示在生成刀軌環(huán)關(guān)系樹中是不是被遍歷過。圖3c所示的各刀軌環(huán)用數(shù)組表示如下：

2.3 基于單向鏈表的刀軌環(huán)關(guān)系樹的生成

2.3.1 基于刀軌環(huán)數(shù)組編制單向鏈表

刀軌環(huán)關(guān)系樹實(shí)際是一個(gè)多向鏈表，本算法先根據(jù)刀軌環(huán)數(shù)組建立多個(gè)單向鏈表Listm（m的初始值設(shè)為1），然后生成多向鏈表List。刀軌環(huán)單向鏈表生成的具體步驟如下：

圖3 等距環(huán)拓?fù)潢P(guān)系構(gòu)建

（1）在 Array（1）中查找 max（offsetnumber）的環(huán)Li，并把Li作為當(dāng)前環(huán)（CurrentLoop，CL），即CL＝Li且CL存入Listm中，CL.isvisited＝1；

（2）If（CL.PParent?。絅ULL）｛

轉(zhuǎn)步驟（3）｝Else｛

轉(zhuǎn)步驟（4）｝；

（3）While（CL.PParent.isvisited＝＝0）｛

CL＝CL.PParent；

CL存入Listm中，CL.isvisited＝1；

轉(zhuǎn)入步驟（2）｝；

（4）CL＝CL.PParent；

CL存入Listm中，CL.isvisited＝1；

m←m＋1；

轉(zhuǎn)入步驟（1）；

（5）If（所有刀軌環(huán)的isvisited＝＝1）

單向鏈表構(gòu)建結(jié)束。

圖3c所示的刀軌環(huán)單向鏈表生成結(jié)果如表1所示。

表1 刀軌環(huán)單向鏈表生成

2.3.2 刀軌環(huán)多向鏈表的構(gòu)建

刀軌環(huán)關(guān)系樹的生成過程即為多個(gè)單向鏈表生成一個(gè)多向鏈表的過程。根據(jù)本算法中等距環(huán)方向的規(guī)定，內(nèi)等距環(huán)的等距邊全部由內(nèi)環(huán)等距得到，所以內(nèi)等距環(huán)組成的等距環(huán)鏈表個(gè)數(shù)等于內(nèi)邊界輪廓環(huán)的個(gè)數(shù)。

本算法在單向鏈表中通過順序取外等距環(huán)、逆序取內(nèi)等距環(huán)的方法，最終得到單根節(jié)點(diǎn)刀軌環(huán)關(guān)系樹，具體流程如圖4所示。由于單向鏈表是根據(jù)環(huán)的等距次數(shù)生成的，所以首先把等距次數(shù)最大即第一個(gè)生成的單向鏈表構(gòu)建成刀軌環(huán)主干樹。按照表1中的第一個(gè)單向鏈表生成主干樹（圖5a），然后查找當(dāng)前環(huán)的父環(huán)，再分別按照順序、逆序把其他單向鏈表插入到主干樹中，最終生成單根節(jié)點(diǎn)多向鏈表即刀軌環(huán)關(guān)系樹。圖5b所示為順序插入外等距環(huán)的結(jié)果，圖5c所示為在圖5b的基礎(chǔ)上逆序插入內(nèi)等距環(huán)的結(jié)果。

圖4 刀軌環(huán)關(guān)系樹生成流程圖

圖5 刀軌環(huán)關(guān)系樹生成示意圖

3 尖角垂線過渡點(diǎn)的計(jì)算及刀軌連接

3.1 尖角垂線過渡點(diǎn)

過渡點(diǎn)是刀具從一個(gè)刀軌環(huán)過渡到另一個(gè)刀軌環(huán)的位置，過渡點(diǎn)位置的確定對實(shí)際加工有著重要影響。在沒有優(yōu)化的刀軌中，應(yīng)用于子域刀軌環(huán)的過渡點(diǎn)主要分為三類，如圖6所示。以子域角分線頂點(diǎn)作為過渡點(diǎn)，通過子域邊界實(shí)現(xiàn)刀軌環(huán)連接，這些過渡點(diǎn)數(shù)據(jù)結(jié)構(gòu)建立簡單，但會使刀軌增加更多的尖角過渡，如圖6a所示；在刀軌環(huán)上任取一點(diǎn)，作其相鄰等距環(huán)的垂線，這種過渡方式能保證刀軌總長度最短，如圖6b所示；本算法提出如圖6c所示的過渡點(diǎn)計(jì)算方法，該方法以減少刀軌中的尖角過渡為目的，在保證刀軌總長度最短的前提下，通過計(jì)算實(shí)現(xiàn)尖角垂線過渡。

圖6 過渡點(diǎn)位置的種類

3.2 基于離散曲率的過渡點(diǎn)計(jì)算

由于刀軌環(huán)由一系列離散點(diǎn)依次相連而成，本算法引入離散曲率確定各刀軌環(huán)尖角過渡點(diǎn)的位置，把曲率計(jì)算轉(zhuǎn)化為三角形內(nèi)邊的計(jì)算，具體實(shí)現(xiàn)方法如下：圓逼近法求曲率是用通過相鄰三個(gè) 點(diǎn) Pi－1（xi－1，yi－1）、Pi（xi，yi）、Pi＋1（xi＋1，yi＋1）的圓來近似Pi點(diǎn)的密切圓的，如圖7所示，圓的曲率Ki為

式中，R 為圓的半徑；S△Pi－1PiPi＋1為相鄰三個(gè)點(diǎn)組成的三角形面積；li為點(diǎn)Pi和點(diǎn)Pi－1之間的距離；li±1為點(diǎn)Pi＋1和 點(diǎn) Pi－1之間的距離；hi為 點(diǎn) Pi到 對 邊 Pi－1Pi＋1的距離。

圖7 點(diǎn)的離散曲率計(jì)算

式（1）中hi的計(jì)算公式為

3.3 環(huán)切無跳刀刀軌的生成

通過計(jì)算刀軌環(huán)關(guān)系樹中葉子環(huán)的離散曲率，取最大者即尖角位置，作其到樹中父環(huán)的垂線段且垂線段的長度等于等距距離。若找不到滿足條件的垂線段，則選取離散曲率次之的尖角點(diǎn)。同時(shí)根據(jù)樹中環(huán)的父子關(guān)系建立過渡點(diǎn)間的父子關(guān)系。最后根據(jù)過渡點(diǎn)之間的父子關(guān)系實(shí)現(xiàn)無跳刀刀軌的生成，偽代碼如下：

（1）關(guān)系樹中根節(jié)點(diǎn)對應(yīng)的等距環(huán)上任取一點(diǎn)作為刀軌的起始點(diǎn)（StartPoint，SP），當(dāng)前刀軌點(diǎn)（CurrentPoint，CP），CP ＝IP，轉(zhuǎn)步驟（2）；

（2）If（CP 是過渡點(diǎn)）｛

轉(zhuǎn)步驟（4）｝Else｛

轉(zhuǎn)步驟（3）｝；

（3）While（CP 不是過渡點(diǎn)）｛

CP－＞isvisited＝1；

沿著當(dāng)前刀軌環(huán)環(huán)中下一個(gè)刀軌元素（NextPoint，NP）：CP ＝CPNP；

｝

If（CP！ ＝SP）｛

轉(zhuǎn)步驟（4）｝Else｛

轉(zhuǎn)步驟（7）｝；

（4）If（所有刀軌環(huán)的刀軌點(diǎn)都已被訪問）｛

轉(zhuǎn)步驟（7）｝Else｛

If（CP.isvisited ＝＝0）｛

步驟（5）｝Else｛

If（CP.son！ ＝ NULL）｛

轉(zhuǎn)步驟（5）｝｝Else｛

轉(zhuǎn)步驟（6）｝

｝；

（5）CP.isvisited ＝1；CP ＝CP.son；轉(zhuǎn)步驟（2）；

（6）CP.isvisited＝1；CP＝CP.father；轉(zhuǎn)步驟（2）；

（7）刀軌連接完成。

4 實(shí)例與驗(yàn)證

算法通過直線加減速關(guān)系圖建立CNC系統(tǒng)中的數(shù)學(xué)模型，驗(yàn)證尖角垂線過渡對加工時(shí)間的影響。以圖8a～圖8c所示的三個(gè)輪廓的等距環(huán)為試驗(yàn)對象，分別生成相應(yīng)的角分線（圖8d～圖8f）、垂線（圖8g～圖8i），以及本文提出的尖角垂線（圖8j～圖8l）來進(jìn)行過渡，再將生成的無跳刀刀軌輸入北京精雕JDPaintV5.50計(jì)算路徑總長度，并取進(jìn)給速度為2m／min，變速系數(shù)為50，分別計(jì)算三種過渡方式下的加工時(shí)間，結(jié)果如表2所示?？梢钥闯?，角分線過渡的刀軌總長度最大，加工時(shí)間最長，而垂線過渡和尖角垂線過渡的刀軌總長度相同，由于垂線過渡增大了刀具軌跡中的尖角從而增大了加減速影響，所以后者的加工時(shí)間明顯短于前者。可見，在綜合考慮刀軌總長度最短和加工時(shí)間最短的前提下，尖角垂線過渡優(yōu)于角分線過渡和垂線過渡。

圖8 過渡方式驗(yàn)證實(shí)例

表2 過渡方式對比結(jié)果

5 結(jié)語

本文以基于子域的等距環(huán)為研究對象，提出環(huán)切無跳刀過渡連接算法。本算法特點(diǎn)如下：

（1）刀軌環(huán)關(guān)系樹構(gòu)建簡單。采用基于子域的等距策略采用逆序生成內(nèi)等距環(huán)、順序生成外等距環(huán)的方式把單向鏈表中環(huán)加入主干關(guān)系樹中，簡化計(jì)算復(fù)雜度。整個(gè)算法的數(shù)據(jù)結(jié)構(gòu)簡單，意義明晰。

（2）以葉子環(huán)的尖點(diǎn)作為過渡點(diǎn)，縮短了實(shí)際加工過程中的加減速時(shí)間。以等距次數(shù)為關(guān)鍵字生成單向鏈表，保證了關(guān)系樹中主干樹中的刀軌環(huán)個(gè)數(shù)最多，從而保證了過渡連接線段位于同一直線方向上。

（3）實(shí)現(xiàn)了無跳刀過渡連接，仿真中沒有過切現(xiàn)象。

［1］Choi B K，Park S C.A Pair－wise Offset Algo－rithm for 2DPoint－sequence Curve［J］.Computer－Aided Design，1999，31（12）：735－745.

［2］Guyder M K.Automating the Optimization of 2 1／2 Axis Milling［J］.Computers in Ind.，1990，15（3）：163－168.

［3］安魯陵，周來水，莊海軍，等.型腔高速銑削刀軌生成算法研究［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16（9）：1202－1206.An Luling，Zhou Laishui，Zhuang Haijun，et al.Tool Path Generation for High－Speed Milling of Pocket［J］.Journal of Computer Aided Design ＆Computer Graphics，2004，16（9）：1202－1206.

［4］Park S C，Chung Y C.Offset Tool－path Linking for Pocket Machining［J］.Computer－Aided Design，2002，34（4）：299－308.

［5］Park S C，Chung Y C，Choi B K.Contour Parallel Offset Machining Without Tool－retractions［J］.Computer－Aided Design，2003，35（9）：841－849.

［6］Hao Y T，Jiang L L.Optimal Algorithm for no Tool－retractions Contour－parallel Offset Toolpath Linking［J］.Journal of Mechanical Engineering，2007，20（2）：21－25.

［7］張鳴，劉偉軍，卞宏友.基于自由區(qū)域的環(huán)切軌跡優(yōu)化連接方法［J］.中國機(jī)械工程，2011，22（4）：468－473.Zhang Ming，Liu Weijun，Bian Hongyou.Optimized Contour－parallel Offset Tool－path Linking Method Based on Free Region［J］.China Mechanical Engineering，2011，22（4）：468－473.

［8］Castelino K，D’Souza R，Wright P K.Tool Path Optimization for Minimizing Airtime during Machining［J］.J.Mfg.Systems，2003，22（3）：173－180.

［9］Kim H C.Tool Path Generation for Contour Parallel Milling with Incomplete Mesh Model［J］.International Journal of Advanced Manufacturing Technology，2010，48（5／8）：443－454.

［10］Hinduja S，Mansor M S A，Owodunni O O.Voronoi－diagram－based Linking of Contour－parallel Tool Paths for Two－and－a－h(huán)alf－dimensional Closedpocket Machining［J］.Proc.IMech.，Part B：Journal of Engineering Manufacture，2010，224（9）：1329－1350.