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

1、 GPU光線跟蹤算法加速結(jié)構(gòu)研究摘要：基于gpu的光線跟蹤算法是當(dāng)前圖形學(xué)研究的一個(gè)熱點(diǎn)，也是將來用于廣告、電影、游戲等娛樂產(chǎn)業(yè)的關(guān)鍵技術(shù)。本文論述了如何對(duì)基于gpu的光線跟蹤算法進(jìn)行實(shí)現(xiàn)，以及利用各種加速結(jié)構(gòu)，加速算法實(shí)現(xiàn)，提高算法執(zhí)行效率，并對(duì)各種加速結(jié)構(gòu)的效果進(jìn)行了比較研究。 關(guān)鍵詞：gpgpu 光線跟蹤 bvh kd-tree 1引言 近年來，cpu無論在運(yùn)算能力，還是在可編程性上都得到了大幅的提高，gpu已經(jīng)在需要大量運(yùn)算的密集運(yùn)算領(lǐng)域發(fā)揮了舉足輕重的作用。各種基于cpu的密集運(yùn)算被移植到gpu上，以利用gpu巨大的運(yùn)算能力，加速整個(gè)算法的運(yùn)算過程。光線跟蹤算法是生成真實(shí)感圖形的一種

2、非常重要的方法，在電影、游戲、廣告等產(chǎn)業(yè)，獲得廣泛的應(yīng)用，而光線跟蹤算法也是典型的密集運(yùn)算算法，利用原始的基于cpu的光線跟蹤渲染一幅圖片是非常耗時(shí)的操作。因此，如果能夠?qū)pu上的光線跟蹤算法，映射到cpu上，加速光線跟蹤算法的執(zhí)行時(shí)間，將會(huì)帶來巨大的經(jīng)濟(jì)效益。因此，基于cpu的光線跟蹤算法已成為國(guó)內(nèi)外科研人員的研究熱點(diǎn)。 2基于gpu的光線跟蹤 相關(guān)工作 當(dāng)前，主要由兩種方法利用cpu來加速光線跟蹤算法。第一種是carr等人提出來的，將cpu轉(zhuǎn)換為一個(gè)蠻力的執(zhí)行光線一三角形求交的計(jì)算器，而將任何的光線生成以及著色過程在cpu上完成。這就需要cpu依然執(zhí)行絕大部分的渲染工作。c arr等人指

3、出，在ati radeon 8500上，每秒最快能夠執(zhí)行1億2千萬次的光線一三角形求交。lOcALHost同時(shí)，作者也指出，由于gpu的單精度浮點(diǎn)的限制，圖片上依然存在一些不太真實(shí)的地方。 第二種方法由purcell等人提出的，改種方法將整個(gè)光線跟蹤器都移植到cpu上進(jìn)行實(shí)現(xiàn)。從光線的產(chǎn)生，加速結(jié)構(gòu)的遍歷，到最后的著色過程都在gpu上執(zhí)行。此后，有很多相同的項(xiàng)目都是基于purcell的模型上進(jìn)行的。 gpu上的光線跟蹤算法的映射方式 將傳統(tǒng)的cpu上執(zhí)行的光線跟蹤算法，映射成為一個(gè)gpu協(xié)助的，或者基于gpu的光線跟蹤器有眾多方法。下面重點(diǎn)介紹purcell提出的映射模型，以及在本文的實(shí)現(xiàn)中提

4、出的一個(gè)基于cpu的whitted模型的光線跟蹤器。該光線跟蹤器的布局如圖所示： 在purcell的論文中，它將光線一三角形求交，以及遍歷過程分離成兩個(gè)獨(dú)立的遍歷內(nèi)核和求交內(nèi)核。本文的實(shí)現(xiàn)中，也按照上述模型圖，將光線跟蹤算法分解成光線生成，光線一三角形求交，著色這三個(gè)步驟。 在對(duì)光線進(jìn)行跟蹤之前，需要生成從視點(diǎn)指向屏幕的原始光線( primary ray)。在一個(gè)gpu上，能夠使用光柵器的插值的能力，在一個(gè)單一的內(nèi)核調(diào)用中，產(chǎn)生所有的原始光線。 給定觀察矩形的四個(gè)角，以及視點(diǎn)，首先計(jì)算出這個(gè)視錐體的四條邊線。如果讓光柵器在這4條光線之間，按照512512規(guī)格，在這四條光線之間按照方向進(jìn)行插值，

5、最終就可以獲得能夠產(chǎn)生一幅512512圖片的所有原始光線的方向。同時(shí)能夠?qū)⑦@些方向存儲(chǔ)在一個(gè)紋理里，并把它作為求交內(nèi)核的輸入。所有的原始光線具有相同的起始點(diǎn)，但是仍然把它存儲(chǔ)在一個(gè)同方向紋理具有相同維度的紋理內(nèi)。因?yàn)楫?dāng)生成陰影光線或者反射光線的時(shí)候，光線的原點(diǎn)會(huì)發(fā)生改變。 求交內(nèi)核把光線的原點(diǎn)，方向，以及場(chǎng)景的描述作為輸入數(shù)據(jù)。在內(nèi)核被調(diào)用數(shù)次之后，我們對(duì)于每一個(gè)像素輸出一個(gè)擊中記錄。如果一條光線擊中了場(chǎng)景中的某個(gè)三角形，返回?fù)糁悬c(diǎn)的3個(gè)重心坐標(biāo)，以及相關(guān)的被擊中的三角形。此外，還將輸出被發(fā)現(xiàn)的交點(diǎn)沿光線的距離，以及被擊中三角形的材質(zhì)。這就需要使用5個(gè)浮點(diǎn)數(shù)值組成一個(gè)擊中記錄。紋理只能夠支持4

6、個(gè)顏色通道( rcba)，所以，如果能把擊中記錄裁減到4個(gè)值，那么將是非常有益的。 觀察發(fā)現(xiàn)，只需要3個(gè)重心坐標(biāo)的兩個(gè)，因?yàn)樵谌切蝺?nèi)部，它們相加的和總是1。這就使得在一個(gè)單獨(dú)的rgba紋理中存儲(chǔ)交點(diǎn)記錄是可行的，并且它的維度同其它兩個(gè)光線紋理的維度相同。 moller和trumbore提出了一個(gè)高效的光線一三角形求交算法，使用這個(gè)算法，并利用cpu在向量計(jì)算上的優(yōu)勢(shì)來進(jìn)行求交計(jì)算。下面列出了求交的代碼，這個(gè)代碼也展示了如何利用向量指令來提高效率。 當(dāng)所有的原始光線都已經(jīng)計(jì)算出了相交的狀態(tài)的時(shí)候，就能夠查詢著色過程所需要的表面法線和材質(zhì)的信息。每一個(gè)擊中記錄都存儲(chǔ)了一個(gè)指向材質(zhì)紋理的索引，這個(gè)

7、材質(zhì)紋理包含了三角形的法線，材質(zhì)顏色以及類型。三個(gè)頂點(diǎn)的法線根據(jù)擊中記錄的中心坐標(biāo)進(jìn)行了插值。最終的顏色能夠按(n-l)c進(jìn)行計(jì)算，此處是法線，l是光源的方向，g是三角形的顏色。 現(xiàn)在根據(jù)擊中的三角形所具有的材質(zhì)的類型，需要產(chǎn)生二次光線，以此來計(jì)算陰影和反射。 1)如果一條光線射出場(chǎng)景之外，像素就被賦予全局的背景顏色。 2)如果一條光線擊中了一個(gè)漫反射材質(zhì)表面，就發(fā)射一條陰影射線( shdow ray)。這些光線的起始點(diǎn)在擊中點(diǎn)，方向?yàn)閺膿糁悬c(diǎn)指向光源。 3)如果一條光線擊中了一個(gè)鏡面反射材質(zhì)表面。就發(fā)射一條鏡面反射光線。鏡面發(fā)射光線的起始點(diǎn)也在擊中點(diǎn)，但是它的方向是在擊中點(diǎn)處關(guān)于入射光線和插

8、值后的法線對(duì)稱的方向。一個(gè)真正的whitted類型的光線跟蹤器也支持透明材質(zhì)，從而能夠產(chǎn)生折射光線。但由于主要是研究加速結(jié)構(gòu)，所以在本文的實(shí)現(xiàn)中，沒有考慮折射光線。 4)如果陰影光線擊中了某個(gè)幾何體，這就說明在光源和擊中點(diǎn)之間，存在某個(gè)幾何體，所以這個(gè)像素就應(yīng)該是黑色。當(dāng)跟蹤陰影光線的時(shí)候，不關(guān)心最近的那個(gè)擊中點(diǎn)，更加關(guān)心的是是否存在這樣的擊中點(diǎn)。因此，當(dāng)有一個(gè)交點(diǎn)被發(fā)現(xiàn)123下一頁 ，就可以停止整個(gè)求交過程，從而加速算法的處理過程。在本文的實(shí)現(xiàn)中，以相同的方式跟蹤陰影光線和反射光線，因此，就沒有使用到這個(gè)優(yōu)化策略。 已經(jīng)對(duì)每一個(gè)像素產(chǎn)生了正確二次光線，如果需要，就能夠執(zhí)行另外一趟遍歷/求交過

9、程，對(duì)上述的二次光線進(jìn)行跟蹤。每一次調(diào)用著色程序就能夠?qū)γ恳粋€(gè)像素返回一個(gè)顏色值和一條新的光線。著色內(nèi)核也可以將前一次著色程序的輸出當(dāng)作本次著色程序的輸入。這就使得能夠在跟蹤連續(xù)的光線的時(shí)候合并這些連續(xù)的鏡面反射的顏色。 同carr等人的程序不同，本文所采用的程序不存在浮點(diǎn)精度太低的問題，因?yàn)閏eforce 7300在整個(gè)管線中支持真正的32位浮點(diǎn)操作。 3加速結(jié)構(gòu)的實(shí)現(xiàn)和比較 均勻柵格 均勻柵格是第一個(gè)在gpu上實(shí)現(xiàn)的加速結(jié)構(gòu)。purcell給出了很多選擇均勻柵格作為加速結(jié)構(gòu)的理由，但是purcell沒有詳細(xì)的說明為什么均勻網(wǎng)格對(duì)于硬件實(shí)現(xiàn)而言比其它的加速結(jié)構(gòu)要更加的簡(jiǎn)單。當(dāng)在探討了均勻柵格

10、的一些主要特性的時(shí)候，更加清晰的知道了均勻柵格為什么會(huì)成為一個(gè)好的gpu機(jī)速結(jié)構(gòu)。 首先，只用使用簡(jiǎn)單的算術(shù)運(yùn)算，就能夠?qū)τ诿總€(gè)體素的遍歷在常量時(shí)間能被定位和存取。這就消除了對(duì)樹的遍歷的需要，以及重復(fù)的紋理查找工作，而紋理查找是相當(dāng)耗時(shí)的。 其次，體素的遍歷是通過遞增算術(shù)運(yùn)算來完成的。這就消除了對(duì)堆棧的需要，使得我們能夠從光線的起始點(diǎn)開始，以距離遞增的順序訪問體素成為可能。 再其次，由于對(duì)于體素的訪問是沿著光線，以距離遞增的方式遍歷的，所以，一旦在一個(gè)被訪問的體素中報(bào)道發(fā)現(xiàn)有一個(gè)交點(diǎn)，就可以停止這條光線對(duì)體素的遍歷過程，從而提高整個(gè)遍歷過程的速度。 最后，用于遍歷的代碼非常適合用向量編寫，而向

11、量形式的編碼風(fēng)格又非常適合gpu的指令集。 然而，均勻柵格的缺點(diǎn)就是由于它是空間細(xì)分結(jié)構(gòu)的一種特殊情況，多個(gè)體素可能包含相同三角形的多個(gè)引用。由于無法使用mailbox技術(shù)，這就意味著需要對(duì)于相同的光線和三角形之間進(jìn)行不止一次的相交測(cè)試。 kd-tree 最近，havran等人對(duì)基于cpu的光線跟蹤算法的加速結(jié)構(gòu)進(jìn)行了比較，得出的結(jié)論是對(duì)于眾多不同類型的測(cè)試場(chǎng)景，平均而言，kd-tree是最快的。所以，有必要考察一下對(duì)于基于kd-tree的gpu光線跟蹤算法，是否也會(huì)有相似的結(jié)論。 就像均勻柵格一樣，kd-tree也是一種空間細(xì)分結(jié)構(gòu)。同均勻網(wǎng)格不同的是，kd-tree利用一個(gè)二叉樹將場(chǎng)景表示

12、成一個(gè)層次結(jié)構(gòu)。 在二叉樹中，我們將內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)區(qū)分開。葉子節(jié)點(diǎn)用來表示體素和與之相關(guān)的保存在該體素內(nèi)的三角形的引用。一個(gè)內(nèi)部節(jié)點(diǎn)用來表示空間區(qū)域的某個(gè)部分。所以，內(nèi)部節(jié)點(diǎn)包含一個(gè)分裂面的兩個(gè)子樹的引用，而葉子節(jié)點(diǎn)只包含一個(gè)三角形列表。 kd-tree的創(chuàng)建過程從上而下，根據(jù)一個(gè)評(píng)價(jià)函數(shù)，通過放置一個(gè)分離平面，遞歸的將場(chǎng)景分離成兩個(gè)體素。我們能夠以遞歸的方式遍歷kd-tree，但是由于gpu沒有堆棧結(jié)構(gòu)，所以無法應(yīng)用遞歸的策略。取而代之的是，我們能夠通過記住我們沿著光線前進(jìn)了多遠(yuǎn)來向上或者向下遍歷樹。這種策略消除了需要堆棧的限制，使得用cpu來完成對(duì)kd-tree結(jié)構(gòu)的遍歷成為可能。 當(dāng)

13、使用gpu對(duì)kd-tree進(jìn)行遍歷的時(shí)候，kd-tree像均勻柵格那樣被表示成一個(gè)紋理的集合。這就意味著有一個(gè)保存樹數(shù)據(jù)的紋理，一個(gè)保存三角形列表的紋理，和一個(gè)保存實(shí)際的三角形數(shù)據(jù)的紋理。gpu的遍歷首先調(diào)用一個(gè)初始化內(nèi)核，然后按照需要，多次調(diào)用合并后的遍歷和求交內(nèi)核。 包圍體層次(bvh) 給定一些隨機(jī)的光線，通過計(jì)算遍歷包圍體層次的平均花費(fèi)，就可以測(cè)量出該包圍體層次的質(zhì)量。迄今為止，還沒有構(gòu)建最優(yōu)的包圍體層次的算法，也就是說，如何準(zhǔn)確的測(cè)量一個(gè)包圍體層次的平均遍歷時(shí)間還不是很明顯。 goldsmith和salmon提出了一個(gè)評(píng)價(jià)函數(shù)，通常被稱為表面積啟發(fā)式函數(shù)。他們通過父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的表

14、面積之比來形式化的表述這個(gè)關(guān)系，此評(píng)價(jià)函數(shù)如下所示： 此處，hit(n)是光線擊中節(jié)點(diǎn)n的情況，sn是節(jié)點(diǎn)n的表面積，c和p分別表示父節(jié)點(diǎn)和孩子節(jié)點(diǎn)。 這個(gè)評(píng)價(jià)函數(shù)給出了，當(dāng)用一條隨機(jī)的光線同層次結(jié)構(gòu)求交的時(shí)候，成本上的估計(jì)。由于沒有最優(yōu)的方法去有效的構(gòu)造一個(gè)最優(yōu)的bvh，提出了不同的構(gòu)造技巧。下面，將列出比較通用的方法。 在實(shí)踐中，對(duì)于包圍體應(yīng)用的最廣泛的就是軸對(duì)齊包圍盒(aabb)。aabb易于實(shí)現(xiàn)，并且同光線的求交測(cè)試非常快。大多數(shù)有關(guān)bvh的論文在描述bvh的創(chuàng)建的時(shí)候，通常分別以kay和kajiya，或者goldsmith和salmon這兩種基本的想法為基礎(chǔ)。kay和kajiaya建

15、議以自上而下遞歸的方式進(jìn)行bvh的創(chuàng)建。 goldsmith和salmon提出了一個(gè)更加復(fù)雜的自底向上的構(gòu)造方式。goldsmith和salmon指出，bvh的質(zhì)量同作為輸入傳人的三角形的順序有關(guān)。因此，他們建議在構(gòu)造bvh之前，隨機(jī)打亂三角形的順序。下述算法就是利用kay/kajiya的思想創(chuàng)建某個(gè)場(chǎng)景的包圍體層次的方法： 4結(jié)束語 本文成功的在gpu上實(shí)現(xiàn)了用于光線跟蹤算法中的各種加速結(jié)構(gòu)，并對(duì)這些加速結(jié)構(gòu)在gpu上的加速效果進(jìn)行了比較。均勻柵格作為第一個(gè)在cpu上實(shí)現(xiàn)的光線跟蹤器的加速結(jié)構(gòu)，也被證明是最慢的，除非是只包含一個(gè)單獨(dú)的物體的場(chǎng)景的情況。均勻柵格不適合幾何體的密度非常高的場(chǎng)景。

16、另外，對(duì)于均勻柵格的cpu上的遍歷表示，也需要大量的數(shù)據(jù)。foley和sugerman認(rèn)為，對(duì)于大多數(shù)場(chǎng)景，kd-tree的效率要比均勻柵格高。但是，在kd-tree的遍歷過程中，無論是重置階段還是回退階段，片元程序都非常的復(fù)雜，但這種復(fù)雜性也使得其能夠在場(chǎng)景的幾何體的密度改變的時(shí)候做出適當(dāng)?shù)恼{(diào)整。本文實(shí)現(xiàn)的bvh被證明在加速效果上要超過均勻柵格和kd-tree，在現(xiàn)階段，bvh是在gpu上實(shí)現(xiàn)的最快的加速結(jié)構(gòu)。并且在gpu上實(shí)現(xiàn)bvh加速結(jié)構(gòu)要比實(shí)現(xiàn)其他加速結(jié)構(gòu)更加的簡(jiǎn)單。 參考文獻(xiàn)： 1randima femado編，姚勇，王小琴譯gpu精粹一實(shí)時(shí)圖形編程的技術(shù)，技巧和技藝m北京：人民郵電出版社，2006. 2 matt pharr編著，龔敏敏譯.gp