光線跟蹤與碰撞檢測(cè)算法的并行化研究.pdf

1、隨著硬件的快速發(fā)展，使得多核計(jì)算成為了可能，為解決海量數(shù)據(jù)的計(jì)算提供了一種有效的方法。本文針對(duì)游戲和計(jì)算機(jī)仿真問題當(dāng)中的真實(shí)感圖形的顯示實(shí)時(shí)性要求和渲染效果，對(duì)計(jì)算機(jī)圖形學(xué)中的相關(guān)算法進(jìn)行了并行化研究。研究的主要內(nèi)容有：
　　 光線跟蹤算法的并行化研究。光線跟蹤計(jì)算隸屬于計(jì)算機(jī)圖形學(xué)范疇并通過投射光線生成圖像。在光線跟蹤計(jì)算模型中，場(chǎng)景由相機(jī)、像素窗口、光線以及對(duì)象(也就是物體)構(gòu)成，光線穿越像素并與相關(guān)對(duì)象執(zhí)行相交測(cè)試。若光線

2、與某一對(duì)象發(fā)生碰撞，則光線跟蹤器將沿著當(dāng)前光線逆向方向計(jì)算反射光線的數(shù)量，以確定像素的顏色值，光線跟蹤器將通過使用足夠的像素，生成場(chǎng)景對(duì)象的渲染圖像。如果場(chǎng)景對(duì)象具有反射特性，則光線可反射多次并與其他對(duì)象發(fā)生碰撞。經(jīng)典的光線跟蹤算法需要計(jì)算每一條與場(chǎng)景中對(duì)象相交的光線，并且要根據(jù)對(duì)象的性質(zhì)進(jìn)行光色反射、折射等計(jì)算，計(jì)算量非常龐大，因此很難滿足真實(shí)感圖形顯示的實(shí)時(shí)性要求。為了提高顯示的實(shí)時(shí)性，一般通過提高光線跟蹤算法的效率及采用并行處理技

3、術(shù)來實(shí)現(xiàn)。經(jīng)典的光線跟蹤算法中各個(gè)像素的渲染與其它的像素?zé)o關(guān)，可以將整個(gè)需要渲染的圖像分為幾個(gè)部分，實(shí)現(xiàn)圖像的并行化渲染，以提高圖像的生成速度。本文采用兩種方法進(jìn)行實(shí)現(xiàn)，一是采用Intel公司的TBB進(jìn)行并行處理：TBB能根據(jù)當(dāng)前使用的CPU自動(dòng)選擇線程的個(gè)數(shù)，并能對(duì)標(biāo)記為并行的代碼段進(jìn)行自動(dòng)的任務(wù)分配，實(shí)現(xiàn)動(dòng)態(tài)負(fù)載平衡。二是采用Nvidia的CUDA對(duì)光線跟蹤算法進(jìn)行并行化：首先生成動(dòng)態(tài)加速結(jié)構(gòu)KD-Free，并將加速結(jié)構(gòu)數(shù)據(jù)復(fù)制到G

4、PU的共享內(nèi)存之中，隨后進(jìn)行光線跟蹤，對(duì)KD-Tree進(jìn)行遍歷。由于GPU能夠生成大量的線程，因此可將圖片進(jìn)行細(xì)粒度分割，每個(gè)線程管理為數(shù)不多的像素，通過并行遍歷KD-Tree的方式實(shí)行并行優(yōu)化。
　　 基于GPU的粒子系統(tǒng)中的碰撞檢測(cè)的并行化。在粒子系統(tǒng)中，景象被定義為由成千上萬個(gè)不規(guī)則的、隨機(jī)分布的粒子所組成，它采用一種統(tǒng)一的模式來生成諸如火、爆炸、煙、水流、火花、落葉、云、霧、雪、塵、流行尾跡或發(fā)光軌跡這樣的抽象視覺效果等

5、。為了保證在計(jì)算機(jī)上具有現(xiàn)實(shí)世界中的的真實(shí)物理感，我們需要在粒子系統(tǒng)中加入碰撞檢測(cè)。碰撞檢測(cè)是檢測(cè)場(chǎng)景中兩個(gè)(或多個(gè))物體是否相交，特別的，碰撞檢測(cè)將確定兩個(gè)(或多個(gè))物體是否、何時(shí)以及在何處形成碰撞。碰撞檢測(cè)廣泛的應(yīng)用于計(jì)算機(jī)游戲、物理仿真(如計(jì)算機(jī)動(dòng)畫)、機(jī)器人技術(shù)、虛擬樣機(jī)技術(shù)以及工程仿真之中。一些基于計(jì)算機(jī)或其他平臺(tái)的動(dòng)作類游戲所涉及的模擬數(shù)據(jù)量要求以每秒30幀～60幀的幀速率進(jìn)行計(jì)算，碰撞檢測(cè)系統(tǒng)將占用游戲一幀中的大量時(shí)間，為