劉逸凡 徐 昆

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

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

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

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

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

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

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

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

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

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

1 直接光照與重要性采樣

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

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

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

(5)

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

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

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

2 加速可見(jiàn)性計(jì)算

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

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

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

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

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

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

相比于緩存1對(duì)1的可見(jiàn)性，Ulbrich等人[14]通過(guò)使用陰影圖記錄1對(duì)多的可見(jiàn)性結(jié)果.他們?cè)谖矬w表面離散地分布一些記錄點(diǎn)，每個(gè)記錄點(diǎn)存儲(chǔ)1張陰影圖.估計(jì)任意2點(diǎn)間的可見(jiàn)性時(shí)，尋找最近的陰影圖，然后將2點(diǎn)間的距離與陰影圖中的相應(yīng)值進(jìn)行比較.

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

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

(6)

(7)

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

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

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

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

Table 1 Analysis of Visibility Test Acceleration Methods表1 可見(jiàn)性測(cè)試加速方法比較

3 使用光源聚類(lèi)加速直接光照計(jì)算

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

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

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

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

Fig. 5 Lights clustering when evaluating VPLs lighting [18]圖5 估計(jì)VPLs光照時(shí)的光源聚類(lèi)[18]

3.1 基于樹(shù)的光源聚類(lèi)

Fig. 6 A light tree and three example lightcuts[20]圖6 1個(gè)光源樹(shù)和3個(gè)光源割[20]

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

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

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

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

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

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

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

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

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

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

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

3.2 基于矩陣的光源聚類(lèi)

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

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

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

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

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

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

Table 2 Analysis of Light Clustering Methods表2 光源聚類(lèi)方法比較

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

4 基于光源聚類(lèi)的重要性采樣

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

1) 采樣一個(gè)光源簇C；

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

3) 在光源l上采樣一個(gè)點(diǎn)y.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2012年Harada[60]提出在使用切片式著色法時(shí)對(duì)每個(gè)切片保守地估計(jì)最小最大深度，裁去影響區(qū)域?yàn)榭瞻椎墓庠?

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

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

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

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

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

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

6 總結(jié)與展望

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

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

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

針對(duì)多光源繪制問(wèn)題，未來(lái)的研究重點(diǎn)可能是3個(gè)方向：

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

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

3) 如何利用空間連貫性，讓相似的著色點(diǎn)共享重要性采樣的概率分布，攤銷(xiāo)計(jì)算量.