虛擬現實光線跟蹤加速方法研究

王彥成++田宏安

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

關鍵詞：光線跟蹤；次級光線；陰影測試；相交測試

中圖分類號：TP391.41 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2016.14.110

計算機圖形學已從純學術理論發展成一個具有實踐性的重要的商業領域，促進這一發展的原動力來自諸如虛擬現實和可視化應用、照相和電影工業以及方興未艾的游戲和娛樂工業。今天，建立在計算機圖形學上的基礎應用主要有兩種，即高質量的離線計算機圖形應用和交互式圖形應用。

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

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

1 成像平面低采樣技術

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

1.1 適應性采樣圖像平面方法

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

1.2 頂點跟蹤方法

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

1.3 渲染緩存方法

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

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

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

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

2.1 陰影緩存方法

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

2.2 局部光照環境方法

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

2.3 修剪光線樹方法

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

3 光線與場景快速相交優化技術

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

3.1 相交測試優化方法

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

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

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

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

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

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

3.3 算法具體實現的變體和優化

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

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

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

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

4 總結

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

雖然相關人員普遍認為所有這些加速方法都具有O（NlogN）的計算復雜度，但實際上隨場景、實現、硬件平臺和應用（比如光線分布）的不同，相應的性能也各不相同。盡管最早的一些光線跟蹤涉及八叉樹，但目前實際使用最普遍的技術不是均勻網格就是KD-樹。網格（尤其均勻網格）的優點是簡單，因而適宜在限制編程模型的硬件結構上實現（比如GPU）。另外，KD-樹能很好地適應不同場景的復雜性。如果能正確使用，通?？梢赃_到優質性能。

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

〔編輯：劉曉芳〕