GPU光線跟蹤算法加速結(jié)構(gòu)研究_第1頁
GPU光線跟蹤算法加速結(jié)構(gòu)研究_第2頁
GPU光線跟蹤算法加速結(jié)構(gòu)研究_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

GPU光線跟蹤算法加速結(jié)構(gòu)研究GPU光線跟蹤算法加速結(jié)構(gòu)討論

GPU光線跟蹤算法加速結(jié)構(gòu)討論

,就可以停止整個求交過程,從而加速算法的處理過程。在本文的實(shí)現(xiàn)中,以相同的方式跟蹤陰影光線和反射光線,因此,就沒有使用到這個優(yōu)化策略。

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

同carr等人的程序不同,本文所采納的程序不存在浮點(diǎn)精度太低的問題,由于ceforce7300在整個管線中支持真正的32位浮點(diǎn)操作。

3.加速結(jié)構(gòu)的實(shí)現(xiàn)和比較

3.1勻稱柵格

勻稱柵格是第一個在gpu上實(shí)現(xiàn)的加速結(jié)構(gòu)。purcell給出了許多選擇勻稱柵格作為加速結(jié)構(gòu)的理由,但是purcell沒有具體的說明為什么勻稱網(wǎng)格對于硬件實(shí)現(xiàn)而言比其它的加速結(jié)構(gòu)要更加的簡潔。當(dāng)在探討了勻稱柵格的一些主要特性的時候,更加清楚的知道了勻稱柵格為什么會成為一個好的gpu機(jī)速結(jié)構(gòu)。

首先,只用使用簡潔的算術(shù)運(yùn)算,就能夠?qū)τ诿總€體素的遍歷在常量時間能被定位和存取。這就消退了對樹的遍歷的需要,以及重復(fù)的紋理查找工作,而紋理查找是相當(dāng)耗時的。

其次,體素的遍歷是通過遞增算術(shù)運(yùn)算來完成的。這就消退了對堆棧的需要,使得我們能夠從光線的起始點(diǎn)開頭,以距離遞增的挨次訪問體素成為可能。

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

最終,用于遍歷的代碼特別適合用向量編寫,而向量形式的編碼風(fēng)格又特別適合gpu的指令集。

然而,勻稱柵格的缺點(diǎn)就是由于它是空間細(xì)分結(jié)構(gòu)的一種特別狀況,多個體素可能包含相同三角形的多個引用。由于無法使用mailbox技術(shù),這就意味著需要對于相同的光線和三角形之間進(jìn)行不止一次的相交測試。

3.2kd-tree

最近,havran等人對基于cpu的光線跟蹤算法的加速結(jié)構(gòu)進(jìn)行了比較,得出的結(jié)論是對于眾多不同類型的測試場景,平均而言,kd-tree是最快的。所以,有必要考察一下對于基于kd-tree的gpu光線跟蹤算法,是否也會有相像的結(jié)論。

就像勻稱柵格一樣,kd-tree也是一種空間細(xì)分結(jié)構(gòu)。同勻稱網(wǎng)格不同的是,kd-tree利用一個二叉樹將場景表示成一個層次結(jié)構(gòu)。

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

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

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

3.3包圍體層次(bvh)

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

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

此處,hit(n)是光線擊中節(jié)點(diǎn)n的狀況,sn是節(jié)點(diǎn)n的表面積,c和p分別表示父節(jié)點(diǎn)和孩子節(jié)點(diǎn)。

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

在實(shí)踐中,對于包圍體應(yīng)用的最廣泛的就是軸對齊包圍盒(aabb)。aabb易于實(shí)現(xiàn),并且同光線的求交測試特別快。大多數(shù)有關(guān)bvh的論文在描述bvh的創(chuàng)建的時候,通常分別以kay和kajiya,或者goldsmith和salmon這兩種基本的想法為基礎(chǔ)。kay和kajiaya建議以自上而下遞歸的方式進(jìn)行bvh的創(chuàng)建。

goldsmith和salmon提出了一個更加簡單的自底向上的構(gòu)造方式。goldsmith和salmon指出,bvh的質(zhì)量同作為輸入傳人的三角形的挨次有關(guān)。因此,他們建議在構(gòu)造bvh之前,隨機(jī)打亂三角形的挨次。下述算法就是利用kay/kajiya的思想創(chuàng)建某個場景的包圍體層次的方法:

4.結(jié)束語

本文勝利的在gpu上實(shí)現(xiàn)了用于光線跟蹤算法中的各種加速結(jié)構(gòu),并對這些加速結(jié)構(gòu)在gpu上的加速效果進(jìn)行了比較。勻稱柵格作為第一個在cpu上實(shí)現(xiàn)的光線跟蹤器的加速結(jié)構(gòu),也被證明是最慢的,除非是只包含一個單獨(dú)的物體的場景的狀況。勻稱柵格不適合幾何體的密度特別高的場景。另外,對于勻稱柵格的cpu上的遍歷表示,也需要大量的數(shù)據(jù)。foley和sugerman認(rèn)為,對于大多數(shù)場景,kd-tree的效率要比勻稱柵格高。但是,在kd-tree的遍歷過程中,無論是重置階段還

GPU光線跟蹤算法加速結(jié)構(gòu)討論

是回退階段,片元程序都特別的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論