Dividingcubes算法在數(shù)控仿真中的應(yīng)用

摘 要：切削計(jì)算是數(shù)控仿真系統(tǒng)中的重要組成部分，不同的切削算法直接影響切削效率與切削精度?；谄史至⒎襟w（dividing cubes）算法思想，對(duì)體素模型稍作改動(dòng)，提出了一種新的切削算法。仿真結(jié)果表明，基于改進(jìn)算法的切削面的重繪過程更加簡(jiǎn)潔，在保證切削精度的同時(shí)能有更高的切削效率。但是，由于算法根據(jù)毛坯的離散精度的不同，所需要的內(nèi)存空間也不同，當(dāng)毛坯的離散精度超過一定程度時(shí)，會(huì)增加切削計(jì)算的計(jì)算量，反而降低了切削計(jì)算的效率。

關(guān)鍵詞：數(shù)控仿真;體素模型;剖分立方體;切削計(jì)算

中圖分類號(hào)：TP391.9

文獻(xiàn)標(biāo)志碼：A

數(shù)控加工過程仿真是數(shù)控加工技術(shù)與虛擬現(xiàn)實(shí)技術(shù)相結(jié)合的一門技術(shù)，其集成了機(jī)床數(shù)控理論、計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助制造、計(jì)算機(jī)輔助設(shè)計(jì)和建模等相關(guān)技術(shù)，在虛擬的場(chǎng)景下，對(duì)數(shù)控設(shè)備的加工過程進(jìn)行全面的仿真。數(shù)控仿真采用計(jì)算機(jī)圖形學(xué)技術(shù)，用動(dòng)畫的方法模擬刀具加工軌跡，可以實(shí)時(shí)直觀地觀測(cè)到加工過程中每一步的信息，以此驗(yàn)證數(shù)字控制程序的正確性，避免在數(shù)控加工過程中出現(xiàn)欠切、過切、走空刀，甚至損壞刀具、機(jī)床的情況。數(shù)控加工過程仿真的核心過程包括工件的三維建模，刀具和毛坯的切削算法以及工件切削面的重繪。

工件的三維實(shí)體模型構(gòu)造方法有很多，如邊界表示法、構(gòu)造實(shí)體幾何法[1]、八叉樹表示法[2]、體素表示法[3]、深度元素法[4]、壓縮體素法[5]。

數(shù)控加工過程中的切削過程其實(shí)是工件和刀具之間的相互作用，在仿真系統(tǒng)中表現(xiàn)為工件實(shí)體模型的離散數(shù)據(jù)與刀具旋轉(zhuǎn)體求交，然后將求交后的數(shù)據(jù)更新到原來的工件模型的數(shù)據(jù)結(jié)構(gòu)中，如此不斷更新工件的離散數(shù)據(jù)并實(shí)時(shí)顯示的過程。比較常用的切削計(jì)算方法有：工件模型的射線組與刀具運(yùn)動(dòng)所形成的掃掠體進(jìn)行求交計(jì)算[6]，刀具掃掠體所構(gòu)造的掃掠面與工件模型上的不規(guī)則表面進(jìn)行曲面之間的求交計(jì)算[7-8]，基于空間分解的思想將工件模型離散為三角網(wǎng)格進(jìn)行求交計(jì)算[9]等。

切削面的重繪是指在計(jì)算出刀具和工件的切削點(diǎn)之后，需要利用相應(yīng)的切削數(shù)據(jù)對(duì)切削面進(jìn)行重新繪制，對(duì)切削面的重新繪制要求盡可能地接近真實(shí)的加工情形。在三維數(shù)據(jù)場(chǎng)中，常用的可視化算法有移動(dòng)立方體（marching cubes）算法[10]，剖分四面體（marching tetrahedral）算法[11]，以及剖分立方體（dividing cubes）算法[12]。

本文基于dividing cubes算法的思想，對(duì)原體素模型稍作改動(dòng)，再結(jié)合刀具旋轉(zhuǎn)體模型進(jìn)行刀具和工件的切削計(jì)算，最后對(duì)切削面進(jìn)行重繪。

1 體素模型

體素（voxel）又稱體積像素（volume pixel），是可以看作二維像素在三維坐標(biāo)空間上的擴(kuò)展，是3D均勻網(wǎng)格組成的結(jié)構(gòu)化數(shù)據(jù)。每個(gè)網(wǎng)格是結(jié)構(gòu)化數(shù)據(jù)的一個(gè)元素，一般稱為體素。體素模型是空間劃分中最常用的一種方法，本文使用該模型對(duì)工件進(jìn)行建模。

將工件的長、寬、高分別以固定的顯示精度在x軸、y軸和z軸上進(jìn)行離散，其中，nx、ny、nz分別為x軸、y軸和z軸上以固定的精度而離散的單元立方體個(gè)數(shù)，如圖1（a）所示。若將每一個(gè)單元立方體作為構(gòu)造工件模型的最小單位元素，則每一個(gè)單元立方體的關(guān)鍵信息元素包含：?jiǎn)卧w的索引值（Key，即該體素的右上角頂點(diǎn)的坐標(biāo)值），單元體是否存在的標(biāo)志位（isExist，默認(rèn)為true），如圖1（b）所示。

由圖1可以看出：體素模型在計(jì)算機(jī)中可以使用一個(gè)三維數(shù)組來存儲(chǔ)工件模型的相關(guān)信息，數(shù)組的大小取決于體素模型的離散精度。但是體素模型需要較大的計(jì)算機(jī)內(nèi)存空間，而且仿真的精度受離散精度的影響較大。盡管體素模型存在一些缺點(diǎn)，但其采用了靜態(tài)的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)模型的外部及內(nèi)部數(shù)據(jù)點(diǎn)的信息，以一定的離散精度為范圍求得立方體作為單位，參與材料的去除與模型重構(gòu)過程，而且還可以用來表示復(fù)雜的模型結(jié)構(gòu)。尤其是對(duì)立方體工件模型以及簡(jiǎn)單的刀路軌跡來說，采用體素建模不僅能夠提高運(yùn)算速度，還能降低重構(gòu)顯示的復(fù)雜度。

2 刀具旋轉(zhuǎn)體

銑削加工中，通用刀具模型[13]如圖2所示。刀具上表面半徑

R=r+r2f-（rf-hf）2+（h-hf）tan γ

式中：r為下表面半徑;rf為圓角半徑;hf為圓角與錐邊切點(diǎn)的高度;h為刀具的長度;γ為半錐角。

通過改變以上參數(shù)，可以定義不同的刀具：

r=0，rf，hf=rf，γ=0球頭刀

r，rf，hf=rf，γ=0圓角刀

r，rf=0，hf=0，γ=0平底刀

其他的刀具模型可以使用類似的方法加入到通用刀具模型中。

刀具旋轉(zhuǎn)體就是刀具在某一時(shí)刻沿主軸旋轉(zhuǎn)一周所形成的包絡(luò)面。刀具的旋轉(zhuǎn)體范圍可以根據(jù)刀具的軸線方程、母線方程、刀具長度以及刀具半徑共同確定。本文主要以平底刀為例，其旋轉(zhuǎn)體可以根據(jù)刀具模型的上、下表面和側(cè)表面共同確定，如圖3所示。

對(duì)于平底刀而言，刀具半徑和刀具的上、下表面半徑相等，即刀具半徑=R（或r）。設(shè)刀具刀心點(diǎn)的坐標(biāo)為O2（x2，y2，z2），刀柄點(diǎn)坐標(biāo)為O1，刀軸單位軸向量為O2O1（i，j，k），則刀具旋轉(zhuǎn)體的上、下表面及側(cè)表面方程式如下：

Ftop（x，y，z）=i·x+j·y+k·z-

i·（x2+i·h）-

j·（y2+j·h）-

k·（z2+k·h）

Fbase（x，y，z）=i·x+j·y+k·z-

（i·x2+j·y2+k·z2）

Fside（x，y，z）=[（-y2）·k-（z-z2）·j]2+

[（z-z2）·i-（x-x2）·k]2+

[（x-x2）·j-（y-y2）·i]2=R2 （1）

在切削計(jì)算的過程中，由于毛坯離散后的數(shù)據(jù)量較大，且每次只有部分?jǐn)?shù)據(jù)與刀具旋轉(zhuǎn)體相交，如果遍歷全部的離散數(shù)據(jù)進(jìn)行切削，顯然會(huì)大大降低切削計(jì)算的效率，因此需要用一定的方法縮小遍歷的范圍。本文使用刀具包圍盒算法[14]來縮小離散數(shù)據(jù)的遍歷范圍，以提高切削計(jì)算的效率。

3 Dividing cubes算法

Dividing cubes算法[12]是W.E.Lorenson和H.E.Cline于1987年提出的，以體素為基本處理對(duì)象。Dividing cubes算法首先對(duì)每個(gè)體素進(jìn)行如下分類：

1）所有的8個(gè)頂點(diǎn)的值都大于等于等值面的值則為內(nèi)部體素（interior cube）;

2）所有的8個(gè)頂點(diǎn)的值都小于等值面的值則為外部體素（exterior cube）;

3）其他則為表面體素（surface cube）。

之后，將表面體素在空間上分割為與最終圖像解析度相同的子體素（sub cube）。例如，若數(shù)據(jù)集的規(guī)模為256×256×128，而最終顯示的窗口的大小為512×512，則在x、y方向上分割一次，在z方向上分割兩次。對(duì)每個(gè)子體素繼續(xù)進(jìn)行分類。對(duì)于最終得到的表面體素，計(jì)算它的中心點(diǎn)的坐標(biāo)及法向量，最終形成一個(gè)點(diǎn)集，每個(gè)點(diǎn)都具有法向量。

Dividing cubes算法實(shí)際上是依次掃描每一個(gè)體素，當(dāng)體素與等值面的值相交時(shí)，將該體素分割為更小的體素，直到子體素在投影平面上的投影為一個(gè)像素大小，然后把所有穿過等值面的子體素作為點(diǎn)投影到平面上。相較于marching cubes算法，dividing cubes算法將繪制的基本元素由三角面片變成了點(diǎn)，無需考慮拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)簡(jiǎn)單。

4 切削計(jì)算

根據(jù)dividing cubes算法對(duì)表面體素進(jìn)行分割的思想，將工件離散后的每個(gè)體素作如下區(qū)分：

1）若體素的8個(gè)頂點(diǎn)都在刀具旋轉(zhuǎn)體內(nèi)部，則該體素被完全切削;

2）若體素的8個(gè)頂點(diǎn)都不在刀具旋轉(zhuǎn)體內(nèi)部，則該體素未被切削;

3）若體素的8個(gè)頂點(diǎn)中，一部分在刀具旋轉(zhuǎn)體內(nèi)部，另一部分在刀具旋轉(zhuǎn)體外部，則該體素被部分切削。對(duì)于此類體素，進(jìn)行一定精度的二級(jí)離散。

考慮到內(nèi)存占用的問題，在具體實(shí)現(xiàn)的過程中，僅對(duì)表面體素進(jìn)行離散，如圖4所示。

在構(gòu)造數(shù)據(jù)結(jié)構(gòu)后，對(duì)基于體素模型的切削計(jì)算也作相應(yīng)改進(jìn)。改進(jìn)后的切削計(jì)算算法如下：

步驟1 計(jì)算刀具包圍盒，判斷體素索引是否在刀具包圍盒范圍之內(nèi)。如果不在，轉(zhuǎn)入步驟6，否則轉(zhuǎn)入步驟2。

步驟2 根據(jù)isExist的值判斷體素是否存在。如果不存在，則跳過。如果存在，則將體素的索引坐標(biāo)值key（x0，y0，z0）帶入式（1）中的Fside（x，y，z），若計(jì)算結(jié)果小于等于刀具半徑的平方，即R2，則轉(zhuǎn)入步驟3，否則轉(zhuǎn)入步驟4。

步驟3 結(jié)合式（1）中刀具上表面方程Ftop（x，y，z）和下表面方程Fbase（x，y，z），分別計(jì)算key（x0，y0，z0）到刀具上表面的距離Dtop和到刀具下表面的距離Dbase。如果h-Dtop-Dbaselt;ε，則該索引在切削范圍之內(nèi)，轉(zhuǎn)入步驟4，否則轉(zhuǎn)入步驟6。其中：h為刀具長度;ε為允許的誤差范圍。

步驟4 對(duì)一個(gè)完整體素的8個(gè)頂點(diǎn)的坐標(biāo)值，依次按照步驟2、3的方法判斷其是否在切削范圍之內(nèi)。若該體素的8個(gè)頂點(diǎn)都在切削范圍之內(nèi)，則該體素為內(nèi)部體素，被完全切削，isExist的值為1，轉(zhuǎn)入步驟6;若該體素的8個(gè)頂點(diǎn)都不在切削范圍內(nèi)，則該體素為外部體素，未被切削，isExist的值為true，轉(zhuǎn)入步驟6;若該體素的8個(gè)頂點(diǎn)中，一部分在切削范圍之內(nèi)，另一部分不在切削范圍之內(nèi)，則該體素為表面體素，被部分切削，isExist的值為true，isPartial的值為true，轉(zhuǎn)入步驟5。

步驟5 對(duì)表面體素進(jìn)行二次離散，然后對(duì)子體素的每一個(gè)體素判斷是否被切削。

步驟6 對(duì)工件模型中的每個(gè)體素依次執(zhí)行步驟1至5，直至所有體素都完成切削計(jì)算，則仿真完成。

本文模型繼承了體素模型切削速度快的特點(diǎn)，而且由于其對(duì)表面體素進(jìn)行了進(jìn)一步的劃分和判斷，從而在一定程度上提高了仿真的精度。

5 切削面重繪

根據(jù)第4節(jié)描述，改進(jìn)體素模型的數(shù)據(jù)結(jié)構(gòu)的Java描述如圖5所示。其中：key為體素的索引值;isExist為體素是否存在的標(biāo)記;isPartial為體素是否被分割為子體素的標(biāo)記;subVoxel為存儲(chǔ)子體素的三維數(shù)組;N為表面體素沿坐標(biāo)軸方向被分割的次數(shù)。

在使用dividing cubes算法進(jìn)行切削面重繪時(shí)，對(duì)于未被切削的完整體素，仍需以體素為單位進(jìn)行繪制，而對(duì)于表面體素，則只需要繪制子體素的中心點(diǎn)即可。同時(shí)，為了能夠提高實(shí)體模型的繪制速度，必須在最大程度上避免冗余面（或點(diǎn)）繪制，只對(duì)實(shí)體模型的外表面和有效切削面進(jìn)行繪制，不對(duì)實(shí)體內(nèi)部的無用面進(jìn)行繪制。具體繪制算法如下：

步驟1 對(duì)于任意體素voxel[i][j][k]，根據(jù)體素是否存在的標(biāo)志位isExsit判斷該單元體是否存在。若體素存在，則轉(zhuǎn)入步驟2，否則轉(zhuǎn)入步驟5。

步驟2 若該體素存在且不是表面體素，則轉(zhuǎn)入步驟3， 否則轉(zhuǎn)入步驟4。

步驟3 根據(jù)式（2）判斷該體素是否位于工件離散模型的表面。若是則需要繪制相應(yīng)面，否則根據(jù)該單元體的索引值算出6個(gè)與其各個(gè)面相鄰的體素，voxel[i-1][j][k]，voxel[i+1][j][k]，voxel[i][j-1][k]，voxel[i][j+1][k]，voxel[i][j][k-1]，voxel[i][j][k+1]，依次判斷這些體素是否存在。若不存在，則根據(jù)需要繪制相應(yīng)面。例如，如果voxel[i][j][k]存在且不是位于工件離散模型的表面，而voxel[i-1][j][k]不存在，則需要繪制voxel[i][j][k]的左表面;若voxel[i+1][j][k]不存在，則需要繪制voxel[i][j][k]的右表面。同理可對(duì)上、下、前、后表面按需繪制。

i=1 " "顯示左表面

i=nx " 顯示右表面

j=1 " "顯示前表面

j=ny " 顯示后表面

k=1 " "顯示下表面

k=nz " 顯示上表面 （2）

步驟4 若該體素是表面體素，則對(duì)子體素運(yùn)用基于體素模型的切削計(jì)算進(jìn)行判斷該體素是否被切削。若該體素未被切削，則求該體素的中心點(diǎn)坐標(biāo)，并在該坐標(biāo)位置繪制一個(gè)像素大小的點(diǎn);若該體素已被切削，則無需對(duì)該體素進(jìn)行繪制。

步驟5 依次執(zhí)行步驟1至4，直至所有體素繪制完成。

圖6為在初始狀態(tài)下，利用本文體素模型對(duì)工件進(jìn)行建模的效果圖。

6 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中如果一級(jí)離散精度過高，則會(huì)產(chǎn)生大量離散數(shù)據(jù)，不僅會(huì)占用大量的內(nèi)存空間，而且會(huì)降低切削效率;相反，如果一級(jí)離散精度過低，則大部分體素會(huì)被部分切削，成為表面體素，從而產(chǎn)生大量的二級(jí)離散數(shù)據(jù)，同樣會(huì)浪費(fèi)大量?jī)?nèi)存空間、降低切削效率。綜合這兩點(diǎn)考慮，將一級(jí)離散精度設(shè)置為R2個(gè)單位長度。本文實(shí)驗(yàn)的硬件環(huán)境為：Windows10操作系統(tǒng)，17-2640M雙核CPU，16 G內(nèi)存。實(shí)驗(yàn)中，刀具半徑為5個(gè)單位長度，毛坯的長、寬、高分別為120、120和30個(gè)單位長度。

圖7展示了在相同實(shí)驗(yàn)環(huán)境下，基于體素模型和marching cubes算法的切削時(shí)間和本文算法在二級(jí)離散精度分別為2×2×2，4×4×4和5×5×5時(shí)切削時(shí)間的對(duì)比圖。

從圖7可以看出：以每1 000個(gè)刀位點(diǎn)的切削時(shí)間對(duì)比，基于dividing cubes算法思想的切削計(jì)算有較高的切削效率，但隨著二級(jí)離散精度的提高，切削效率隨之下降。

7 結(jié)語

本文根據(jù)dividing cubes算法的思想，對(duì)體素模型進(jìn)行了改進(jìn)，并在此基礎(chǔ)上提出了對(duì)應(yīng)的切削算法。實(shí)驗(yàn)證明該算法可以在保證切削精度的同時(shí)，有更高的切削效率，并且基于dividing cubes算法的切削面的重繪過程也更加簡(jiǎn)潔。但是該算法會(huì)受到二級(jí)離散精度的影響，隨著二級(jí)離散精度的提高，切削計(jì)算量會(huì)增加，切削效率會(huì)下降，同時(shí)也需要更多的計(jì)算機(jī)內(nèi)存。因此，在實(shí)際應(yīng)用中需要根據(jù)實(shí)際情況選擇合適的二級(jí)離散精度。

參考文獻(xiàn)：

[1]REQUICHA A A G， VOELCKER H B. Solid modeling： current status and research directions[J]. IEEE Computer Graphics and Applications， 1983， 3（7）： 25-37.

[2]閆立華. 數(shù)控仿真系統(tǒng)的幾何建模方法研究與設(shè)計(jì)[D]. 秦皇島： 燕山大學(xué)， 2006.

[3]JANG D G， KIM K， JUNG J M. Voxel-based virtual " multi-axis machining[J]. Advanced Manufacturing Technology， 2000， 16（10）： 709-713.

[4]VAN HOOK T. Real-time shaded NC milling display[J]. ACM SIGGRAPH Computer Graphics （Comput Graph）， 1986， 20（4）： 15-20.

[5]候增選， KRAUSE F L， 田榮鑫. 基于壓縮Voxel模型的五坐標(biāo)數(shù)控加工仿真新方法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2006， 42（20）： 25-28.

[6]毛一硯. 五軸數(shù)控工具磨床磨削仿真算法研究[D]. 成都： 西南交通大學(xué)， 2019.

[7]楊挺， 吳寶海， 李山， 等. 利用密切平面的自由曲面求交算法[J]. 機(jī)械科學(xué)與技術(shù)， 2009， 28（3）： 371-374.

[8]張接信， 吳堅(jiān). 工程機(jī)械零件離散復(fù)雜曲面求交算法[J]. 長安大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2007， 27（5）： 116-119.

[9]張少麗， 王毅剛， 陳小雕. 基于空間分解的三角網(wǎng)格模型求交方法[J]. 計(jì)算機(jī)應(yīng)用， 2009， 29（10）： 2671-2673.

[10]LORENSEN W E， CLINE H E.Marching cubes： a high resolution 3D surface construction algorithm[J]. Computer Graphics， 1987， 21（4）： 163-169.

[11]吳建偉， 王子牛. 基于改進(jìn) MC 和 MT 算法的CT圖像三維重建[J]. 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015， 32（2）： 82-85， 93.

[12]CLINE H E， LORENSEN W E， LUDKE S，et al. Two algorithms for the three-dimensional reconstruction of tomograms[J]. Medical Physics， 1988， 15（3）： 29-37.

[13]王哲， 王知行， 鐘詩勝. 刀具掃描體生成新算法及在數(shù)控加工仿真中的應(yīng)用[J]. 機(jī)械工程學(xué)報(bào)， 2001， 37（1）： 28-31.

[14]李楊， 王子牛， 王彥， 等. 基于刀具空間包圍體算法的數(shù)控切削仿真[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2012， 33（3）： 1073-1078.

（責(zé)任編輯：周曉南）

Abstract：

Cutting calculation is an important part of the CNC simulation system. Different cutting algorithms directly affect cutting efficiency and cutting accuracy. Based on the idea of dividing cubes algorithm， a new cutting algorithm is proposed by slightly changing the voxel model. The experiment results shows that this method can ensure the cutting accuracy and has higher cutting efficiency， and the redrawing process of cutting surface based on dividing cubes algorithm is more concise and efficient. However， this method requires different memory space according to the discrete accuracy of the rough. At the same time， it is found that when the discrete accuracy of the rough exceeds a certain degree， the amount of cutting calculation will be increased， and the efficiency of cutting calculation will be reduced.

Key words：

CNC simulation; voxel model; dividing cubes; cutting calculation