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

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

3．加速結構的實(shí)現和比較

3.1均勻柵格

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

首先，只用使用簡(jiǎn)單的算術(shù)運算，就能夠對于每個(gè)體素的遍歷在常量時(shí)間能被定位和存取。這就消除了對樹(shù)的遍歷的需要，以及重復的紋理查找工作，而紋理查找是相當耗時(shí)的。

其次，體素的遍歷是通過(guò)遞增算術(shù)運算來(lái)完成的。這就消除了對堆棧的需要，使得我們能夠從光線(xiàn)的起始點(diǎn)開(kāi)始，以距離遞增的順序訪(fǎng)問(wèn)體素成為可能。

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

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

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

3.2 KD-tree

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

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

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

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

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

3.3 包圍體層次(BVH)

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

Goldsmith和Salmon提出了一個(gè)評價(jià)函數，通常被稱(chēng)為表面積啟發(fā)式函數。他們通過(guò)父節點(diǎn)和孩子節點(diǎn)的表面積之比來(lái)形式化的表述這個(gè)關(guān)系，此評價(jià)函數如下所示：

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

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

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

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

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

4．結束語(yǔ)

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

參考文獻：

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

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

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

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

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