環切刀軌無跳刀過渡連接算法

董光雷 戴 寧 楊 峰 韓厚年 郭保蘇 王 勇 呂培軍

1.南京航空航天大學，南京，210016 2.北京大學口腔醫學院，北京，100081

0 引言

計算機輔助制造（CAM）技術在口腔醫學領域中的應用越來越廣泛。將CAM技術引入口腔修復領域，利用CAM技術高效率、高精度的特點可大幅提高修復體制作的效率，明顯縮短治療周期，充分保證修復體的精度［1］。目前世界上最先進的口腔CAM系統完成一個全冠的制作，全程最快只需5min左右，患者只需就診一次就可以完成治療。在口腔修復體整個加工過程中，粗加工占用大部分時間，因此提高粗加工加工效率是關鍵，在由加工區域最外邊界（外環）和加工區域內島嶼邊界（內環）構成的連通域內環切刀具軌跡主要由刀軌環軌跡［2－7］和軌跡環之間過渡連接［8－15］兩部分組成。環切刀軌環計算完成后相互獨立，直接加工會產生大量對實際加工沒用的走刀（如快速抬刀、快速下刀、快速移動），影響加工效率，并且刀具頻繁的跳刀與突進會在被加工模型的切削表面留下刀痕，影響加工質量。因此，刀軌環軌跡之間的過渡連接質量好壞對提高修復體的加工效率和質量非常重要。

目前國內外對環切刀軌環的過渡連接作了一定的研究，解決方式大體上可分為兩種：①基于刀軌樹結構過渡連接刀軌環。Guyder［8］提出了環切刀軌過渡連接應該滿足的基本準則，這些準則比較符合實際加工情況，但是文中算法把環過渡連接問題過于簡化為刀軌環的排序。Park等［9］構建了多根節點刀軌樹結構，通過遍歷刀軌樹實現子軌跡的無跳刀連接，但當加工區域邊界個數為n時，會造成n－1次跳刀。Park等［10］在文獻［9］的研究基礎上把由刀軌環組成的多根節點樹結構轉化為單根節點結構實現無跳刀連接，當刀軌樹根節點數目較多時轉化工作需要大量額外計算，并且還會出現無法轉化的情況，這樣會增加算法的復雜度。Kim［13］根據刀軌環計算時建立的父子關系構建刀軌環關系樹，計算具有父子關系的兩個環之間距離最小的點，然后把兩個環連接起來，把環切刀軌的連接簡單看作是遍歷刀軌環樹，但此方法并不能總是實現無跳刀。Hao等［14］提出的算法同樣是基于刀軌環關系樹的，但是其算法中刀軌環父子關系不能在軌跡計算過程中獲得，需要額外計算。張鳴等［15］構建了一種稱之為區域樹的樹形數據結構，能夠顯著減少跳刀次數但并不能總是實現無跳刀。②把環過渡問題轉化為其他算法數學模型。Castelino等［11］把環過渡問題轉化為解決TSP問題以縮短空走刀時間，但是不能實現無跳刀。Hinduja等［12］基于Voronoi圖提出環切刀軌連接算法，根據不同的過渡準則（減少跳刀、避免重復切削、減少開槽加工等）對刀軌環進行過渡連接，并對生成的刀軌作了對比分析，該算法可以有效減小刀具路徑長度。與①相比，方式②不僅沒有充分利用刀軌環之間的潛在拓撲關系，而且增加了計算復雜度。

根據上述研究，本文提出了基于單根節點刀軌環樹結構的環切無跳刀刀軌過渡連接算法，該方法通過對刀軌環樹的拓撲分解實現對刀軌環的編組，不僅獲得了無跳刀刀軌，而且還使盡量多數目的刀軌環之間的過渡連接線段位于同一直線方向上。最后通過仿真實驗說明了本文算法的有效性。

1 定義

為了系統地描述算法，對相關的概念術語進行定義。

定義1 刀軌環。當前加工層所在的水平面與被加工模型的刀位面的交線，即加工區域的初始邊界，如圖1a中外環L［0－1］，內環I［0－1］、I［0－2］。經過m次等距計算后得到n個有效加工軌跡環，每個有效加工軌跡環為刀軌環（tool path loop，TPL），記為L［m－k］（0≤k≤n）（內環等距形成的刀軌環記為I［m－k］（0≤k≤n））。內／外環的初始等距計算次數為0。例如，在圖1b中，L［2－1］表示經過2次等距計算。

定義2 刀軌環父／子關系。刀軌環L［mi］是由上次計算得到的刀軌環L［（m－1）－j］和內環I［0－k］的等距環組成，則L［m－i］的父環（L［m－i］）Farther＝L［（m－1）－j］，L［（m－1）－j］的一個子環是L［m－i］。內環I［0－k］只與由部分I［0－k］等距環組成的刀軌環建立父子關系，則（I［0－k］）Farher＝L［m－i］。如 圖 1b 所 示，L［1－2］和I［0－2］等距后得到刀軌環L［2－1］和L［2－2］，則（L［1－2］）Son＝｛L［2－1］，L［2－2］｝，L［2－1］和L［2－2］的父環均為L［1－2］；L［2－1］和L［2－2］均為部分由I［0－2］的等距環組成，所以I［0－2］的父環可為兩個環中的一個，例如（I［0－2］）Farther＝L［2－1］。

本文中算法在計算刀軌環時內環只向外等距一次，外環連續向內等距，在刀軌環計算的同時建立環之間的父子關系，所以當所有刀軌環計算完成后可以建立單根刀軌環關系樹。圖1c中的單根刀軌樹結構是建立在圖1b中刀軌環父子關系的基礎上的。

圖1 環切刀具軌跡

定義3 過渡點、虛過渡點、過渡點對。具有父／子關系的兩刀軌環Li／Lj上存在兩點Pi和Pj，并且Pi和Pj之間的距離為刀軌行間距δ，則稱Pi／Pj分別為Li／Lj上的過渡點（圖2）。在過渡點Pi之后插入P′i，并且P′i＝Pi，則稱P′i為Li上與Pi相對應的虛過渡點。Pi、P′i、Pj、P′j組成過渡點對（Pi，P′j）和（Pj，P′i），如圖2b所示建立過渡點對元素之間連接關系，L［1－1］上過渡點P2與父環L［0－1］的 虛 過 渡 點 P′1具 有 連 接 關 系，（P2）Farther＝P′1，與子環L［2－1］上虛過渡點P′3具有連接關系，（P2）Son＝P′3；對于虛過渡點 P′2，則（P′2）Farther＝P1，（P′2）Son＝P3，構成過渡點對集合Γ＝｛（P1，P′2），（P2，P′1），（P2，P′3），（P3，P′2）｝。

圖2 過渡點、虛過渡點、過渡點對

2 刀軌環編組

數控加工過程既是幾何過程又是物理過程，刀軌環的計算除了依據幾何運算來構建外，還要考慮到軌跡之間的過渡連接對實際加工的影響。“無跳刀”刀軌不僅要提高加工效率，而且還要考慮到環之間的過渡連接對實際加工的影響。如圖3所示，圖3a中的刀軌環之間的過渡線段位于不同直線上，類似臺階式，不僅增加了走刀過渡路徑，還會造成刀具在實際加工中頻繁地沿著不同方向從父刀軌環進入子環或是從子環返回父環引起機床的振動。文獻［10］指出不恰當的過渡連接可能造成重復走刀，而圖3b中的刀軌環之間的過渡線段位于同一直線方向上，可以避免上述缺點。因而有必要使盡量多的刀軌環之間過渡線段方向相同。

圖3 多個刀軌環之間過渡

2.1 刀軌環樹拓撲分解

刀軌環的組成屬性有三種：①完全由外輪廓的等距環構成；②完全由內輪廓環的等距環構成；③由內／外輪廓環的等距環復合構成。前兩種能夠保持環之間等距信息的連續性，而③會阻斷這種等距連續性，稱之為“分界環”，其對應刀軌環樹中的節點為“分界節點”。如圖4a所示，刀軌環L［2－1］組成屬性為③，其對應刀軌環樹中的分界節點如圖4b所示，刀軌環L［4－1］和L［1－1］之間不能用一條直線段連接，只能連接L［4－1］、L［3－2］、L［2－1］，如圖4c所示。

圖4 由內／外輪廓等距環組成的刀軌環阻斷等距連續性

文獻［10］中指出一種特殊情況，內環等距后可能構成“內包”等距環，如圖5a、圖5b中內環I［0－1］等距形成內包環I［1－1］，由于L［2－1］和L［2－2］部分由I［0－1］的等距環I［1－2］組成，則I［0－1］的父環是L［2－1］或L［2－2］。內包環只與構成該內包環的內環之間存在等距的連續信息，因此內環可以阻斷等距的連續性，也是“分界環”。由上述可知，內環和由內環等距環構成的刀軌環均是“分界環”，如圖5c所示。

圖5 內包環示例

根據分界環對應的分界節點，對刀軌環樹進行拓撲分解，分解為一系列拓撲子樹（sub tree，ST），進而對刀軌環進行編組，提取出可以用一條直線段相互連接的編組環集合Ω，使最多數目的刀軌環直線過渡連接。步驟如下：

（1）查找層數最大的并且沒有被訪問過的葉子節點環作為初始節點環（inital loop）LI，設當前刀軌環（current loop）為LC，LC←LI，若LI存在，則轉步驟（2），否則轉步驟（6）。

（2）If（LC）Parent是根節點，轉步驟（5）；

Else｛

①（LC）Parent不是分界環，轉步驟（3）；

②（LC）Parent是分界環或是已被訪問，轉步驟（4）；

｝。

（3）標 記 LC為 已 訪 問，保 存 LC，LC←（LC）Parent，轉步驟（2）。

（4）標記LC為已訪問，保存LC和（LC）Parent，轉步驟（1）。

（5）標記LC和（LC）Parent為已訪問，保存LC和（LC）Parent，轉步驟（1）。

（6）刀軌環樹拓撲分解結束。

以圖5c中含有分界節點的刀軌環樹為例，刀軌環樹拓撲分解結果如圖6所示。刀軌環節點I［0－1］、L［2－1］、L［2－2］為分界環，第一次拓撲分離的初始環為I［1－1］，其父環I［0－1］為邊界環，則標記I［1－1］為已訪問，保存I［0－1］和I［1－1］為一個拓撲子樹ST－1。拓撲子樹ST－2、ST－3、ST－4、ST－5的提取與ST－1類似，當ST－6分離計算時，初始環為L［2－2］，其父環L［1－1］在拓撲子樹ST－5提取時已經被訪問過，則保存L［2－2］和L［1－1］后提取結束。

圖6 刀軌樹拓撲分解結果

2.2 環集合過渡線段

編組環集合Ω中有n個刀軌環元素，由于環集合保留了等距連續信息，所以環集合中最內／外層環 LIM／LOM上 存 在 點 PIM／POM，并 且 線 段PIMPOM的長度為（n－1）δ，則PIMPOM即為該環集合的過渡線段LSeg。如圖7a所示，編組環集合為L［2－1］、L［1－1］、L［0－1］，n＝3，LIM＝L［2－1］，LOM＝L［0－1］，環集合過渡線段長度＝2δ。

2.3 構造過渡點對

根據定義3，編組環集合Ω中的每一個刀軌環元素和其過渡線段LSeg的交點為過渡點。如圖7b所示，過渡點P1、P2、P3為LSeg分別和L［0－1］、L［1－1］、L［2－1］的交點，P′1、P′2、P′3為虛過渡點，構成過渡點對集合Γ＝｛（P1，P′2），（P2，P′1），（P2，P′3），（P3，P′2）｝。

3 環切無跳刀刀軌生成

根據過渡點對建立父子刀軌環之間的連接關系實現無跳刀刀軌的提取，令外環為順時針方向，內環為逆時針方向，具體提取步驟如下：

（1）選取某個刀軌環上的一點作為提取出刀軌的初始點（inital point）PI，設當前刀軌點（cur－rent point）為PC，PC←PI，轉步驟（2）。

圖7 構造過渡點對

（2）If（PC是過渡點）｛轉步驟（4）｝

Else｛轉步驟（3）｝。

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

標記PC已被訪問：PC→bVisited＝True；

沿著當前刀軌環遍歷賦值PC下一個刀軌

元素（Next Point）PNP：PC←PNP；｝

If（PC！＝PI）｛轉步驟（4）｝Else｛轉步驟

（7）｝。

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

轉步驟（7）｝Else｛

If（（PC）Son！＝NULL）｛

If（（PC）Son→bVisited＝＝False）｛

轉步驟（5）｝Else｛轉步驟（6）｝；

｝Else｛轉步驟（6）｝

｝。

（5）PC→bVisited＝True，PC←（PC）Son轉步驟（2）。

（6）If（（PC）Farther→isVisited＝＝True）

｛PC→bVisited＝True，PC←（虛過渡點

（PC）Farther對應的過渡點），轉步驟（2）；｝

Else｛PC→bVisited ＝ True，PC←

（PC）Farther轉步驟（2）；｝。

（7）刀軌連接完成。

圖8所示為上述刀軌提取流程，在刀軌環L［0－1］上選擇點Q作為刀軌提取初始點PI，PC←PI；由于PC不是過渡點轉向步驟（3），沿著刀軌環L［0－1］遍歷至過渡點P1，PC←P1，轉向步驟（4）；過渡點（P1）Farther為空，進入子環的指針（P1）Son非空，并且 P′2沒有被訪問過，則轉向步驟（5）進入子環 L［1－1］，PC←P′2，沿著刀軌環L［1－1］遍歷至過渡點P4；P4與P1情況相同，則PC←P′5，進入L［2－2］后遍歷至P6，然后進入L［3－1］遍歷至P7；由于（P7）Son為空則返回其父環L［2－2］，按照圖8b所示依次遍歷刀軌環。當遍歷至過渡點P3時，（P3）Son為空，并且與P3組成過渡點對的父環上的虛過渡點P′2已經被訪問過，則在步驟（6）中 PC←P2；（P2）Son為空，但是（P2）Son已經被訪問過，則返回環L［0－1］，PC←P′1，沿著刀軌環L［0－1］遍歷至初始點Q，刀軌提取結束。

圖8 無跳刀刀軌提取

4 實例驗證

本文算法已應用于南京航空航天大學開發的DentalEngineer軟件中。圖9所示加工對象為三維橋體牙齒模型（31mm×13mm×11mm），當前加工層所在的水平面和被加工牙齒模型刀位面的交線的最外輪廓為刀具走刀的最大區域。圖10所示為在圖9加工區域內應用本文算法規劃的環切刀軌，可以看出所有的刀軌環之間建立了連接關系，只有一次進刀和一次跳刀，在加工過程中無跳刀，并且沒有重復切削。實例刀具軌跡仿真結果如圖11所示，輪廓的加工質量較好。

圖9 實例加工區域

圖10 本文算法連接生成的刀具軌跡

圖11 實例刀具軌跡仿真結果

在數控加工中，粗加工階段常用的走刀方式有單向行切（Zig）、雙向行切（Zig－Zag）、環切和螺旋線切等方式，在實例1的加工區域內用上述走刀方式實現的走刀刀具軌跡如圖12所示，其中圖12中的環切刀軌指的是各個刀軌環之間沒有進行過渡的刀軌。表1中的時間數據是在德國imes－icore公司生產的型號為CORiTEC 340i的面向齒科修復體加工的專用機床上統計得到的。加工參數為：進給速度2000mm／min、刀軌路徑間距0.4mm。加工刀具為直徑2mm的球頭刀。從表1中的對比數據可以看出，本文算法生成的環切刀軌由于在加工過程中沒有跳刀，使G00路徑長度顯著縮短，同時總的走刀路徑長度也縮短了，從而縮短了加工時間，提高了加工效率，該走刀方式要明顯優于單向行切、雙向行切、環切三種走刀方式。盡管螺旋刀軌連續性較好，走刀平穩，適用于高速加工，可以在一定程度上減少刀具的跳刀次數，但一般適用于沒有島嶼的加工區域，由于牙齒修復體有牙尖、牙窩等表面形態特征，所以加工區域常常存在多個島嶼，表1中的數據也說明了在牙齒修復體加工中應用本文算法生成的刀軌在加工效率方面要優于螺旋線刀軌。

圖12 實例1不同走刀方式刀具軌跡

表1 實例1刀軌對比結果

5 結論

（1）刀軌樹結構構建簡單。采用特殊的等距策略，充分利用刀軌環等距計算建立刀軌環之間的父子關系，構建單根節點刀軌樹避免了多根樹向單根樹的轉化，簡化了計算復雜度。整個算法的數據結構清晰，便于在程序中實現。

（2）刀軌樹拓撲分解得到的編組環集合元素之間過渡直線方向相同不僅提高模型的加工質量，而且提高加工時走刀的穩定性，減少機床的振動。

（3）實現了跳刀次數為零，并且沒有重復切削。

（4）正如Park等［10］和 Hinduja等［12］所述，刀軌環的過渡連接需要滿足一些符合實際加工的準則，比如避免重復切削、減少開槽加工、減少跳刀次數、刀軌路徑長度最短等，但是，要找到能夠同時滿足這些條件的過渡連接方式比較困難，因為有些技術條件是相互矛盾的，如避免重復切削和減少開槽加工，所以可以根據實際加工條件選用恰當的刀軌連接策略。例如本文中算法應用于口腔修復加工中的粗加工階段，減少跳刀次數和避免重復切削可以顯著地縮短加工時間。鑒于牙齒修復體加工時切削量小，少量的開槽加工對刀具磨損和整體加工質量影響較小，因此本文算法以減少跳刀次數和避免重復切削為主要準則。

［1]Takashi M，Yasuhiro H，Jun K，et al.A Review of Dental CAD／CAM：Current Status and Future Perspectives from 20Years of Experience［J］.Dental Materials Journal，2009，28（1）：44－56.

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

［3]Wong T N ，Wong K W.NC Tool Path Generation for Arbitrary Pockets with Islands［J］.International Journal of Advanced Manufacturing Technology，1996，12（3）：174－179.

［4]Jeong J，Kim K.Generation of Tool Paths for Machining Free－form Pockets with Islands Using Distance Maps［J］.International Journal of Advanced Manufacturing Technology，1999，15（5）：311－316.

［5]Kim D S.Polygon Offsetting Using a Voronoi Diagram and Two Stacks［J］.Computer－aided Design，1998，30（14）：1069－1078.

［6]Lee C S，Phan T T，Kim D S.2DCurve Offset Algorithm for Pockets with Islands Using a Vertex Offset［J］.International Journal of Precision Engineer and Manufacturing，2009，10（2）：127－135.

［7]Held M，Lukacs G，Andor L.Pocket Machining Based on Contour－parallel Tool Paths Generated by Means of Proximity Maps［J］.Computer－aided Design，1994，26（3）：189－203.

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

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

［10]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.

［11]Castelino K，D’Souza R，Wright P K.Tool Path Optimization for Minimizing Airtime During Machining［J］.Journal of Manufacturing Systems，2003，22（3）：173－180.

［12]Hinduja S，Mansor M S A，Owodunni O O.Voronoi－diagram－based Linking of Contourparallel Tool Paths for Two－and－a－half－dimensional Closed－pocket Machining［J］.Proc.IMech，Part B：Journal of Engineering Manufacture，2010，224（9）：1329－1350.

［13]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.

［14]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.

［15]張鳴，劉偉軍，卞宏友.基于自由區域的環切軌跡優化連接方法［J］.中國機械工程，2011，22（4）：468－473.