GPU光線跟蹤算法加速結構分析

論文類別:計算機論文 > 計算機應用論文
論文作者: 王世元 溫…
上傳時間:2011/11/10 10:52:00

代寫論文網:

摘要:基於GPU的光线跟蹤算法是當前圖形學研究的一個热點,也是將來用於廣告、電影、遊戲等娛乐產業的關鍵技術。本文論述了如何對基於GPU的光線跟蹤算法進行實現,以及利用各种加速結構,加速算法實現,提高算法執行效率,並對各種加速結构的效果進行了比較研究。

關鍵词:GPGPU 光线跟蹤 BVH KD-Tree

1.引言

近年來,CPU無論在運算能力,還是在可编程性上都得到了大幅的提高,GPU已經在需要大量運算的密集運算領域發揮了举足輕重的作用。各種基於CPU的密集運算被移植到GPU上,以利用GPU巨大的運算能力,加速整個算法的運算過程。光线跟蹤算法是生成真实感圖形的一種非常重要的方法,在電影、游戲、廣告等產業,獲得廣泛的应用,而光線跟蹤算法也是典型的密集運算算法,利用原始的基於CPU的光線跟蹤渲染一幅圖片是非常耗時的操作。因此,如果能夠將CPU上的光線跟蹤算法,映射到CPU上,加速光線跟踪算法的執行時間,将會帶來巨大的經濟效益。因此,基於CPU的光線跟蹤算法已成為國內外科研人員的研究熱點。

2.基於GPU的光線跟蹤

2.1 相關工作

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

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

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

將傳统的CPU上執行的光線跟蹤算法,映射成為一個GPU協助的,或者基於GPU的光線跟踪器有眾多方法。下面重點介紹Purcell提出的映射模型,以及在本文的实現中提出的一個基於CPU的Whitted模型的光線跟踪器。該光線跟蹤器的布局如圖2.1所示:

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

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

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

求交內核把光線的原點,方向,以及場景的描述作為輸入數據。在内核被調用數次之後,我們对於每一個像素輸出一個击中記錄。如果一條光線擊中了場景中的某個三角形,返回擊中點的3個重心坐標,以及相關的被击中的三角形。此外,還将輸出被發現的交點沿光线的距離,以及被擊中三角形的材質。這就需要使用5個浮點数值組成一個擊中記錄。紋理只能夠支持4個顏色通道( RCBA),所以,如果能把擊中記錄裁減到4個值,那麽将是非常有益的。

觀察發現,只需要3個重心坐標的兩個,因為在三角形內部,它们相加的和總是1。這就使得在一個單獨的RGBA紋理中存储交點記錄是可行的,並且它的維度同其它兩個光線紋理的維度相同。轉貼于 免費論文下载中心 http://www.hi138.com

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

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

現在根據擊中的三角形所具有的材質的類型(漫反射材質,或者鏡面反射材質),需要產生二次光線,以此來計算陰影和反射。

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

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

3)如果一條光線擊中了一個鏡面反射材质表面。就發射一條鏡面反射光線。鏡面發射光線的起始點也在擊中点,但是它的方向是在擊中點處關於入射光線和插值后的法線對稱的方向。一個真正的Whitted類型的光線跟蹤器也支持透明材質,從而能够產生折射光線。但由於主要是研究加速結構,所以在本文的實现中,沒有考慮折射光線。

4)如果阴影光線擊中了某個幾何體,這就說明在光源和击中點之間,存在某個幾何體,所以這個像素就應該是黑色(處於陰影中)。當跟蹤陰影光線的時候,不關心最近的那個擊中點,更加關心的是是否存在這樣的擊中點。因此,當有一個交點被發現,就可以停止整個求交過程,從而加速算法的處理過程。在本文的實現中,以相同的方式跟蹤陰影光线和反射光線,因此,就沒有使用到這個優化策略。

已經對每一個像素產生了正確二次光線,如果需要,就能夠執行另外一趟遍歷/求交過程,對上述的二次光線進行跟蹤。每一次調用著色程序就能夠對每一個像素返回一個顏色值和一條新的光线。著色內核也可以将前一次著色程序的輸出當作本次著色程序的輸入。這就使得能夠在跟蹤連續的光線的時候合並這些連續的鏡面反射的顏色。

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

3.加速結構的實現和比較

3.1均勻柵格

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

首先,只用使用簡單的算術運算,就能夠對於每個體素的遍歷在常量时間能被定位和存取。这就消除了對樹的遍歷的需要,以及重復的紋理查找工作,而紋理查找是相當耗時的。

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

再其次,由於對於體素的訪问是沿著光線,以距離递增的方式遍歷的,所以,一旦在一个被訪問的體素中報道发現有一個交點,就可以停止這條光線對體素的遍歷過程,从而提高整個遍歷過程的速度。

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

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

3.2 KD-tree

最近,Havran等人對基於CPU的光線跟踪算法的加速結構進行了比較,得出的結論是對於眾多不同類型的測試場景,平均而言,KD-tree是最快的。所以,有必要考察一下對於基於KD-tree的GPU光線跟蹤算法,是否也會有相似的結論。 免費論文下載中心 http://www.hi138.com

就像均勻柵格一樣,KD-tree也是一種空间細分結構。同均勻網格不同的是,KD-tree利用一個二叉樹將場景表示成一個層次结構。

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

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

當使用GPU對KD-tree進行遍歷的時候,KD-tree像均勻柵格那樣被表示成一個紋理的集合。這就意味著有一個保存樹数據的紋理,一個保存三角形列表的紋理,和一个保存實際的三角形數據的紋理。GPU的遍歷首先調用一個初始化內核,然後按照需要,多次調用合並後的遍歷和求交內核。

3.3 包圍體層次(BVH)

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

Goldsmith和Salmon提出了一個評價函數,通常被稱為表面積啟發式函數。他們通過父節點和孩子節點的表面積之比來形式化的表述這個關系,此評價函數如下所示:

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

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

在實踐中,对於包圍體應用的最廣泛的就是軸對齐包圍盒(AABB)。AABB易於實現,並且同光線的求交測試非常快。大多數有關BVH的論文在描述BVH的創建的時候,通常分别以Kay和Kajiya,或者Goldsmith和Salmon這兩种基本的想法為基礎。Kay和Kajiaya建議以自上而下遞歸的方式進行BVH的創建。

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

4.結束语

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

參考文獻

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

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

[3]昊恩華,柳有權.基於圖形處理器(GPU)的通用計算叨.計算机輔助設計與圖形學學報,2004,16(5): 601-612.转貼於 免費論文下載中心 http://www.hi138.com

[4] Philip J.Schneider,David H.Eberly著,周長發譯,計算機圖形學几何工具算法詳解[M].北京:電子工業出版社,2005.

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

免費論文下載中心 http://www.hi138.com
下载论文

論文《GPU光線跟蹤算法加速結構分析》其它版本

計算機應用論文服務

網站聲明 | 聯系我們 | 網站地圖 | 論文下載地址 | 代寫論文 | 作者搜索 | 英文版 | 手機版 CopyRight@2008 - 2017 免費論文下載中心 京ICP备17062730号