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

陳宇峰，張 鉑，李 林

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

1 引言

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

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

體繪制起始于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]。體繪制也是電磁場(chǎng)可視化仿真領(lǐng)域中的重要組成部分。其優(yōu)點(diǎn)是不僅僅可以顯示高質(zhì)量的圖片，而且這些圖片可以表達(dá)出三維物體的內(nèi)部信息，這一點(diǎn)是傳統(tǒng)的計(jì)算機(jī)圖形學(xué)不可企及的[5-6]。基于以上的優(yōu)點(diǎn)，體繪制技術(shù)更加適用于繪制不可見(jiàn)的數(shù)據(jù)場(chǎng)信息，例如，人體骨骼密度，雷達(dá)探測(cè)范圍等。然而體繪制方法的缺點(diǎn)就是算法執(zhí)行的時(shí)間效率問(wèn)題。由于從視點(diǎn)投射出的每一條光線都需要和場(chǎng)景進(jìn)行碰撞檢測(cè)，所以體繪制效率改善的關(guān)鍵問(wèn)題就是改善光線求交運(yùn)算的碰撞檢測(cè)效率。

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

2 電磁場(chǎng)探測(cè)范圍的體繪制

2.1 體繪制方法概述

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

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

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

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

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

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

圖1 采用光線跟蹤算法的電磁場(chǎng)可視化圖

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

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

光線是從視點(diǎn)到屏幕像素點(diǎn)的多條射線。根據(jù)交點(diǎn)的個(gè)數(shù)的不同對(duì)交點(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á)工作波長(zhǎng)。如果假設(shè)發(fā)射天線增益和接收天線增益相等。式（2）可以表示為如下形式[8]：

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

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

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

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

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

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

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

在第2章已經(jīng)介紹了光線跟蹤算法在計(jì)算機(jī)中耗時(shí)最多的兩個(gè)步驟：（1）光線繪制；（2）相交檢測(cè)并根據(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)，可以將問(wèn)題劃分為粗放子問(wèn)題，以并行的方式獨(dú)立解決[11-12]。文獻(xiàn)[13]提出了CUDA所使用的從內(nèi)存拷貝數(shù)據(jù)到顯存的方法很低效，這也正是使用CUDA架構(gòu)進(jìn)行并行計(jì)算編程的瓶頸所在。而光線繪制并不需要對(duì)大量的數(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來(lái)計(jì)算屏幕像素點(diǎn)的坐標(biāo)值。屏幕像素點(diǎn)的坐標(biāo)值與如下幾個(gè)量有關(guān)：

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

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

（3）投影平面的像素仿真步長(zhǎng)。

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

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

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

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

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

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

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

步驟2.1 CUDA的__global__函數(shù)中通過(guò)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)核中開(kāi)啟了多線程，改進(jìn)了光線繪制在內(nèi)存中的單線程執(zhí)行，節(jié)省了內(nèi)存空間，提高了光線繪制效率。

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

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

在本文中，投影平面像素點(diǎn)的顏色值與檢測(cè)到的交點(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來(lái)處理交點(diǎn)計(jì)算任務(wù)。

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

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

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

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

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

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

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

運(yùn)行參數(shù)設(shè)置：體繪制投影平面分辨率為1 024×1 024，THREAD_NUM設(shè)置為512，BLOCK_NUM設(shè)置為512，開(kāi)啟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。現(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中可以看出，對(duì)于OSG引擎來(lái)實(shí)現(xiàn)雷達(dá)波探測(cè)范圍的可視化效率較低。通過(guò)GPU光線繪制方法，可以極大程度地提升光線繪制的時(shí)間，加速比達(dá)到11～18倍。

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

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

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

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

5 結(jié)語(yǔ)

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