摘要：基于GPU的光線跟蹤算法是當前圖形學研究的一個熱點，也是將來用于廣告、電影、游戲等娛樂產(chǎn)業(yè)的關鍵技術。本文論述了如何對基于GPU的光線跟蹤算法進行實現(xiàn)，以及利用各種加速結構，加速算法實現(xiàn)，提高算法執(zhí)行效率，并對各種加速結構的效果進行了比較研究。

關鍵詞：GPGPU 光線跟蹤 BVH KD-Tree

1．引言

近年來，CPU無論在運算能力，還是在可編程性上都得到了大幅的提高，GPU已經(jīng)在需要大量運算的密集運算領域發(fā)揮了舉足輕重的作用。各種基于CPU的密集運算被移植到GPU上，以利用GPU巨大的運算能力，加速整個算法的運算過程。光線跟蹤算法是生成真實感圖形的一種非常重要的方法，在電影、游戲、廣告等產(chǎn)業(yè)，獲得廣泛的應用，而光線跟蹤算法也是典型的密集運算算法，利用原始的基于CPU的光線跟蹤渲染一幅圖片是非常耗時的操作。因此，如果能夠?qū)PU上的光線跟蹤算法，映射到CPU上，加速光線跟蹤算法的執(zhí)行時間，將會帶來巨大的經(jīng)濟效益。因此，基于CPU的光線跟蹤算法已成為國內(nèi)外科研人員的研究熱點。

2．基于GPU的光線跟蹤

2.1 相關工作

當前，主要由兩種方法利用CPU來加速光線跟蹤算法。第一種是Carr等人提出來的，將CPU轉(zhuǎn)換為一個蠻力的執(zhí)行光線一三角形求交的計算器，而將任何的光線生成以及著色過程在CPU上完成。這就需要CPU依然執(zhí)行絕大部分的渲染工作。C arr等人指出，在ATI Radeon 8500上，每秒最快能夠執(zhí)行1億2千萬次的光線一三角形求交。同時，作者也指出，由于GPU的單精度浮點的限制，圖片上依然存在一些不太真實的地方。

第二種方法由Purcell等人提出的，改種方法將整個光線跟蹤器都移植到CPU上進行實現(xiàn)。從光線的產(chǎn)生，加速結構的遍歷，到最后的著色過程都在GPU上執(zhí)行。此后，有很多相同的項目都是基于Purcell的模型上進行的。

2.2 GPU上的光線跟蹤算法的映射方式

將傳統(tǒng)的CPU上執(zhí)行的光線跟蹤算法，映射成為一個GPU協(xié)助的，或者基于GPU的光線跟蹤器有眾多方法。下面重點介紹Purcell提出的映射模型，以及在本文的實現(xiàn)中提出的一個基于CPU的Whitted模型的光線跟蹤器。該光線跟蹤器的布局如圖2.1所示：

在Purcell的論文中，它將光線一三角形求交，以及遍歷過程分離成兩個獨立的遍歷內(nèi)核和求交內(nèi)核。本文的實現(xiàn)中，也按照上述模型圖，將光線跟蹤算法分解成光線生成，光線一三角形求交，著色這三個步驟。

在對光線進行跟蹤之前，需要生成從視點指向屏幕的原始光線( primary ray)。在一個GPU上，能夠使用光柵器的插值的能力，在一個單一的內(nèi)核調(diào)用中，產(chǎn)生所有的原始光線。

給定觀察矩形（被采樣用于產(chǎn)生圖片的投影平面的一部分）的四個角，以及視點，首先計算出這個視錐體的四條邊線。如果讓光柵器在這4條光線之間，按照512×512規(guī)格，在這四條光線之間按照方向進行插值，最終就可以獲得能夠產(chǎn)生一幅512×512圖片（一個像素一個采樣點）的所有原始光線的方向。同時能夠?qū)⑦@些方向存儲在一個紋理里，并把它作為求交內(nèi)核的輸入。所有的原始光線具有相同的起始點，但是仍然把它存儲在一個同方向紋理具有相同維度的紋理內(nèi)。因為當生成陰影光線或者反射光線的時候，光線的原點會發(fā)生改變。

求交內(nèi)核把光線的原點，方向，以及場景的描述作為輸入數(shù)據(jù)。在內(nèi)核被調(diào)用數(shù)次之后，我們對于每一個像素輸出一個擊中記錄。如果一條光線擊中了場景中的某個三角形，返回擊中點的3個重心坐標，以及相關的被擊中的三角形。此外，還將輸出被發(fā)現(xiàn)的交點沿光線的距離，以及被擊中三角形的材質(zhì)。這就需要使用5個浮點數(shù)值組成一個擊中記錄。紋理只能夠支持4個顏色通道( RCBA)，所以，如果能把擊中記錄裁減到4個值，那么將是非常有益的。

觀察發(fā)現(xiàn)，只需要3個重心坐標的兩個，因為在三角形內(nèi)部，它們相加的和總是1。這就使得在一個單獨的RGBA紋理中存儲交點記錄是可行的，并且它的維度同其它兩個光線紋理的維度相同。

Moller和Trumbore提出了一個高效的光線一三角形求交算法，使用這個算法，并利用CPU在向量計算上的優(yōu)勢來進行求交計算。下面列出了求交的代碼，這個代碼也展示了如何利用向量指令來提高效率。

當所有的原始光線都已經(jīng)計算出了相交的狀態(tài)的時候，就能夠查詢著色過程所需要的表面法線和材質(zhì)的信息。每一個擊中記錄都存儲了一個指向材質(zhì)紋理的索引，這個材質(zhì)紋理包含了三角形的法線，材質(zhì)顏色以及類型。三個頂點的法線根據(jù)擊中記錄的中心坐標進行了插值。最終的顏色能夠按(N-L)C進行計算，此處Ⅳ是法線，L是光源的方向，G是三角形的顏色。

現(xiàn)在根據(jù)擊中的三角形所具有的材質(zhì)的類型（漫反射材質(zhì)，或者鏡面反射材質(zhì)），需要產(chǎn)生二次光線，以此來計算陰影和反射。

1)如果一條光線射出場景之外，像素就被賦予全局的背景顏色。

2)如果一條光線擊中了一個漫反射材質(zhì)表面，就發(fā)射一條陰影射線( shdow ray)。這些光線的起始點在擊中點，方向為從擊中點指向光源。

3)如果一條光線擊中了一個鏡面反射材質(zhì)表面。就發(fā)射一條鏡面反射光線。鏡面發(fā)射光線的起始點也在擊中點，但是它的方向是在擊中點處關于入射光線和插值后的法線對稱的方向。一個真正的Whitted類型的光線跟蹤器也支持透明材質(zhì)，從而能夠產(chǎn)生折射光線。但由于主要是研究加速結構，所以在本文的實現(xiàn)中，沒有考慮折射光線。

4)如果陰影光線擊中了某個幾何體，這就說明在光源和擊中點之間，存在某個幾何體，所以這個像素就應該是黑色（處于陰影中）。

當跟蹤陰影光線的時候，不關心最近的那個擊中點，更加關心的是是否存在這樣的擊中點。因此，當有一個交點被發(fā)現(xiàn)，就可以停止整個求交過程，從而加速算法的處理過程。在本文的實現(xiàn)中，以相同的方式跟蹤陰影光線和反射光線，因此，就沒有使用到這個優(yōu)化策略。

已經(jīng)對每一個像素產(chǎn)生了正確二次光線，如果需要，就能夠執(zhí)行另外一趟遍歷/求交過程，對上述的二次光線進行跟蹤。每一次調(diào)用著色程序就能夠?qū)γ恳粋€像素返回一個顏色值和一條新的光線。著色內(nèi)核也可以將前一次著色程序的輸出當作本次著色程序的輸入。這就使得能夠在跟蹤連續(xù)的光線的時候合并這些連續(xù)的鏡面反射的顏色。

同Carr等人的程序不同，本文所采用的程序不存在浮點精度太低的問題，因為Ceforce 7300在整個管線中支持真正的32位浮點操作。

3．加速結構的實現(xiàn)和比較

3.1均勻柵格

均勻柵格是第一個在GPU上實現(xiàn)的加速結構。Purcell給出了很多選擇均勻柵格作為加速結構的理由，但是Purcell沒有詳細的說明為什么均勻網(wǎng)格對于硬件實現(xiàn)而言比其它的加速結構要更加的簡單。當在探討了均勻柵格的一些主要特性的時候，更加清晰的知道了均勻柵格為什么會成為一個好的GPU機速結構。

首先，只用使用簡單的算術運算，就能夠?qū)τ诿總€體素的遍歷在常量時間能被定位和存取。這就消除了對樹的遍歷的需要，以及重復的紋理查找工作，而紋理查找是相當耗時的。

其次，體素的遍歷是通過遞增算術運算來完成的。這就消除了對堆棧的需要，使得我們能夠從光線的起始點開始，以距離遞增的順序訪問體素成為可能。

再其次，由于對于體素的訪問是沿著光線，以距離遞增的方式遍歷的，所以，一旦在一個被訪問的體素中報道發(fā)現(xiàn)有一個交點，就可以停止這條光線對體素的遍歷過程，從而提高整個遍歷過程的速度。

最后，用于遍歷的代碼非常適合用向量編寫，而向量形式的編碼風格又非常適合GPU的指令集。

然而，均勻柵格的缺點就是由于它是空間細分結構的一種特殊情況，多個體素可能包含相同三角形的多個引用。由于無法使用mailbox技術，這就意味著需要對于相同的光線和三角形之間進行不止一次的相交測試。

3.2 KD-tree

最近，Havran等人對基于CPU的光線跟蹤算法的加速結構進行了比較，得出的結論是對于眾多不同類型的測試場景，平均而言，KD-tree是最快的。所以，有必要考察一下對于基于KD-tree的GPU光線跟蹤算法，是否也會有相似的結論。

就像均勻柵格一樣，KD-tree也是一種空間細分結構。同均勻網(wǎng)格不同的是，KD-tree利用一個二叉樹將場景表示成一個層次結構。

在二叉樹中，我們將內(nèi)部節(jié)點和葉子節(jié)點區(qū)分開。葉子節(jié)點用來表示體素和與之相關的保存在該體素內(nèi)的三角形的引用。一個內(nèi)部節(jié)點用來表示空間區(qū)域的某個部分。所以，內(nèi)部節(jié)點包含一個分裂面的兩個子樹的引用，而葉子節(jié)點只包含一個三角形列表。

KD-tree的創(chuàng)建過程從上而下，根據(jù)一個評價函數(shù)，通過放置一個分離平面，遞歸的將場景分離成兩個體素。我們能夠以遞歸的方式遍歷KD-tree，但是由于GPU沒有堆棧結構，所以無法應用遞歸的策略。取而代之的是，我們能夠通過記住我們沿著光線前進了多遠來向上或者向下遍歷樹。這種策略消除了需要堆棧的限制，使得用CPU來完成對KD-tree結構的遍歷成為可能。

當使用GPU對KD-tree進行遍歷的時候，KD-tree像均勻柵格那樣被表示成一個紋理的集合。這就意味著有一個保存樹數(shù)據(jù)的紋理，一個保存三角形列表的紋理，和一個保存實際的三角形數(shù)據(jù)的紋理。GPU的遍歷首先調(diào)用一個初始化內(nèi)核，然后按照需要，多次調(diào)用合并后的遍歷和求交內(nèi)核。

3.3 包圍體層次(BVH)

給定一些隨機的光線，通過計算遍歷包圍體層次的平均花費，就可以測量出該包圍體層次的質(zhì)量。迄今為止，還沒有構建最優(yōu)的包圍體層次的算法，也就是說，如何準確的測量一個包圍體層次的平均遍歷時間還不是很明顯。

Goldsmith和Salmon提出了一個評價函數(shù)，通常被稱為表面積啟發(fā)式函數(shù)。他們通過父節(jié)點和孩子節(jié)點的表面積之比來形式化的表述這個關系，此評價函數(shù)如下所示：

此處，hit(n)是光線擊中節(jié)點n的情況，Sn是節(jié)點n的表面積，c和p分別表示父節(jié)點和孩子節(jié)點。

這個評價函數(shù)給出了，當用一條隨機的光線同層次結構求交的時候，成本上的估計。由于沒有最優(yōu)的方法去有效的構造一個最優(yōu)的BVH，提出了不同的構造技巧。下面，將列出比較通用的方法。

在實踐中，對于包圍體應用的最廣泛的就是軸對齊包圍盒(AABB)。

AABB易于實現(xiàn)，并且同光線的求交測試非?？?。大多數(shù)有關BVH的論文在描述BVH的創(chuàng)建的時候，通常分別以Kay和Kajiya，或者Goldsmith和Salmon這兩種基本的想法為基礎。Kay和Kajiaya建議以自上而下遞歸的方式進行BVH的創(chuàng)建。

Goldsmith和Salmon提出了一個更加復雜的自底向上的構造方式。Goldsmith和Salmon指出，BVH的質(zhì)量同作為輸入傳人的三角形的順序有關。因此，他們建議在構造BVH之前，隨機打亂三角形的順序。下述算法就是利用Kay/Kajiya的思想創(chuàng)建某個場景的包圍體層次的方法：

4．結束語

本文成功的在GPU上實現(xiàn)了用于光線跟蹤算法中的各種加速結構，并對這些加速結構在GPU上的加速效果進行了比較。均勻柵格作為第一個在CPU上實現(xiàn)的光線跟蹤器的加速結構，也被證明是最慢的，除非是只包含一個單獨的物體的場景的情況。均勻柵格不適合幾何體的密度非常高的場景。另外，對于均勻柵格的CPU上的遍歷表示，也需要大量的數(shù)據(jù)。Foley和Sugerman認為，對于大多數(shù)場景，KD-tree的效率要比均勻柵格高。但是，在KD-tree的遍歷過程中，無論是重置階段還是回退階段，片元程序都非常的復雜，但這種復雜性也使得其能夠在場景的幾何體的密度改變的時候做出適當?shù)恼{(diào)整。本文實現(xiàn)的BVH被證明在加速效果上要超過均勻柵格和KD-tree，在現(xiàn)階段，BVH是在GPU上實現(xiàn)的最快的加速結構。并且在GPU上實現(xiàn)BVH加速結構要比實現(xiàn)其他加速結構更加的簡單。

參考文獻：

[1]Randima Femado編，姚勇，王小琴譯．GPU精粹一實時圖形編程的技術，技巧和技藝[M]．北京：人民郵電出版社，2006.

[2] Matt Pharr編著，龔敏敏譯.GPU精粹2-高性能圖形芯片和通用計算編程技巧[M].北京：清華大學出版社．

[3]昊恩華，柳有權．基于圖形處理器(GPU)的通用計算叨．計算機輔助設計與圖形學學報，2004，16(5): 601-612．

[4] Philip J.Schneider，David H.Eberly著，周長發(fā)譯，計算機圖形學幾何工具算法詳解[M].北京：電子工業(yè)出版社，2005.

[5] Martin Christen. Implementing ray tracing on GPU. Master´sthesis, University of Applied Sciences Basel