何 森，張李超*，牛其華，張軍飛

(1.華中科技大學(xué) 材料科學(xué)與工程學(xué)院，湖北 武漢 430074；2.廣州中望龍騰軟件股份有限公司，廣東 廣州 510635)

0 引 言

在自動化加工中，刀位軌跡生成算法是關(guān)系到加工精度的關(guān)鍵部分。傳統(tǒng)的刀位軌跡生成算法中，計算加工路徑的常見方式有等參數(shù)線法[1]、截平面法[2]、等殘留高度法等[3]。其中，截平面法是利用一組平行的平面簇和網(wǎng)格表面或其等距面求交來獲得刀位軌跡，與環(huán)切四軸加工方案十分契合。但是采用諸如光固化立體造型(STL)模型或參數(shù)曲面模型作為輸入數(shù)據(jù)的刀位軌跡生成算法，往往在進(jìn)行必要的模型求交運算中會造成算法效率瓶頸。

在模型求交過程中，體素模型由于其自身的體素單元離散性特點而具備高效、快速的優(yōu)越性，因此將傳統(tǒng)CAD/CAM中應(yīng)用的常見模型如STL模型進(jìn)行體素化，則可以解決傳統(tǒng)刀位軌跡生成算法中由于布爾求交運算造成的效率瓶頸問題。國內(nèi)外對于體素化的研究有許多，王鴻亮等[4]則對傳統(tǒng)八叉樹方式進(jìn)行改進(jìn)，提出了一種面向STL模型的雙層次八叉樹的體素化方法；LORENSEN W E和CLINE H E提出的Marching-Cube算法[5]，用一個邊交叉點的案例表來描述三維數(shù)據(jù)中的面是如何與立方體相交的，該方法成為了體素化技術(shù)中的標(biāo)志性算法；吳耕宇等[6]利用幾何求交原理進(jìn)行了三角網(wǎng)格模型的表面體素化，模型的內(nèi)部體素化則利用掃描線種子填充算法實現(xiàn)。

以上體素化算法都只是單純地將模型進(jìn)行體素化的過程，并沒有將體素化算法與刀位軌跡生成算法進(jìn)行有機(jī)結(jié)合。此外，由于以上算法把模型進(jìn)行完整體素化，在對大型模型的處理時往往造成巨額的內(nèi)存空間消耗。

本文將基于截平面法的“逐平面計算”原則，結(jié)合每層刀位軌跡計算過程，在降維體素化方法的基礎(chǔ)上，實現(xiàn)一種動態(tài)局部體素化技術(shù)，進(jìn)而提出一種基于局部體素模型的STL模型加工路徑干涉檢測和處理算法。

1 動態(tài)局部體素化

1.1 局部體素化

在二維像素圖像中，分辨率等于像素點個數(shù)與圖像面積的比值，類似地本文中體素模型的分辨率等于三維體素單元個數(shù)與模型體積之比。因此體素單元越小，分辨率越高，越能精確地表達(dá)模型細(xì)節(jié)。但是在傳統(tǒng)全局體素化算法中，無法避免離散精度和內(nèi)存容量之間的沖突，即：

(1)

式中：r—離散體素邊長；V—模型體積；M—所需要內(nèi)存容量。

可見在一定體積V下，離散模型所需內(nèi)存容量與體素單元邊長的三次方成反比，在有限的內(nèi)存限制下，全局體素化方法難以做到用精細(xì)、巨量的體素群來精確表達(dá)模型。

為了在有限的內(nèi)存容量中，以更精確地體素模型表達(dá)原始模型，基于文獻(xiàn)[7]中全局體素化算法，本文通過將體素化的范圍限制在原始模型的一段區(qū)域內(nèi)，構(gòu)建局部體素模型，如圖1所示。

圖1 模型中的局部區(qū)域

基于截平面法的刀位軌跡生成算法需要在刀具體的范圍內(nèi)判斷干涉問題，因此局部體素化的區(qū)域范圍需要依據(jù)干涉處理算法對于體素范圍的需求來確定。將每次體素化的區(qū)域P中的高度范圍限制在[h-R,h+R]中(其中：h—當(dāng)前截平面高度，R—刀具半徑)。

這個思路實際上是通過將模型全局體素化過程所需的三次空間復(fù)雜度O(r3)，轉(zhuǎn)變?yōu)镹次局部體素化過程所需的空間復(fù)雜度N*O(r2)(其中：N—截平面數(shù))，從而達(dá)到在有限內(nèi)存限制下，減小干涉檢測過程中所需要的體素化數(shù)據(jù)內(nèi)存容量，提高體素精度的目的。原始STL模型的高度可能達(dá)到幾百毫米，而通過局部體素化將體素化的區(qū)域范圍限制刀具直徑范圍，通常只有幾到十幾毫米。隨著STL模型的體積增大，這種優(yōu)勢更加明顯。

1.2 動態(tài)局部體素化

1.2.1 算法原理

在CAM中，截平面法是以在Z方向上等間距的截面簇與整體模型截交后，計算每層截面上輪廓的刀位軌跡，然后算法要對所有截平面層生成的上加工路徑進(jìn)行基于局部體素的干涉檢測和處理。

動態(tài)局部體素化算法是在截平面法“逐個平面計算”的動態(tài)過程中，在每層截平面上計算刀位軌跡前，預(yù)先進(jìn)行局部體素化，生成指定截平面高度附近的局部體素模型，從而提供本次刀位軌跡生成后干涉處理所需要的輸入模型數(shù)據(jù)。此外，截平面間距即加工行距則可以以體素邊長為單位進(jìn)行自由設(shè)定，從而進(jìn)行下一截平面上加工路徑的計算。

由于截平面簇的間距d一般小于刀具半徑R，依據(jù)局部體素化區(qū)域的選擇，必然導(dǎo)致相鄰兩次局部體素化的范圍發(fā)生重合。而重合的這部分體素化數(shù)據(jù)是可復(fù)用的。因此，算法設(shè)計在內(nèi)存中維持一個存儲區(qū)域，每次局部體素化前先將可復(fù)用部分?jǐn)?shù)據(jù)移動、保存，然后再計算需要重新體素化的部分?jǐn)?shù)據(jù)，從而保證數(shù)據(jù)的高效利用。

1.2.2 相關(guān)定義

基于局部體素化算法，結(jié)合截平面法生成刀位軌跡的過程，實現(xiàn)動態(tài)局部體素化算法。為描述算法過程，定義如下：

定義1。原始STL模型的范圍為V，V的最小包圍長方體分別在x、y、z軸向上的范圍為：l0、l1、w0、w1、h0、h1。

定義2。體素化的分辨率為r，代表了離散體素單元的邊長，單位為mm。

定義3。等截平面法的平面簇間距為d，單位mm。

定義4。刀具半徑為R，單位mm。

為了便于描述，筆者假設(shè)刀具為球頭刀，則可以用一個三維數(shù)組Voxel[x][y][z]來描述需要體素化的區(qū)域，這個數(shù)組容量為：

(2)

即這個三維數(shù)組始終表示了一個長、寬、高分別為(l1-l0)、(w1-w0)、2R的三維柵格長方體區(qū)域。記3個維度上的數(shù)組大小分別為：mX、mY、mZ。

定義5。在一次沿高度方向的體素化中，三維數(shù)組中需要更新數(shù)據(jù)沿Z向的范圍為[si,ei]。

定義6。對于模型空間中一點A坐標(biāo)為(x，y，z)，A點對應(yīng)的體素元素索引為(X，Y，Z)，則坐標(biāo)-索引換算公式為：

(3)

(4)

(5)

定義7。三維光柵空間中，體素單元為6鄰接關(guān)系；在二維光柵空間中，像素單元為4鄰接關(guān)系[8]。

1.2.3 算法描述

由于具有對稱性，在此只描述從h0高度開始向Z軸正向計算的方向。算法過程流程圖如圖2所示。

圖2 動態(tài)局部體素化算法流程圖

(1)初始截平面高度h=h0；

(2)把當(dāng)前目標(biāo)平面高度h，傳入局部體素化算法模塊，記錄上次截平面高度為h′；

(3)判斷上一次體素化數(shù)據(jù)能否復(fù)用：

①如果是第一次體素化，或者|h-h′|>2R，令si=0，ei=mZ-1，進(jìn)入步驟(5)；

②如果|h-h′|>2R，則本次將要體素化區(qū)域的高度范圍與當(dāng)前已體素化的區(qū)域發(fā)生重合，進(jìn)入步驟(4)；

(5)計算本次體素化區(qū)域的高度范圍[ha,hb]，計算公式為：

ha=(h-R)+r×si

(6)

hb=(h+R)+r×ei

(7)

①當(dāng)ha

②當(dāng)hb>h1時，將模型h1高度作為體素化的結(jié)束高度hb；

(6)對模型高度ha到高度hb范圍區(qū)域進(jìn)行降維體素化算法，將體素化的結(jié)果保存在三維數(shù)組中，將三維數(shù)組作為算法輸出，轉(zhuǎn)入刀位路徑生成算法；

(7)本截平面高度上刀位路徑計算完畢后，令h=h+d，若h

在每次局部體素化時，將上一次計算的數(shù)據(jù)的復(fù)用過程如圖3所示。

圖3 數(shù)據(jù)復(fù)用過程

由于數(shù)據(jù)保存在內(nèi)存中，這種移動比重新計算體素化要快。

2 干涉檢測與處理

2.1 干涉檢測和處理的常見方法

由于基礎(chǔ)刀位軌跡無法作為CAM結(jié)果輸出給后處理器，對生成的基礎(chǔ)刀位軌跡信息，需要進(jìn)行刀頭處的局部干涉和刀軸整體的全局干涉檢測以及調(diào)整。根據(jù)不同的模型表達(dá)方式以及不同的刀位軌跡算法，干涉的檢測有不同的方法。

(1)對于局部干涉的情況，李敏[10]針對三角網(wǎng)格模型提出了一種無干涉刀位點生成算法，此外在三軸加工領(lǐng)域中被廣泛使用的Z-Map加工方法是一種基于二維柵格模型的算法；

(2)對于全局干涉的情況，一旦發(fā)生全局干涉，則必須調(diào)整刀軸矢量，使得刀具能夠從一個無干涉的角度進(jìn)刀，從而完成加工[11]。李萬軍[12]、段裕剛[13]等學(xué)者主要針對NURBS曲面模型提出了全局干涉檢測算法。

由上述算法可見：在檢測和處理干涉問題中，通常都會用到幾何模型的求交運算、布爾運算。而在STL模型的布爾運算中，需要將待求交物體(刀具頭或刀軸)進(jìn)行建模后再與STL模型的N個三角面片進(jìn)行遍歷求交，這個相交三角面片搜索過程造成了算法在效率上的瓶頸。

而使用體素化模型進(jìn)行干涉的檢測和處理的方法中，只需在一個公共的體素化空間中，對刀具進(jìn)行體素化，檢查其中是否有體素單元同時位于另一實體模型內(nèi)。這種求交方法不涉及到布爾運算以及算術(shù)計算過程因此算法速度很快，其時間復(fù)雜度只與模型體素數(shù)目k有關(guān)，可以達(dá)到常數(shù)時間O(k)。故利用體素模型的干涉檢測和處理算法具備快速、簡潔、準(zhǔn)確的優(yōu)勢。

2.2 局部干涉檢測處理算法

按照上述原理，局部干涉的檢測是將刀具頭進(jìn)行體素化，并且為了加速這一過程，避免重復(fù)進(jìn)行干涉檢測，體素化的過程從刀具頭的底部開始向刀具頭頂點進(jìn)行。在體素化過程中，一旦發(fā)現(xiàn)重合體素單元，則該重合體素單元必然是發(fā)生“過切”現(xiàn)象的最嚴(yán)重點。因此本研究計算所需的平移距離后，對刀具進(jìn)行沿刀軸矢量的平移。

對于局部干涉的情況，在該算法中，干涉檢測與處理能同時完成。假設(shè)使用刀具為球頭刀，算法描述如下：

(1)以輪廓環(huán)為單位，遍歷所有刀位軌跡，若遍歷完畢，則算法結(jié)束；

(2)對每個刀位軌跡上的每個刀位點，對該處的刀具頭半球體進(jìn)行體素化。若該刀位軌跡中所有點遍歷完畢，則返回步驟(1)；

(3)在體素化過程中，若存在體素單元i位于局部體素模型的實體內(nèi)，則說明存在干涉現(xiàn)象，進(jìn)入步驟(4)，否則說明無干涉，返回步驟(2)檢測下一個刀位點；

(4)計算相交體素單元i到刀頭半球面頂點在刀軸方向上的投影距離l，將刀位點沿著刀軸方向平移l長度，返回步驟(3)再次檢測。

通過以上算法，確保了刀位點處的刀具頭不會發(fā)生局部干涉現(xiàn)象。

2.3 全局干涉處理算法

2.3.1 全局干涉處理算法原理

全局干涉的檢測與2.2節(jié)中描述的局部干涉檢測算法類似，先對刀軸進(jìn)行體素化，進(jìn)而檢查是否具有重合體素單元。但是過程更為復(fù)雜。首先對全局干涉情況進(jìn)行算法原理說明：

定義1：與刀具軸發(fā)生全局干涉的模型部分定義為干涉體Q；截平面上當(dāng)前加工的輪廓環(huán)為L。

(1)無干涉方向的規(guī)定

全局干涉的一般處理過程如圖4(a)所示。在加工輪廓環(huán)L時發(fā)生全局干涉，需要將刀軸沿一定旋轉(zhuǎn)方向旋轉(zhuǎn)，從而避開發(fā)生干涉的干涉體Q，將刀軸矢量從原始方向O旋轉(zhuǎn)到P0或P1方向。

定義2：稱P0和P1方向為相對干涉體Q的無干涉臨界方向(其中：P0—順時針調(diào)整方向，P1—逆時針調(diào)整方向)。

當(dāng)出現(xiàn)特殊的自干涉現(xiàn)象如圖4(b)所示。此時P0或P1相對于原始方向O的調(diào)整角度大于90°，必然發(fā)生與輪廓環(huán)L的自干涉，這種情況下P0和P1可能缺失一個或者都不存在。

圖4 全局干涉及一般處理

(2)P0和P1的獲取

由于全局干涉發(fā)生的區(qū)域是一個重合的三維空間，不能僅考慮當(dāng)前截平面上的無干涉方向P′，否則盡管在計算出在當(dāng)前平面上無干涉的起始方向，但該方向在空間上仍存在干涉。

因此，必須考慮在刀具體的體積范圍內(nèi)、發(fā)生干涉的所有重合體素所在的平面高度。本文首先根據(jù)2.1所描述的干涉檢測原理，獲取刀軸每個高度平面上的重合體素，在重合體素所在平面高度上利用掃描先線種子填充算法進(jìn)行邊界搜尋，從而生成的干涉體Q在引起干涉的各個平面高度上體素輪廓環(huán)集合。根據(jù)這些輪廓環(huán)，進(jìn)一步計算出能夠包圍所有輪廓環(huán)的最小矩形Rect。

刀位點與Rect的位置關(guān)系示意圖如圖5所示。

圖5 刀位點與Rect的位置關(guān)系示意圖

根據(jù)刀位點的和Rect的位置關(guān)系，分別計算出全局無干涉的刀軸起始方向P0和P1。

(3)無干涉刀軸矢量N的生成

設(shè)當(dāng)前點為i，且點i-1處無全局干涉發(fā)生，由于模型的連續(xù)性，從點i開始的一組刀位點{i，i+1，…}都可能與干涉體Q發(fā)生全干涉，判斷依據(jù)是這些刀位點發(fā)生干涉的原始刀軸矢量O均穿過矩形Rect。

定義3：與干涉體Q發(fā)生全局干涉的一組刀位點{i，i+1，…}，稱為Q的干涉序列。

Q的干涉序列{i，i+1，…}中刀位點的刀軸矢量N的調(diào)整為：若經(jīng)原理(2)的計算方法，至少P0存在，則Ni=(Ni-1+P0)；若P0不存在但P1存在，則取Ni=P1。

2.3.2 全局干涉處理算法描述

基于上述原理，全局干涉檢測處理算法如流程圖6所示。

詳細(xì)描述如下：

(1)針對刀位點C：體素化刀軸，且體素化過程從刀軸最前端開始，向末端進(jìn)行。記錄每個Z值平面上的第一個重合體素單元，歸并到集合S中；

圖6 全局干涉檢測與處理算法流程圖

(2)若集合S為空，則無干涉發(fā)生，令C=C+1，返回步驟(1)；否則進(jìn)入(3)；

(3)若Rect存在且刀位點C的原始刀軸矢量經(jīng)過Rect，則進(jìn)入步驟(5)，否則進(jìn)入步驟(4)；

(4)根據(jù)記錄的重合體素單元集合S，利用掃描線種子填充算法，搜尋每個Z值平面上造成干涉的部分模型實體Q的輪廓環(huán)，并根據(jù)邊界生成能夠在二維X-Y平面上包圍所有輪廓環(huán)的最小矩形Rect；

(5)判斷刀位點C與Rect位置關(guān)系：

①點C位于Rect外：分別作Rect的4個頂點到刀具頭所在圓的切線，取其中夾角最大的兩個作為相對A的無干涉起始方向P0和P1；

②點C位于Rect內(nèi)：從每個輪廓環(huán)上的干涉點開始，沿著輪廓環(huán)向兩個方向遍歷輪廓，計算所有點到刀具頭所在圓的切線，分別取兩個遍歷方向上相對原始刀軸方向偏轉(zhuǎn)最大的切線作為相對Q的無干涉起始方向P0和P1；

(6)判斷P0和P1是否存在，即是否仍然存在干涉：

①若均不可使用則該點無法生成無干涉刀軸，另C=C+1，返回步驟(1)；

②P0和P1至少存在一個，則利用2.2.3中原理進(jìn)行計算刀位點C的無干涉刀軸矢量，另C=C+1，返回步驟(1)。

3 舉例驗證

企鵝STL模型如圖7所示。

圖7 企鵝STL模型

該模型尺寸為：長165 mm、寬100 mm，高150 mm。選用φ=4 mm的球頭刀具，刀軸長假設(shè)為L=100 mm。

3.1 局部體素化

企鵝模型的體素化效果圖如圖8所示。

圖8 體素化效果對比圖

在計算機(jī)上，本研究以Byte數(shù)據(jù)類型表征一個體素單元，按公式(1)進(jìn)行計算，在8 G有限內(nèi)存下得到海豚模型、BayMax(動畫人物)模型和埃菲爾鐵塔模型的全局體素化和一次動態(tài)局部體素化的極限精度(在前提刀具尺寸下)，如表1所示。

表1 8 G內(nèi)存下兩種體素化精度對比表

結(jié)果表明：在相等的內(nèi)存容量下，相比于全局體素化算法，該局部體素化算法可以使用更高的精度，并且隨著模型體積的增大二者的差距越明顯。

以海豚模型為例的效果對比圖如圖9所示。

圖9顯示：在全局體素化下，海豚嘴角處十分粗糙失真，在局部體素化下則可以精細(xì)表達(dá)出模型細(xì)節(jié)。這一點在四軸雕刻領(lǐng)域極為重要。

3.2 干涉檢測和處理算法

干涉檢測與處理效果圖如圖10所示。

其中，圖10(a，b)是利用基于體素模型的干涉檢測算法，分別在高度h=7 mm和h=110 mm處刀位軌跡上檢測出的局部干涉和全局干涉現(xiàn)象；圖10(c，d)則是使用干涉處理算法后，在高度h=7 mm和h=110 mm刀位軌跡上發(fā)生干涉出生成的無干涉刀具位置效果圖?？梢钥闯觯航?jīng)過算法的調(diào)整，生成的刀位軌跡避免了局部干涉和全局干涉問題。

圖10 干涉檢測與處理

3.3 實例對比

利用本文算法與Power Mill CAM軟件生成的“旋轉(zhuǎn)精加工路徑”，在“企鵝”模型雙腳加工路徑干涉段和圖9中模型魚鰭干涉處產(chǎn)生的加工路徑進(jìn)行對比，如圖11所示(圖中黑色線條表示在發(fā)生干涉的刀位點處，算法調(diào)整后的刀具方向)。

圖11 本文算法對比Power Mill軟件

從圖11(a)中可以看出：POWERMILL軟件對于刀具發(fā)生全局干涉的區(qū)域未進(jìn)行細(xì)節(jié)處理，導(dǎo)致加工件細(xì)節(jié)失真。

4 結(jié)束語

針對模型求交方法導(dǎo)致的刀具干涉處理算法的效率瓶頸問題，本文研究了一種基于STL模型動態(tài)局部體素化技術(shù)的四軸環(huán)切干涉處理算法，得出以下結(jié)論：

(1)設(shè)計動態(tài)局部體素化技術(shù)，在逐平面計算刀位軌跡的同時，動態(tài)生成局部區(qū)域的體素模型，解決了大型STL模型在體素化時的空間復(fù)雜度過高問題；

(2)利用體素模型快速求交原理，進(jìn)行局部、全局干涉檢測，該檢測方法具備常數(shù)時間的時間復(fù)雜度效率，因此相對于傳統(tǒng)的干涉檢測過程該算法能夠更高效快速地檢測干涉現(xiàn)象；

(3)算法對于全局干涉進(jìn)行刀軸智能調(diào)節(jié)，能夠在平面范圍內(nèi)準(zhǔn)確的處理干涉刀軸，并且具有高度的健壯性，能夠處理多種全局干涉情況。

本文算法高效、準(zhǔn)確，具備可行性。從整體看，在全局干涉處理過程需要進(jìn)一步完善，以避免調(diào)整刀軸后的二次干涉現(xiàn)象。