光線跟蹤算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)光線跟蹤算法的研究與進展劉進摘要：光線跟蹤算法是圖形繪制技術(shù)中的經(jīng)典算法，但是該算法光線與物體的求交量龐大，嚴重制約著應(yīng)用。本文從經(jīng)典的光線跟蹤算法出發(fā)，研究了目前光線跟蹤算法的國內(nèi)外研究狀況，具體從改進的光線跟蹤算法和光線跟蹤算法的加速技術(shù)，并進行了對比和分析。最后對近幾年的光線跟蹤方法發(fā)展進行了總結(jié)，對未來研究熱點及應(yīng)用前景進行了展望。關(guān)鍵詞：可視化；光線跟蹤算法；并行繪制；GPUResearch Status and Prospect for ray tracin

2、g algorithmsAbstract: As an classic algorithms of volume rendering in computer graphics, ray tracing algorithms is hindered by the huge computation cost in ray and volume. This paper summarizes the research status in ray tracing technology from the two main solutions: different extended ray tracing

3、algorithms and the acceleration techniques in ray tracing algorithms. Comparison and analysis the different performance. Both current research focus and the future research prospect are also discussed in recent years.Key words: visualization; ray tracing algorithms; parallel rendering; GPU引言隨著科學(xué)技術(shù)和計

4、算機高速發(fā)展，人類已經(jīng)進入到一個科技支撐的時代，在我們的生活中到處充滿了高科技產(chǎn)品和技術(shù)，給我們的生活帶來了改變和方便，其中計算機圖形學(xué)的應(yīng)用已經(jīng)滲透到了各個工程技術(shù)領(lǐng)域，其已經(jīng)成為計算機科學(xué)的重要學(xué)科之一，具有相當?shù)闹匾院蜔o可替代的作用。計算機圖形學(xué)自誕生以來得到了飛速發(fā)展，其通過計算機的輸入設(shè)備、顯示設(shè)備及繪制設(shè)備等對圖形的表示、繪制、存儲、顯示等相關(guān)理論知識、算法技術(shù)進行研究的一門學(xué)科。真實感圖形繪制是計算機圖形學(xué)的主要研究內(nèi)容之一，在虛擬現(xiàn)實、文物保護、影視游戲、三維動畫、醫(yī)學(xué)研究、建筑設(shè)計和系統(tǒng)仿真等領(lǐng)域中得到廣泛應(yīng)用，它追求對場景的逼真渲染1。其中逼真的圖形繪制技術(shù)是最為活躍的研

5、究領(lǐng)域之一。光線跟蹤算法是真實感圖形繪制技術(shù)的主要算法之一，其原理簡單，能夠有效生成具有比較真實視觀效果的各種各樣的場景。該算法可通過一些光照明模型模擬在光源或環(huán)境光照射下物體表面發(fā)生的多種光照效果，例如漫反射、高光、鏡面映像、場景消隱及陰影等。在計算機中對現(xiàn)實場景或是虛擬場景進行顯示，除了要構(gòu)建場景圖形外，還要將場景中的各種光照效果模擬出來，這樣生成的場景才能更逼真，光線跟蹤算法就是既在幾何上相似，也能模擬出大部分的光照效果的生成真實感圖形的方法。光線跟蹤算法是逆著真實光線的投射方向進行反向跟蹤的，從視點向場景發(fā)射光線，光線與場景中的物體相交，計算光分量，因為視點向場景的光線較多，因而該算法

6、光線與物體的求交量較大，但是因為其對場景的模擬的逼真，及其可以模擬漫反射、鏡面反射、反射折射以及陰影等光照效果1-2。進入90年代，隨著計算機技術(shù)的發(fā)展，光線跟蹤技術(shù)廣泛應(yīng)用于三維特技電影、電視廣告、電子游戲的制作中，其應(yīng)用領(lǐng)域也正在向如物理、化學(xué)、生物等其他學(xué)科領(lǐng)域滲透，其應(yīng)用的范圍正不斷擴大，很多基于光線跟蹤算法的新理論也應(yīng)運而生，物理學(xué)中的相對論、地理中地層的繪圖等與光線跟蹤算法相結(jié)合的研究已經(jīng)實現(xiàn)，極大的推動其學(xué)科的發(fā)展。可以說它已經(jīng)與我們的生活息息相關(guān)了，因此對光線跟蹤進行研究具有很現(xiàn)實的重要意義1-3。1.光線跟蹤算法原理對光線跟蹤算法研究最早可以追索到 1968 年，Appel

7、等在對消除隱藏面的研究時運用的光線投射算法，在原理上第一次描述了光線跟蹤算法。1979年，Kay與Greenberg對光的折射進行了研究，直到1980年，Whitted綜合考慮了多種光照效果，模擬出了漫反射、鏡面反射、高光、反射折射以及陰影等光照效果，提出了第一個整體的光照明模型Whitted 模型4。光線跟蹤思路：從視點出發(fā)，通過圖像平面上每個像素中心向場景發(fā)出一條光線，光線的起點為視點，方向為像素中心和視點連線單位向量。光線與離視點最近的場景物體表面交點有三種可能：1.當前交點所在的物體表面為理想漫射面，跟蹤結(jié)束。2.當前交點所在的物體表面為理想鏡面，光線沿其鏡面發(fā)射方向繼續(xù)跟蹤。3.當前

8、交點所在的物體表面為規(guī)則透射面，光線沿其規(guī)則透射方向繼續(xù)跟蹤。圖1 三個半透明玻璃球場景跟蹤圖如圖1中，場景中有三個半透明玻璃球，視點發(fā)出光線與場景最近交點為P1，使用任意局部光照模型可以計算出P1點處的局部光亮度Ilocal，為了計算周圍環(huán)境在P1點處產(chǎn)生的鏡面發(fā)射光和規(guī)則折射光，光線1在P1點處衍生出兩支光線：反射光2和折射光3。P1處的光照由三部分組成：Ilocal + ks * I2 + kt * I3 (1)其中：I3 為折射光線3的顏色，Kt為折射率，I2為反射光線2的顏色，Ks為反射率，I3和 I2的計算需要遞歸。我們知道光源向其四周發(fā)射出數(shù)不清的光線，從光源對光線進行跟中是永遠

9、也跟蹤不完的。而光源發(fā)出的光線進入人眼的只有少部分直接或是通過場景中的物體表面之間的折射和反射后間接地射入觀察者眼中。所以，標準的光線跟蹤算法是逆著射入觀察者眼中的光線進行跟蹤的方法來完成整個跟蹤過程的。在光線跟蹤的過程中選定視點，將一個與視點位置相當?shù)钠矫婢匦螀^(qū)域當做顯示屏幕，將顯示屏幕均勻網(wǎng)格劃分，每一個網(wǎng)格表示顯示屏幕的一個像素，從視點向像素網(wǎng)格中心引射線作為跟蹤光線進行跟蹤，跟蹤該光線得到的光亮度就是顯示屏幕對應(yīng)的像素的光亮度，所有像素點組成場景圖形5。光線跟蹤的流行來源于它比其它渲染方法如掃描線渲染或者光線投射更加能夠現(xiàn)實地模擬光線，象反射和陰影這樣一些對于其它的算法來說都很難實現(xiàn)的

10、效果，卻是光線跟蹤算法的一種自然結(jié)果。光線跟蹤易于實現(xiàn)并且視覺效果很好，所以它通常是圖形編程中首次嘗試的領(lǐng)域。光線跟蹤的一個最大的缺點就是性能，掃描線算法以及其它算法利用了數(shù)據(jù)的一致性從而在像素之間共享計算，但是光線跟蹤通常是將每條光線當作獨立的光線，每次都要重新計算。但是，這種獨立的做法也有一些其它的優(yōu)點，例如可以使用更多的光線以抗混疊現(xiàn)象，并且在需要的時候可以提高圖像質(zhì)量。盡管它正確地處理了相互反射的現(xiàn)象以及折射等光學(xué)效果，但是傳統(tǒng)的光線跟蹤并不一定是真實效果圖像，只有在非常近似或者完全實現(xiàn)渲染方程的時候才能實現(xiàn)真正的真實效果圖像。由于渲染方程描述了每個光束的物理效果，所以實現(xiàn)渲染方程可以

11、得到真正的真實效果，但是，考慮到所需要的計算資源，這通常是無法實現(xiàn)的。于是，所有可以實現(xiàn)的渲染模型都必須是渲染方程的近似，而光線跟蹤就不一定是最為可行的方法。包括光子映射在內(nèi)的一些方法，都是依據(jù)光線跟蹤實現(xiàn)一部分算法，但是可以得到更好的效果5-6。2光線跟蹤算法及擴展算法光線跟蹤算法通過模擬光的傳播方式，即光從光源出發(fā)經(jīng)過若干次反射或折射到達攝像機的過程來實現(xiàn)全局光照效果。其思想起源于光線投射算法5。目前，國內(nèi)外對光線跟蹤算法的研究大部分處于理論研究的水平，集中在對光線跟蹤算法的加速，而對于光線跟蹤算法在生產(chǎn)生活和科學(xué)研究中的應(yīng)用還是較少的，還處于起步階段。針對標準的光線跟蹤算法的不足，研究者

12、提出了很多基于標準光線跟蹤算法的改進算法。Cook等7提出分布式的光線跟蹤算法，根據(jù)分布函數(shù)進行采樣而產(chǎn)生一定方向分布的光線，并在場景中進行跟蹤而產(chǎn)生運動模糊、景深、半影和模糊反射等光照效果。Kajiya等8提出基于分布式光線跟蹤的層次采樣算法，它適應(yīng)具有廣泛多樣性的基于蒙特卡洛方法的光線跟蹤。Mitchell9將圖像的非均勻采樣方法應(yīng)用到高維的分布式的光線跟蹤算法中。Walter等10通過對光源進行聚類生成相應(yīng)的樹狀結(jié)構(gòu)，對多種光源進行光線跟蹤，產(chǎn)生豐富的視覺效果。Hachisuka等11提出光線跟蹤的多維自適應(yīng)采樣與重建技術(shù)，通過多維函數(shù)的綜合進行分布式的繪制效果。在具有復(fù)雜的漫反射和鏡面

13、反射成分表面的場景中，Ward等12提出一個計算全局光照效果的有效方法，即在繪制階段用蒙特卡洛方法計算間接光照并將其保存起來，提高計算效率。Lafortune等13提出雙向的路徑跟蹤算法，即先從人眼與光源兩個方向發(fā)射光線并在場景中 進行分布式跟蹤，然后進行光照計算，達到增強室內(nèi)間接光照的繪制效果的目的。 Lafortune等14描述了種的全局反射分布函數(shù)的概念，通過簡化光照模型，對射能量和聚集能量進行卡洛繪制方法，提高成像效果。Veach等15對優(yōu)化的光線方向進行采樣而計算光照，在增加少量的計算成本下提高成像效果。Veach等16提一種新的蒙特卡洛光線跟蹤算法，根據(jù)光線跟蹤的路徑對場景中明亮的

14、區(qū)域進行密集采樣，對多維采樣空間進行自適應(yīng)采樣。Mller等17提出高效的并且所需內(nèi)存空間最小的光線與三角形的求交算法；Kajiya 18和Toth19分別提出了光線與參數(shù)表面的求交算法；Hanrahan 20提出光線與代數(shù)曲面的求交算法；Hart等21提出光線與確定性的不規(guī)則碎片形表面的求 交算法；Knoll等22提出高效的光線與代數(shù)隱式曲面的求交算法；Heckbert等23提出光柱和網(wǎng)格模型的求交算法；Amanatides 24提出光錐和三維模型的求交算法。Reshetov25提出以層次性的光束作為光線集合的代理，實現(xiàn) 多級的光線跟蹤算法，能極大減少計算量并且能嚴格保證了方案的幾何正確性。

15、Moon等26提出光線跟蹤的光線重新排序的緩存算法，能有效地匹配光線跟蹤中各級緩存的數(shù)據(jù)，極大地提高了光線跟蹤效率，特別就無法全部載入內(nèi)存的大規(guī)模的三維模型而言。Mora27提出基于分而治之策略的光線跟蹤算法，即在空間細分時直接計算光線與場景的交點，無需存儲相關(guān)的數(shù)據(jù)，大大提高動態(tài)場景的繪制效率。Hou等28提出高效的基于微三角形的光線跟蹤的重用算法。光線跟蹤算法簡潔靈活且修改移植方便，繪制結(jié)果真實感程度高，繪制速度慢一直是一個嚴峻的問題。對此人們提出了許多改進的算法來加快繪制速度，但由于體數(shù)據(jù)龐大，單純的算法改進越來越難以滿足現(xiàn)在的需求，隨著圖形處理器的迅速發(fā)展，因此人們開始將目光轉(zhuǎn)向圖形硬

16、件，希望借助硬件來實現(xiàn)光線跟蹤體繪制，提高實際應(yīng)用價值。3基于加速技術(shù)的光線跟蹤法光線跟蹤需要完成大量的光線與場景的求交測試運算，所以求交計算構(gòu)成了光線跟蹤算法的瓶頸，因此，要提高光線跟蹤的效率就必須提高光線與場景的求交測試效率。近幾年，快速發(fā)展的圖形處理器GPU強大的并行處理能力和高精度的浮點運算能力使得越來越多的應(yīng)用研究開始利用GPU來完成29。目前基于GPU的光線跟蹤、交互式體繪制技術(shù)是國內(nèi)外研究熱點。Purcell30首先提出完全基于GPU的光線跟蹤算法，成為一些基于GPU的光線跟蹤渲染器的基礎(chǔ)。Cullip等首先將體數(shù)據(jù)沿投影軸進行切片依次裝入GPU紋理內(nèi)存，在體數(shù)據(jù)內(nèi)定義代理幾何體

17、元進行重采樣、顏色合成等操作。Meiner31采取壓縮紋理的方式以提高速度，但影響繪制結(jié)果準確度。Kruger32在GPU上進行光線投射繪制時，將與光線相交的體元從紋理表中取出，計算并更新其透明度和顏色值，利用片段著色沿光線方向采用步進法完成采樣進行最終繪制。Chen33使用視點相關(guān)的層次采樣將面向多邊形繪制的圖形引擎轉(zhuǎn)化為體光線投射算法引擎，提供了基于GPU的一種新的體光線投射繪制方法。Singh等34在GPU上實現(xiàn)了實時的光線與代數(shù)隱式曲面的求交算法。Zhou等35通過在圖形硬件上實現(xiàn)光線跟蹤的加速結(jié)構(gòu) k-d樹的實時構(gòu)造，以現(xiàn)對動態(tài)場景進行實時地光線跟蹤。Woop36研制的可編程光線處理

18、芯片RPU(ray processing unit)可用來實時光線跟蹤動態(tài)繪制復(fù)雜的幾何場景，達到了理想的交互繪制速度。在加速光線跟蹤體繪制技術(shù)中，另一種有效地方法是采用并行技術(shù)，利用多個處理單元，將整個繪制任務(wù)合理地分成若干個子任務(wù)提供給若干個繪制單元分別進行繪制，最后將每個繪制單元得到的結(jié)果進行拼接或是合成得到最終的繪制結(jié)果，以達到負載均衡和加速繪制的目的。Pfister等37給出的Cube4系統(tǒng)是一個比較成功并行體系結(jié)構(gòu)的設(shè)計，它能在30幀/秒速率下實現(xiàn) 512 級大小數(shù)據(jù)場的實時繪制, Knitel等38提出將體數(shù)據(jù)內(nèi)存組織成 8個可同時訪問的內(nèi)存模塊，以支持三線性插值計算中對8個相鄰

19、體素的同時存取。2010年等人在文獻39采用的就是層次包圍體加速結(jié)構(gòu)它將標準的光線跟蹤算法分解為一些可以數(shù)據(jù)并行的多個階段，采用的是廣度優(yōu)先遍法將這些并行階段能有效地映射到GPU的并行結(jié)構(gòu)上。4總結(jié)和討論光線跟蹤算法是計算機圖形學(xué)中生成真實感圖形的核心算法之一，它的研究和應(yīng)用一直是計算機圖形學(xué)研究的熱點。本文著重論述了國內(nèi)外體光線跟蹤算法、加速的光線跟蹤繪制技術(shù)等，并討論了各自特點及其相互聯(lián)系。目前，基于硬件加速的光線跟蹤繪制技術(shù)應(yīng)用越來越廣泛，但是如何構(gòu)造有效的數(shù)據(jù)結(jié)構(gòu)以及高效的遍歷算法一直是研究的重點，使這些數(shù)據(jù)結(jié)構(gòu)和算法能夠在硬件上達到優(yōu)化配置，如何充分發(fā)揮圖形硬件的功能、實時生成真實感

20、強的圖像將是今后的重點研究方向。隨著強大的可編程性GPU高端圖形卡的和并行可視化技術(shù)的不斷發(fā)展，具有高度真實感的實時可視化技術(shù)將會應(yīng)用得越來越廣泛。參考文獻1 張少帥. 真實感圖形中光線跟蹤算法及其加速技術(shù)的研究D. 西安電子科技大學(xué), 2008.2 裴雪飛. 光線跟蹤體繪制算法的研究D. 燕山大學(xué), 2007.3 周鵬. 基于光線跟蹤的真實感全局光照問題研究D. 山東大學(xué), 2012.4 Whitted T. A scan line algorithm for computer display of curved surfacesJ. ACM SIGGRAPH Computer Graphi

21、cs, 1978, 12(SI): 8-13.5 彭群生、鮑虎軍、金小鋼編著. 計算機真實感圖形的算法基礎(chǔ)M. 北京：科學(xué)出版社，1999，66 蔡勛, 曾亮, 劉光國. 光線跟蹤方法在體繪制中的應(yīng)用與發(fā)展J. 計算機工程與設(shè)計, 2009 (21): 4956-4959.7 Robert Cook, Thomas Porter, and Loren Carpenter Distributed Ray Tracing. Computer Graphics (Proceeding of SIGGRAPH 84), 18(3):137-144, 1984.8Kajiya J T. The rend

22、ering equationC/ACM Siggraph Computer Graphics. ACM, 1986, 20(4): 143-150.9Mitchell D P. Spectrally optimal sampling for distribution ray tracingJ. ACM SIGGRAPH Computer Graphics, 1991, 25(4): 157-164.10Walter B, Drettakis G, Parker S. Interactive rendering using the render cacheM/Rendering techniqu

23、es 99. Springer Vienna, 1999: 19-30.11 Hachisuka T, Jarosz W, Weistroffer R P, et al. Multidimensional adaptive sampling and reconstruction for ray tracingC/ACM Transactions on Graphics (TOG). ACM, 2008, 27(3): 33.12 Ward G J, Rubinstein F M, Clear R D. A ray tracing solution for diffuse interreflec

24、tionJ. ACM SIGGRAPH Computer Graphics, 1988, 22(4): 85-92.13 Lafortune E P, Willems Y D. Bi-directional path tracingC/Proceedings of CompuGraphics. 1993, 93: 145-153.14 Lafortune E P, Willems Y D. A 5D tree to reduce the variance of Monte Carlo ray tracingM/Rendering Techniques 95. Springer Vienna,

25、1995: 11-20.15 Veach E, Guibas L J. Optimally combining sampling techniques for monte carlo rendering C. Computer Graphics Proceedings, Annual Conference Series, 1995: 419428.16 Veach E, Guibas L J. Metropolis light transport C. Computer Graphics Proceedings, SIGGRAPH 97, 1997: 65-76.17 Mller T, Tru

26、mbore B. Fast, minimum storage ray-triangle intersection J. Journal of Graphics Tools, 1997, 2(1): 21-28.18 Kajiya J T. Ray tracing parametric patches J. Computer Graphics, 1982, 16(3): 245-254. 19 Toth D L. On ray tracing parametric surfaces J. Computer Graphics, 1985, 19(3): 171-179.20 Hanrahan P.

27、 Ray tracing algebraic surfaces J. Computer Graphics, 1983, 17(3): 83-90.21 Hart J C, Sandin D J, Kauffman L H. Ray tracing deterministic 3-D fractals J. Computer Graphics, 1989, 23(3): 289-296.22 Knoll A. Ray tracing implicit surfaces for interactive visualization. PhD Thesis, University of Utah, M

28、ay 2009.23 Heckbert P S, Hanrahan P. Beam tracing polygonal objects J. Computer Graphics, 1984, 18(3): 119-127.24 Amanatides J. Ray tracing with cones J. Computer Graphics, 1984, 18(3): 129-135.25 Reshetov A, Soupikov A, Hurley J. Multi-level ray tracing algorithm J. ACM Transactions on Graphics, 20

29、05, 24(3): 1176-1185.26 Moon B, Byun Y, Kim T-J, Claudio P, Kim H-S, Ban Y-J, Nam S W, Yoon S-Eui. Cache-oblivious ray reordering J. ACM Transactions on Graphics, 2010, 29(3): 1-10.27Mora B. Naive ray-tracing: A divide-and-conquer approach J. ACM Transactions on Graphics, 2011, 30(5): 1-12.28 Hou Q

30、M, Zhou K. A shading reuse method for efficient micropolygon ray tracing J. ACM Transactions on Graphics, 2011, 30(6): 1-8.29 柳有權(quán), 張曼. 光線跟蹤算法的加速技術(shù)研究J. 計算機與數(shù)字工程, 2013, 41(6): 863-865.30 Purcell T J, Buck I, Mark W R, et al. Ray tracing on programmable graphics hardwareC/ACM Transactions on Graphics (

31、TOG). ACM, 2002, 21(3): 703-712.31 Meiner M,Guthe S,Strasser W.Interactive lighting models and pre-integration for volume rendering on PC graphics accelera-torsC.Proceedings of Graphics Interface,2002:209-218.32Kruger J, Westermann R. Acceleration techniques for GPU-based volume renderingC. Proceedings of IEEE Vis