一種在銑削實時仿真中基于二叉樹網格劃分方法

成 建 群

(蘇州健雄職業技術學院中德工程學院 江蘇 太倉 215411)

0 引 言

銑削仿真就是利用計算機模擬銑刀沿著銑削軌跡與被加工工件(毛坯)之間的相對運動，實現對加工中銑刀移動、銑削等過程的監控和驗證[1]。當前銑削仿真中幾何模型主要有線框模型、圖像空間模型、實體模型和離散矢量模型[2]。實體模型方法用數學模型描述幾何體，保留了全部的數據，計算結果精確可控，可以進行旋轉、縮放等幾何變換和數據分析測量。但是實體模型在銑削仿真中求交計算量大，仿真速度慢。留量幾何模型基于實體模型方法，以網格來模擬工件表面，通過網格Z方向(或矢量方向)的值來表示工件上留存的材料。仿真時，通過修改網格節點的Z值來模擬工件表面的變化，簡稱為Z-Map方法。該方法在車削[3]、磨削[4]和銑削[5-6]等仿真中得到了廣泛的應用。

在留量幾何模型中網絡數量的多少直接關系到計算量的大小，占用內存的多少，響應速度的快慢。而實時仿真要求計算速度快、響應及時，同時占有內存空間小。在銑削仿真時，傳統研究中絕大多數首先對工件整體進行網格劃分，然后進行仿真計算。本文提出一種二叉樹的網格表示方法，僅僅對需要銑削仿真的區域進行網格細分，快速響應仿真過程。

1 二叉樹網格表示方法

三角形網格具有模型簡單、仿真精度可控、實時性好、視角連續可變等優點，在加工仿真、虛擬加工領域應用廣泛[7-9]。這里討論的網格均是三角形網格。為了節省內存空間，3D模型用頂點和三角形表示(n個頂點，m個三角形)，即：

(1)

三角形的頂點順序表示三角面的朝外法向。三角形中僅保存頂點的序號，第k+1個三角形頂點為Triangles[3k]、Triangles[3k+1]、Triangles[3k+2]。三角形的邊按頂點順序分別標記為0、1、2。同時邊分為父邊(P)、左邊(L)、右邊(R)，與頂點順序一致，如圖1所示。每一個三角形有且僅有一個父邊、左邊、右邊。

圖1 頂點與邊關系

三角形作為二叉樹的節點，左邊與二叉樹左節點的父邊共邊，右邊與二叉樹右節點的父邊共邊。如圖2所示，三角形1左節點為三角形2，右節點為三角形3。進一步可以看出，三角形1的頂點序號為Triangles[0]、Triangles[1]、Triangles[2]，三角形2的頂點序號為Triangles[3]、Triangles[4]、Triangles[5]，三角形3的頂點序號為Triangles[6]、Triangles[7]、Triangles[8]。

圖2 二叉樹構成

經以上分析，m個三角形構成的3D模型可以表示為一個由m個節點構成的二叉樹，每個節點代表一個三角形，二叉樹的節點關系表示了三角形的共邊關系，即：

(2)

2 二叉樹網格的創建

創建二叉樹網格時，原來所有的三角形構成了一個三角形庫(Triangles)。在三角形庫中任選擇一個三角形作為起始三角形，以該三角形任一條邊為父邊，并確定左邊和右邊，得到樹節點庫(TreeNodes)的第一個樹節點。尋找與左邊、右邊共邊的另外三角形，該共邊為父邊。再從以此為父邊的新三角形繼續遍歷查找，直到所有的三角形均查找完成，最終可得到完整的樹節點庫，即完成二叉樹網格的創建。處理流程如圖3所示。立方體三角形網格按流程圖可以得到如圖4所示結果，左側為立方體的網格及三角形標識，右側為該立方體網格的二叉樹。

圖3 二叉樹創建流程

圖4 立方體網格的二叉樹

3 二叉樹網格的劃分

3.1 共邊兩網格單元的劃分

在銑削仿真中網格隨銑削區域進行細分，首先就是要對網格單元劃分。相鄰的網格單元劃分，取公共邊中點，原來的兩個三角形劃分為四個三角形，產生一個新的頂點。在網格二叉樹中，相鄰網格有兩種關系：父子共邊網格和無父子共邊網格。

(1) 父子共邊網格。如圖4所示，網格三角形1和2相鄰，用虛線劃分，生成網格三角形1、2、3、4。網格三角形1的左邊或右邊與網格三角形2的父邊一致。因共邊的端點次序可能不一致，構成四種情況。可以依照圖5中結構關系，修改網格二叉樹數據。處理流程如圖6所示。

圖5 父子共邊網格劃分

圖6 父子共邊網格處理流程

(2) 無父子共邊網格。無父子共邊網格處理流程與父子共邊網格處理流程一致，但無父子關系共邊的三角形因兩個三角形共左邊與共右邊、頂點次序相同與相反共有八種情況(如圖7所示)。劃分網格后，三角形劃分后的二叉樹的結構僅僅與公共邊為左邊還是右邊有關，不妨稱為左連接、右連接。三角形1劃分后變為1、3，三角形2劃分后變為2、4，并且1、3為父子關系，2、4為父子關系，可以得到如表1所示的關系。

圖7 無父子共邊網格劃分

表1 無父子共邊網格劃分

3.2 左右連接關系分析

如圖8所示，網格中n1、n2的公共邊劃分后產生n1、n2、n3、n4，為了表述方便，不妨記原n1為N1。二叉樹節點N1進行劃分生成n3，n1與n2共邊，n3與n4共邊，從圖8不難看出對于左連接(僅僅需要考慮n1、n3的關系)，左邊為公共邊，n3的父節點為n1，n3的左節點為n4，n3的右節點為原n1的右節點。即得到以下關系：

(3)

(a) 左連接 (b) 右連接圖8 左右連接關系

原n1(N1)的右節點與N1的關系需要修改為與n3的關系。若原n1的右節點的父節點為原n1，則原n1的右節點的父節點為n3。否則，若原n1的右節點的左節點為原n1，則原n1的右節點的左節點為n3。否則，若原n1的右節點的右節點為原n1，則原n1的右節點的右節點為n3。即得到以下關系：

(4)

另外，n1的父節點保持不變，n1的右節點為n3，n1的左節點為n2。即得到以下關系：

(5)

從圖8不難看出，對于右連接(僅僅需要考慮n1、n3的關系)，右邊為公共邊，n3的父節點為n1，n1右節點為n4，n3的左節點為原n1的左節點。即得到以下關系：

(6)

原n1(N1)的左節點與N1的關系需要修改為與n3的關系。若原n1(N1)的左節點的父節點為n1，則原n1的左節點的父節點為n3。否則，若原n1的左節點的左節點為原n1，則原n1的左節點的左節點為n3。否則，若原n1的左節點的右節點為原n1，則原n1的左節點的右節點為n3。即得到以下關系：

(7)

另外，n1的父節點保持不變，n1的左節點為n3，n1的右節點為n2。即得到以下關系：

(8)

根據以上分析，可以完成左右連接的處理函數，分別記為：

左右連接形式參數序列均為n1、n2、n3、n4，表示兩個相鄰節點劃分后產生四個節點，并且節點n1劃分后產生n3，且n1與n2相鄰，n3與n4相鄰。

在應用表1關系時，以表1序號3為例，節點n1、n2進行劃分產生n3、n4，n1的左邊與n2的右邊共邊，頂點次序相同。構造二叉樹關系時，n1、n3關系為左連接，參數為n1、n4、n3、n2，即相當于n1劃分后產生n3，且n1與n4相鄰，n3與n2相鄰。調用過程如下：

LeftLink(n1,n4,n3,n2)

n2、n4關系為右連接，參數為n2、n3、n4、n1，即相當于n2劃分后產生n4，且n2與n3相鄰，n4與n1相鄰。調用過程如下：

RightLink(n2,n3,n4,n1)

這樣處理大大簡化了程序判斷，提高了處理效率，節省了響應時間。

3.3 銑削區域網格的劃分

在銑削仿真時，工件表面需要變化的網格區域是刀具運動在網格表面的投影區域。為了分析方便，不妨設投影區域為二維點t1、t2圍成的矩形區域。當網格與本區域相交或在本區域內就需要進行細分，直到滿足細分最大面積的要求。

因切削區域是在工件表面的投影是連續的，所以從一個與切削區域相交或在切削區域內的三角形出發，通過事先構造的二叉樹，就可以找到所有的相關三角形，并進行細分。為了不使細長三角形影響仿真效果，在切削區域內劃分的兩個三角形的共邊必須為三角形的最長邊。在切削區域邊界處，若三角形在切削區域外或者三角形在切削區域上的投影面積為0，則該三角形的劃分情況不影響切削仿真，沒有細長三角形的要求，可以在非最長邊上進行劃分。區域網格劃分流程如圖9所示。

圖9 區域網格劃分流程

設銑削刀具半徑為r，刀具中心由p1沿X軸或Y軸移動到p2(與Z軸運動無關)，則銑削細分網格區域t1、t2滿足以下關系：

(9)

但是，考慮到切削區域邊緣網格精度必須要將細分網格區域擴展一個細分網格單元。一般情況下，細分網格單元邊長l與最大細分網格最大面積S滿足式(10)。l過大造成細分網格浪費，過小會導致切削區域邊緣網格拉扯明顯，仿真效果差。

(10)

銑削細分網格區域頂點t1、t2修正如下：

(11)

本文在Windows 10環境下，利用Unity3D實現了3D模型基于二叉樹的網格表示方法。圖10是對單位正方體上t1(0,0)、t2(0.2,0.5)矩形區域內網格進行劃分的效果。可以看出，矩形區域內網格劃分均勻，區域外網格數量少，達到了預期的效果。

圖10 區域網格的劃分

4 仿真算例

進一步，基于Z-Map方法仿真和本文的網格表示方法可以仿真球頭刀切削立方體毛坯，驗證本文方法的性能。不妨假設工件為邊長100的立方體，頂點坐標為(0，0，0)、(0，100，0)、(100，0，0)、(100，100，0)、(0，0，100)、(0，100，100)、(100，0，100)、(100，100，100)，刀具垂直于工件表面(xoy平面)銑削工件，刀具球頭半徑為2，刀具球心由點(10，3，95)切削到點(10，40，90)。利用本文方法進行區域網格劃分和全域網格劃分，測試數據如表2所示。圖11是單元網格最大面積是1時的區域網格與全部網格的仿真對比圖。

表2 區域網格仿真性能比較數據

(a) (b)圖11 區域網格與全域網格仿真

頂點數量和三角形數量直接與占用內存成正比，頂點數量和三角形數量越大占用內存越多。用Z-Map方法銑削仿真時，模型上每一個頂點均需要進行判斷或調整Z值，所以頂點數量直接關系到系統響應時間。單元網格最大面積越小，仿真精度越高，顯示越精細。從表2的數據可以看出，全域網格仿真響應時間對單元網格面積大小非常敏感，采用區域網格仿真有明顯優勢。圖12-圖14為模具仿真加工實例。

圖14 圓底槽仿真加工

5 結 語

本文提出一種3D模型的網格表示方法，用二叉樹結構表示三角形網格邊的組成關系，快速實現銑削區域網格劃分，并基于Unity3D平臺實現了Z-Map方法銑削仿真。結果表明，用二叉樹結構表示區域網格劃分相較于全域網格能夠節省內存資源，加快仿真響應，提高仿真精度，能夠應用于銑削加工仿真過程，滿足實時性要求，有較高的應用價值。