陳占芳，張國玉，師為禮，任濤

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

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

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

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

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

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

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

2.1 CPU端控制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果與分析

基于 GPU加速的光線跟蹤繪制速度的測試不包含加速結(jié)構(gòu)構(gòu)建時間，因?yàn)閷?shí)驗(yàn)的目的是測試GPU加速對場景繪制速度的影響。對于靜態(tài)場景繪制，加速結(jié)構(gòu)構(gòu)建可在預(yù)處理階段完成。上述算法中，GPU實(shí)現(xiàn)部分使用NVIDIA推出的通用并行計算架構(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)時的速度比較Tab.1 speed of the ray tracing on CPU and GPU

4 結(jié)論

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

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

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

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

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