陳 昱 江蘭帆

（福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108）

1 引言

光線跟蹤是一種基于物理的圖形渲染算法，相比于實(shí)時(shí)流水線光柵化算法，更方便實(shí)現(xiàn)真實(shí)環(huán)境中的反射、折射、透明、陰影等全局光照效果。光線跟蹤算法產(chǎn)生的畫面真實(shí)感強(qiáng)，被廣泛應(yīng)用于電影后期制作等領(lǐng)域。

光線跟蹤算法需要跟蹤每一條光線，將其與場(chǎng)景中幾何對(duì)象執(zhí)行相交測(cè)試，計(jì)算量很大。因此，目前光線跟蹤主要應(yīng)用于離線渲染，在實(shí)時(shí)渲染中的應(yīng)用還處于試驗(yàn)階段。如果光線跟蹤算法的性能可以達(dá)到實(shí)時(shí)交互，必然可以極大地提高該算法的應(yīng)用領(lǐng)域，對(duì)計(jì)算機(jī)圖形學(xué)相關(guān)應(yīng)用（如游戲，電影等）將產(chǎn)生重大影響。

2 光線跟蹤算法加速分析

為了提高光線跟蹤算法的速度，一種思路是改進(jìn)算法（如研究提高求交計(jì)算的效率，采用加速結(jié)構(gòu)減少求交的次數(shù)等），另一種則是從硬件體系出發(fā)。光線跟蹤渲染中每條光線獨(dú)立計(jì)算，十分適合并行體系結(jié)構(gòu)。近年來，集成大量處理核心的GPU（圖形處理器）在計(jì)算能力方面增長(zhǎng)迅速，在特定類型計(jì)算中已遠(yuǎn)超CPU[1]。光線跟蹤算法理論上可以利用GPU架構(gòu)的數(shù)據(jù)并行性獲得較高的性能，利用GPU實(shí)現(xiàn)光線跟蹤的實(shí)時(shí)交互成為了一個(gè)新的思路。

本文采用NVIDIA公司的CUDA作為GPU編程平臺(tái)，采用BVH作為加速結(jié)構(gòu)，對(duì)三角形網(wǎng)格模型進(jìn)行渲染，針對(duì)CUDA體系結(jié)構(gòu)進(jìn)行了算法的重新設(shè)計(jì)與優(yōu)化。實(shí)驗(yàn)結(jié)果表明10萬三角形的場(chǎng)景在目前主流型號(hào)GPU上算法已可以達(dá)到實(shí)時(shí)交互的性能，與CPU實(shí)現(xiàn)相比加速比達(dá)到5倍以上；與采用Kd-tree作為加速結(jié)構(gòu)的實(shí)現(xiàn)相比[2,3]，在同等復(fù)雜度的場(chǎng)景下性能更好。

3 基于GPU的光線跟蹤渲染

3.1渲染算法流程

渲染算法的流程和階段如圖1所示。整個(gè)渲染分成兩個(gè)工作階段：

1、CPU準(zhǔn)備階段是在CPU上運(yùn)算完成的，負(fù)責(zé)讀取場(chǎng)景數(shù)據(jù)和創(chuàng)建BVH。在得到這些數(shù)據(jù)之后，將其復(fù)制到顯卡的顯存中，供GPU渲染時(shí)使用。

2、GPU渲染階段是通過CUDA的kernel函數(shù)實(shí)現(xiàn)光線跟蹤渲染算法，編譯后運(yùn)行于GPU上。首先從視平面的像素點(diǎn)向場(chǎng)景空間中投射光線，獲取光線與場(chǎng)景中對(duì)象的最近碰撞點(diǎn)，利用BVH加速結(jié)構(gòu)進(jìn)行快速相交測(cè)試。接著判斷該碰撞點(diǎn)是否處在陰影區(qū)域，如果不在則利用光照模型計(jì)算該位置的直接光照強(qiáng)度。如果考慮間接反射情況，則應(yīng)繼續(xù)跟蹤光線，計(jì)算碰撞點(diǎn)的間接光照強(qiáng)度。將直接光照和間接光照疊加起來，即可計(jì)算出視平面的像素點(diǎn)的顏色值。在GPU中每一個(gè)線程計(jì)算一條光線方向，計(jì)算出像素顏色后寫入OpenGL PBO緩存區(qū)域，最終顯示在窗口中。

3.2 場(chǎng)景初始化

程序首先完成場(chǎng)景數(shù)據(jù)（包括對(duì)象，光源和照相機(jī)）的初始化。其中場(chǎng)景中的對(duì)象使用三角形網(wǎng)格（Mesh）進(jìn)行描述，實(shí)現(xiàn)了從模型文件中讀取頂點(diǎn)數(shù)據(jù)（坐標(biāo)，顏色，法向量）和多邊形定義。光源可在程序中設(shè)定其初始位置，類型采用點(diǎn)光源。照相機(jī)默認(rèn)采用透視投影。光源和照相機(jī)位置在程序執(zhí)行過程中可以動(dòng)態(tài)改變。這些場(chǎng)景數(shù)據(jù)的數(shù)據(jù)量比較大而且要能供所有線程訪問，因此只能通過CUDA API將其以數(shù)組的方式拷貝進(jìn)GPU的全局內(nèi)存或紋理內(nèi)存，供GPU渲染程序使用。

3.3 生成光線

根據(jù)觀察方向和視平面分辨率，可以計(jì)算得到每個(gè)像素的坐標(biāo)；結(jié)合照相機(jī)位置，就可以得到從投影中心到每個(gè)像素的主光線的參數(shù)方程。在GPU中，每個(gè)線程計(jì)算一條光線在場(chǎng)景中的反射光強(qiáng)度，即像素的顏色值。每個(gè)線程塊（Block）分配的光線數(shù)用以下公式計(jì)算：(SIZEX*SIZEY+THREADS_PER_BLOCK-1)/THREADS_PER_BLOCK。其中SIZEX和 SIZEY為屏幕窗口長(zhǎng)寬方向上的像素?cái)?shù)，THREADS_PER_BLOCK為CUDA中每個(gè)block的線程數(shù)。

3.4 BVH的構(gòu)建與遍歷

在生成光線后，渲染程序需要將光線與場(chǎng)景進(jìn)行相交檢測(cè)，獲取距離視點(diǎn)最近的物體交點(diǎn)。一種簡(jiǎn)單的做法是將光線與場(chǎng)景中的所有幾何對(duì)象進(jìn)行碰撞檢測(cè)，通過比較獲取最近的碰撞點(diǎn)。這種做法易于實(shí)現(xiàn)，但所需的計(jì)算量也是極為龐大，時(shí)間復(fù)雜性為O(N)，N為場(chǎng)景中對(duì)象的數(shù)量，而使用BVH和Kd-tree等加速結(jié)構(gòu)的時(shí)間復(fù)雜性為O(logN)，判斷效率提高明顯[4]。

1、BVH 的構(gòu)建

BVH（層次包圍盒）的基本思想是按照某一空間維度將原包圍盒分成兩部分，每部分再接著往下分，直到滿足結(jié)束條件，其過程與二叉樹類似。BVH中內(nèi)部節(jié)點(diǎn)不包含三角形，但包含兩個(gè)子節(jié)點(diǎn)的索引，而葉子節(jié)點(diǎn)包含一個(gè)三角形列表。創(chuàng)建過程是一個(gè)遞歸地劃分包圍盒的過程，每次包圍盒劃分位置的確定將影響B(tài)VH的生成結(jié)果，并影響整個(gè)加速結(jié)構(gòu)的遍歷性能。比較常用的方法是劃分時(shí)采用表面積啟發(fā)式（Surface Area Heuristic）代價(jià)模型，估算光線穿越包圍盒的期望代價(jià)，求得近似最優(yōu)解。

基于SAH評(píng)估的BVH創(chuàng)建過程如下[4]：

（1）將當(dāng)前節(jié)點(diǎn)包圍盒的最長(zhǎng)軸的方向作為分割方向；

（2）將三角形列表按照包圍盒的中心點(diǎn)在分割方向上的位置N等分，產(chǎn)生N-1種備選劃分方式：左邊1份，右邊N-1份，…，左邊N-1份，右邊1份；

（3）對(duì)每種分割方式分別計(jì)算兩部分包圍盒的表面積，再應(yīng)用SAH代價(jià)模型估算當(dāng)前劃分方式的代價(jià)，選取代價(jià)最小的分割方式劃分當(dāng)前節(jié)點(diǎn)；

（4）以同樣的方式遞歸生成孩子節(jié)點(diǎn)，一直到三角形數(shù)量小于設(shè)定的閾值為止，即可完成BVH的創(chuàng)建。

在CPU中完成BVH的構(gòu)建后，將其數(shù)據(jù)結(jié)構(gòu)拷貝到顯存中，供GPU渲染程序用于遍歷。

2、GPU中遍歷BVH進(jìn)行相交測(cè)試的實(shí)現(xiàn)

BVH的遍歷是一個(gè)深度優(yōu)先的遞歸過程。從根節(jié)點(diǎn)開始，光線與節(jié)點(diǎn)的包圍盒進(jìn)行相交測(cè)試。如果沒有相交，返回。如果相交，將光線與該節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)進(jìn)行相交測(cè)試；或者該節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則與該節(jié)點(diǎn)的三角形列表逐一進(jìn)行相交測(cè)試。

在CUDA平臺(tái)上實(shí)現(xiàn)BVH遍歷的問題是，CUDA前期的架構(gòu)版本（G80/GT200）是不支持遞歸函數(shù)調(diào)用的，所以為了實(shí)現(xiàn)更好的GPU兼容性，需將BVH遍歷修改為非遞歸算法，將原本指向節(jié)點(diǎn)的指針用節(jié)點(diǎn)索引替代，并引入堆棧保存節(jié)點(diǎn)列表。算法如下：

初始化節(jié)點(diǎn)列表為空，將根節(jié)點(diǎn)添加到節(jié)點(diǎn)列表中

初始化當(dāng)前相交的最近距離為無限遠(yuǎn)：min_t=INEnd While

3.5 陰影計(jì)算

當(dāng)確定光線和場(chǎng)景中三角形的最近交點(diǎn)后，下一步需計(jì)算交點(diǎn)處的反射光強(qiáng)度（即顏色值）。首先要判斷的就是在交點(diǎn)和光源之間是否有物體遮擋，如有遮擋則光源對(duì)該像素點(diǎn)的顏色無直接貢獻(xiàn)；否則在計(jì)算像素顏色時(shí)需要考慮該光源的貢獻(xiàn)。當(dāng)確定光線和場(chǎng)景中三角形的最近交點(diǎn)后，可以在光源與交點(diǎn)之間生成陰影檢測(cè)光線，并利用3.4節(jié)中基于BVH的相交測(cè)試算法進(jìn)行遮擋測(cè)試。

3.6 光照模型計(jì)算

為了計(jì)算光線所對(duì)應(yīng)的像素顏色（即交點(diǎn)處反射向視點(diǎn)的光線顏色），在交點(diǎn)處可以使用常用的Blinn-Phong光照模型公式[5]計(jì)算其在每個(gè)光源下的反射光顏色并疊加：

CUDA支持float4數(shù)據(jù)類型，十分方便進(jìn)行上述公式中向量的計(jì)算。其中鏡面反射分量計(jì)算時(shí)需要交點(diǎn)處的法向量n，通過三角形三個(gè)頂點(diǎn)處的法向量（從模型文件中讀取）結(jié)合交點(diǎn)處的質(zhì)心坐標(biāo)（Barycentric Coordinates）插值計(jì)算得到，實(shí)現(xiàn)Phong插值著色，這樣計(jì)算得到的物體表面的反射光顏色過渡較為自然。

3.7 間接反射計(jì)算

在光線跟蹤渲染中，光線與場(chǎng)景第一次相交后通常還需計(jì)算間接反射情況。像素的顏色除了包含光源的反射光顏色之外，還需其他表面產(chǎn)生的間接反射光顏色。光線每反射一次便需計(jì)算一次交點(diǎn)處的顏色值，這樣經(jīng)過多次反射后，像素點(diǎn)最終色彩便是多個(gè)間接反射顏色的累加。

上述間接反射過程是一個(gè)遞歸的計(jì)算，實(shí)現(xiàn)中為了函數(shù)在有限時(shí)間內(nèi)返回，需定義遞歸的深度（即跟蹤的反射次數(shù)），可以表示成以下的偽代碼：

//利用傳入的光線參數(shù)查找最近相交點(diǎn)intersec-

上述光線跟蹤的遞歸算法十分簡(jiǎn)潔，但為了在CUDA上實(shí)現(xiàn)上述算法，必須進(jìn)行非遞歸模式的改寫。由于RayTrace函數(shù)中變量眾多，如果用3.4節(jié)中添加堆棧的方式改寫該算法，代碼的改寫量大、改寫后可讀性差。因此，本文利用C++的模板元編程（Template Meta Programming,TMP）技術(shù)解決這個(gè)問題。所謂模板元編程，是C++將計(jì)算從運(yùn)行期轉(zhuǎn)移至編譯期、由編譯器在編譯期執(zhí)行部分計(jì)算的技術(shù)統(tǒng)稱[6]，利用其中的“遞歸模板實(shí)例化”技術(shù)可以實(shí)現(xiàn)編譯期遞歸結(jié)構(gòu)。

在原遞歸函數(shù)聲明前加上template定義遞歸深度depth作為模板元參數(shù)，得到如下的模板主函數(shù)：

template

Color RayTrace(Vector3 ray,Vector3 origin,...){

....

//利用傳入的光線參數(shù)查找最近相交點(diǎn)intersectionPoint

//計(jì)算交點(diǎn)處光照模型下的顏色值.phongColor

//計(jì)算反射光線reflectionRay

...

return color+RayTrace(reflectionRay,intersectionPoint);}

再定義如下形式的完全特化（Specialization）后的模板函數(shù)，其中的遞歸深度被預(yù)先定義的常量MAX_DEPTH（比如4）特化了，從而得到遞歸結(jié)束時(shí)的函數(shù)如下：

template<>

Color RayTrace(Vector3 ray,Vector3 origin,...){

return BLACK;//這里結(jié)束了遞歸

在編譯過程中，編譯器會(huì)分析depth在執(zhí)行過程中可能的值的情況，根據(jù)函數(shù)模板生成depth值不同時(shí)的函數(shù)版本，即生成從RayTrace<0>（這是主光線時(shí)的情況）到RayTrace的執(zhí)行代碼。

從上述代碼片段可以發(fā)現(xiàn)其對(duì)原算法的代碼改變是很小的，并且克服了CUDA無法編寫遞歸函數(shù)的問題。當(dāng)然，元編程也有其缺點(diǎn)，比如編譯時(shí)間變長(zhǎng)，執(zhí)行文件變大，不宜調(diào)試等。

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

實(shí)驗(yàn)采用不同頂點(diǎn)數(shù)和多邊形數(shù)的場(chǎng)景對(duì)上述渲染算法的GPU和CPU實(shí)現(xiàn)進(jìn)行性能測(cè)試，測(cè)試過程中設(shè)定一個(gè)點(diǎn)光源，視點(diǎn)位置繞固定軸旋轉(zhuǎn)一周，記錄下渲染360幀（即旋轉(zhuǎn)360度）所需時(shí)間后求每秒平均幀數(shù)（FPS）。測(cè)試平臺(tái)軟硬件配置如下：

*CPU：AMD Athlon II X2 255 3.1GH，雙核心

*GPU：NVIDIA GeForce GTS 450，192 個(gè)流處理單元

*CUDA Toolkit：版本 4.2.9

測(cè)試場(chǎng)景分別為兩個(gè)3DS模型文件 （Chess和Gundam），兩個(gè)Stanford提供的PLY模型 （Horse和Armadillo），渲染結(jié)果如下：

4.1 GPU線程配置測(cè)試

在CUDA中，kernel函數(shù)執(zhí)行的性能受到底層硬件配置和軟件配置的影響，從軟件層面的優(yōu)化來說，很主要的是合理配置其線程參數(shù)，以便達(dá)到較好的處理器利用率。CUDA中的線程以兩層結(jié)構(gòu)的形式組織管理，即網(wǎng)格（Grid）包含多個(gè)線程塊（Block），線程塊包含多個(gè)線程（Thread）。如果每個(gè)塊的線程數(shù)太少，無法充分利用多核心的處理能力，也無法通過調(diào)度隱藏訪問顯存的延時(shí)。如果一個(gè)塊的線程數(shù)太多，由于在一個(gè)多核流處理器 （Streaming Multiprocessor,SM）上同時(shí)執(zhí)行的線程數(shù)受到寄存器數(shù)量、共享內(nèi)存數(shù)量等硬件資源限制，又會(huì)使得許多線程處于等待狀態(tài)，無法并行執(zhí)行[7]。

對(duì)線程塊包含不同線程數(shù)時(shí)的Chess場(chǎng)景渲染測(cè)試的結(jié)果如圖3所示：

圖3測(cè)試結(jié)果表明，對(duì)上述光線跟蹤算法GPU實(shí)現(xiàn)在測(cè)試平臺(tái)上的最佳數(shù)配置是每個(gè)線程塊包含128個(gè)線程。這與光線跟蹤的kernel函數(shù)需要的寄存器數(shù)量比較多有關(guān)系，更多的并發(fā)線程所需的寄存器數(shù)量無法在硬件上得到滿足。

4.2 GPU和CPU渲染對(duì)比測(cè)試

對(duì)上述光線跟蹤渲染器的GPU和CPU實(shí)現(xiàn)進(jìn)行性能測(cè)試，其中GPU測(cè)試采用每塊128線程配置下的測(cè)試結(jié)果；CPU也是用BVH加速結(jié)構(gòu)，并且采用OpenMP實(shí)現(xiàn)多線程并行計(jì)算，以利用CPU的多個(gè)核心。測(cè)試結(jié)果見表1。

從表1可以看出，GPU實(shí)現(xiàn)的渲染引擎可以在512x512分辨率下對(duì)10萬個(gè)三角形以內(nèi)的場(chǎng)景實(shí)現(xiàn)大于15 fps的渲染速度，相比CPU的實(shí)現(xiàn) （使用OpenMP優(yōu)化）有5倍以上的性能提升。渲染速度與場(chǎng)景的構(gòu)成（頂點(diǎn)數(shù)量，三角形數(shù)量）、模型表面多反射的發(fā)生數(shù)量以及渲染的視角都有關(guān)系?？偟膩碚f，頂點(diǎn)數(shù)量和三角形數(shù)量少的場(chǎng)景渲染速度較快，物體表面相互反射較少時(shí)速度較快，物體占據(jù)畫面的面積較小時(shí)速度較快 （空白背景的像素光線直接穿越，BVH可以快速判斷此情況）。

5 總結(jié)

本文在基于BVH加速結(jié)構(gòu)的光線跟蹤算法基礎(chǔ)上，根據(jù)CUDA平臺(tái)的特點(diǎn)重新對(duì)渲染算法進(jìn)行了設(shè)計(jì)與優(yōu)化，在GPU上實(shí)現(xiàn)了具有實(shí)時(shí)性的光線跟蹤算法。測(cè)試結(jié)果表明，主流GPU在512x512分辨率下，10萬個(gè)三角形以內(nèi)的場(chǎng)景可以達(dá)到超過15 fps的渲染速度，可實(shí)現(xiàn)實(shí)時(shí)交互；與采用Kd-tree作為加速結(jié)構(gòu)的實(shí)現(xiàn)相比[2,3]，在同等復(fù)雜度的場(chǎng)景下性能更好。

經(jīng)過實(shí)驗(yàn)，也發(fā)現(xiàn)GPU在實(shí)現(xiàn)光線跟蹤渲染上的不足之處。由于光線跟蹤渲染算法代碼復(fù)雜，編譯后線程所需的寄存器數(shù)量較多，限制了可同時(shí)并發(fā)的線程數(shù)量[8]；雖然程序使用了CUDA手冊(cè)中的多種優(yōu)化技巧，但渲染更高的分辨率和更復(fù)雜的場(chǎng)景仍需要性能更強(qiáng)大的GPU才有希望實(shí)現(xiàn)實(shí)時(shí)性。

表1各場(chǎng)景在不同分辨率下的渲染性能測(cè)試結(jié)果

[1] 吳恩華,柳有權(quán).基于圖形處理器(GPU)的通用計(jì)算[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(5)：601-612.

[2] 陸建勇,曹雪虹,焦良葆等.基于GPU交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)[J].南京工程學(xué)院學(xué)報(bào)（自然科學(xué)版）,2009,7(3)：61-67.

[3] 曹家音.基于KD-Tree遍歷的并行光線跟蹤加速算法[J].科技傳播,2010,(17)：233-233,224.

[4] Matt Pharr,Greg Humphreys.Physically Based Rendering,Second Edition：From Theory To Implementation[M].Morgan Kaufmann,2010.217-222.

[5] Edward Angel著,張榮華等譯.交互式計(jì)算機(jī)圖形學(xué)—基于OpenGL的自頂向下方法（第五版）[M].北京：電子工業(yè)出版社,2009.222-226.

[6] David Abrahams,Aleksey Gurtovoy著,榮耀譯.C++模板元編程[M].北京：機(jī)械工業(yè)出版社,2010.

[7] David B.Kirk,Web-mei W.Hwu著,陳曙暉等譯.大規(guī)模并行處理器編程實(shí)踐[M].北京：清華大學(xué)出版社,2010.59-60.

[8] NVIDIA.CUDA C BEST PRACTICES GUIDE v4.2[Z].NVIDIA Corporation,2012.48-53.