王彥成++田宏安

摘 要：介紹了虛擬現(xiàn)實技術(shù)中的光線跟蹤技術(shù)，總結(jié)了不同種類的加速技術(shù)和方法，分析了這些技術(shù)的原理、特征及應(yīng)用這些技術(shù)時的建議或限制因素。成像屏幕低采樣類型的技術(shù)通過減少每幀射出的主光線數(shù)目的方法縮短計算時間，次級光線局部裁剪與陰影測試技術(shù)通過減少每幅圖像跟蹤主光線數(shù)目的方法縮短渲染時間，光線與場景快速相交優(yōu)化技術(shù)通過改進(jìn)光線跟蹤算法內(nèi)核加快渲染速度。三類方法各有優(yōu)缺點，適用于不同的環(huán)境和場景，并隨著虛擬現(xiàn)實技術(shù)的發(fā)展而不斷發(fā)展。

關(guān)鍵詞：光線跟蹤；次級光線；陰影測試；相交測試

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A DOI：10.15913/j.cnki.kjycx.2016.14.110

計算機圖形學(xué)已從純學(xué)術(shù)理論發(fā)展成一個具有實踐性的重要的商業(yè)領(lǐng)域，促進(jìn)這一發(fā)展的原動力來自諸如虛擬現(xiàn)實和可視化應(yīng)用、照相和電影工業(yè)以及方興未艾的游戲和娛樂工業(yè)。今天，建立在計算機圖形學(xué)上的基礎(chǔ)應(yīng)用主要有兩種，即高質(zhì)量的離線計算機圖形應(yīng)用和交互式圖形應(yīng)用。

目前，在游戲和虛擬現(xiàn)實等應(yīng)用中使用的交互式計算機圖形學(xué)幾乎全部由三角形光柵化方法支配（比如OpenGL和DirectX），并運行在速度極快、越來越精致的商業(yè)圖像芯片上。由于三角形光柵化的一些限制，交互式計算機圖形學(xué)通常不得不依賴近似方法，達(dá)不到物理正確性的要求。離線渲染方法用于高質(zhì)量的圖形和正確的物理渲染中，它在設(shè)計、動畫、電影工業(yè)有許多用處。這一方法能創(chuàng)造幾乎與真實照片毫無區(qū)別的計算機圖像。由于嚴(yán)格的質(zhì)量和正確性要求，這些應(yīng)用絕大多數(shù)建立在光線跟蹤方法上。

“光線跟蹤”概念多出現(xiàn)于計算機圖形領(lǐng)域，通常需要投射大量的光線（一般為百萬級），用在光線投射上的計算時間占很大比例。自光線跟蹤技術(shù)出現(xiàn)以來，找到一種加速光線跟蹤的方法極其重要。經(jīng)深入研究，人們提出了許多不同的加速技術(shù)?？蓪⑦@些技術(shù)粗略地劃分為三類，即通過低采樣率重構(gòu)圖像的技術(shù)、通過減少每個采樣中被跟蹤的光線數(shù)目的技術(shù)和改進(jìn)光線跟蹤算法內(nèi)核的技術(shù)。

1 成像平面低采樣技術(shù)

在成像平面上以低采樣率重構(gòu)圖像的技術(shù)，是基于渲染一幀的時間與該幀的總像素數(shù)緊密聯(lián)系在一起的原理，通過減少每幀射出的主光線數(shù)目的方法縮短計算時間。該技術(shù)主要包括適應(yīng)性采樣圖像平面方法、定點跟蹤方法和渲染緩存方法等。

1.1 適應(yīng)性采樣圖像平面方法

適應(yīng)性采樣圖像平面方法不是對每個像素跟蹤一條光線，而是以某個固定間隔采樣圖像平面。采用啟發(fā)方法中間像素的顏色或4個角上像素的插值，或者圖像位置上的采樣密度適應(yīng)性增加。重復(fù)這一過程，直到可以執(zhí)行插值或所有像素都已被跟蹤為止。適應(yīng)性采樣圖像平面方法適合渲染非常大的場景。對于高細(xì)節(jié)幾何體或高頻特征（比如紋理），該方法幾乎不可避免地導(dǎo)致某些細(xì)節(jié)特征丟失。除了不重要的場景外，該方法中止得非常快，容易引起人為失真。

1.2 頂點跟蹤方法

頂點跟蹤方法不是對每個單獨像素跟蹤主光線，而是將光線直接投射到可見三角形的頂點，用遞歸光線跟蹤計算頂點顏色，用圖形硬件執(zhí)行頂點間插值。為避免額外插值，頂點跟蹤通常采用一些啟發(fā)式方法。如果滿足某些條件，則進(jìn)行適應(yīng)性三角形劃分（同時生成新光線跟蹤新出現(xiàn)的頂點）。另外，光線僅投射到顯示“光線跟蹤物體”的物體上，光柵化硬件負(fù)責(zé)其他物體的渲染。如果被光線跟蹤的物體特別簡單（比如僅有幾個可見頂點），該方法能極大地減少必須跟蹤的光線數(shù)目，甚至能在PC工作站上達(dá)到交互式更新速率。頂點跟蹤的光線數(shù)目與劃分三角形的順序有關(guān)。

1.3 渲染緩存方法

采用渲染緩存方法維護(hù)前面的一些幀采樣得到的舊圖像緩存，并將這些圖像重新投影到每個新生成的幀上。重新投景采樣是對成像平面的稀疏采樣。然后通過某些啟發(fā)式方法解決遮擋、開裂和采樣點之間的插值，最后重構(gòu)完整的圖像。為了提高性能，渲染緩存用啟發(fā)式方法決定成像平面的哪些區(qū)域需要更多的采樣，以在這些區(qū)域生成更好的采樣。新采樣進(jìn)入渲染緩存數(shù)據(jù)結(jié)構(gòu)，并替代已經(jīng)陳舊的采樣。渲染緩存將采樣生成速度和幀率分開，因此在非常低的渲染器中也能保證交互幀率。重新投影和圖像重構(gòu)步驟代價巨大，僅能由極其昂貴的渲染器使用，同時，即使渲染緩存使用上結(jié)啟發(fā)式方法處理最糟糕的情況，也不能避免所有人為失真，經(jīng)常出現(xiàn)某些物體或區(qū)域欠采樣、過時采樣、過多的模糊。

2 次級光線局部裁剪與陰影測試技術(shù)

除了每幀的主光線數(shù)目外，影響總渲染時間的另一個因素是每個像素對應(yīng)的平均光線數(shù)目。因為這兩者的乘積決定了每幀投射的光線總數(shù)。

實際渲染中，每個像素對應(yīng)的次級光線數(shù)目可能非常大，特別是在場景中有很多光源和大量鏡面物體時更是如此。由于投射進(jìn)場景的每條光線（除次級光線之外的主光線）都會發(fā)射陰影光線到每個光源，因此，光源數(shù)目以接近線性的方式影響渲染時間。在實際場景（通常包含主光源、鏡面物體）中，每個像素對應(yīng)的光線數(shù)目將非常大，減少這一數(shù)目將會有效縮短渲染時間。在實踐中，廣泛采用的方法主要有陰影緩存方法、局部光照環(huán)境方法和修剪光線樹方法等。

2.1 陰影緩存方法

陰影緩存方法的基本假設(shè)是，每條主光線或次級光線通常會引起很多陰影光線，所以在光線跟蹤器中的光線主要是陰影光線。但對于陰影光線而言，找出任一遮擋物體，以確認(rèn)遮擋就足夠了，而且許多陰影光線都非常相似（比如所有陰影光線射向同一點光源），也經(jīng)常與同一物體相交。因此，陰影緩存通過保留該光源最后一次遮擋體的信息，每條新陰影光線首先與被緩存的遮擋體求交。如果其中任何一個物體有正的相交距離，則確認(rèn)陰影光線發(fā)生遮擋。此時，將不再跟蹤陰影光線。對于高度遮擋、多光源場景，采用陰影緩存法能極大地減少陰影光線數(shù)目，而且不需要任何近似，不產(chǎn)生任何失真，也與其他大多數(shù)技術(shù)正交（很容易與其他技術(shù)結(jié)合）。但如果主光線與陰影光線不連貫，則因陰影緩存失效導(dǎo)致整個算法失效，特別是對存在面光源的場景和全局光照算法。

2.2 局部光照環(huán)境方法

局部光照環(huán)境方法是針對陰影光線更進(jìn)一步的優(yōu)化，它將場景分隔成“體元”的集合，每個體元存儲著不同光源對該體元區(qū)域的影響方式，比如完全遮擋的光源列表、完全可見的光源列表、部分可見光源列表等。用這些信息能有效減少陰影光線的數(shù)目，不必再去考慮某體元對應(yīng)的完全遮擋的光源，而完全可見光源則可以不必再跟蹤任何陰影光線，只有部分可見光源需要發(fā)射陰影光線。采用局部光照環(huán)境方法時，可以僅跟蹤陰影光線中的很小一部分，尤其是對于有很多光源的場景，能有效縮短渲染時間。

2.3 修剪光線樹方法

修剪光線樹方法的基本假設(shè)是，光線跟蹤需要計算反射和折射，如果每個表面著色器投射多于一條的次級光線（比如一條反射光加一條折射光），那么次級光線的數(shù)目將隨遞歸層數(shù)呈指數(shù)增長，容易導(dǎo)致在每幀投射出巨大數(shù)目的光線，即所謂的“光線樹爆炸”。但在實際渲染時，次級光線往往帶有反射和折射權(quán)重系數(shù)（由表面性質(zhì)和入射光線方向等決定），可能會變得很小，而且在衰減因素與遠(yuǎn)處表面相交的綜合作用下，很多光線對像素貢獻(xiàn)微乎其微。為避免跟蹤這些“不重要”的光線，根據(jù)跟蹤每條光線的像素貢獻(xiàn)修剪光線樹，一旦像素貢獻(xiàn)低于某一閾值就立即終止遞歸。

3 光線與場景快速相交優(yōu)化技術(shù)

除了減少投射出的光線數(shù)目外，另一加速光線跟蹤的明顯方法是改進(jìn)光線跟蹤算法內(nèi)核，使之更快地跟蹤光線。

3.1 相交測試優(yōu)化方法

通常，光線跟蹤中一大部分時間都花在光線與元素相交上，95%的計算時間都花在了求交運算上。任何一種元素與光線求交都有多種方法。這些不同的算法有不同的性質(zhì)，諸如浮點運算、整數(shù)運算、判斷運算的次數(shù)，存儲器開銷，數(shù)據(jù)精度等，不同的應(yīng)用有不同的偏好性質(zhì)，同時，各種不同硬件的特性（比如快速浮點單元）進(jìn)一步改變相應(yīng)的優(yōu)點和缺點。實際上，對于每種元素，各個光線跟蹤系統(tǒng)都有各自特有的實現(xiàn)算法。

對于支持復(fù)雜元素類型（比如參數(shù)曲面）的光線跟蹤器，通過緊密包圍這些耗時元素的邊界體可以避免過高的計算開銷。邊界體是一種能快速求交的簡單幾何元素（通常是盒子或球）。如果光線與邊界體不相交（這是開銷非常小的檢查），則它必定不與邊界體對應(yīng)的復(fù)雜元素相交。只有與邊界體相交的光線需要再次與原來的元素進(jìn)行測試。在光線跟蹤中，邊界體是一項標(biāo)準(zhǔn)技術(shù)，但只對復(fù)雜元素有效。

3.2 場景的空間劃分和層次劃分

通常，加速光線跟蹤最成功的方法是減少光線-元素求交運算的數(shù)目，通過建立一種索引數(shù)據(jù)結(jié)構(gòu)，允許快速找出接近給定光線的元素，并跳過過熟光線的元素。在遍歷這種加速結(jié)構(gòu)時，只對潛在的候選者執(zhí)行求交，因此能顯著減少求交運算的數(shù)目。

一般情況下，存在許多不同的加速結(jié)構(gòu)，比如均勻、非均勻、遞歸、層次網(wǎng)格和BSP樹（或KD-樹），甚至更高維、定向技術(shù)，比如光線分類。在層次邊界體中，每個元素在層次中僅存儲一次。通常，這種結(jié)構(gòu)占用可預(yù)計的存儲，并保證在遍歷層次時每個元素僅執(zhí)行一次相差（通常空間劃分技術(shù)達(dá)不到此要求）。另外，層次的不同部分可能在空間中占用同一區(qū)域，導(dǎo)致諸如錯誤的求交次序或多次遍歷同一空間等無效率的遍歷。

在空間劃分技術(shù)中，將三維空間劃分成有限的、不互相重疊的體積元素（體元voxels），每個體元維護(hù)一個與該體元重疊的所有元素的列表。光線遍歷空間加速結(jié)構(gòu)，依次重復(fù)穿過與光線相交的所有體元，進(jìn)而與體元中的元素相交。如果這種遍歷以“從前至后”的次序執(zhí)行，空間分隔技術(shù)允許早期光線終止。一旦沿光線以下距離內(nèi)的相交被驗證，所有位于此距離之外的體元就無需計算，立即跳過?？臻g分隔存在一個缺點——如果體元很小，光線遇到元素的數(shù)目大量減少，要求具備大量存儲器，而且元素通過與許多不同的體元重疊。這不僅進(jìn)一步增加了存儲開銷，還經(jīng)常導(dǎo)致跟蹤一條光線時多次重復(fù)遇到相同的元素。

3.3 算法具體實現(xiàn)的變體和優(yōu)化

快速相交優(yōu)化類型的加速技術(shù)主要是概念上的差別，實際上，在固定一種數(shù)據(jù)結(jié)構(gòu)的情況下，構(gòu)造和遍歷這一數(shù)據(jù)結(jié)構(gòu)的確切方法仍顯著影響著算法的性能。

盡管不同的遍歷算法確定的遍歷同一體元（因而與同一元素相交），遍歷算法本身通常要占用很大一部分計算時間。因此，不同的遍歷算法可能顯著地影響性能。目前，每種不同的加速結(jié)構(gòu)都有一些不同的遍歷算法，各自優(yōu)缺點并存。雖然這些變體的絕大多數(shù)不改變基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，但有一些方法也要求作一些輕微的改變，例如通過增加相鄰鏈接加速從一個體元到其相鄰體元的遍歷。

除了遍歷算法外，對加速結(jié)構(gòu)的性能有顯著影響的是建立數(shù)據(jù)結(jié)構(gòu)的算法。因為遍歷算法本身一般不改變光線遇到的體元數(shù)目或階數(shù)，所以遍歷步驟和原始的求交次數(shù)通常取決于建立加速數(shù)據(jù)結(jié)構(gòu)的方法（比如體元的數(shù)目、尺寸或組織）。實際上，很難確定最優(yōu)的網(wǎng)格分辨率，只能用某些啟發(fā)式方法近似猜測。由于大多數(shù)光線跟蹤應(yīng)用中投射最多的光線是陰影光線，因此這項優(yōu)化特別有效，大多數(shù)可用的光線跟蹤系統(tǒng)都要實現(xiàn)它。

要想使光線跟蹤更快，關(guān)鍵在于開發(fā)不同的、更強大的硬件設(shè)備。這類的例子有在高并行超級計算機上的光線跟蹤，其采用目前大多數(shù)CPU具備的SIMD-擴(kuò)展，可編程GPU上的光線跟蹤，開發(fā)更一般的可編程設(shè)備，最終使用專門為光線跟蹤設(shè)計的硬件。

4 總結(jié)

虛擬現(xiàn)實光線跟蹤加速技術(shù)中，層次劃分這一類方法是最重要的。因為這些方法可將計算復(fù)雜度從O（N）降低到O（logN）。大體上而言，其他方法僅能改進(jìn)光線跟蹤算法的“常數(shù)項”。因而，任何重要的光線跟蹤系統(tǒng)都使用本文討論的某種場景劃分和遍歷技術(shù)。

雖然相關(guān)人員普遍認(rèn)為所有這些加速方法都具有O（NlogN）的計算復(fù)雜度，但實際上隨場景、實現(xiàn)、硬件平臺和應(yīng)用（比如光線分布）的不同，相應(yīng)的性能也各不相同。盡管最早的一些光線跟蹤涉及八叉樹，但目前實際使用最普遍的技術(shù)不是均勻網(wǎng)格就是KD-樹。網(wǎng)格（尤其均勻網(wǎng)格）的優(yōu)點是簡單，因而適宜在限制編程模型的硬件結(jié)構(gòu)上實現(xiàn)（比如GPU）。另外，KD-樹能很好地適應(yīng)不同場景的復(fù)雜性。如果能正確使用，通常可以達(dá)到優(yōu)質(zhì)性能。

除更快的相交測試和層次劃分外，其他技術(shù)（比如以這樣或那樣的方法減少光線數(shù)目）則各有限制，只能用于一些特殊情況和應(yīng)用中，在一個用于一般情況的光線跟蹤系統(tǒng)中，這些技術(shù)的使用是受限的。

〔編輯：劉曉芳〕