刀軌環無跳刀尖角垂線過渡連接算法

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

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

0 引言

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

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

本文提出一種刀軌環過渡連接算法，該算法基于子域構造區域等距環，根據環的等距關系構建刀軌環數組，進而生成單根節點關系樹，并根據樹中葉子環上點的尖角大小確定過渡點的位置，遍歷刀軌環樹實現無跳刀環切刀軌，最后通過實例驗證了該算法的有效性。

1 刀軌環過渡連接算法基本流程

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

圖1 刀軌環過渡連接算法流程圖

2 基于子域等距的刀軌環樹生成

2.1 基于子域構造等距環

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

2.2 刀軌環數組的建立

圖2 基于子域生成等距線

如圖3a所示，3個封閉環分別為被加工對象的邊界輪廓，等距過程中，約定內環的方向為順時針，外環的方向為逆時針。圖3b中的內部環是基于子域生成的等距環。邊界輪廓和等距環統稱刀軌環。刀軌環之間具有嵌套關系，本算法用數組表示刀軌環，并規定逆時針方向的等距環為外等距環，順時針方向的等距環為內等距環。

本文參考文獻［6］定義了環的父子關系，即：當沿逆時針走刀路環Li行進時，如果刀路環Lj在左邊，且Li與Lj至少在一段區域內相鄰（即兩者之間沒有其他刀路環，兩環之間的距離為ρ），則稱Li是Lj的父環。

刀軌環數組定義格式如下：

Struct Loop

｛

bool clockwise；

unsigned offsetnumber；

Loop＃PParent；

bool isvisited；

｝

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

2.3 基于單向鏈表的刀軌環關系樹的生成

2.3.1 基于刀軌環數組編制單向鏈表

刀軌環關系樹實際是一個多向鏈表，本算法先根據刀軌環數組建立多個單向鏈表Listm（m的初始值設為1），然后生成多向鏈表List。刀軌環單向鏈表生成的具體步驟如下：

圖3 等距環拓撲關系構建

（1）在 Array（1）中查找 max（offsetnumber）的環Li，并把Li作為當前環（CurrentLoop，CL），即CL＝Li且CL存入Listm中，CL.isvisited＝1；

（2）If（CL.PParent！＝NULL）｛

轉步驟（3）｝Else｛

轉步驟（4）｝；

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

CL＝CL.PParent；

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

轉入步驟（2）｝；

（4）CL＝CL.PParent；

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

m←m＋1；

轉入步驟（1）；

（5）If（所有刀軌環的isvisited＝＝1）

單向鏈表構建結束。

圖3c所示的刀軌環單向鏈表生成結果如表1所示。

表1 刀軌環單向鏈表生成

2.3.2 刀軌環多向鏈表的構建

刀軌環關系樹的生成過程即為多個單向鏈表生成一個多向鏈表的過程。根據本算法中等距環方向的規定，內等距環的等距邊全部由內環等距得到，所以內等距環組成的等距環鏈表個數等于內邊界輪廓環的個數。

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

圖4 刀軌環關系樹生成流程圖

圖5 刀軌環關系樹生成示意圖

3 尖角垂線過渡點的計算及刀軌連接

3.1 尖角垂線過渡點

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

圖6 過渡點位置的種類

3.2 基于離散曲率的過渡點計算

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

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

圖7 點的離散曲率計算

式（1）中hi的計算公式為

3.3 環切無跳刀刀軌的生成

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

（1）關系樹中根節點對應的等距環上任取一點作為刀軌的起始點（StartPoint，SP），當前刀軌點（CurrentPoint，CP），CP ＝IP，轉步驟（2）；

（2）If（CP 是過渡點）｛

轉步驟（4）｝Else｛

轉步驟（3）｝；

（3）While（CP 不是過渡點）｛

CP－＞isvisited＝1；

沿著當前刀軌環環中下一個刀軌元素（NextPoint，NP）：CP ＝CPNP；

｝

If（CP！ ＝SP）｛

轉步驟（4）｝Else｛

轉步驟（7）｝；

（4）If（所有刀軌環的刀軌點都已被訪問）｛

轉步驟（7）｝Else｛

If（CP.isvisited ＝＝0）｛

步驟（5）｝Else｛

If（CP.son！ ＝ NULL）｛

轉步驟（5）｝｝Else｛

轉步驟（6）｝

｝；

（5）CP.isvisited ＝1；CP ＝CP.son；轉步驟（2）；

（6）CP.isvisited＝1；CP＝CP.father；轉步驟（2）；

（7）刀軌連接完成。

4 實例與驗證

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

圖8 過渡方式驗證實例

表2 過渡方式對比結果

5 結語

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

（1）刀軌環關系樹構建簡單。采用基于子域的等距策略采用逆序生成內等距環、順序生成外等距環的方式把單向鏈表中環加入主干關系樹中，簡化計算復雜度。整個算法的數據結構簡單，意義明晰。

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

（3）實現了無跳刀過渡連接，仿真中沒有過切現象。

［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］.計算機輔助設計與圖形學學報，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］張鳴，劉偉軍，卞宏友.基于自由區域的環切軌跡優化連接方法［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－half－dimensional Closedpocket Machining［J］.Proc.IMech.，Part B：Journal of Engineering Manufacture，2010，224（9）：1329－1350.