數(shù)控仿真中切削面計算的并行化研究＊

于 珊，王子牛，趙鵬陽

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

數(shù)控加工仿真技術(shù)是利用計算機來模擬和驗證數(shù)控加工的實際過程和結(jié)果，針對離散精度高的工件模型，為滿足實時性顯示要求，必須減少數(shù)控加工仿真過程的時間，提高仿真效率。通過查閱和研究大量文獻發(fā)現(xiàn)目前大量的研究和成果都在傳統(tǒng)CPU 上實現(xiàn)并改進幾何算法和圖形算法。但由于CPU 的串行性、計算速度和內(nèi)存帶寬的劣勢，使得某些算法在CPU 上無法進行快速的計算，達不到實時性要求。本文根據(jù)文獻［1］中提出的基于MC 算法的實體構(gòu)造模型及其在數(shù)控仿真中的應(yīng)用，采用GPU 代替?zhèn)鹘y(tǒng)的CPU 進行計算，利用GPU 的并行性、超大的內(nèi)存帶寬以及極高的運算速度等優(yōu)勢，通過并行方式處理刀具空間包圍體與工件模型的切削計算加速切削面的顯示。

1 GPU 并行計算模式

GPU 起初只負責(zé)圖形渲染，隨著計算機的發(fā)展，如今的GPU 架構(gòu)是具有并行處理能力的架構(gòu)，具有極強的并行計算能力，能夠執(zhí)行高強度的海量數(shù)據(jù)任務(wù)，數(shù)據(jù)規(guī)模已經(jīng)達到TB 到PB 量級。在虛擬現(xiàn)實領(lǐng)域，人們對繪制場景也提出了更高要求，需要構(gòu)建更加精細的場景，同時要求進行實時交互，因此需要快速計算在視角范圍內(nèi)的大量幾何物體并繪制場景。

GPU 和CPU 在設(shè)計思路上存在很大差異:CPU為優(yōu)化串行代碼而設(shè)計，將大量的晶體管作為控制和緩存等非計算功能，注重低延遲地快速實現(xiàn)某個操作;GPU 則將大量的晶體管用作ALU 計算單元，適合高計算強度的應(yīng)用。在協(xié)同并行計算時，CPU 和GPU 應(yīng)各取所長，快速、高效協(xié)同地完成高性能計算任務(wù)［2］。CPU 負責(zé)管理GPU 的工作，為GPU 提供數(shù)據(jù)并接收GPU 傳回的數(shù)據(jù)，由GPU 承擔(dān)復(fù)雜而繁重的計算任務(wù)。

2 CUDA 編程技術(shù)

CUDA 是NVIDIA 推出的運算平臺，指的是計算統(tǒng)一設(shè)備架構(gòu)，CUDA 的推出破除傳統(tǒng)GPU 硬件架構(gòu)限制，可以充分地利用GPU 進行并行計算，使得CPU-GPU 協(xié)同計算成為可能且更加方便簡單。在CUDA 架構(gòu)下，程序分別在host(主機)和device(設(shè)備)上面執(zhí)行，一個host 和多個device 組成一個CUDA 系統(tǒng)。host 指的是CPU，device 則是GPU，CUDA 一般通過Kernel 來控制GPU 進行計算。每一個Kernel 和CUDA 組織模型的網(wǎng)格Grid對應(yīng)。多個Block 構(gòu)成一個Grid，多個Thread 構(gòu)成一個Block。Kernel 函數(shù)由大量GPU 線程并發(fā)執(zhí)行，不同線程處理的數(shù)據(jù)卻各不相同。眾多GPU線程以塊(Block)和網(wǎng)格(Grid)的層次化結(jié)構(gòu)加以組織。線程塊與網(wǎng)格的結(jié)構(gòu)(維數(shù)和規(guī)模)由用戶根據(jù)實際需求制定。此外，CUDA為GPU 線程提供了索引自身線程編號以及線程塊編號的方法，因此在程序中可以令線程根據(jù)自身編號處理不同的數(shù)據(jù)。與GPU 線程的層次化結(jié)構(gòu)相對應(yīng)，CUDA提供的編程模型將CPU 中的存儲器也加以層次化的組織，線程擁有各自的本地存儲，其中存放每個線程的私有變量。線程塊擁有各自的共享存儲，其中存放塊內(nèi)線程均能夠訪問的數(shù)據(jù)。此外，CUDA還為所有線程提供了一個全局存儲器(顯存)。圖1為CUDA 編程模型。CUDA 采用了SIMD 執(zhí)行模型［3］，該模型可歸納為6 個步驟:

①數(shù)據(jù)類型初始化:變量的定義與聲明。

②存儲空間分配:為主機端和設(shè)備端變量分別分配存儲空間，用來存儲不同類型的數(shù)據(jù)。

③數(shù)據(jù)傳遞:從主機端將數(shù)據(jù)傳輸?shù)皆O(shè)備端。

④并行執(zhí)行:調(diào)用Kernel 函數(shù)，并分配設(shè)備端執(zhí)行參數(shù)和函數(shù)參數(shù)，該函數(shù)將會被GPU 內(nèi)分配到的所有線程分別執(zhí)行1 次，從而實現(xiàn)單指令多數(shù)據(jù)的并行處理過程。

⑤結(jié)果返回:將設(shè)備端計算的結(jié)果傳回主機端。

⑥釋放顯存:在GPU 端的全局存儲器中回收空間。

圖1 CUDA 編程模型

3 數(shù)控切削仿真模型

3.1 模型構(gòu)造

MC 算法是三維數(shù)據(jù)場中對等值面進行構(gòu)造的經(jīng)典算法，由于其原理簡單且容易實現(xiàn)，所以得到了廣泛的應(yīng)用。根據(jù)MC 算法的相關(guān)思想及實現(xiàn)原理，可將其應(yīng)用到幾何仿真中的三維實體模型構(gòu)造和實體模型加工面的顯示計算兩個部分。規(guī)則三維數(shù)據(jù)場的構(gòu)造是通過在某個三維空間區(qū)域內(nèi)沿X，Y，Z 三個方向進行均勻采樣，采樣間距為Δx，Δy，Δz，那么在該區(qū)域內(nèi)上下對應(yīng)的8 個點所組成的立方體就構(gòu)成1 個體素，組成體素的采樣點稱為體素的角點。圖2為單位體素模型結(jié)構(gòu)。

圖2 單位體素模型結(jié)構(gòu)

MC 算法主要是遍歷數(shù)據(jù)場中的每個體素，根據(jù)體素頂點的標記狀態(tài)進行組合和分類。每個體素包含8 個頂點，且各頂點均有可能處于等值面內(nèi)或等值面外(角點位于等值面外則標記為“+”，角點位于等值面內(nèi)則標記為“－”)，如果體素的某一條邊和等值面發(fā)生相交，則該條邊上兩個角點的標記是相反的;反之，如果體素的任意一條邊上兩個角點的標記相同，那么等值面與該條邊未發(fā)生相交，所以體素可能有256 種不同的狀態(tài)［4］。雖然可能的狀態(tài)有256 種，但很多狀態(tài)的拓撲結(jié)構(gòu)一樣，這就是等值面的二義性。對于MC 算法的二義性問題，已有很多文獻論述并提出了一些較好的解決方法這里就不再贅述。經(jīng)過狀態(tài)合并后得到最終的15 種基本狀態(tài)［5］。

3.2 切削面顯示

將MC 算法應(yīng)用于五軸數(shù)控仿真中的切削面顯示，提出了一種基于MC 算法等值面提取思想的實體模型構(gòu)造方法，即MC 實體構(gòu)造法。該實體構(gòu)造法沿用了MC 算法中對三維規(guī)則數(shù)據(jù)場進行構(gòu)建的相關(guān)原理，以體素作為構(gòu)造實體模型的基本單元，并對體素中的8 個角點和12 條棱邊信息進行存儲，圖3為單位體素模型的數(shù)據(jù)存儲結(jié)構(gòu)。在數(shù)控加工仿真切削計算中，串行依次計算X，Y，Z 三個方向的射線組分別與刀具包圍體在對應(yīng)方向上的交點的值(如:與X 方向射線組求交得到交點的X 方向坐標值)，求得的交點記錄在切削體素內(nèi)，最后遍歷所有體素的狀態(tài)對單位體素內(nèi)各條邊上存在的等值點進行連接，即采用三角面片來近似表達等值面，若離散的采樣點越多，那么等值面顯示精度也就越高。利用OpenGL 函數(shù)對重構(gòu)的切削面進行顯示。

圖3 單位體素模型的數(shù)據(jù)存儲結(jié)構(gòu)

4 并行方式的數(shù)控仿真顯示算法

并行線程處理的是規(guī)則三維離散數(shù)據(jù)場中的體素，而體素之間不存在相互影響的關(guān)系，即體素中的等值面片提取不受鄰近體素等值面提取過程的影響。所以基于MC 算法的數(shù)控仿真切削面計算可以利用GPU 的SIMD 并行方式進行加速處理［6］。傳統(tǒng)CPU 實現(xiàn)的數(shù)控加工仿真系統(tǒng)采用從三個方向引出的射線組成的射線組分別與刀具包圍體進行求交計算得到等值點坐標，但在離散精度很高的情況下，由于使用射線組與刀具包圍體求交的方法會帶來更大的時間開銷，而使用體素存儲的邊信息與刀具包圍體求交點代替以前的求交方法所重建出來的結(jié)果能大量減少代數(shù)運算，從而減少重建的時間。

本文主要將MC 算法對等值面進行提取的相關(guān)計算原理與實現(xiàn)方法應(yīng)用到數(shù)控仿真中切削面的顯示，在基于CUDA 并行開發(fā)平臺的基礎(chǔ)上，采用圖形處理器GPU 對等值面與邊界體素的交點坐標及法向量進行計算［7］，在保證圖像質(zhì)量的前提下，加速數(shù)控仿真切削面的提取，從而提高三維圖像的繪制速度。具體算法流程:

(1)初始化Grid 和Block，將Block 中的每個線程和三維離散數(shù)據(jù)空間中的體素一一對應(yīng)，將線程m 的一維坐標index(index=0，l，…，maxVoxel-Size－l)轉(zhuǎn)化為體素的三維坐標(i，j，k)(i=0，1，…，mCol－1;j=0，1，…，mRow－1;k=0，1，…，mVer－1)，并以該坐標作為體素的左下角點的坐標，然后沿三個方向上進行釆樣，獲取體素p 另外7 個鄰近的角點的坐標，完成體素p 的構(gòu)建。

(2)判斷各角點在當(dāng)前刀具包圍體空間范圍的內(nèi)部還是外部，標記各角點的狀態(tài)(若角點在刀具包圍體內(nèi)部，則表示該角點已被切削;若角點在刀具包圍體外部，則表示該角點未被切削)，確定體素的拓撲結(jié)構(gòu)，根據(jù)體素的拓撲結(jié)構(gòu)查詢構(gòu)型索引表得到體素構(gòu)型索引cubeIndex。

(3)求解刀具包圍體與體素12 條邊的交點坐標，存入到開辟的共享顯存空間vertList［12］［32］數(shù)組中。

(4)根據(jù)體素的構(gòu)型索引號cubeIndex 查詢交點數(shù)目索引表numVertTable，確定體素的構(gòu)型索引號cubeIndex 和刀具包圍體與各體素的交點的個數(shù)numvertex。圖4為體素角點狀態(tài)及256 種構(gòu)型索引表和交點數(shù)目表numVertTable。

圖4 體素角點狀態(tài)及256 種構(gòu)型索引表和交點數(shù)目表numVertTable

(5)以numvertex為循環(huán)控制條件，每隔三個頂點進行一次循環(huán)。利用體素拓撲構(gòu)型索引cubeIndex 查詢?nèi)切螖?shù)組triTable［256］［16］。獲取三角形三個頂點(即等值點)所在的邊號el，e2，e3(e=0，1，…，11)。將el，e2，e3 作為索引查詢vertList 數(shù)組，獲取三角形三個頂點的空間幾何坐標v0，v1，v2，利用向量叉乘法計算出三角形面片的法向量，最后將所有三角形的頂點坐標和法向量保存到顯存中。

(6)從顯存依次取出頂點和法向量進行三角形擬合，利用OpenGL 函數(shù)繪制切削面，實現(xiàn)3D 渲染。

以數(shù)控加工的五軸圓餅為例，通過測試本文提出的并行方式進行切削計算的時間與原來串行方式進行切削計算的時間進行對比:離散精度越高即切削點越多，切削計算的時間越長，并行與串行的切削計算耗時加速比越大，說明該方法有效地減少了切削計算耗時。表1為并行方式與串行方式切削計算耗時加速比。

表1 并行方式與串行方式切削計算耗時加速比

實驗環(huán)境為:Visual Studio 2008、CUDA3.2;操作系統(tǒng)是windows7(32 位);GPU為NVIDIAGe-ForceGTX 570;顯存為2G，CPU為i5－2300，其主頻為2.80GHz;主存為4G。

5 結(jié)束語

針對傳統(tǒng)CPU 實現(xiàn)的數(shù)控加工仿真系統(tǒng)，采用循環(huán)遍歷體素數(shù)組對其進行求交計算和繪制，在工件模型構(gòu)建離散精度較高時，這種遍歷體素的方式相當(dāng)費時，本文應(yīng)用GPU 代替?zhèn)鹘y(tǒng)的CPU 進行數(shù)控加工仿真中的切削計算，減少了切削計算時間，并通過構(gòu)建查找表的方式加快提取與之匹配的切削面的構(gòu)型類型，從而提高了數(shù)控仿真的顯示速度。

［1］李楊.基于MC 算法的數(shù)控加工過程三維實體仿真的研究與實現(xiàn)［D］.貴陽:貴州大學(xué)，2012.

［2］盧風(fēng)順，宋君強，銀福康，等.CPU/GPU 協(xié)同并行計算研究綜述［J］.計算機科學(xué)，2011，38(3):5－10.

［3］張慶科，楊波，王琳，等.基于GPU 的現(xiàn)代并行優(yōu)化算法［J］.計算機科學(xué)，2012，39(4):304－311.

［4］黃明艷，王子牛.基于CUDA 的數(shù)控仿真加工面顯示算法的研究［J］.貴州大學(xué)學(xué)報:自然科學(xué)版，2013，30(4):70－73.

［5］姜赟.基于面繪制的圖像三維可視化算法研究［D］.成都:電子科技大學(xué)，2007.

［6］李晉舟.基于GPU 的移動立方體算法及其應(yīng)用［D］.西安:西安電子科技大學(xué)，2010.

［7］程詠華.基于CUDA 的醫(yī)學(xué)圖像3D 可視化技術(shù)的研究［D］.成都:西南交通大學(xué)，2013.