GPU光線(xiàn)跟蹤算法加速結構研究

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

關(guān)鍵詞：GPGPU 光線(xiàn)跟蹤 BVH KD-Tree

1．引言

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

2．基于GPU的光線(xiàn)跟蹤

2.1 相關(guān)工作

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

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

2.2 GPU上的光線(xiàn)跟蹤算法的映射方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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