基于GPU的光線跟蹤算法分析
發(fā)布時間：2014-07-28 21:19
基于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ā)生改變。
加速結構的實現(xiàn)和比較
3.1均勻柵格
均勻柵格是第一個在GPU上實現(xiàn)的加速結構。Purcell給出了很多選擇均勻柵格作為加速結構的理由，但是Purcell沒有詳細的說明為什么均勻網(wǎng)格對于硬件實現(xiàn)而言比其它的加速結構要更加的簡單。當在探討了均勻柵格的一些主要特性的時候，更加清晰的知道了均勻柵格為什么會成為一個好的GPU機速結構。
首先，只用使用簡單的算術運算，就能夠?qū)τ诿總�體素的遍歷在常量時間能被定位和存取。這就消除了對樹的遍歷的需要，以及重復的紋理查找工作，而紋理查找是相當耗時的。其次，體素的遍歷是通過遞增算術運算來完成的。這就消除了對堆棧的需要，使得我們能夠從光線的起始點開始，以距離遞增的順序訪問體素成為可能。再其次，由于對于體素的訪問是沿著光線，以距離遞增的方式遍歷的，所以，一旦在一個被訪問的體素中報道發(fā)現(xiàn)有一個交點，就可以停止這條光線對體素的遍歷過程，從而提高整個遍歷過程的速度。最后，用于遍歷的代碼非常適合用向量編寫，而向量形式的編碼風格又非常適合GPU的指令集。然而，均勻柵格的缺點就是由于它是空間細分結構的一種特殊情況，多個體素可能包含相同三角形的多個引用。由于無法使用mailbox技術，這就意味著需要對于相同的光線和三角形之間進行不止一次的相交測試。
3.2 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結構的遍歷成為可能。
3.3 包圍體層次(BVH)
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)建。
本文編號：6722
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ā)生改變。
加速結構的實現(xiàn)和比較
3.1均勻柵格
均勻柵格是第一個在GPU上實現(xiàn)的加速結構。Purcell給出了很多選擇均勻柵格作為加速結構的理由，但是Purcell沒有詳細的說明為什么均勻網(wǎng)格對于硬件實現(xiàn)而言比其它的加速結構要更加的簡單。當在探討了均勻柵格的一些主要特性的時候，更加清晰的知道了均勻柵格為什么會成為一個好的GPU機速結構。
首先，只用使用簡單的算術運算，就能夠?qū)τ诿總�體素的遍歷在常量時間能被定位和存取。這就消除了對樹的遍歷的需要，以及重復的紋理查找工作，而紋理查找是相當耗時的。其次，體素的遍歷是通過遞增算術運算來完成的。這就消除了對堆棧的需要，使得我們能夠從光線的起始點開始，以距離遞增的順序訪問體素成為可能。再其次，由于對于體素的訪問是沿著光線，以距離遞增的方式遍歷的，所以，一旦在一個被訪問的體素中報道發(fā)現(xiàn)有一個交點，就可以停止這條光線對體素的遍歷過程，從而提高整個遍歷過程的速度。最后，用于遍歷的代碼非常適合用向量編寫，而向量形式的編碼風格又非常適合GPU的指令集。然而，均勻柵格的缺點就是由于它是空間細分結構的一種特殊情況，多個體素可能包含相同三角形的多個引用。由于無法使用mailbox技術，這就意味著需要對于相同的光線和三角形之間進行不止一次的相交測試。
3.2 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結構的遍歷成為可能。
3.3 包圍體層次(BVH)
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)建。
本文編號：6722
本文鏈接：http://www.wukwdryxk.cn/kejilunwen/jisuanjikexuelunwen/6722.html
最近更新
教材專著
