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

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

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

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

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

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