陳占芳，張國(guó)玉，師為禮，任濤

(長(zhǎng)春理工大學(xué)，長(zhǎng)春 130022)

光線跟蹤體繪制算法是體繪制技術(shù)中的一種經(jīng)典算法，傳統(tǒng)算法中所有的計(jì)算都在CPU上進(jìn)行，重建速度較慢，無(wú)法達(dá)到實(shí)時(shí)效果。本文使用GPU編程技術(shù)，將原先在CPU中進(jìn)行的場(chǎng)景求交和光線遍歷采樣等步驟，移入GPU中進(jìn)行，利用GPU的高速浮點(diǎn)運(yùn)算能力，來(lái)實(shí)現(xiàn)三維圖像的實(shí)時(shí)繪制。與在 CPU上實(shí)現(xiàn)光線跟蹤體繪制算法相比，速度大大提高。

1 GPU原理與光線跟蹤技術(shù)分析

GPU(Graphic Processing Unit)，即圖形處理器，是顯示卡的核心。GPU使顯卡減少了對(duì)CPU的依賴，并進(jìn)行部分原本CPU的工作，特別在三維圖像處理時(shí)，更能體現(xiàn) GPU的浮點(diǎn)運(yùn)算能力。但GPU的指令執(zhí)行方式和CPU不一樣，無(wú)法直接實(shí)現(xiàn)遞歸，所以不能直接執(zhí)行在 CPU中實(shí)現(xiàn)的算法。依據(jù) GPU特性，本文把光線跟蹤表示成一種流計(jì)算模式，把可編程的 GPU抽象成通用的流處理器，充分利用了 GPU并行處理體系結(jié)構(gòu)的性能優(yōu)勢(shì)來(lái)實(shí)現(xiàn)算法。

實(shí)現(xiàn)基于流的光線跟蹤最大的難度是如何把光線跟蹤映射到設(shè)計(jì)的流計(jì)算模型中。GPU有很強(qiáng)的流處理能力，但實(shí)現(xiàn)遞歸非常困難。把光線跟蹤細(xì)分成多個(gè)內(nèi)核，內(nèi)核通過(guò)數(shù)據(jù)流聯(lián)系在一起。不管是靜態(tài)場(chǎng)景還是動(dòng)態(tài)場(chǎng)景繪制，首先要確定光線跟蹤能夠處理的幾何體片元的類型和系統(tǒng)實(shí)現(xiàn)中所使用的加速結(jié)構(gòu)的類型。光線跟蹤能夠渲染由不同幾何體片元組成的場(chǎng)景，其中最適合的是三角形。同時(shí)圖形硬件僅支持三角形渲染，其它表面形狀雖能使用，但在渲染之前它們都要被轉(zhuǎn)換成三角形。所以使用三角形來(lái)表示場(chǎng)景中幾何體。其次，建模程序和掃描軟件產(chǎn)生的模型都是由三角形網(wǎng)格組成的，當(dāng)在場(chǎng)景中只有一種簡(jiǎn)單圖形單元時(shí)，光線跟蹤會(huì)顯得更加簡(jiǎn)單有效。對(duì)于流計(jì)算來(lái)說(shuō)，場(chǎng)景中所有繪制可以被相同的內(nèi)核集來(lái)處理，這種方式使系統(tǒng)的數(shù)據(jù)流得到簡(jiǎn)化。

2 算法實(shí)現(xiàn)

光線跟蹤算法可以分解為兩大部分。一部分由CPU端來(lái)完成，主要負(fù)責(zé)整體計(jì)算的控制和平衡。另一部分則在GPU中，主要負(fù)責(zé)光線跟蹤的計(jì)算，這部分主要由四個(gè)類型的計(jì)算內(nèi)核來(lái)完成。

2.1 CPU端控制

CPU用來(lái)進(jìn)行算法的整體控制和計(jì)算平衡。

在 GPU上進(jìn)行光線衍生技術(shù)時(shí)，會(huì)獲得一組反射和一組折射光線，整個(gè)計(jì)算過(guò)程是一個(gè)多路徑的復(fù)雜計(jì)算，在多個(gè)路徑之間進(jìn)行切換需要CPU的控制。GPU無(wú)法對(duì)這些光線同時(shí)進(jìn)行計(jì)算，這需要CPU對(duì)計(jì)算資源進(jìn)行控制分配，即當(dāng)光線生成或光線衍生產(chǎn)生光線時(shí)，將生成的光線壓入棧，由CPU來(lái)分配GPU計(jì)算資源。

另外，由于訪問(wèn)存儲(chǔ)空間的限制，光線的遍歷和求交成為了算法實(shí)現(xiàn)最難解決的問(wèn)題。為此，必須設(shè)計(jì)合適的遍歷加速結(jié)構(gòu)來(lái)組織場(chǎng)景中的幾何基元數(shù)據(jù)。在經(jīng)典的加速結(jié)構(gòu)中，主要有兩種組織方式。一種以場(chǎng)景的幾何基元為中心，一種以場(chǎng)景的空間為中心。本文使用后一種，構(gòu)建類 BSP的算法，同時(shí)為了提高效率，采取一組光線并行入棧的方式。

2.2 GPU端算法實(shí)現(xiàn)

在 GPU端進(jìn)行光線跟蹤計(jì)算，使用一種基于流的光線跟蹤算法。整個(gè)框架由四個(gè)功能內(nèi)核組成:光線生成、場(chǎng)景遍歷、模型求交、渲染和光線衍生。每一種對(duì)應(yīng)于GPU中一個(gè)路徑的計(jì)算。

(1)光線生成：生成初始光線的起點(diǎn)和方向。

(2)場(chǎng)景遍歷：使用類二叉樹結(jié)構(gòu)來(lái)組織場(chǎng)景，利用光線信息在整體場(chǎng)景的空間剖分結(jié)構(gòu)中尋找可能需要進(jìn)行光線求交的模型表面基元。

(3)模型求交：主要完成交點(diǎn)的探測(cè)及光線與表面基元的求交計(jì)算。

(4)渲染和光線衍生：利用 phone光照模型來(lái)進(jìn)行光照計(jì)算，并將獲得值累加到幀緩存相關(guān)象素中。如果光線有交，就利用交點(diǎn)信息生成相應(yīng)的反射或折射光線。必要時(shí)，也會(huì)生成陰影測(cè)試光線。

如圖1所示，每個(gè)功能內(nèi)核的輸入顯示在盒子的左邊，內(nèi)核之間傳輸?shù)牧鲾?shù)據(jù)的類型由虛線所指的內(nèi)容表示。這種細(xì)分的方式在流編程模型中并不是強(qiáng)制性的。

圖1 基于流的光線跟蹤算法流程Fig.1 the ray tracing based on flow

光線產(chǎn)生器內(nèi)核產(chǎn)生一束光線流，每根光線都和圖像中的某個(gè)像素相關(guān)聯(lián)，以此形成光線向量集。網(wǎng)格遍歷內(nèi)核讀取由光線產(chǎn)生器產(chǎn)生的光線流，然后作用光線，使光線一步一步地遍歷網(wǎng)格直到碰到一個(gè)包含三角形面片的體素，光線和體素對(duì)被輸出并傳遞到光線與三角形面片求交測(cè)試內(nèi)核里。

場(chǎng)景遍歷中，改進(jìn)的遍歷算法描述如下：

第一步，建立2維KD_Tree結(jié)構(gòu)來(lái)存儲(chǔ)場(chǎng)景信息，該樹中的每個(gè)節(jié)點(diǎn)代表一個(gè)軸向包圍盒;每一個(gè)內(nèi)部節(jié)點(diǎn)表示分離平面，該平面將場(chǎng)景劃分為兩個(gè)子區(qū)域。劃分包圍盒的方法是沿軸循環(huán)分割，首先從根節(jié)點(diǎn)沿x軸對(duì)盒子進(jìn)行分割，然后再沿y軸分割子盒子，最后再沿 z軸分割孫子盒子，以此循環(huán)。

第二步，在求交和遍歷之前將該樹中序線索化為線索二叉樹；

第三步，如果光線的跨度區(qū)間橫跨分離軸的兩側(cè)，說(shuō)明該光線同時(shí)穿過(guò)兩個(gè)子包圍盒，則先和第一個(gè)子節(jié)點(diǎn)求交，只要先遍歷第一個(gè)節(jié)點(diǎn)，不將第二個(gè)節(jié)點(diǎn)壓入堆棧；否則，和相交的子節(jié)點(diǎn)求交；

第四步，如果該節(jié)點(diǎn)是葉子節(jié)點(diǎn)，且射線和該子節(jié)點(diǎn)有交，則返回成功，否則，直接搜索該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。

本算法可避免堆棧操作帶來(lái)的開(kāi)銷。雖然建立線索二叉樹本身也會(huì)有一定的開(kāi)銷，但該操作在初始化時(shí)一次完成，后面的每次操作都將加快遍歷速度。在實(shí)際應(yīng)用中，通過(guò)限制中間節(jié)點(diǎn)的深度，并保證KD_Tree的平衡性，平均的算法時(shí)間復(fù)雜度為O(log2n)。

模型求交內(nèi)核主要負(fù)責(zé)測(cè)試該光線是否和體素中包含的三角形面片有交點(diǎn)。光線跟蹤實(shí)際上就是復(fù)雜場(chǎng)景和一個(gè)光線樹的遍歷求交過(guò)程，每次重新生成的光線都是原來(lái)光線的子光線，這樣將動(dòng)態(tài)生成一個(gè)光線樹。每個(gè)像素點(diǎn)的最終顏色都是沿著光線樹向下迭代求交所得，由于 GPU體系結(jié)構(gòu)的限制，無(wú)法動(dòng)態(tài)生成光線樹，可以利用光線棧來(lái)管理每次求交生成的子光線。對(duì)于反射光線，為了提高效率，可以利用循環(huán)迭代來(lái)代替原來(lái)的遞歸調(diào)用。N次迭代的公式可以表示如下：

其中 表示模j，ri表示i物體的反射系數(shù)， 為像素的最終顏色，N為反射深度。

渲染和光線衍生的功能主要是計(jì)算顏色值。如果一根光線終止在相交點(diǎn)上，那么把這個(gè)相交點(diǎn)的顏色值寫進(jìn)累加的圖像上。此外，繪制內(nèi)核可能產(chǎn)生陰影或次光線，這種情況下，將這些新產(chǎn)生的光線返回到遍歷階段，開(kāi)始新的跟蹤。

3 結(jié)果與分析

基于 GPU加速的光線跟蹤繪制速度的測(cè)試不包含加速結(jié)構(gòu)構(gòu)建時(shí)間，因?yàn)閷?shí)驗(yàn)的目的是測(cè)試GPU加速對(duì)場(chǎng)景繪制速度的影響。對(duì)于靜態(tài)場(chǎng)景繪制，加速結(jié)構(gòu)構(gòu)建可在預(yù)處理階段完成。上述算法中，GPU實(shí)現(xiàn)部分使用NVIDIA推出的通用并行計(jì)算架構(gòu) CUDA(Compute Unified Device Architecture)完成，根據(jù) GPU中獨(dú)立 ALU(算術(shù)邏輯部件)數(shù)量將光線投射運(yùn)算拆分，所有 ALU并行運(yùn)算，提高光線投射處理速度。兩種實(shí)現(xiàn)方式在分辨率為256×256、512×512情況下，繪制速度如表1所示。

表1 光線跟蹤算法在CPU和GPU上實(shí)現(xiàn)時(shí)的速度比較Tab.1 speed of the ray tracing on CPU and GPU

4 結(jié)論

主要討論了一種改進(jìn)的光線跟蹤算法，它是一種基于GPU的快速光線跟蹤繪制算法，在普通PC機(jī)上(Pentium4 3.0G，ATI9500)，根據(jù)3個(gè)不同復(fù)雜度的場(chǎng)景，在分辨率分別為256*256、512*512時(shí)，實(shí)現(xiàn)了GPU和CPU實(shí)現(xiàn)光線跟蹤繪制，并進(jìn)行結(jié)果比較分析。從實(shí)驗(yàn)結(jié)果可得到基于GPU加速的光線跟蹤的優(yōu)勢(shì)，隨著場(chǎng)景復(fù)雜度的增加，基于GPU加速的光線跟蹤算法將明顯優(yōu)于CPU上的算法。

[1]楊俊華，符紅光，郭惠.基于GPU快速光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2007，27(8)：2033-2035.

[2]儲(chǔ)璟駿.基于GPU的直接體繪制技術(shù)[D].上海交通大學(xué)碩士論文，2007.

[3]章圣潔，王國(guó)榮，王小平.基于GPU加速的光線跟蹤技術(shù)研究[J].計(jì)算機(jī)時(shí)代，2007(6)：3638.

[4]王碧薇.基于GPU的光線跟蹤算法的分析[J].科技資訊，2007，23(6)：64-.