劉逸凡 徐 昆

(清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084)

全局光照效果(global illumination)包含直接光照效果(direct illumination)和間接光照效果(indirect illumination)，可以表現(xiàn)反射、折射、焦散(caustics)、互反射等效果，繪制結(jié)果具有很高的真實感.近年來，隨著游戲、影視、動畫等圖形學(xué)相關(guān)產(chǎn)業(yè)的發(fā)展，全局光照效果成為普遍而重要的需求[1-2].

計算某點的全局光照，既要考慮光源對該點的直接光照，又要考慮來自光源的光線與其他物體表面發(fā)生1次或多次反射折射后對該點的間接光照.在光線跟蹤框架[3]中，可以通過從視點處反向追蹤光路來計算到達(dá)成像平面的全局光照.如圖1所示，對于成像平面上的每一個像素，從視點發(fā)射若干條射線.對于每條射線，嘗試與場景中的物體求交：如相交，則可能在交點處發(fā)生反射或折射，產(chǎn)生新的反射折射射線，然后繼續(xù)與場景中的其他物體求交，如此遞歸下去.在圖1中，點x1的出射光亮度L1，由直接光照和間接光照2部分組成：通過依次計算場景中每個光源對點x1的貢獻(xiàn)并求和，得到直接光照；通過計算點x2的出射光亮度L2對點x1的貢獻(xiàn)，得到間接光照.

Fig. 1 Global illumination in path tracing圖1 光線跟蹤中的全局光照

一方面，通過引入虛擬點光源(virtual point lights, VPLs)，全局光照的計算(包括間接光照分量)可以轉(zhuǎn)化為多光源下的直接光照計算；另一方面，隨著工業(yè)界對于圖像真實感訴求的提高，越來越多的繪制場景本身就含有大量光源：夜景的霓虹燈、火星四濺的粒子特效、復(fù)雜網(wǎng)格光源的模擬等.這使得多光源繪制成為計算機圖形學(xué)和繪制領(lǐng)域的一個重要研究內(nèi)容，涌現(xiàn)出了一大批重要方法.

理論上，多光源繪制計算的時間復(fù)雜度與場景中光源的數(shù)量成正比.如此一來，隨著光源數(shù)量的增多，每個點的光照計算量也會成線性增加，造成總體繪制時間的線性增長.例如，圖2是動畫電影《尋夢環(huán)游記》中的一個場景，它包含了約800萬個光源，如果不采取更好的優(yōu)化算法，如此多光源所帶來的繪制時間的增加是難以處理的.

Fig. 2 Complex illumination in Coco(? 2017 Disney·Pixar)[2]圖2 《尋夢環(huán)游記》中的復(fù)雜光照[2]

為了提高多光源場景的繪制效率，研究人員一般從3個方面入手：1)使用蒙特卡洛方法對直接光照進(jìn)行重要性采樣，以縮短繪制時間；2)從占據(jù)計算量主體的可見性測試入手，提高單個光源的光照計算效率；3)通過光源聚類等方法實現(xiàn)繪制時間對光源數(shù)量的可伸縮性(scalable)，使總體繪制的時間復(fù)雜度由O(n)變?yōu)镺(logn)，其中n為光源數(shù)量.

根據(jù)單幀圖像的繪制時長，繪制可以分為實時繪制和離線繪制.實時繪制與離線繪制的實現(xiàn)方法有著很大差異，對于多光源問題的處理方式也有所不同.這里，本文著重分析離線繪制的優(yōu)化算法，簡要介紹實時繪制的相關(guān)方法.

本文將首先闡述直接光照計算和重要性采樣的基本概念；然后從加速可見性計算、通過光源聚類加速光照計算、通過光源聚類優(yōu)化重要性采樣等方面，對現(xiàn)有的離線方法進(jìn)行總結(jié)和分析；最后對實時繪制中的光源剔除方法進(jìn)行介紹.

1 直接光照與重要性采樣

我們將物體表面需要進(jìn)行繪制的點稱作著色點(shading point).如圖3所示，僅考慮直接光照，著色點x在反射方向ω的反射光亮度，可通過對所有光源表面A進(jìn)行積分得到[3-4]

(1)

其中，積分項F(·)定義為

Le(y→x)B(y→x→ω)V(y?x)G(y?x),

(2)

其中，y為光源表面一點.Le(y→x)為y朝x發(fā)射的光亮度.B(y→x→ω)為雙向反射分布函數(shù)(bidirectional reflectance distribution function, BRDF)，描述x處的材質(zhì)反射性質(zhì).V(y?x)是二值可見性函數(shù)：x,y之間可見為1，不可見為0.幾何項

(3)

其中d(y,x)為x,y之間的歐幾里得距離;θx為x,y連線與x法向之間的夾角;θy為x,y連線與y法向之間的夾角.

由于式(1)沒有解析解，一般使用蒙特卡洛方法將其近似為N次采樣的積分項的加權(quán)平均：

(4)

其中，p(y|x,ω)表示給定著色點x和方向ω，采樣光源上一點y的概率密度函數(shù)(probability density function, PDF).概率密度函數(shù)與積分項越相似，蒙特卡洛估計的方差就越小.當(dāng)概率密度函數(shù)正比于積分項時，方差為0，此時，式(4)可以看作等式.這種采樣方法也稱作重要性采樣(importance sampling).

Fig. 3 Illustration of direct illumination圖3 直接光照示意圖

一般地，尤其是對于非環(huán)境光源，采樣光源上一點y，通常分解為2步[4]：先采樣一個光源l，再在光源上采樣一個點y.則式(4)變換為

(5)

關(guān)于在給定幾何形狀的光源上進(jìn)行點的采樣這一問題(即得到p(y|l,x,ω))，許多技術(shù)已經(jīng)提供了近似最優(yōu)的解決方法[4-5]，因此不再是研究重點.而如何合理對光源本身進(jìn)行采樣(即得到p(l|x,ω))，是直接光照計算中一個開放性的研究問題.

在對光源進(jìn)行重要性采樣時，采樣的概率分布與光源對場景的貢獻(xiàn)越相近，則生成的圖片噪點越少.為了提高繪制質(zhì)量，往往需要為每個著色點分別計算光源采樣的概率密度函數(shù)：估計每一個光源的重要性程度，從而形成離散的概率分布.關(guān)于光源重要性的估計，理想情況是考慮到式(2)中的所有項：發(fā)射光亮度、BRDF、可見性和幾何項.但為了保證計算效率，往往只能考慮其中的一部分.應(yīng)該考慮哪幾項？又如何進(jìn)行快速估計？這些問題是重要性采樣研究中的主要研究目標(biāo).

下面，本文將從提高單個光源的光照估計效率和實現(xiàn)光照估計的亞線性復(fù)雜度這2個角度，介紹離線繪制對于多光源場景的解決辦法.

2 加速可見性計算

2點之間可見性的判斷占據(jù)整個繪制計算量的主體.許多工作都是從可見性入手，提高繪制效率.

由于暗光源對場景整體貢獻(xiàn)較小，1994年Ward[6]提出在直接光照計算中對暗光源跳過可見性測試以加速繪制.1996年Shirley等人[5]將該思想拓展到重要性采樣中，只對亮度大的光源進(jìn)行采樣.由于不考慮暗光源，這些方法造成了繪制結(jié)果的有偏性.

1995年Jensen等人[7]的方法和2000年Keller等人[8]的方法通過擴(kuò)展光子圖(photon map)方法來減少繪制時的可見性計算.然而對于大規(guī)模場景，產(chǎn)生的光子常常不處于視點重要區(qū)域，難以取得理想效果.

1999年Hart等人[9]利用圖像空間的連貫性提前記錄每個“像素-光源”對之間的潛在遮擋物體，后續(xù)計算著色點可見性時只需考慮這些記錄的潛在遮擋物體.2002年Fernandez等人[10]將該思想擴(kuò)展到場景空間.他們對場景分塊，預(yù)先將區(qū)域塊與光源之間的可見性關(guān)系分為3種進(jìn)行記錄：完全可見、完全不可見、不確定.在繪制時，只對那些相對著色點所在區(qū)域塊可見性關(guān)系為不確定的光源進(jìn)行可見性測試.2003年Wald等人[11]將類似方法用到了計算采樣權(quán)重上.

2009年Dong等人[12]提出了VPLs框架下的可見性加速計算方法.他們用K-Means方法將虛擬點光源聚類為虛擬面光源，采用虛擬面光源計算可見性的同時，仍使用虛擬點光源進(jìn)行其他項的計算.

Fig. 4 Algorithm overview of ref [13]圖4 文獻(xiàn)[13]的算法總覽

相比于緩存1對1的可見性，Ulbrich等人[14]通過使用陰影圖記錄1對多的可見性結(jié)果.他們在物體表面離散地分布一些記錄點，每個記錄點存儲1張陰影圖.估計任意2點間的可見性時，尋找最近的陰影圖，然后將2點間的距離與陰影圖中的相應(yīng)值進(jìn)行比較.

這類緩存記錄的方法，通過犧牲一定的存儲，避免了一部分可見性測試的重復(fù)計算，從而提高了計算效率.然而對于復(fù)雜的場景，由于物體表面的相似性不高，緩存的方法往往難以得到很好的效果，并且會占用大量存儲.

同年，Billen等人[15]提出一種基于隨機選取的可見性估計算法：計算2點之間可見性時，利用蒙特卡洛方法隨機選取一部分場景物體進(jìn)行測試.理論上，2點之間的可見性值，是分別只考慮單個潛在遮擋物體時可見性值的累乘.該算法的核心思想是將累乘分解為累加，然后進(jìn)行蒙特卡洛采樣.例如，當(dāng)只存在2個潛在的遮擋物體A和B時，考察點x和點y之間的可見性V(x,y)，它等于VA(x,y)·VB(x,y).通過分解得到：

(6)

(7)

假設(shè)采樣概率p1,p2,p3均為13，相比原來需要測試2個物體，現(xiàn)在平均只需要測試 (1+2+3)3=1.33個物體，減少了可見性測試的次數(shù).

2014年Billen等人[16]進(jìn)一步提出利用蒙特卡洛估計來降低可見性測試中潛在遮擋物體的平均網(wǎng)格復(fù)雜度.在測試2點之間的可見性時，隨機地選擇遮擋物體的簡化模型或原始網(wǎng)格模型.與傳統(tǒng)方法相比，該方法并不具有太多優(yōu)勢.主要因為，很多情況下簡化網(wǎng)格和原始網(wǎng)格的可見性測試的時間消耗相差不大.

上面2種算法雖然在效果提升上不是十分顯著，但巧妙地將蒙特卡洛估計運用到可見性計算中，非常具有啟發(fā)意義.

表1從準(zhǔn)確性、存儲占用、應(yīng)用范圍3個方面對上述加速可見性計算的工作進(jìn)行了分析總結(jié).本節(jié)介紹的算法，通過加速可見性測試降低了單個光源的計算時間消耗，對于小規(guī)模光源場景可以取得較好的效果.然而，繪制時間與光源數(shù)量成線性的復(fù)雜度并沒有降低，隨著場景中的光源數(shù)量繼續(xù)增多，僅僅加速可見性測試難以顯著提高計算效率.這時，常見的做法是將光源聚類，相似的一組光源用一個單獨的大光源替代，從而使得繪制時間相比光源數(shù)量的復(fù)雜度從線性降為對數(shù).下面，我們將首先介紹光源聚類的基本方法，然后介紹基于光源聚類的重要性采樣方法.

Table 1 Analysis of Visibility Test Acceleration Methods表1 可見性測試加速方法比較

3 使用光源聚類加速直接光照計算

場景中每個光源對繪制結(jié)果的貢獻(xiàn)往往是不均勻的.部分光源有著較低的重要性，例如，當(dāng)光源被遮擋時，或光源距離著色區(qū)域很遠(yuǎn)；同時，部分光源是非常重要的，比如對于繪制結(jié)果中的高光有貢獻(xiàn)的光源，我們需要精確計算它們的光能貢獻(xiàn).通過利用場景中光源重要程度的不均勻性和光源之間的相似性，對光源進(jìn)行自適應(yīng)的聚類，并以類為單位進(jìn)行直接光照計算，是光源聚類加速方法的主要思想.

使用光源聚類來加速直接光照計算的相關(guān)研究主要是基于VPLs算法框架.VPLs算法源自Keller的即時輻射度方法[17]，其核心思想是將復(fù)雜的全局光照計算問題近似為大量虛擬點光源(VPLs)下的直接光照計算問題.為了確保圖像的真實性，VPLs算法往往需要生成數(shù)量巨大的虛擬點光源.此時，通過依次遍歷光源來計算直接光照的蠻力方法不再適用，需要有更優(yōu)化的算法來降低線性時間復(fù)雜度，實現(xiàn)可伸縮性.近10多年，出現(xiàn)了許多研究成果，其中2014年的1篇綜述[18]詳細(xì)介紹了VPLs算法的原理以及相關(guān)算法，感興趣的讀者可以進(jìn)行查閱.本文將著重介紹2014年之后的相關(guān)工作.

需要注意的是，基于VPLs框架的光源聚類不一定能直接泛化到一般情形下的直接光照計算中.原因主要有2點：1)VPLs框架中的虛擬光源往往是點光源，基于此的一些光源聚類方法可能不適用于球光源、面光源等其他光源類型；2)VPLs算法的應(yīng)用場合決定了它往往不需要過多的像素采樣數(shù)，基于此的一些光源聚類算法會預(yù)先計算和存儲所有著色點，用于后續(xù)的繪制過程.當(dāng)像素采樣數(shù)增多時，這種算法會占用大量的存儲空間，不適合泛化到一般情境中.

光源聚類的方法大致可分為2類：基于樹的方法和基于矩陣的方法.不同聚類方法的主要區(qū)別在于，估計光源重要性的標(biāo)準(zhǔn)以及聚類的形式存在差異.但總體來說，光源聚類的核心思路都是將相似的光源聚成一類，形成一個光源簇(light cluster).每個光源簇的總體光能貢獻(xiàn)，可以通過將該光源簇看作一個更大、更亮的光源來進(jìn)行近似估計，如圖5所示:

Fig. 5 Lights clustering when evaluating VPLs lighting [18]圖5 估計VPLs光照時的光源聚類[18]

3.1 基于樹的光源聚類

Fig. 6 A light tree and three example lightcuts[20]圖6 1個光源樹和3個光源割[20]

Fig. 7 Product graph [24]圖7 乘積圖 [24]

Lightcuts算法需要為每個著色點選擇一個合適的光源割.當(dāng)光源數(shù)量很多且分布復(fù)雜時，從光源樹中搜索合適的光源割也需要花費不少的計算時間.針對這一問題，一些工作提出了改進(jìn)方法.

2006年Walter等人[24]將Lightcuts算法擴(kuò)展，提出多維Lightcuts算法(multidimensional lightcuts)，以便能夠處理高維空間的繪制積分，例如景深、運動模糊、空間抗鋸齒等.對于每個像素，他們將高維積分離散成一系列著色點的光照求和.由此產(chǎn)生的著色點數(shù)量非常多，對每個著色點都重新計算一個光源割將帶來巨大的時間成本.他們分別將同一個像素內(nèi)的著色點用二叉樹組織起來，并通過使用圖7所示的乘積圖(product graph)來隱式地表達(dá)“著色點-光源”對的層次結(jié)構(gòu)，從而提高了效率.

2013年王光偉等人[25]提出對所有的著色點進(jìn)行空間聚類，同一類中的著色點使用同一個光源割作為初始光源割，然后對同一類中的每個著色點進(jìn)一步細(xì)化光源割.這樣的做法避免了每次都從光源樹的根節(jié)點開始搜索光源割，一定程度上減少了計算量.

2015年Bus等人[26]提出的IlluminationCut沿用多維Lightcuts[24]的思路，但不再只考慮同一像素內(nèi)的著色點，而是將所有著色點都用一個二叉樹組織起來，并用乘積圖(圖7所示)隱性地對“著色點-光源”對進(jìn)行聚類.這樣一來，只需遍歷一次乘積圖(等價于同時遍歷一次著色點樹和光源樹)，即可得到每個著色點的光源割，平攤了計算時間.

Fig. 9 The light transport matrices of two complex scenes (subsampled from the original) [31]圖9 2個樣例場景的光能傳輸矩陣(欠采樣之后的結(jié)果)[31]

2016年Rehfeld等人[27]提出一種Lightcuts插值算法.他們利用光源割的局部連貫性，先選取一部分著色點按照原始的Lightcuts算法計算光源割，然后通過插值來得到其余著色點的光源割.如此一來，減少了光源割的計算次數(shù)，提高了計算效率.

上面介紹的算法都是基于Lightcuts的聚類思路，即先建立光源二叉樹，從光源樹根節(jié)點自頂向下通過誤差上界標(biāo)準(zhǔn)來得到光源割.除此之外，一些工作提出了其他的基于樹的聚類方法.

2015年Bus等人[28]基于VPLs框架提出了一種不依賴視角信息的點光源聚類算法.它的核心思路是：1)在預(yù)處理過程中，針對每個點光源，將其余點光源聚類；2)繪制過程中，對著色點計算直接光照時，使用最近鄰的點光源的聚類作為該著色點的初始聚類，然后進(jìn)行細(xì)微調(diào)整.這樣一來，由于預(yù)處理過程中的聚類操作只依賴場景物體信息和光源信息，視點的變換不需要重新進(jìn)行聚類操作，節(jié)省了大量的計算時間.在具體的聚類方法上，他們以文獻(xiàn)[29]作為理論依據(jù)，使得聚類后的光源簇與對應(yīng)點滿足完全分離(well-separated)標(biāo)準(zhǔn).如圖8所示，這保證了對應(yīng)點到光源簇內(nèi)任意一點的距離和朝向都是相似的.然而，由于這種聚類標(biāo)準(zhǔn)沒有考慮到著色點的材質(zhì)信息，該算法更適用于漫反射表面.另外需要注意的是，VPLs框架中，虛擬點光源的分布與場景幾何分布非常接近，因此對著色點的光源聚類使用最近鄰點光源對應(yīng)的光源聚類來代替在直觀上是合理的.但這一思路不易推廣到光源分布與場景幾何分布不一致的一般情形.

Fig. 8 Definition of well-separated[28]圖8 完全分離的定義[28]

2018年Maria等人[30]基于Bus等人[28]算法做了進(jìn)一步的改進(jìn)，在聚類時考慮了可見性.他們提出在構(gòu)造完全分離對分解(well-separated pair decom-position, WSPD)結(jié)構(gòu)時直接查詢點對之間的可見性，這樣雖然增加了WSPD結(jié)構(gòu)的構(gòu)造時間，但總體上節(jié)約了45%左右的繪制時間，效果提升明顯.

3.2 基于矩陣的光源聚類

這一類方法，將多光源場景的繪制問題用光能傳輸矩陣(如圖9所示)來形式化地表示：矩陣的行索引指向著色點，列索引指向光源，第i行第j列的元素表示第j個光源對第i個著色點的光能貢獻(xiàn).第i行所有元素之和代表了所有光源對第i個著色點的總貢獻(xiàn).樸素的蠻力算法需要計算矩陣中每個元素的值，然后將它們沿著列方向進(jìn)行累加以得到每個著色點的光照.當(dāng)存在m個著色點、n個光源時，蠻力算法所需的時間復(fù)雜度為O(mn).為了減少時間成本，這類方法通常的做法是僅計算矩陣的部分元素再估計矩陣的其余部分，而不是直接計算全部元素.需要注意的是，此類方法常常需要占據(jù)較多的存儲空間，當(dāng)像素數(shù)量非常大時，往往不太適用.

2007年的MRCS(matrix row-column sampling)算法[32]是首個基于矩陣的多光源繪制方法.他們觀察到，由于著色點以及光源的空間連貫性，光能傳輸矩陣往往是一個低秩矩陣(例如圖9中大部分區(qū)域都是黑色)，它的信息可以通過計算低維矩陣來近似.算法的主要思路如圖10所示：首先對傳輸矩陣的行做降采樣，把這些行合并為一個簡化矩陣(reduced matrix)，然后對這個簡化矩陣的列索引(即對應(yīng)的光源)做聚類.根據(jù)傳輸矩陣的低秩假設(shè)，簡化矩陣的列聚類結(jié)果可以近似為傳輸矩陣的列聚類結(jié)果.接下來在每一列簇中隨機選擇一個代表列進(jìn)行繪制(繪制結(jié)果需要乘以列簇大小)來近似整個列簇的值.最后通過累加這些代表列即可得到最終繪制結(jié)果.該算法的優(yōu)點在于，部分計算步驟可以用陰影圖方法實現(xiàn)，通過GPU運算提高了計算效率.

Fig. 10 Overview of MRCS algorithm [32]圖10 MRCS算法總覽[32]

Fig. 11 Algorithm overview of ref [33]圖11 文獻(xiàn)[33]的算法總覽

將MRCS與Lightcuts算法進(jìn)行比較： 前者讓所有著色點共享相同的光源聚類，平攤了聚類計算量，但容易忽視只對局部區(qū)域有貢獻(xiàn)的光源，難以捕捉光照細(xì)節(jié)；后者對每個著色點都分別進(jìn)行光源聚類，雖然能捕捉局部光照細(xì)節(jié)，但存在不必要的重復(fù)計算，時間成本高.2011年提出的LightSlice算法[31]結(jié)合了兩者的思想，先對所有著色點劃分一個粗糙的光源聚類，然后以此為起始點，對每一部分著色點繼續(xù)細(xì)分光源聚類.

2015年Huo等人[33]通過求解一個矩陣恢復(fù)問題來加速聚類之后的計算效率.他們觀察到，即使采用之前的LightSlice等方法進(jìn)行聚類，最后要繪制的矩陣仍然很大，需要不少的計算時間.由于可見性測試是整個計算過程中最耗時的部分，他們決定從這部分入手.他們提出只對一小部分的矩陣元素的可見性進(jìn)行精確計算，其余部分采用矩陣分離技術(shù)[34]恢復(fù)得到.具體的算法流程如圖11所示： 1)將矩陣按行聚類得到一系列切片(slice)，對每個切片按列聚類，在每個列簇中選擇一個代表列合并成簡化矩陣.計算簡化矩陣中每個元素不包含可見性的光照值，由于不包含可見性，這部分的計算很快.2)離散采樣一些元素進(jìn)行可見性測試，并利用可見性的局部性特點大致估計其余未采樣元素的可見性.3)得到的矩陣可看作是低秩目標(biāo)矩陣(希望恢復(fù)的矩陣)與稀疏誤差矩陣(估計值與實際值之差)的和，通過矩陣分離算法，恢復(fù)得到目標(biāo)矩陣.

在VPLs框架中，為了生成云、霧等體繪制效果，一些工作將虛擬點光源替換為虛擬線光源(virtual ray lights, VRLs)[35]或虛擬束光源(virtual beam lights, VBLs)[36].學(xué)者們提出了LightSlice的改進(jìn)算法[37]和自適應(yīng)的矩陣恢復(fù)方法[38]以應(yīng)對這類光源.

表2從存儲占用、GPU友好性、對一般情形的可泛化性這3個方面對基于樹的光源聚類方法和基于矩陣的光源聚類方法進(jìn)行對比.相比基于樹的算法，基于矩陣的聚類算法由于需要構(gòu)建光能傳輸矩陣，內(nèi)存占用量大.但由于傳輸矩陣的一整列能通過陰影圖的方法進(jìn)行繪制，基于矩陣的方法GPU實現(xiàn)方便.基于矩陣的方法往往需要提前知曉并存儲所有著色點，可泛化程度較低.

Table 2 Analysis of Light Clustering Methods表2 光源聚類方法比較

總的來說，本節(jié)所介紹的方法均沒有使用重要性采樣，這樣雖然減少了噪聲的引入、降低了時間成本，但造成了圖像結(jié)果的不準(zhǔn)確性和有偏性.光源聚類也可以用來加速重要性采樣的概率分布的計算，從而提高計算效率，這部分工作將在第4節(jié)進(jìn)行介紹.

4 基于光源聚類的重要性采樣

當(dāng)光源數(shù)量比較多時，如果對每個著色點都遍歷一遍所有光源來計算采樣概率分布，會花費巨大的時間成本.對此，許多工作將光源聚類之后再進(jìn)行重要性采樣，使得直接光照采樣過程由2步變?yōu)?步：

1) 采樣一個光源簇C；

2) 在光源簇C的內(nèi)部采樣一個光源l；

3) 在光源l上采樣一個點y.

由于光源簇的數(shù)量遠(yuǎn)少于光源數(shù)量，建立光源簇的采樣概率分布只需要消耗亞線性的時間復(fù)雜度；位于同一光源簇內(nèi)部的光源往往很相似，因此在光源簇內(nèi)部采樣光源可以使用較簡單的采樣策略，例如均勻采樣或只根據(jù)光源發(fā)射光亮度采樣.如此一來，通過聚類的方法，對每個著色點進(jìn)行光源采樣的時間復(fù)雜度與光源數(shù)量呈亞線性，實現(xiàn)了伸縮性.

為了在直接光照采樣中同時考慮光源光亮度(這里代指光源發(fā)射光亮度與幾何項的乘積)和BRDF的信息，常常使用1997年由Veach[39]提出的多重重要性采樣 (multiple importance sampling, MIS)方法：分別按照光源光亮度和著色點BRDF的分布進(jìn)行直接光照的采樣計算，再將結(jié)果進(jìn)行加權(quán)平均.這種方法雖然實現(xiàn)簡單方便，但會造成采樣的浪費.

2007年Akerlund等人[40]在計算光源簇的重要性時直接考慮了BRDF信息.他們假設(shè)著色點的BRDF值在同一個光源簇內(nèi)的變化非常平滑且可以忽略，從而通過在光源簇內(nèi)隨機選擇一個光源計算BRDF值來作為權(quán)重，乘以該光源簇的光亮度估計，作為采樣的重要性.這種隨機選取光源簇內(nèi)部光源進(jìn)行BRDF信息估計的方法計算量雖小，但精確度較低.

Fig. 12 Detect the number of BRDF sample intersects for each cluster [41]圖12 檢查每個光源簇與BRDF采樣光線發(fā)生相交的數(shù)量 [41]

BRDF常常具有高頻特性，在光源簇內(nèi)平滑變化的假設(shè)往往難以成立.2009年Wang等人[41]提出了更加實際的結(jié)合BRDF信息的光源簇采樣方法.如圖12所示，計算光源簇的重要性時，在著色點位置按照BRDF的分布采樣若干條射線，記錄與每個光源簇所在包圍盒發(fā)生相交的射線數(shù)量，以此近似BRDF在光源簇內(nèi)的積分，將其再除以包圍盒相對于著色點的立體角，得出BRDF在光源簇內(nèi)的均值，最后乘以光源簇的光亮度估計，作為該光源簇的重要性.這種BRDF的估計方法，相比Akerlund等人[40]的方法更加精確，但它依賴于BRDF采樣射線的命中率，并且難以拓展到在光源簇內(nèi)部采樣光源的過程中.

2013年提出的VisibilityCluster方法[42]使用基于矩陣的聚類思想，在光源簇采樣中考慮可見性因素.他們按圖13所示的步驟來估計可見性：首先，根據(jù)幾何相似性分別對光源和著色點進(jìn)行聚類；然后，隨機進(jìn)行可見性測試，估計每個小矩陣塊的平均可見性；再通過分離光源簇，進(jìn)一步細(xì)分矩陣塊；在估計得到可見性信息之后，結(jié)合前面上述采樣方法[41]，即可在光源簇采樣中同時考慮光源光亮度、BRDF和可見性3項.然而，基于矩陣的聚類思想需要占用大量的存儲，難以適用于大規(guī)模場景的繪制.

Fig. 13 Construction of VisibilityClusters[42]圖13 可見性簇的構(gòu)建[42]

2006年Donikian等人[43]提出在繪制過程中迭代漸近地學(xué)習(xí)光源簇的采樣概率分布.他們首先用Lightcuts算法[20]對光源聚類，并將圖像空間劃分為若干塊.在繪制過程中，通過極大似然估計迭代地學(xué)習(xí)光源簇對每個塊以及每個像素的重要性，形成相對塊的采樣概率分布和相對像素的采樣概率分布.每一次迭代后，按照一定的經(jīng)驗性權(quán)重，將相對塊的采樣分布、相對像素的采樣分布以及均勻采樣分布進(jìn)行加權(quán)平均，作為下一次迭代中光源簇的采樣概率密度函數(shù).對于光源簇內(nèi)部，他們根據(jù)光源發(fā)射亮度進(jìn)行采樣.對于常見的光源，其發(fā)射亮度與著色點無關(guān)，只需計算1次，不影響算法的可伸縮性.該算法的主要缺點在于，3個概率分布的結(jié)合權(quán)重是經(jīng)驗性的設(shè)定，不夠魯棒和可靠.

2016年Vévoda等人[44]將上面的思想從圖像空間擴(kuò)展到場景空間：他們將整個繪制場景劃分為均勻的網(wǎng)格，對每個網(wǎng)格塊單獨進(jìn)行自適應(yīng)的光源聚類，并以此進(jìn)行重要性采樣.為了避免不必要的計算，他們延遲到繪制過程中才進(jìn)行聚類：對每個著色點，判斷其所屬網(wǎng)格塊是否已經(jīng)進(jìn)行了光源聚類，如果沒有則立即進(jìn)行聚類操作.當(dāng)區(qū)域塊包含聚類結(jié)果后，簡單估計每個光源簇到著色點的光能貢獻(xiàn)，以此生成離散的概率分布來采樣光源簇.

2016年P(guān)harr等人[4]也給出了一種針對多光源采樣問題的實現(xiàn).他們也將繪制場景劃分為均勻的網(wǎng)格，與前面方法不同的是，他們沒有選擇聚類，而是在繪制過程中自適應(yīng)地構(gòu)建對所有光源的采樣概率分布：在著色點所屬區(qū)域塊中隨機采樣一些點，簡單計算每個光源到這些采樣點的光能貢獻(xiàn)，從而形成對該區(qū)域塊的光源采樣分布.該算法實現(xiàn)起來很簡單，但由于沒有進(jìn)行光源聚類，當(dāng)光源數(shù)量增多時，每個區(qū)域快的光源采樣分布的構(gòu)造都需要花費大量時間，且采樣沒有考慮可見性以及BRDF的信息.

2018年Vévoda等人[45]繼續(xù)研究改進(jìn)他們在2016年提出的方法[44]，提出使用貝葉斯回歸模型在線學(xué)習(xí)每個光源簇的采樣重要性.與之前相同，他們首先使用類似Lightcuts[7]的算法將光源用二叉樹組織起來，然后對場景區(qū)域均勻劃分，在繪制過程中對每個場景塊自適應(yīng)地進(jìn)行光源聚類.不同的是，類似Donikian等人的方法[43]，他們也在繪制過程中漸近地學(xué)習(xí)光源簇的采樣概率分布.

1) 通過理論推導(dǎo)，他們發(fā)現(xiàn)光源簇的采樣重要性既與光源簇內(nèi)部光源采樣點的光能貢獻(xiàn)的均值有關(guān)，又與光能貢獻(xiàn)的方差有關(guān).

2) 他們觀察到，不考慮BRDF信息和采樣點與著色點之間的距離時：若可見性為1，光源簇內(nèi)采樣點的光能貢獻(xiàn)近似平滑，可以用高斯函數(shù)來擬合；若可見性為0，光能貢獻(xiàn)為常值0，可以用狄拉克δ函數(shù)來擬合.因此，光源簇對著色點的光能貢獻(xiàn)可以建模為高斯函數(shù)與狄拉克δ函數(shù)的混合模型.

3) 對每個著色點和每個光源簇：參考Lightcuts算法對光源簇簡單估計的重要性作為先驗，用當(dāng)前著色點所屬場景塊內(nèi)記錄的其他已繪制的著色點的光照信息作為后驗，通過最大后驗估計推斷模型得到均值與方差，進(jìn)而計算出光源簇的采樣重要性.

該方法的主要優(yōu)勢有2點：一是估計光源簇的重要性時，不僅考慮了光能貢獻(xiàn)的均值，還考慮到光能貢獻(xiàn)的方差，即內(nèi)部光源差異性越大的光源簇應(yīng)該更高概率地被采樣到；二是通過漸進(jìn)式學(xué)習(xí)，光源簇的重要性中包含了可見性信息，在遮擋關(guān)系復(fù)雜的場景中也能夠取得很好的繪制效果.

同年，Estevez等人[46]從另一個角度對多光源的重要性采樣問題進(jìn)行研究.算法的基本步驟非常簡潔：對光源建樹，然后對每個著色點采樣一個光源.他們的貢獻(xiàn)主要有3點：

1) 對光源進(jìn)行層次結(jié)構(gòu)的組織時，不再采用以往方法通常使用的Lightcuts[7]建樹方法，而是提出了表面積朝向準(zhǔn)則(surface area orientation heuristic, SAOH)來引導(dǎo)光源層次結(jié)構(gòu)的構(gòu)建，使得相似空間位置和朝向的光源位于同一節(jié)點之下，生成的光源樹質(zhì)量更好，并且能夠很好地適用于網(wǎng)格光源(mesh lights).

2) 相比計算所有光源的重要性，構(gòu)建概率密度函數(shù)進(jìn)行采樣，他們提出通過遍歷光源樹來采樣光源，即從根節(jié)點出發(fā)估計左右子節(jié)點的重要性，隨機采樣一個子節(jié)點，如此遞歸直到抵達(dá)葉節(jié)點.這樣一來，光源采樣消耗的時間與光源數(shù)量從線性關(guān)系降低為對數(shù)關(guān)系，實現(xiàn)了可伸縮性.

3) 對于深度較低的光源樹節(jié)點，其包含的光源差異可能較大，由此估計的重要性程度會存在不準(zhǔn)確性；另外，當(dāng)著色點位于某個節(jié)點包圍盒內(nèi)部時，也無法較好地估計該節(jié)點的重要性程度.對于這些問題，他們提出在遍歷光源樹時，先不采樣子節(jié)點，而是進(jìn)行分離(split)操作，同時對左右子節(jié)點進(jìn)行遍歷.只有當(dāng)節(jié)點的光能貢獻(xiàn)誤差小于一定閾值，且著色點位于節(jié)點包圍盒之外時，才停止分離操作開始子節(jié)點的采樣，如圖14所示.其實從另一個角度來看，他們采取的分離操作等價于尋找一個光源割并對光源進(jìn)行了聚類.不同的是，他們不是隨機選擇一個光源簇再選擇一個光源，而是對每個光源簇都分別采樣一個光源，計算光能貢獻(xiàn)并相加.從這樣的角度來看，該方法提出的遍歷樹采樣方法是一種光源簇內(nèi)采樣光源的策略.

2019年“Ray Tracing Gems”中[47]介紹了該算法的GPU實現(xiàn)，并比較分析了多種光源樹構(gòu)建方法.

2019年Liu等人[48]基于Estevez等人的工作，提出在光源采樣中考慮BRDF信息.他們用現(xiàn)有的面光源解析方法[49-50]估計BRDF在光源樹節(jié)點對應(yīng)包圍盒的立體角下的積分，以此作為該光源樹節(jié)點的BRDF重要性權(quán)重.他們的方法可以有效解決在同時包含多光源和光澤材質(zhì)的場景中傳統(tǒng)BRDF采樣方法失效的問題.然而，由于在光源上進(jìn)行點的采樣時無法考慮BRDF信息，他們的方法仍然需要與BRDF采樣方法進(jìn)行結(jié)合.

Fig. 14 Importance sampling with adaptive tree splitting[46]圖14 帶有自適應(yīng)樹分離的重要性采樣[46]

基于光源聚類的重要性采樣方法，近年來已經(jīng)成為離線繪制中處理多光源場景的主流手段.本文之前介紹的加快可見性測試、光源聚類進(jìn)行直接光照計算等工作，都可對光源聚類的重要性采樣算法起到貢獻(xiàn)作用.例如，加快可見性測試方面的工作可用于加快光源(簇)可見性項的重要性估計；光源聚類進(jìn)行直接光照計算的相關(guān)工作可以用于構(gòu)建更好的光源樹和光源割，提高重要性采樣的效率.

表3對本節(jié)介紹的光源采樣方法進(jìn)行了比較.可以發(fā)現(xiàn)，在采樣時考慮可見性項的方法往往是通過預(yù)處理或者數(shù)據(jù)驅(qū)動地在線學(xué)習(xí).而考慮BRDF項的方法仍然具有很大的改進(jìn)空間.如何在采樣過程中又快又好地同時考慮光源的可見性和著色點的BRDF，仍然是一個值得探討的話題.

Table 3 Analysis of Lights Sampling Methods表3 光源采樣方法比較

5 實時繪制中的光源剔除(light culling)

實時繪制往往將光源的影響范圍看作是有限的，這里將簡要介紹通過光源剔除來加速繪制速率的方法，感興趣的讀者可以查閱2015年的SIGGRAPH課程[51]進(jìn)行深入了解.

早先為了處理多光源場景，許多工作[52-54]提出使用延遲著色法(deferred shading)來替代正向著色法(forward shading)，其分為2步操作：在幾何處理階段用G緩存(G-Buffer)存儲可見片元的幾何信息；在繪制階段，遍歷每個光源，對其影響范圍內(nèi)的每個可見片元進(jìn)行繪制.由于每次繪制一個片元在一個光源下的光照時都需要讀寫G-Buffer，這類方法會占用非常高的帶寬.

為了解決高帶寬占用的問題，一些工作[55-57]提出切片式延遲著色法(tiled deferred shading或deferred lighting)，將原本繪制階段的內(nèi)外循環(huán)顛倒：對G-Buffer中的每個片元，查找可能受影響的光源，分別進(jìn)行繪制.為了給片元分配受影響的光源，他們選擇將屏幕空間用網(wǎng)格劃分，每個網(wǎng)格共享相同的光源分配結(jié)果，從而攤銷計算時間.光源分配的方法為：分別計算每個光源投影到屏幕空間的包圍盒，對每個包圍盒內(nèi)所有網(wǎng)格區(qū)域記錄對應(yīng)的光源索引.

為了避免延遲著色法本身所具有的高存儲要求，切片式的思想被運用到正向著色法，出現(xiàn)了切片式正向著色法(tiled forward shading, forward+)[58-59].

2012年Harada[60]提出在使用切片式著色法時對每個切片保守地估計最小最大深度，裁去影響區(qū)域為空白的光源.

2012年Olsson等人[61]將切片式著色法擴(kuò)展為聚類著色法(clustered shading).他們發(fā)現(xiàn)，原先的切片式方法是在屏幕空間進(jìn)行光源分配，由于不同視角下屏幕空間的光源密度不同，繪制時間充滿不確定性.對此，他們提出為原本屏幕空間的切片(tile)引入深度，將視錐體用網(wǎng)格劃分(屏幕坐標(biāo)方向均勻劃分，深度方向?qū)?shù)劃分)，然后對每個非空的網(wǎng)格單元進(jìn)行光源分配，如圖15所示.之后，一些工作對具體的實現(xiàn)方法進(jìn)行了探索和改進(jìn)[62-63].

Fig. 15 View frustum in tiled shading and clustered shading[63]圖15 切片式著色和聚類著色中的視錐體[63]

2017年O’Donnell等人[64]提出通過沿深度方向建立一維的完全二叉樹來存儲每個屏幕切片或者視錐體網(wǎng)格塊中的光源，并且給出了GPU友好的構(gòu)造和遍歷算法.該算法與聚類著色法結(jié)合，可以很好地彌補視錐體后方網(wǎng)格塊深度范圍過大、光源數(shù)量過多的問題.

上面的光源剔除算法只考慮有限的光源影響范圍，這會造成圖像結(jié)果的有偏性.2016年Tokuyoshi等人[65]提出隨機光源采樣方法，使得繪制結(jié)果保持無偏.他們分別為每個光源設(shè)定一個固定的隨機數(shù)，通過俄羅斯輪盤賭(Russian roulette)決定每個光源的影響范圍，然后使用現(xiàn)有的光源剔除方法進(jìn)行繪制.

表4給出了本節(jié)介紹的5種光源剔除方法的特點.可以看出，傳統(tǒng)的延遲著色法會占用較多帶寬.相比切片式著色，聚類式著色不太依賴視角，不同視角的效果相近.另外，所有的延遲著色類算法都需要花費較高的存儲.

Table 4 Analysis of Lights Culling Methods表4 光源剔除方法比較

6 總結(jié)與展望

本文對近年來離線繪制和實時繪制中的多光源繪制方法進(jìn)行了綜述.

在離線繪制方面，本文首先介紹了通過加速可見性測試以提高單個光源繪制效率的一類方法.這類方法通?？梢赃\用在直接光照采樣的重要性估計中；然后介紹了基于VPLs框架的光源聚類方法，可以實現(xiàn)計算時間相對光源數(shù)量的可伸縮性；最后介紹了使用光源聚類思想的重要性采樣方法，這方面的工作往往受益于前2個領(lǐng)域的工作成果.如何在采樣中高效地同時考慮光源的可見性和著色點的BRDF仍然是一個開放性的問題.

在實時繪制方面，本文介紹了光源剔除方面的工作.對于這一部分，如何結(jié)合GPU硬件更好地優(yōu)化具體的實現(xiàn)算法，往往起到非常關(guān)鍵的作用.

針對多光源繪制問題，未來的研究重點可能是3個方向：

1) 如何建立更優(yōu)的光源樹.提出更好的建樹啟發(fā)準(zhǔn)測，嘗試自底向上建立光源樹.

2) 如何制定更優(yōu)的重要性采樣策略，盡可能地包含BRDF項和可見性項.一方面繼續(xù)優(yōu)化光源簇的采樣方法，另一方面也要考慮如何高效地在光源簇內(nèi)部采樣光源.

3) 如何利用空間連貫性，讓相似的著色點共享重要性采樣的概率分布，攤銷計算量.