基于位置有效性檢測(cè)的環(huán)形刀路偏置算法研究

朱洪軍，張 亞，2

(1.浙江工業(yè)職業(yè)技術(shù)學(xué)院數(shù)控學(xué)院，浙江紹興 312000;2.浙江大學(xué)機(jī)械工程系，杭州 310027)

基于位置有效性檢測(cè)的環(huán)形刀路偏置算法研究

朱洪軍1，張 亞1，2

(1.浙江工業(yè)職業(yè)技術(shù)學(xué)院數(shù)控學(xué)院，浙江紹興 312000;2.浙江大學(xué)機(jī)械工程系，杭州 310027)

數(shù)控加工的層切法中經(jīng)常會(huì)用到環(huán)形刀路。在環(huán)形刀路生成過(guò)程中，關(guān)鍵算法是多邊形的偏置算法。在偏置過(guò)程中，偏置曲線上可能會(huì)產(chǎn)生局部問(wèn)題，比如局部尖角、無(wú)效環(huán)等。這些局部問(wèn)題必須消除，否則得到的環(huán)形刀路將無(wú)法使用。論文提出一種基于頂點(diǎn)位置有效性檢測(cè)的多邊形偏置算法。通過(guò)實(shí)例測(cè)試，表明該算法能夠很好地消除在偏置過(guò)程中產(chǎn)生的局部問(wèn)題，保證環(huán)形刀路的準(zhǔn)確有效。

環(huán)形刀路;多邊形偏置;位置有效性

0 引言

對(duì)于現(xiàn)代化的產(chǎn)品來(lái)說(shuō)，其外形設(shè)計(jì)中大量使用自由曲線和自由曲面，用傳統(tǒng)的機(jī)械加工方法相當(dāng)困難［1］。產(chǎn)品的粗加工是加工過(guò)程的一個(gè)重要環(huán)節(jié)，其目的是快速切除工件毛坯上的大部分多余材料，大約70%的原材料由粗加工過(guò)程切除，大量的加工時(shí)間消耗在粗加工過(guò)程中。因而，開(kāi)發(fā)出快速、高效的加工刀路生成算法，對(duì)于縮短加工周期、提高加工效率具有重要的實(shí)際意義。目前，應(yīng)用層切法進(jìn)行數(shù)控粗加工在國(guó)內(nèi)已引起了廣泛的研究［2-4］。但是，生成環(huán)形刀路有一個(gè)主要障礙，就是多邊形的偏置問(wèn)題。文獻(xiàn)中對(duì)多邊形偏置問(wèn)題的解決方法主要可分為以下三種:Voronoi圖法、邊平移法、角平分線法。

Voronoi圖最早由Persson［5］引進(jìn)到刀具路徑生成領(lǐng)域。這種方法能夠很好地處理由直線和圓弧構(gòu)成的輪廓的偏置問(wèn)題。Held［6］繼續(xù)發(fā)展了Persson的理論，使Voronoi圖能夠處理帶小島的輪廓偏置問(wèn)題。雖然Voronoi圖一直被認(rèn)為是一種高效的、魯棒性好的算法，但是它在計(jì)算接近圓弧半徑區(qū)域的偏置時(shí)卻容易出錯(cuò)［7-9］?；谶吰揭频姆椒ㄓ梢韵氯綐?gòu)成:①多邊形每條邊在沿著垂直于該邊的方向上平移給定的偏置距離;②相鄰兩條偏置邊之間如果不相交則用半徑大小等于偏置距離的圓弧銜接，如果相交則以交點(diǎn)為節(jié)點(diǎn)修剪兩相鄰偏置邊;③檢測(cè)偏置多邊形上所有的自相交環(huán)并移除這些自相交環(huán)。Choi等學(xué)者［8，10］基于邊偏置方法提出了著名的PWID算法。在偏置過(guò)程中產(chǎn)生所有的局部或全局無(wú)效環(huán)都可以用PWID測(cè)試方法消除。在角平分線的方法中，初始偏置曲線在原始曲線每個(gè)頂點(diǎn)的角平分線上取點(diǎn)連接而成。在初始偏置曲線上，可能存在局部問(wèn)題，比如局部尖角、無(wú)效環(huán)等。Kim等學(xué)者［11-12］通過(guò)檢測(cè)偏置邊的方向有效性來(lái)消除局部問(wèn)題。對(duì)一條偏置邊，如果它的方向和它的原始多邊形上對(duì)應(yīng)邊方向相反的話，那么它是方向無(wú)效的;反之則是方向有效的。Lee等學(xué)者［7］在檢查偏置邊方向有效的基礎(chǔ)上，又提出了檢查偏置邊位置有效性。對(duì)一條偏置邊，如果它的兩個(gè)端點(diǎn)都在偏置區(qū)域里面，那么它是位置有效的;反之則是位置無(wú)效的。

本文在Lee等方法的基礎(chǔ)上，提出基于偏置頂點(diǎn)位置有效性的方法來(lái)檢測(cè)并消除局部問(wèn)題。其中，初始偏置曲線用基于頂點(diǎn)偏置的方法獲得，然后標(biāo)記出位置無(wú)效點(diǎn)兩側(cè)的前置有效點(diǎn)和后置有效點(diǎn)。在此基礎(chǔ)上，通過(guò)文中提出的4個(gè)步驟移除期間所有的位置有效點(diǎn)，很好地消除了刀具在偏移過(guò)程中產(chǎn)生的局部問(wèn)題。

1 初始偏置曲線生成

本文中，初始偏置曲線是通過(guò)角平分線生成的。如圖 1 所示，點(diǎn) Pi－1，Pi，Pi+1是原始曲線上 3 個(gè)連續(xù)點(diǎn)，向量 ei－1和 ei分別是向量 PiPi－1和 PiPi+1的單位向量，R是給定的偏置距離，點(diǎn)Oi是點(diǎn)Pi對(duì)應(yīng)的偏置點(diǎn)，θi是角Pi－1PiPi+1的大小。圖1a所示是當(dāng)0＜θi＜π的情況，而圖1b是當(dāng)?shù)那闆r。結(jié)合圖1中的兩種情況，偏置點(diǎn)Oi可由以下公式(1)計(jì)算得到:

圖1 基于角平分線的頂點(diǎn)偏置

公式(1)并沒(méi)有包含θi=π的情況，這是因?yàn)樵谟?jì)算初始偏置曲線之前，首先要對(duì)原始曲線的每對(duì)相鄰邊進(jìn)行檢查，如果存在相鄰邊所夾的角是平角，表明這兩條相鄰邊在同一直線上，則刪除兩相鄰邊的中間的頂點(diǎn)。對(duì)原始曲線的所有頂點(diǎn)按公式(1)計(jì)算出相應(yīng)的偏置點(diǎn)，然后將這些偏置點(diǎn)依次連接起來(lái)，便能得到初始偏置曲線，如圖2a所示。在圖2a中，位于外部的曲線是原始曲線，位于內(nèi)部的曲線是初始偏置曲線。

2 偏置頂點(diǎn)位置有效性檢測(cè)

在如圖2所示的初始偏置曲線上，存在局部尖角和無(wú)效環(huán)。這些局部問(wèn)題是由位置無(wú)效的偏置頂點(diǎn)引起的。如圖3所示，對(duì)于一個(gè)偏置頂點(diǎn)O，如果O位于偏置區(qū)域里面，那么定義O為位置無(wú)效的偏置頂點(diǎn);否則定義O為位置無(wú)效的偏置頂點(diǎn)。對(duì)圖(3)中的四個(gè)偏置點(diǎn) Oi－1，Oi，Oi+1，Oi+2中，按照上面的定義，可知Oi和Oi+1為位置無(wú)效的偏置點(diǎn)，而Oi－1和Oi+2為位置有效的偏置點(diǎn)。

圖2 初始偏置曲線生成

圖3 原始曲線的偏置區(qū)域

檢測(cè)一個(gè)偏置頂點(diǎn)O是否在偏置區(qū)域里面需要計(jì)算該點(diǎn)到原始曲線的最近距離。如果最近距離小于或大于給定的偏置距離，那么這個(gè)偏置頂點(diǎn)就在偏置區(qū)域里面，從而判斷該點(diǎn)為位置無(wú)效的偏置頂點(diǎn);如果最近距離恰好等于偏置距離，則可以判斷該點(diǎn)為位置有效的偏置頂點(diǎn)。原始曲線可以看成是由一系列線段按順序拼接而成的，所以要計(jì)算某個(gè)偏置頂點(diǎn)到原始曲線的距離，只需要遍歷計(jì)算該點(diǎn)到組成原始曲線所有的線段的距離并且從中找出最小值即可。計(jì)算點(diǎn)到線段的距離時(shí)需要注意的是，如圖4所示，假設(shè)PjPj+1是原始曲線上的其中一條線段，Pa，Pb，Pc同一平面上的三個(gè)點(diǎn)，由圖可見(jiàn)，Pa在PjPj+1投影不在線段PjPj+1上但在Pj的左邊，這種情況下Pa到線段PjPj+1的距離為PaPj的長(zhǎng)度;同理Pc到線段PjPj+1的距離就是PcPj+1的長(zhǎng)度;Pb在PjPj+1投影在線段PjPj+1上，這種情況下Pb到線段PjPj+1的距離就是PbP'b的長(zhǎng)度。

圖4 計(jì)算點(diǎn)到線段的距離

3 局部問(wèn)題移除

局部問(wèn)題是由位置無(wú)效的偏置頂點(diǎn)引起的。在處理這些位置無(wú)效的偏置頂點(diǎn)之前，首先需要定位它們前面和后面的位置有效點(diǎn)。實(shí)際上，位置無(wú)效點(diǎn)有時(shí)可能是單個(gè)出現(xiàn)的，如圖2a中的O2;或者有時(shí)可能連續(xù)出現(xiàn)，如圖2a 中的點(diǎn)列 O4，O5，O6，O7，O8或O11，O12，O13。無(wú)論是那種情況，記錄下位置無(wú)效點(diǎn)序列之前的一個(gè)前置有效點(diǎn)和之后的一個(gè)后置有效點(diǎn)，分別表示為Ob和Of。顯然，在Ob和Of之間的所有點(diǎn)都是位置無(wú)效點(diǎn)。如圖2a所示，對(duì)偏置頂點(diǎn)O2來(lái)說(shuō)，它的前置有效點(diǎn)是O1，它的后置有效點(diǎn)是 O3。對(duì)頂點(diǎn)序列 O4，O5，O6，O7，O8來(lái)說(shuō)，它們的前置有效點(diǎn)是O3，他們的后置有效點(diǎn)是O9。具體查找前置有效點(diǎn)和后置有效點(diǎn)的方法可按流程圖5來(lái)實(shí)現(xiàn)。在圖5中，b和f分別是輸出的前置有效點(diǎn)和后置有效點(diǎn)的在偏置曲線中的點(diǎn)序。

圖5 標(biāo)記前置有效點(diǎn)和后置有效點(diǎn)流程圖

對(duì)一個(gè)局部問(wèn)題來(lái)說(shuō)，已經(jīng)確定了前置有效點(diǎn)Ob和后置有效點(diǎn)Of，那么也可以將Ob附近兩條前置線段Ob－1Ob和ObOb+1以及Of附近兩條后置線段Of－1Of和OfOf+1。移除局部問(wèn)題具體包含以下四個(gè)步驟。

步驟1:計(jì)算 ObOb+1和 Of－1Of的交點(diǎn) PI，檢測(cè) PI是否是位置有效點(diǎn)。如果PI是位置有效點(diǎn)的話，那么從偏置曲線中移除點(diǎn)列Ob+1至Of－2，并且令Of－1=PI;如果PI是一個(gè)位置無(wú)效點(diǎn)的話，那么跳至步驟2。

步驟 2:計(jì)算 Ob－1Ob和 Of－1Of的交點(diǎn) PI，檢測(cè) PI是否是位置有效點(diǎn)。如果PI是位置有效點(diǎn)的話，那么從偏置曲線中移除點(diǎn)列Ob+1至Of－2，并且令Of－1=PI;如果PI是一個(gè)位置無(wú)效點(diǎn)的話，那么跳至步驟3。

步驟3:計(jì)算 ObOb+1和 OfOf+1的交點(diǎn) PI，檢測(cè) PI是否是位置有效點(diǎn)。如果PI是位置有效點(diǎn)的話，那么從偏置曲線中移除點(diǎn)列Ob+1至Of－2，并且令Of－1=PI;如果PI是一個(gè)位置無(wú)效點(diǎn)的話，那么跳至步驟4。

步驟4:計(jì)算 Ob－1Ob和 OfOf+1的交點(diǎn) PI，從偏置曲線中移除點(diǎn)列 ObOb+1至 Of－2，并且令 Of－1=PI。

如圖 2a 所示，對(duì)于點(diǎn)列 O4，O5，O6，O7，O8來(lái)說(shuō)，它們的前置點(diǎn)和后置點(diǎn)分別是O3和O9。從上述步驟1開(kāi)始，首先計(jì)算O3O4和O8O9的交點(diǎn)PI。因?yàn)镻I是位置有效點(diǎn)，所以直接移除無(wú)效點(diǎn) O4，O5，O6，O7，并且使O8=PI。這樣就可以消除由點(diǎn)列O4，O5，O6，O7，O8引起的局部問(wèn)題。對(duì)點(diǎn)列 O11，O12，O13來(lái)說(shuō)，也只需要上述步驟1就能消除局部問(wèn)題。而對(duì)位置無(wú)效點(diǎn)O2來(lái)說(shuō)，它的前置點(diǎn)和后置點(diǎn)分別是O1和O3。從步驟1開(kāi)始，首先計(jì)算O1O2和O2O3的交點(diǎn)PI。顯然，在此例中，交點(diǎn)PI和O2重合，而O2是位置無(wú)效點(diǎn)，所以跳至步驟2，重新計(jì)算O0O1和O2O3的交點(diǎn)PI。此時(shí)PI是一個(gè)位置有效點(diǎn)，直接令O2=PI。這樣由點(diǎn)O2帶來(lái)的局部尖角問(wèn)題也能消除了。

值得注意的是，每次消除一個(gè)局部問(wèn)題的時(shí)候，在偏置曲線上點(diǎn)的序號(hào)會(huì)發(fā)生一次更新。當(dāng)初始偏置曲線上所有的點(diǎn)都遍歷過(guò)一遍時(shí)，就能移除所有的局部問(wèn)題。圖2b顯示了移除所有局部問(wèn)題的偏置曲線。

4 實(shí)例測(cè)試

本文提出的算法用C++語(yǔ)言編程實(shí)現(xiàn)并且測(cè)試了一些例子。圖6為其中兩個(gè)例子。圖6a為圖2中圖形的連續(xù)偏置，圖6b為一個(gè)“黑桃”形狀的連續(xù)偏置。從這兩張圖中，我們可以看出文中提出的方法能夠很好的處理偏置過(guò)程中局部問(wèn)題。與Lee等人的算法進(jìn)行比較可以發(fā)現(xiàn)，Lee等人的算法不僅需要考慮偏置線段的位置有效性還需考慮其方向有效性，而本文算法只需要考慮偏置點(diǎn)的位置有效性，算法結(jié)構(gòu)和步驟更加簡(jiǎn)單，計(jì)算時(shí)間更快。

圖6 文中提出的算法的兩個(gè)實(shí)例

5 總結(jié)

本文提出了數(shù)控粗加工層切法的一種新的偏置算法，該方法可以對(duì)偏置頂點(diǎn)的位置有效性進(jìn)行檢測(cè)。初始偏置曲線通過(guò)角平分線的方法獲得。在初始偏置曲線上，可能存在局部問(wèn)題，如局部尖角、局部無(wú)用環(huán)等。這些局部問(wèn)題通過(guò)檢測(cè)偏置曲線上頂點(diǎn)的位置有效性來(lái)消除。對(duì)偏置頂點(diǎn)來(lái)說(shuō)，如果該點(diǎn)位于偏置區(qū)域里面，那么這些點(diǎn)被定義為位置無(wú)效點(diǎn)。通過(guò)圖5中的流程圖標(biāo)記出 位置無(wú)效點(diǎn)兩側(cè)的前置有效點(diǎn)和后置有效點(diǎn)。在此基礎(chǔ)上，通過(guò)文中提出的4個(gè)步驟移除期間所有的位置有效點(diǎn)。該方法可以消除層切法數(shù)控加工過(guò)程中環(huán)形刀路的局部問(wèn)題，保證環(huán)形刀路準(zhǔn)確有效。

［1］張永超，于洋，趙嫚嫚.加工中直線插補(bǔ)刀路的誤差評(píng)估修正研究［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2011(6):61－64.

［2］劉偉軍，張嘉易.計(jì)算機(jī)集成制造系統(tǒng)［J］.層切法模具粗加工中自適應(yīng)刀軌規(guī)劃方法，2005(9):1296－1300.

［3］莊海軍，周儒榮，安魯陵，等.實(shí)體模型的三軸數(shù)控粗加工刀軌生成算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15(1):81 －84.

［4］李學(xué)藝，王小椿，陳松，等.離散數(shù)據(jù)復(fù)雜曲面的粗加工［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15(3):338－342.

［5］ Persson H:NC machining of arbitrarily shaped pockets.Computer-Aided Design，1978，10(3):169 －174.

［6］Held M，Lukács G，Andor L:Pocketmachining based on contour-parallel tool paths generated by means of proximity maps.Computer-Aided Design，1994，26(3):189 －203.

［7］Lee C-S，Phan T-T，Kim D-S:2D curve offsetalgorithm for pockets with islands using a vertex offset.International Journal of Precision Engineering and Manufacturing，2009，10(2):127－135.

［8］ Choi BK，Park SC:A pair-wise offset algorithm for 2D point-sequence curve.Computer-Aided Design，1999，31(12):735－745.

［9］Dragomatz D，Mann S:A classified bibliography of literature on NC milling path generation.Computer-Aided Design，1997，29(3):239 －247.

［10］Park SC，Choi BK:Uncut free pocketing tool-paths generation using pair-wise offset algorithm.Computer-Aided Design，2001，33(10):739 －746.

［11］Kim H-C，Lee S-G，Yang M-Y:A new offset algorithm for closed 2D lines with Islands.International Journal of Advanced Manufacturing Technology，2006，29(Compendex):1169－1177.

［12］Kim H-C:Tool path generation for contour parallelmilling with incomplete mesh model.The International Journal of Advanced Manufacturing Technology，2010，48(5):443 －454.

(編輯 李秀敏)

Research on the Counter Parallel Tool Path O ffset Algorithm based on Position Validity Checking

ZHU Hong-jun1，ZHANG Ya1，2
(1.School of NC，Zhejiang Industry Polytechnic College，Shaoxing Zhejiang 312000，China;2.Department of Mechanical Engineering，Zhejiang University，Hangzhou 310027，China)

Counter parallel tool path plays an important role in CNC machining process.Initial offset curve is obtained by vertex offset via bisector.in the generation of counter parallel tool path，the key algorithm is polygon offset algorithm.On the initial offset curve，local problems，like invalid loops or sharp anglesmay exist.These local problems should be removed.Otherw ise，counter parallel tool path w ill not be able to use.A new polygon offset algorithm for Point-sequence curve offset based on the effectiveness of the vertex position detection is proposed.The algorithm has been programmed and tested，the results shows that the algorithm can deal wellw ith the local problems in point sequence offset.

counter parallel tool path;polygon offset;position validity

TH16;TG65

A

1001－2265(2013)03－0093－03

2012－10－23;

2012－11－28

朱洪軍(1979—)，男，浙江上虞人，浙江工業(yè)職業(yè)技術(shù)學(xué)院數(shù)控學(xué)院講師，碩士，研究方向?yàn)閿?shù)控技術(shù)等，(E－mail)48653963@qq.com。