基于空間自適應(yīng)剖分的Lightcuts多光源聚類算法

袁昱緯，劉傳輝，全吉成，，王宏偉，吳晨

（1.海軍航空工程學(xué)院電子信息工程系，山東煙臺264001；2.空軍航空大學(xué)航空航天情報系，長春130022）

基于空間自適應(yīng)剖分的Lightcuts多光源聚類算法

袁昱緯1，劉傳輝1，全吉成1，2，王宏偉2，吳晨1

（1.海軍航空工程學(xué)院電子信息工程系，山東煙臺264001；2.空軍航空大學(xué)航空航天情報系，長春130022）

針對Lightcuts算法在面對大規(guī)模復(fù)雜光源時計算效率較低的問題，提出了一種基于空間自適應(yīng)剖分的Lightcuts多光源聚類算法。該算法采用二叉樹森林代替?zhèn)鹘y(tǒng)Lightcuts算法中的二叉樹，并提出自適應(yīng)的視景體劃分方法對三維場景進行剖分，通過構(gòu)建包含“簇-光源”對的列表，快速剔除與當(dāng)前渲染點無關(guān)的光源，同時利用空間聚類的相似性減少“光源割”搜索過程中的重復(fù)計算。實驗結(jié)果表明，與傳統(tǒng)方法相比，文章提出的算法在“光源割”計算階段能夠?qū)⑺阉鞑綌?shù)平均減少30.71%～42.09%，繪制時間平均縮短28.35%～34.84%，有效地加快了Light?cuts算法的計算速度，提高了多光源三維場景的繪制效率。

多光源；Lightcuts；自適應(yīng)空間剖分；二叉樹森林；場景繪制

隨著三維場景繪制技術(shù)應(yīng)用的普及，人們對多光源環(huán)境下的繪制性能要求越來越高，如采用傳統(tǒng)的光源累加計算方法，會導(dǎo)致光照計算時間與光源數(shù)量成正比，并且較大的時間開銷成為制約算法效率提升的關(guān)鍵。

多光源環(huán)境下的場景繪制加速方法主要有：基于分類管理的方法[1]、基于空間層次結(jié)構(gòu)的方法[2]、基于并行處理的方法[3-4]和基于空間聚類的方法[5]等，但都各有利弊。此外，Hollander等[6]研究了多光源環(huán)境下的實時全局光照，可以近似計算大量光源照射下的幾何體偽影，但無法為少量光源照射的幾何體產(chǎn)生精確的陰影。Sun等[7]基于稀疏體素八叉樹提出混合實時GI算法來實現(xiàn)多光源全局光照計算，但多光源的組織管理沒有進行優(yōu)化。Olsson等[8]提出的平鋪陰影技術(shù)支持包含大規(guī)模光源的三維場景繪制，該算法能夠大幅度提高前向渲染和延遲渲染的效率。Olsson等[9]還提出了基于虛擬陰影圖的算法來支撐大規(guī)模光源的繪制，能夠快速剔除場景中與光照計算無關(guān)的幾何體，但沒有提高多光源本身的光照計算效率。

基于聚類的多光源場景繪制加速算法是通過對光源進行聚類，并采用代表光源表示光源集合，在保證繪制質(zhì)量的前提下盡量減少參與計算的光源數(shù)量，降低光照計算的計算量，其中最典型的算法是Walter等[10]提出的Lightcuts算法。Lightcuts算法基于二叉樹進行聚類，其關(guān)鍵在于繪制時如何高效地在二叉樹中搜索“光源割”。Condon等[11]基于Lightcuts算法提出了預(yù)計算的方案，提高了“光源割”的搜索效率，但由于存儲開銷較大，不適合大規(guī)模場景的繪制。Walter等[12]和Laurent等[13]還分別提出了雙向Lightcuts算法和前向Lightcuts算法。王光偉等[14]利用空間的連續(xù)性改進了Lightcuts算法，基于空間聚類的思想減少了“光源割”的搜索計算，但當(dāng)光源和場景中的幾何體分布極不均勻時，其加速效果并不明顯。

本文基于Lightcuts算法，采用二叉樹森林代替?zhèn)鹘y(tǒng)Lightcuts算法中的二叉樹結(jié)構(gòu)，并提出自適應(yīng)的視景體劃分方案對三維場景進行剖分，通過構(gòu)建包含“簇-光源”對的列表，實現(xiàn)了一種基于空間自適應(yīng)剖分的Lightcuts多光源聚類算法，不僅能夠快速剔除與當(dāng)前渲染點無關(guān)的光源，而且能夠利用相鄰渲染點的“光源割”搜索路徑，有效降低多光源環(huán)境下的計算量并減少繪制時間，提高多光源三維場景的繪制效率。

1 改進的Lightcuts多光源聚類算法

1.1 Lightcut算法原理

Lightcuts算法由多光源聚類和計算“光源割”2部分組成。

在光源的聚類部分，按照光源依據(jù)權(quán)值最小原則聚集成二叉樹。2光源間的權(quán)值與距離、亮度相關(guān)，權(quán)值的算法見文獻[10]，本文不再贅述。構(gòu)建過程是每次選取權(quán)值最小的2個光源，并選擇其中1個作為該聚類的代表，然后將代表光源與其他剩下的光源一起繼續(xù)搜索權(quán)值最小的光源，并加入到二叉樹中，直到只有最后1個光源，完成聚類過程。該過程形成的層次化結(jié)構(gòu)的二叉樹稱為光源樹，聚類過程如圖1所示。

在計算“光源割”部分，是在二叉樹結(jié)構(gòu)里找到場景繪制所需的代表光源。由于場景中某個幾何體往往需要計算多個光源的光照，為避免遍歷所有光源，Lightcuts算法根據(jù)韋伯-費德勒定理[15]，在閾值范圍內(nèi)，使用光源樹中的一些光源聚類的代表光源，來減少參與計算的光源數(shù)目。在光源樹的自頂向下搜索過程中，若某個節(jié)點的子節(jié)點的最大可能亮度在該節(jié)點的全部光源亮度中大于閾值范圍的上限，則繼續(xù)向該子節(jié)點搜索，直至找到小于閾值范圍的子節(jié)點或到達葉子節(jié)點，這個過程叫作計算“光源割”。

計算“光源割”的過程中，需要先確定多光源的二叉樹結(jié)構(gòu)中某一節(jié)點C對渲染點x的亮度的貢獻Lc(x)，以及節(jié)點C的某個子節(jié)點光源理論上所能產(chǎn)生的亮度最大值Eupperbound。

式（1）中：x為渲染點；M為材質(zhì)因子；w為視點方向；G為幾何因子；V為可見性；I為光源亮度；i為實際光源；j為代表光源；為節(jié)點C包含光源的亮度之和。

式（2）中：Mmax為材質(zhì)因子的上限；Gmax為幾何因子的上限。

此外，由于V取上限值，則令V=1，因此在式（2）中可以略去。

最后，根據(jù)韋伯-費德勒定理，渲染點x的亮度誤差閾值EX由下式確定：

最后，通過判斷Eupperbound和EX的大小關(guān)系來確定節(jié)點是否需要繼續(xù)分裂。

1.2 采用二叉樹森林取代單獨的二叉樹

在傳統(tǒng)的基于Lightcuts算法的多光源聚類中，場景中的光源采用二叉樹結(jié)構(gòu)進行組織和聚類。然而在實際應(yīng)用中發(fā)現(xiàn)，有些場景的光源數(shù)量雖然很多，但由于光源的影響范圍有限，部分光源的影響范圍之間并沒有重疊，此時如果將它們依據(jù)權(quán)值最小原則聚類在二叉樹結(jié)構(gòu)中，雖然能夠在后續(xù)計算“光源割”時再將它們分開，但是這需要額外的計算量。因此，為了減少二叉樹結(jié)構(gòu)的層級，同時適應(yīng)后文提出的基于空間自適應(yīng)剖分的多光源聚類算法，降低搜索時的計算量，本文采用二叉樹森林代替單獨二叉樹對光源進行聚類：

1）按照傳統(tǒng)Lightcuts算法找到權(quán)值最小的2個光源之后，不直接將其聚類組成二叉樹，而是判斷2個光源的權(quán)值是否大于某一閾值，該閾值根據(jù)場景實際情況，由兩光源的影響范圍恰好重疊時的權(quán)值進行確定；

2）若小于該閾值，則按照Lightcuts算法對兩光源進行聚類，并指定代表光源；若大于該閾值，則不進行聚類，分別按照兩棵二叉樹進行組織；

3）重復(fù)上述聚類過程，直至所有代表光源之間的權(quán)值都大于閾值，則停止對光源二叉樹的聚類，得到二叉樹森林，如圖2所示，二叉樹森林中每棵二叉樹的根節(jié)點都是該樹各自的代表光源。

1.3 采用視景體自適應(yīng)空間剖分的多光源聚類

由于三維場景中可能存在的光源數(shù)量較多，且照射范圍有限，經(jīng)過基于Lightcuts的多光源聚類，可能得到包含較多棵二叉樹的二叉樹森林，也就是說聚類后仍然存在較多的光源或代表光源。為了在渲染時進一步快速剔除與渲染點無關(guān)的光源，同時利用場景的空間相關(guān)性，本文提出采用視景體自適應(yīng)空間剖分的多光源聚類方法。

在繪制大規(guī)模三維場景時一般采用基于視點的空間剖分方法，以快速剔除不必要的計算。但是如果采用均勻剖分的方法，會導(dǎo)致因為分辨率不能同時適應(yīng)場景的所有區(qū)域，而產(chǎn)生較嚴重的欠采樣或過采樣現(xiàn)象。

本文借鑒文獻[16]提出的場景剖分方法，進一步考慮到屏幕像素分辨率為rS1×rS2，且rS1和rS2可以不相等的情況，提出將視景體的自適應(yīng)劃分方法改進為：

式（4）中：Ci為劃分平面在深度方向z上的坐標(biāo)；γ為視景體的視角；第i個劃分區(qū)域所對應(yīng)光照計算的分辨率為ri×ri，rS1、rS2、ri和γ都是已知量。

特別地，視景體劃分的初始點C0=n，劃分的終點為場景的邊界。

在確定每個劃分區(qū)域?qū)?yīng)的光照計算分辨率的情況下，可以基于式（4）的迭代關(guān)系，從視景體劃分的起始點開始，自適應(yīng)地計算出各個劃分平面在視景體深度方向的位置坐標(biāo)，且這種劃分方式下的光照計算走樣程度最小[16]，而不是根據(jù)經(jīng)驗來確定劃分參數(shù)，如文獻[17-18]。

基于視景體的場景分割示意圖見圖3。

上述劃分方法將視景體細分成不同深度的條帶狀空間，然后在與深度方向垂直的平面上進行規(guī)則二維網(wǎng)格分割，在空間中形成自相似的子視景體，完成對三維場景基于視景體的自適應(yīng)空間剖分。這些剖分形成的子視景體在本文中稱為簇，如圖4所示，其中藍色的簇表示其包含幾何體，黃色范圍表示光源的光照范圍。

在完成上述視景體的自適應(yīng)空間剖分后，本文將場景中的所有幾何體按簇進行組織，確定視景體中哪些簇包含幾何體。一旦某個簇確定被幾何體占用，則給該簇分配光源或光源樹。如果存在某個光源或光源樹能夠?qū)υ摯禺a(chǎn)生影響，即該簇位于光源的影響范圍內(nèi)，就產(chǎn)生一個“簇-光源”對，完成一次采用視景體自適應(yīng)空間剖分的光源（樹）聚類，如圖4中與簇C0關(guān)聯(lián)的光源（樹）包括L0和L1。繼續(xù)上述光源（樹）的聚類過程，直至所有簇都完成與光源（樹）的關(guān)聯(lián)。每個簇包含幾何體的數(shù)量和分辨率則可以通過視景體細分時簇的大小來調(diào)節(jié)。

為記錄每個簇的“簇-光源”對，本文建立一個包含“簇-光源”對的列表，圖5所示為圖4的“簇-光源”對列表。應(yīng)注意的是，某些簇可能被分配不止1個光源（樹），某些簇也可能由于位于光源范圍之外，不存在“簇-光源”對，并且這些“簇-光源”對支持并行地生成。

上述包含“簇-光源”對應(yīng)關(guān)系的列表將每個簇與所有可能影響其包含幾何體的光源聯(lián)系在一起，同時為視景體區(qū)域的幾何體提供一個盡可能小的、能夠?qū)ζ洚a(chǎn)生影響的光源集合。因此，在對場景中的幾何體進行光照計算和渲染繪制時，通過列表查找簇對應(yīng)的光源（樹），僅須采用相關(guān)的光源（樹）對簇中的幾何體進行光照和陰影計算，無關(guān)光源無須計算即可快速剔除，從而有效避免遍歷無關(guān)的光源，提高場景繪制時的光照計算效率。

1.4 基于空間剖分的Lightcuts“光源割”計算

在通過“簇-光源”對列表排除無關(guān)光源后，需要針對各個簇對應(yīng)的光源樹采用Lightcuts算法搜索渲染點的“光源割”。由式（1）、（2）可以看出，渲染點的材質(zhì)、可見性和幾何特征等屬性決定了其Lc(x,w)和Eupperbound，而絕大部分三維場景具有空間的相似性，也就是說空間區(qū)域相鄰的渲染點具有相似的屬性信息，計算得到的“光源割”也是相似的。因此，本文利用空間相似性，在計算光源割時，采用共享相鄰渲染點“光源割”路徑的思路，提高“光源割”的計算速度。

在對三維場景進行分割時，本文采用第1.3節(jié)的視景體自適應(yīng)剖分方案。對于剖分過程的某個格網(wǎng)，如果其中的所有渲染點在材質(zhì)和幾何特征等方面都很相似，則不繼續(xù)剖分；如果其中的渲染點在材質(zhì)和幾何特征等方面有差異，則繼續(xù)細分，直至達到分辨率要求。在對渲染點是否相似的判定上，本文約定如果2個渲染點具有相同的材質(zhì)和可見性，且模型面片的法線方向變化量不超過10°，則認為它們是相似的。

由于場景進行了基于相似性的空間剖分，簇內(nèi)的渲染點在計算“光源割”時可以利用簇內(nèi)的相似性，減少公共“光源割”的計算，只計算2個光源割的差異部分，以此來減少“光源割”的計算量。具體方法如下：

1）在同一個簇內(nèi)，計算渲染點的“光源割”時共享同一個存儲堆棧；

2）如當(dāng)前渲染點是該簇內(nèi)的第一個渲染點，即初始點時，由式（1）、（2）計算相關(guān)渲染點的亮度上限值和閾值，得到“光源割”，計算方法與Lightcuts算法相同，并將“光源割”的搜索路徑存放在堆棧中；

3）如果在當(dāng)前點渲染時堆棧中已存在“光源割”，則以堆棧中上一次計算的“光源割”為初始“光源割”，采用回溯或繼續(xù)搜索的方式計算當(dāng)前渲染點的“光源割”，并將最新的“光源割”壓入堆棧中存放；

4）循環(huán)3），直至該簇內(nèi)所有渲染點計算完畢。簇內(nèi)所有渲染點的“光源割”都可以在堆棧中獲得。

因此，當(dāng)?shù)谝粋€渲染點正常計算其“光源割”并壓入堆棧后，該簇內(nèi)接下來的渲染點可以利用上一次“光源割”的搜索路徑繼續(xù)進行閾值判斷，確定是否需要繼續(xù)向下分裂，并對“光源割”進行動態(tài)更新，而不需要每次都重新搜索整個二叉樹。同時，由于簇內(nèi)的空間相似性，大部分搜索路徑是相同的，因而能夠減少在計算“光源割”時的大量搜索運算。

但是，在利用上一次計算的“光源割”時，會發(fā)現(xiàn)上一次計算的“光源割”可能已經(jīng)滿足閾值要求，沒有必要繼續(xù)分裂，甚至當(dāng)前節(jié)點的父節(jié)點或更高層級的節(jié)點也都已滿足閾值要求，上面若干層節(jié)點都沒有必要分裂。在這種情況下，雖然不會降低渲染的質(zhì)量，但是會使參與光照計算的光源數(shù)量增加，增大渲染時的計算開銷。為了盡量避免這種情況的發(fā)生，本文提出在計算當(dāng)前渲染點的“光源割”時，首先判斷堆棧中“光源割”的分割情況。如果欠分割，則繼續(xù)對其進行分割，考慮其子節(jié)點所代表的光源；如果過分割，則進行回溯，回溯到的節(jié)點層級需要滿足：①該層級節(jié)點的父節(jié)點大于式（3）所述的誤差閾值；②該層級節(jié)點恰好能滿足閾值要求。

2 實驗結(jié)果與分析

本文實驗平臺的軟硬件環(huán)境為：CPU Intel Core i7-67003.4 GHz，RAM32 GB，NVIDIA GTX 1070，Windows 7 ultimate x64操作系統(tǒng)。實驗素材包括3個多光源場景：Corridor1、Corridor2和Cubes場景。Corridor1場景包含30個靜態(tài)光源，Corridor2場景包括30個靜態(tài)光源和2個在空間中勻速運動的動態(tài)光源，Cubes場景包含256個光源，光源均勻分布在場景上方，且照射范圍相同。上述實驗場景渲染后的效果如圖6所示。

將本文提出的基于空間自適應(yīng)剖分的Lightcuts算法與傳統(tǒng)Lightcuts算法對比，分別構(gòu)建二叉樹森林和二叉樹結(jié)構(gòu)。在計算“光源割”的過程中，實驗根據(jù)韋伯-費德勒定理，亮度的誤差閾值的系數(shù)選取為0.02。分別計算渲染點在對應(yīng)“光源割”中的平均節(jié)點數(shù)量、平均搜索步數(shù)和繪制所需時間，如表1所示。渲染時，每個場景在屏幕空間的分辨率設(shè)定為1K×1K，不使用GPU的并行計算。

表1 本文提出的改進方法與傳統(tǒng)方法的對比Tab.1 Performance comparison between traditional lightcuts algorithm and our method

從表1中可以看出，雖然光源割的平均節(jié)點數(shù)變化不大，但是在平均搜索步數(shù)方面，本文提出的改進的Lightcuts算法與傳統(tǒng)Lightcuts算法相比，在3個實驗場景中分別減少了42.09%、30.71%和33.52%，平均繪制時間分別減少了34.84%、28.35%和31.31%。這是因為本文算法能夠利用空間自適應(yīng)剖分在簇內(nèi)形成的相關(guān)性，避免對每個渲染點都進行完整的“光源割”計算，減少了相同路徑的重復(fù)搜索，降低了計算開銷，具有很好的加速效果，同時“簇-光源”對列表能夠有效剔除無關(guān)光源對繪制速度的影響，縮短繪制的時間。

Cubes場景中的單個光源影響范圍較小，光源之間重疊的數(shù)量也不多，在對該場景進行本文改進的Lightcuts聚類時，二叉樹森林中二叉樹的數(shù)量較多，每個光源樹的層級較少，因此“光源割”的節(jié)點數(shù)和搜索節(jié)點數(shù)較少，過分割的節(jié)點數(shù)也相對較少，效率提高最明顯，但由于Cubes場景中光源總數(shù)最多，場景規(guī)模最大，其繪制消耗的總時間最多。而另外2個場景Corridor1和Corridor2中光源相互重疊較多，二叉樹森林中二叉樹的數(shù)量較少，在每棵二叉樹中需要搜索的節(jié)點數(shù)量就相對較多，本文改進算法對繪制效率的提高幅度相對較小。

為驗證本文提出的基于空間自適應(yīng)剖分的Lightcuts算法在利用空間相關(guān)性方面的優(yōu)勢，除傳統(tǒng)Lightcuts算法，本文還與同樣基于空間相關(guān)性的Lightcuts改進算法進行了比較，包括文獻[14]提出的基于空間聚類增強的Lightcuts算法（S.C.Lightcuts）和文獻[19]提出的Coherence Lightcuts算法（C.Lightcuts）。在實驗過程中，以Cubes場景為例，視點飛過場景上方，分別統(tǒng)計3種Lightcuts改進算法的平均搜索節(jié)點數(shù)和繪制時間，并計算它們相對于傳統(tǒng)Lightcuts算法的減少率，如圖7、8所示，圖中的橫坐標(biāo)為在場景中連續(xù)變化的視角對應(yīng)的每一幀，縱坐標(biāo)分別為搜索節(jié)點數(shù)量的減少率和繪制時間的減少率。減少率的計算式為：

式（5）中：Na為對比算法的相關(guān)指標(biāo)（如搜索節(jié)點數(shù)量和繪制時間）；Nb為傳統(tǒng)Lightcuts算法的相關(guān)指標(biāo)；R為減少率，R越大說明相關(guān)指標(biāo)減小越多，性能提高越大。

與S.C.Lightcuts算法相比，本文提出的改進算法在繪制時間和搜索節(jié)點數(shù)量方面都明顯更優(yōu)。這是因為該文獻[14]的方法將屏幕空間分為若干像素塊，每個像素塊內(nèi)部的渲染點的光照采用插值算法來快速求得，可以節(jié)省一定的光照計算時間，但是每個像素塊需要分別建立局部“光源樹”，并且需要在每個像素塊的4個角分別計算“光源割”，因而文獻方法在搜索節(jié)點數(shù)量上的減少并不明顯。而本文算法不僅可以利用每個剖分區(qū)域內(nèi)上一個渲染點的光源割，避免相同遍歷路徑的重復(fù)搜索，而且還優(yōu)化了亮度貢獻的計算，因而本文算法可以獲得更高的搜索節(jié)點數(shù)量減少率和繪制時間減少率。

與C.Lightcuts算法相比，該方法在搜索節(jié)點數(shù)量方面明顯優(yōu)于本文算法，這是由于文獻[19]對算法搜索過程進行了改進，通過對屏幕空間的剖分，將每個剖分單元看作一個整體計算“光源割”，剖分單元內(nèi)部的所有渲染點僅需進行一次“光源割”的搜索計算，因而可以獲得更高的搜索節(jié)點減少率，但該算法僅能減少搜索的計算，對于Lightcuts算法中的亮度貢獻計算并沒有進行改進，因而其繪制時間減少率仍然低于本文提出的改進Lightcuts算法。

綜上所述，本文提出的基于空間自適應(yīng)剖分的Lightcuts算法能夠有效提高多光源環(huán)境下的三維場景繪制速度，且性能比較穩(wěn)定。

3 結(jié)論

本文采用二叉樹森林代替?zhèn)鹘y(tǒng)Lightcuts算法中的二叉樹，并提出自適應(yīng)的視景體劃分方案對三維場景進行空間剖分，通過構(gòu)建包含“簇-光源”對的列表，實現(xiàn)了一種基于空間自適應(yīng)剖分的Lightcuts多光源聚類算法，不僅能快速剔除與當(dāng)前渲染點無關(guān)的光源，且能有效利用空間聚類的相似性減少搜索“光源割”的計算量。

與傳統(tǒng)方法比，本文的算法在計算“光源割”階段能將搜索步數(shù)平均減少30.71%～42.09%，繪制時間平均縮短28.35%～34.84%，提高了三維場景渲染效率。

[1]SHIRLEY P，WANG C，ZIMMERMAN K.Monte Carlo techniques for direct lighting calculations[J].ACM Transactions on Graphics，1996，15（1）：1-36.

[2]PAQUETTE E，POULIN P，DRETTAKIS G.A light hierarchy for fast rendering of scenes with many lights[J]. Computer Graphics Forum，1998，17（3）：63-74.

[3]閆志.面向可編程著色器的多光源加速算法研究與實現(xiàn)[D].濟南：山東大學(xué)，2014. YAN ZHI.Research and implementation of multi-light source accelerating algorithm for programmable shaders [D].Jinan：Shangdong University，2014.（in Chinese）

[4]張薇薇，楊懌菲.多光源并行化算法的實現(xiàn)[J].火力與指揮控制，2016，41（3）：111-115. ZHANG WEIWEI，YANG YIFEI.Study and implementation of lighting parallelization algorithm[J].Fire Control &Command Control，2016，41（3）：111-115.（in Chinese）

[5]HUO Y，WANG R，JIN S，et al.A matrix sampling-andrecovery approach for many-lights rendering[J].ACM Transactions on Graphics，2015，34（6）：1-12.

[6]HOLLANDER M，RITSCHEL T，EISEMANN E，et al. ManyLoDs：parallel many-view level-of-detail selection for real-time global illumination[J].Computer Graphics Forum，2011，30（4）：1233-1240.

[7]SUN C，AGU E.Many-lights real time global illumination using sparse voxel octree[C]//International Symposium on Visual Computing.Germany：Springer International Publishing，2015：150-159.

[8]OLSSON O，ASSARSSON U.Tiled shading[J].Journal of Graphics Tools，2011，15（4）：235-251.

[9]OLSSON O，BILLETER M，SINTORN E，et al.More efficient virtual shadow maps for many lights[J].IEEE Transactions on Visualization and Computer Graphics，2015，21（6）：701-713.

[10]WALTER B，F(xiàn)ERNANDEZ S，ARBREE A，et al.Lightcuts：a scalable approach to illumination[J].ACM Transactions on Graphics，2005，24（3）：1098-1107.

[11]CONDON T，WALTER B，BALA K.Precomputed&hybrid variants of lightcuts[R].New York：Cornell University，2010.

[12]WALTER B，KHUNGURN P，BALA K.Bidirectional lightcuts[J].Acm Transactions on Graphics，2012，31（4）：1-11.

[13]LAURENT G，DELALANDRE C，DE LA RIVIERE G，et al.Forward light cuts：a scalable approach to real-time global illumination[J].Computer Graphics Forum，2016，35（4）：79-88.

[14]王光偉，謝國富，王文成.基于空間聚類增強Lightcuts的光照計算[J].計算機學(xué)報，2013，36（11）：2364-2370. WANG GUANGWEI，XIE GUOFU，WANG WENCHENG.Enhancing illumination computation of lightcuts with spatial coherence[J].Chinese Journal of Computers，2013，36（11）：2364-2370.（in Chinese）

[15]BLACKWELL H R.Luminance difference thresholds [M].Berlin：Springer International Publishing AG，1972：78-101.

[16]陳國棟，葉東文，黨琪琪.混合場景中陰影繪制方法研究[J].計算機工程，2016，42（2）：242-248. CHEN GUODONG，YE DONGWEN，DANG QIQI.Research on shadow rendering method in hybrid scene[J]. Computer Engineering，2016，42（2）：242-248．[17]劉松平，肖德貴.陰影繪制中的PSSM與VSM混合算法[J].計算機工程，2015，41（2）：228-233. LIU SONGPING，XIAO DEGUI.Hybrid algorithm of PSSM and VSM in shadow rendering[J].Computer Engineering，2015，41（2）：228-233.（in Chinese）

[18]ZHANG F，SUN H，XU L，et al.Parallel-split shadow maps for large-scale virtual environments[C]//Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications.Hongkong：DBLP，2006：311-318.

[19]BODT T D，DUTRé P.Coherent lightcuts[D].Belgium：University of Leuven，2008.

Lightcuts Multi-Light Source Clustering Algorithm Based on Adaptive Space Subdivision

YUAN Yuwei1,LIU Chuanhui1,QUAN Jicheng1,2,WANG Hongwei2,WU Chen1
（1.Department of Electronic and Information Engineering,NAAU,Yantai Shandong 264001,China; 2.Department of Aeronautic and Astronautic Intelligence,Aviation University of Air Force,Changchun 130022,China）

In order to overcome the shortcomings of low efficiency of lightcuts algorithm when dealing with plenty of com?plex light sources,a lightcuts multi-source clustering algorithm based on adaptive space subdivision was proposed.Binary tree forest that was used in this algorithm,replaced the binary tree in traditional lightcuts algorithm,and a scheme of adap?tive spatial subdivision based on view frustum was proposed to subdivide the 3D scene.For purpose of quickly culling the light sources which was irrelevant to current rendering point,a list of“cluster-light”pairs was built.At the same time,the repeated computation in the process of finding cuts was reduced based on the similarity of space clustering.The experimen?tal results showed that,compared with the traditional method,the algorithm that was proposed in this paper could reduce the number of search steps by 30.71%-42.09%averagely in the stage of finding cut,and reduce the rendering time by 28.35%-34.84%averagely.It could accelerate the calculation speed of lightcuts algorithm significantly,and improve the rendering efficiency of multiple light source in 3D scene.

multiple light sources;lightcuts;adaptive space subdivision;binary tree forest;scene rendering

TP391.9

A

1673-1522（2017）02-0181-06

10.7682/j.issn.1673-1522.2017.02.001

2017-02-21；

2017-03-12

國家自然科學(xué)基金資助項目（61301233）；吉林省自然科學(xué)基金資助項目（20130101069JC）

袁昱緯（1988-），男，博士生。