基于多核CPU+GPU運(yùn)算的電磁場高效體繪制算法研究

陳宇峰，張 鉑，李 林

北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081

1 引言

電磁場被發(fā)現(xiàn)以來就一直是人類在生產(chǎn)生活過程中一種重要的物理環(huán)境。但是，電磁場難以被人的感官直接感受到，在某種程度上限制了人的觀察能力和思考范圍。因此，研究如何將這種看不見的電磁場及其與物質(zhì)相互作用的現(xiàn)象能直接轉(zhuǎn)變?yōu)橐妆蝗说娜庋塾^察到的方法，即電磁場可視化方法，具有重要的現(xiàn)實(shí)意義。

近年來對以雷達(dá)探測范圍為例的電磁場可視化的研究取得了日新月異的發(fā)展。伴隨著計(jì)算機(jī)圖形學(xué)的快速發(fā)展，雷達(dá)探測范圍可視化方法已經(jīng)由傳統(tǒng)的數(shù)值參數(shù)、二維雷達(dá)威力圖方法轉(zhuǎn)為三維可視化技術(shù)[1]。國防科技大學(xué)的楊超，陳鵬等人研究了在大氣吸收衰減的條件下，雷達(dá)探測范圍并且生成了三維仿真場景[2]?？哲姽こ檀髮W(xué)的張敬卓、袁修久等人為了解決在虛擬戰(zhàn)場環(huán)境下數(shù)據(jù)場內(nèi)密外疏的難題，采用了數(shù)據(jù)環(huán)拼接的方式，最終實(shí)現(xiàn)了雷達(dá)在虛擬戰(zhàn)場環(huán)境下自然環(huán)境干擾的三維探測范圍可視化[3]。但是這些方法采用的都是面繪制，其缺點(diǎn)是邊緣提取不準(zhǔn)確，并且容易造成數(shù)據(jù)場信息丟失。如果采用體繪制的方法可視化雷達(dá)探測范圍，可以很好地保留整體數(shù)據(jù)場的細(xì)節(jié)，然而體繪制采用的光線跟蹤算法對內(nèi)存資源需求大，對場景雷達(dá)探測范圍的碰撞檢測效率低，所以并沒有被廣泛的使用。

體繪制起始于20世紀(jì)70年代中期，它是由于醫(yī)學(xué)技術(shù)斷層投影（CT）、核磁共振（MRI）等發(fā)展而興起的一種可視化技術(shù)。在醫(yī)學(xué)領(lǐng)域中，動(dòng)態(tài)體繪制可視化技術(shù)龐大的數(shù)據(jù)量使得計(jì)算的復(fù)雜度大大提高，基于CUDA的高效體繪制技術(shù)可以進(jìn)一步提高數(shù)據(jù)處理效率[4]。體繪制也是電磁場可視化仿真領(lǐng)域中的重要組成部分。其優(yōu)點(diǎn)是不僅僅可以顯示高質(zhì)量的圖片，而且這些圖片可以表達(dá)出三維物體的內(nèi)部信息，這一點(diǎn)是傳統(tǒng)的計(jì)算機(jī)圖形學(xué)不可企及的[5-6]?；谝陨系膬?yōu)點(diǎn)，體繪制技術(shù)更加適用于繪制不可見的數(shù)據(jù)場信息，例如，人體骨骼密度，雷達(dá)探測范圍等。然而體繪制方法的缺點(diǎn)就是算法執(zhí)行的時(shí)間效率問題。由于從視點(diǎn)投射出的每一條光線都需要和場景進(jìn)行碰撞檢測，所以體繪制效率改善的關(guān)鍵問題就是改善光線求交運(yùn)算的碰撞檢測效率。

本文采用OSG（Open Scene Graph）作為渲染引擎。采用體繪制技術(shù)來可視化雷達(dá)探測范圍，實(shí)驗(yàn)結(jié)果表明，OSG引擎對雷達(dá)探測范圍的體繪制的可視化效果良好。并且在OSG場景中針對體繪制渲染效率慢的缺點(diǎn)，實(shí)現(xiàn)了多核CPU+GPU體繪制的并行計(jì)算。最終較好地實(shí)現(xiàn)了電磁場的可視化，降低了可視化的渲染時(shí)間。

2 電磁場探測范圍的體繪制

2.1 體繪制方法概述

體繪制是將三維數(shù)據(jù)場的信息變換生成屏幕上的二維圖像。體繪制主要的方法有：

（1）光線投射算法（Ray Casting）。

（2）光線跟蹤算法（Splatting）。

（3）頻域體繪制算法（Shear-warp）。

（4）硬件輔助的三維紋理映射法（3D Texture Mapping）[7]。

光線跟蹤算法是現(xiàn)階段體繪制使用最多的方法，它是指從三維數(shù)據(jù)場中的視點(diǎn)繪制出覆蓋整個(gè)屏幕像素點(diǎn)的光線，并且查找阻擋光線最近的那個(gè)物體，然后根據(jù)材料的特性以及場景中光線的效果來確定渲染在二維圖片上的每一個(gè)像素點(diǎn)的顏色值。相比光線投射算法，光線跟蹤算法的重點(diǎn)并不是進(jìn)行色彩的積累，如圖1所示，光線跟蹤算法僅僅只考慮光線和幾何體的相交情況。

圖1 采用光線跟蹤算法的電磁場可視化圖

本文采用了光線跟蹤算法，要求判斷每一條光線和模型的交點(diǎn)個(gè)數(shù)，從而確定二維圖像的像素值。因?yàn)槊恳淮喂饩€繪制和求交過程中數(shù)據(jù)之間不存在依賴，所以在光線繪制和求交計(jì)算過程是比較好的并行選擇。

2.2 電磁場體繪制技術(shù)

光線是從視點(diǎn)到屏幕像素點(diǎn)的多條射線。根據(jù)交點(diǎn)的個(gè)數(shù)的不同對交點(diǎn)進(jìn)行判斷，根據(jù)式（1）找出一個(gè)交點(diǎn)的坐標(biāo)(xi,yi,zi)。其中(xi,yi,zi)分別表示第i個(gè)交點(diǎn)的坐標(biāo)值，(oxi,oyi,ozi)分別表示第i個(gè)交點(diǎn)的雷達(dá)波發(fā)射中心的坐標(biāo)值。

然后根據(jù)雷達(dá)波能量衰減函數(shù)，獲得該點(diǎn)的能量函數(shù)Pr；Pt表示雷達(dá)發(fā)射機(jī)峰值的功率；Gt表示發(fā)射天線增益；Gr表示接收天線增益；σ表示雷達(dá)反射截面積；τ表示雷達(dá)工作波長。如果假設(shè)發(fā)射天線增益和接收天線增益相等。式（2）可以表示為如下形式[8]：

最后按照式（3）將能量值轉(zhuǎn)化為光學(xué)屬性進(jìn)行繪制，形成體繪制二維圖。其中Pixel表示的是渲染在投影平面上像素點(diǎn)的RGB和?值。

在上述過程中造成體繪制效率低主要表現(xiàn)在兩個(gè)方面：（1）在渲染場景中的使用光線跟蹤算法繪制光線；（2）光線跟蹤算法中光線和雷達(dá)波探測范圍模型的交點(diǎn)計(jì)算。本文針對雷達(dá)探測范圍體繪制的這兩個(gè)低效問題進(jìn)行了改進(jìn)，主要貢獻(xiàn)如下：（1）將電磁場能量值轉(zhuǎn)化為光學(xué)屬性在計(jì)算機(jī)中進(jìn)行繪制；（2）采用GPU進(jìn)行光線的繪制，采用多核CPU進(jìn)行光線和電磁場探測范圍模型的交點(diǎn)計(jì)算。

張文波，曹耀欽等人將體繪制技術(shù)創(chuàng)新地運(yùn)用在電磁場仿真領(lǐng)域，并且采用CUDA將電磁場傳播模型（ITM）的計(jì)算移植到GPU中進(jìn)行，最終基于CUDA架構(gòu)實(shí)現(xiàn)了較高的加速比[9]。但是這種方法有兩個(gè)缺陷：（1）ITM模型是一種高效預(yù)測電磁波衰減的模型，文章的加速效果受限于所選取的ITM模型；（2）電磁場體繪制技術(shù)的時(shí)間開銷主要表現(xiàn)在兩個(gè)方面：①在渲染引擎中繪制光線的計(jì)算。②電磁場數(shù)據(jù)的計(jì)算以及交點(diǎn)信息的計(jì)算。而上述方法僅僅改進(jìn)了電磁場數(shù)據(jù)的計(jì)算以及交點(diǎn)計(jì)算，對于體繪制信息數(shù)據(jù)渲染的并行化算法并沒有涉及。

而本文針對這兩個(gè)時(shí)間開銷都進(jìn)行了改進(jìn)。在3.1節(jié)中使用GPU提高光線繪制的效率；在3.2節(jié)中使用多核CPU提高電磁場數(shù)據(jù)計(jì)算和交點(diǎn)計(jì)算效率。實(shí)驗(yàn)表明，對于光線繪制效率的改進(jìn)可以提高模型的可視化效果。

3 基于OSG的光線跟蹤并行計(jì)算

OSG（OpenSceneGraph）誕生于1990年，是C++編寫的、使用標(biāo)準(zhǔn)模板庫（STL）作為容器的圖形引擎。OSG使用場景圖的方法來構(gòu)造3D世界，其中場景圖中的每一個(gè)NODE節(jié)點(diǎn)都是存在于場景中，并且與場景中的其他節(jié)點(diǎn)存在一定的從屬關(guān)系。OSG最大的優(yōu)點(diǎn)是模塊化和可拓展性，并且容易學(xué)習(xí)，所以現(xiàn)如今受到了大多數(shù)計(jì)算機(jī)圖形學(xué)工作者的青睞[10]。

OSG場景圖是采用AABB包圍盒和包圍球技術(shù)來實(shí)現(xiàn)碰撞檢測的相交測試，并且對于碰撞檢測進(jìn)行了類的封裝。這種封裝對于初學(xué)者來說可以快速地實(shí)現(xiàn)三維場景的碰撞檢測功能，但是其缺點(diǎn)是實(shí)現(xiàn)的功能僅限于是OSG自帶的碰撞檢測方法。如果開發(fā)者想要拓展新的方法來提高OSG程序執(zhí)行的效率，則是非常困難的。

在第2章已經(jīng)介紹了光線跟蹤算法在計(jì)算機(jī)中耗時(shí)最多的兩個(gè)步驟：（1）光線繪制；（2）相交檢測并根據(jù)交點(diǎn)的數(shù)量繪制像素點(diǎn)的顏色值。本文在3.1節(jié)和3.2節(jié)分別進(jìn)行了時(shí)間效率的改進(jìn)。

3.1 基于GPU的光線繪制

CUDA（Compute Unified Device Architecture）是由NVIDIA公司提出的建立在GPU上的統(tǒng)一計(jì)算架構(gòu)。充分利用GPU強(qiáng)大的多線程浮點(diǎn)數(shù)計(jì)算能力和多計(jì)算核心的特點(diǎn)，可以將問題劃分為粗放子問題，以并行的方式獨(dú)立解決[11-12]。文獻(xiàn)[13]提出了CUDA所使用的從內(nèi)存拷貝數(shù)據(jù)到顯存的方法很低效，這也正是使用CUDA架構(gòu)進(jìn)行并行計(jì)算編程的瓶頸所在。而光線繪制并不需要對大量的數(shù)據(jù)進(jìn)行內(nèi)存到顯存的拷貝，因此可以極大地發(fā)揮CUDA的多線程浮點(diǎn)數(shù)運(yùn)算的特性。

光線繪制是指在視點(diǎn)和屏幕像素點(diǎn)之間分別繪制射線，射線指向屏幕像素點(diǎn)。視點(diǎn)的位置是固定不變的，因此光線繪制階段主要的任務(wù)就是確定屏幕像素點(diǎn)的坐標(biāo)值。本文采用CUDA來計(jì)算屏幕像素點(diǎn)的坐標(biāo)值。屏幕像素點(diǎn)的坐標(biāo)值與如下幾個(gè)量有關(guān)：

（1）投影平面的分辨率。

（2）投影平面的起始點(diǎn)坐標(biāo)值。

（3）投影平面的像素仿真步長。

（4）場景漫游器camera的坐標(biāo)值。

以下內(nèi)容將會(huì)介紹在OSG引擎中如何避免文獻(xiàn)[13]中提到的數(shù)據(jù)拷貝效率低下的問題，進(jìn)一步介紹如何使用CUDA計(jì)算屏幕像素點(diǎn)坐標(biāo)值。

本文光線繪制算法步驟如下：

CUDA輸入。投影平面的仿真步長（s_dx），投影平面起始點(diǎn)坐標(biāo)值（m.x，m.y，m.z），場景漫游器camera的坐標(biāo)值（p.x，p.y，p.z）。

CUDA輸出。繪制完成的若干光線。

步驟1 在顯存中申請大小為sizeof（float3）×THREAD_NUM×BLOCK_NUM的空間用于存放計(jì)算結(jié)果（其中BLOCK_NUM為CUDA內(nèi)核開啟的線程塊數(shù)量，THREAD_NUM為每個(gè)CUDA線程塊開啟的線程數(shù)量）。

步驟2 CUDA計(jì)算階段：申請float3類型的變量dir來表示屏幕像素點(diǎn)的坐標(biāo)值。

步驟2.1 CUDA的__global__函數(shù)中通過threadIdx.x和blockIdx.x函數(shù)獲得線程和線程塊的ID。

tid=threadIdx.x

bid=blockIdx.x

步驟2.2在__global__中分別計(jì)算dir的x、y、z坐標(biāo)值。以計(jì)算dir的x值為例：

dir[bid×512+tid].x=（m.x+tid×s_dx）－p.x

步驟3 CUDA光線繪制階段：根據(jù)屏幕像素點(diǎn)的坐標(biāo)值和camera的坐標(biāo)值繪制光線向量。

此方法在CUDA內(nèi)核中開啟了多線程，改進(jìn)了光線繪制在內(nèi)存中的單線程執(zhí)行，節(jié)省了內(nèi)存空間，提高了光線繪制效率。

3.2 基于多核CPU的交點(diǎn)計(jì)算

在傳統(tǒng)的單核CPU架構(gòu)中，通過提高CPU頻率來提高程序運(yùn)行速度已經(jīng)使CPU頻率發(fā)展到了極限。如今越來越多的多核CPU模型被設(shè)計(jì)出來，以此來充分利用CPU空閑資源。文獻(xiàn)[14-15]分析了一些現(xiàn)有的典型計(jì)算模型，以Jacobi迭代算法為例，說明了多核CPU模型可以改善運(yùn)行的性能。文獻(xiàn)[16]通過以遺傳算法（GP）——機(jī)器學(xué)習(xí)的典型算法之一為例，證明了通過利用cache（高速緩沖存儲(chǔ)器），基于多核CPU的GP算法的實(shí)現(xiàn)可以達(dá)到與GPU同樣級(jí)別的效率。因此，多核CPU也是重要的計(jì)算資源，不應(yīng)該忽略這種資源。

在本文中，投影平面像素點(diǎn)的顏色值與檢測到的交點(diǎn)數(shù)目有關(guān)。使用OSG+CUDA引擎進(jìn)行光線交點(diǎn)計(jì)算的弊端是：有大量的數(shù)據(jù)需要從內(nèi)存拷貝到顯存，由于OSG引擎的模塊化架構(gòu)，數(shù)據(jù)從內(nèi)存?zhèn)鬟f到顯存的時(shí)間消耗要近似等于CUDA提升的計(jì)算效率。因此，采用OSG+CUDA架構(gòu)進(jìn)行光線跟蹤的相交計(jì)算并不會(huì)很好地提高程序執(zhí)行的效率。所以，本文采用利用多核CPU來處理交點(diǎn)計(jì)算任務(wù)。

光線跟蹤算法的交點(diǎn)計(jì)算部分從原理上說是不存在數(shù)據(jù)依賴的，因此光線相交計(jì)算的每一次迭代都是可以使用多核CPU進(jìn)行并行化處理的。本文采用OpenMp來實(shí)現(xiàn)多核CPU的并行編程。

圖2是基于OSG體繪制方法的算法流程圖。

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

圖3是在同一個(gè)OSG場景下，關(guān)于雷達(dá)探測范圍面繪制和體繪制效果的對比。其中，圖3（a）和（b）是對同一個(gè)雷達(dá)發(fā)射源分別進(jìn)行面繪制和加速體繪制的結(jié)果。從圖中可以看出，（a）圖中面繪制有明顯的塊狀效果，對背景數(shù)據(jù)保留得較少，有部分空間數(shù)據(jù)丟失。（b）圖中體繪制的結(jié)果比較連續(xù)，很好地保留了背景數(shù)據(jù)。（c）圖是投影平面和3D場景的側(cè)視圖。

表1 體繪制和加速體繪制耗時(shí)關(guān)系

圖2 基于OSG實(shí)現(xiàn)體繪制計(jì)算流程

圖3 雷達(dá)探測范圍面繪制與加速體繪制對比圖

運(yùn)行參數(shù)設(shè)置：體繪制投影平面分辨率為1 024×1 024，THREAD_NUM設(shè)置為512，BLOCK_NUM設(shè)置為512，開啟8個(gè)線程計(jì)算射線交點(diǎn)。

（1）GPU：NVIDIA GeForce GTX 750Ti，顯存2 GB，顯存帶寬86.4 GB/s，時(shí)鐘頻率1 020 MHz，渲染到屏幕的像素點(diǎn)率16.3 GPixel/s?，F(xiàn)階段屬于中端顯卡。

（2）CPU：Inter Core i7 2600，高速緩沖存儲(chǔ)器（cache memory）32 KB×4，4核8線程，主頻3.4 GHz，峰值時(shí)運(yùn)算能力37.63 GFLOP/s。

分別使用分辨率為512×512、1 024×1 024、2 048×2 048的投影平面進(jìn)行體繪制，采用以上的配置的計(jì)算機(jī)進(jìn)行加速體繪制，結(jié)果如表1所示。

從表1中可以看出，對于OSG引擎來實(shí)現(xiàn)雷達(dá)波探測范圍的可視化效率較低。通過GPU光線繪制方法，可以極大程度地提升光線繪制的時(shí)間，加速比達(dá)到11～18倍。

（1）當(dāng)投影屏幕分辨率為1 024×1 024時(shí)，基于OSG的交點(diǎn)計(jì)算耗時(shí)明顯增加，已經(jīng)不滿足實(shí)時(shí)性的要求，通過多核CPU+GPU的加速體繪制算法，可以使交點(diǎn)計(jì)算的時(shí)間縮短到不到8 s。

（2）當(dāng)投影屏幕分辨率為2 048×2 048時(shí)，基于OSG的交點(diǎn)計(jì)算耗時(shí)已經(jīng)無法正常測量，采用多核CPU進(jìn)行交點(diǎn)計(jì)算后可以改進(jìn)這一缺陷。

圖4是本算法在大地形戰(zhàn)場環(huán)境中的應(yīng)用效果展示圖，從圖中可以看出對三維數(shù)據(jù)場的體繪制方法可以保留大量的背景信息。

圖4 戰(zhàn)場環(huán)境中體繪制算法的應(yīng)用

5 結(jié)語

本文針對面繪制三維數(shù)據(jù)場帶來的空間信息丟失問題，采用體繪制算法彌補(bǔ)了這個(gè)問題，提高了可視化效果，并利用GPU和多核CPU的并行處理能力提高算法的執(zhí)行效率。在OSG引擎下，實(shí)現(xiàn)了基于多核CPU+GPU的加速體繪制算法。可以完成對電磁場體繪制的實(shí)時(shí)渲染功能。本算法應(yīng)用在戰(zhàn)場環(huán)境的雷達(dá)波體繪制仿真中，已經(jīng)取得了很好的效果。