摘 要：當虛擬場景發(fā)生變化時，擴展的逐步求精算法作為一種快速的輻射度算法，大量減少了重新計算輻射度所花費的時間。對擴展的逐步求精算法進行研究，并利用OpenGL對算法進行了實現(xiàn)。通過在實驗中對虛擬場景的表面反射率和幾何屬性進行改變，獲得了一些證明算法有效性的數(shù)據(jù)，從而驗證了該算法的有效性。

關(guān)鍵詞：虛擬場景；輻射度；擴展的逐步求精算法；OpenGL

中圖分類號：TP274 文獻標識碼：A 文章編號：1004373X(2008)1616603

Implementation Research of Fast Radiosity Algorithm

WANG Xun，LI Changhua

(College of Information and Control Engineering，Xi′an University of Architecture and Technology，Xi′an，710055，China)

Abstract：Extended progressive refinement method as a fast algorithm of radiosity minimize the recomputation time after any virtual scene modification.In this paper，the extended progressive refinement method is studied and implemented in the way of OpenGL.Then the data which can prove the efficiency of the algorithm by changing scene reflectivity and scene geometry during experiment is obtained.In this way，the method is proved to be efficient.

Keywords：virtual scene;radiosity;extended progressive refinement method;OpenGL

輻射度方法作為一種實現(xiàn)照片級渲染效果的重要工具，在虛擬現(xiàn)實系統(tǒng)中已經(jīng)得到越來越廣泛的應用，特別是在建筑物虛擬展示和內(nèi)部裝修設計中的作用顯得尤為突出。但是在一個由若干個幾何元素描述的場景中，獨立視點的光照模型需要在預處理過程中進行計算并且顏色值也要分配到每一個面片的各個頂點上。這些虛擬場景看上去都很逼真，但是當進行交互式操作或是虛擬漫游時，由于場景幾何元素的變動，整個光照模型的處理過程都需要被重復進行，用于輻射度的計算將會產(chǎn)生昂貴的時間消耗。所以輻射度算法的性能優(yōu)良與否直接決定了虛擬現(xiàn)實系統(tǒng)的運行速度與場景質(zhì)量。

1 逐步求精迭代算法

逐步求精迭代算法^［1］很好地解決了在復雜漫射環(huán)境中求解全局光照模型的問題，在每一次迭代t中，擁有最多待輻射度的面片被選作輻射源面片（以下用St表示）ΔB.t－1St=max{ΔB.t－1i}。在每一次迭代t中每一面片i的輻射度和待輻射度分別可以用以下方程表示：

輻射度：B.ti=B.t－1i+ρiΔB.t－1StFiSt(1) 待輻射度：ΔB.ti=ΔB.t－1i+ρiΔB.t－1StFiSt(2)其中面片i的初始值為：B.0i=ΔB.0i=Ei，當一次迭代結(jié)束后輻射源面片的待輻射度ΔB.tSt=0。

如圖1所示的樹形結(jié)構(gòu)圖可以很直觀地表示出逐步求精迭代算法的運算過程。

圖1 逐步求精迭代算法樹形結(jié)構(gòu)圖圖1顯示了在3次迭代中求解面片i的輻射度的過程，其中面片的ID號用下角標表示，迭代次數(shù)用上角標表示。輻射源面片用St標記，其中t的值表示是第幾次迭代，每次迭代中被選中的輻射源面片的待輻射度都用圓圈進行標記。

2 基于動態(tài)場景的輻射度算法

逐步求精迭代算法用于靜態(tài)場景的輻射度求解時性能良好，但是在交互式設計的場景中，每次場景的改變都可能引起場景幾何、光源、表面材料屬性的變化，此時單純的逐步求精迭代算法就無法勝任。于是在逐步求精迭代算法的基礎上，產(chǎn)生一些適用于動態(tài)場景的輻射度算法。

2.1 基于表面屬性改變的算法

由于形狀因子為純幾何量，當場景中僅光源色彩、發(fā)光強度以及景物表面的反射率發(fā)生改變時，各景物面片間的形狀因子值將維持不變。此時，就沒有必要對形狀因子進行重復計算。Eric Chen給出了一個統(tǒng)一處理表面屬性和光源照明屬性變化的增量輻射度算法^［2］。當場景中只有少數(shù)幾個面片的漫反射系數(shù)改變時，先計算該面片的輻射度增量，然后像逐步求精輻射度算法那樣，將這些新增的輻射度能量向周圍環(huán)境輻射，直至環(huán)境中的光能分布重新趨于平衡。輻射度的增量值在一些情況下可能是負的。例如，當關(guān)閉一光源時，算法即從該光源向場景輻射負能量，每一個面片都要減掉由于該光源輻射所接受的來自該光源的能量^［3］。

假設初始面片的輻射度解由以下方程確定：Bi=Ei+ρi∑Nj=1BjFij(3)其中Bi為面片i所具有的總輻射度；Ei為面片i自身所具有的輻射度；ρi為漫反射系數(shù)；Bj為面片j向面片i輻射的能量；Fij為面片j對面片i的形狀因子。

設第i個面片的自身所具有的輻射度和漫反射系數(shù)分別改變?yōu)镋i′和ρi′，則第i個面片的新輻射度為：Bi′=Ei′+ρi′∑Nj=1BjFij(4) 將式（3），（4）兩式相減得到第i個面片的輻射度增量為：ΔBi=Bi′－Bi=(Ei′－Ei)+(ρi′－ρi)∑Nj=1BjFij

=(Ei′－Ei)+(ρi′－ρi)ρi(Bi－Ei)(5) 本式有意義的條件是ρi必須為非零值，即初始個面片的漫反射率限定為非零。

2.2 基于場景幾何改變的算法

場景幾何元素的改變會引起大部分形狀因子的改變，因而當場景中發(fā)生類似變化時輻射度的求解過程幾乎需要從頭開始。但當只有少數(shù)景物的幾何位置發(fā)生改變時，一些加速算法還是非常有效的。

Baum等曾經(jīng)提出一個基于動態(tài)環(huán)境的輻射度算法^［3］，該算法假設景物的移動路徑已經(jīng)被預先定義好，該方法利用半立方體算法標識由于物體的運動而可能改變的形狀因子，雖然該算法的效率是每次只需更新少量的形狀因子，但是由于它限定了物體的運動路徑，所以在實際應用中很難有用武之地。

Eric Chen提出一個有效的動態(tài)場景的輻射度算法^［2］。它的基本思想是，當場景幾何發(fā)生改變時，所有已向場景輻射過能量的面片都要被逐一回溯。對于每一面片，首先在舊的場景幾何條件下將它曾做出的場景貢獻消除，然后根據(jù)新的場景幾何將面片的總輻射度全部輻射出去。當所有這類面片處理完畢時，就可以繼續(xù)使用逐步求精迭代算法進行輻射度求解^［3］。

對光能重新分布的計算過程如下：B.Si=B.i－B.ui(6) 其中Bi為第i個面片的總輻射度；B.ui為待輻射度；B.Si為單位面積已向場景輻射過的能量。

場景的每一面片j上需要消除第i個面片所貢獻的輻射度，則修正后的面片輻射度為:Bj′=Bj－ρjB.SiFji j=1，2，…，N，j≠i(7) 然后依據(jù)新的場景幾何，重新計算面片i對面片j的輻射度貢獻，設在新的場景中面片j對面片i的新的形狀因子為F′ji，則第j個面片的輻射度增量為ρjB.iFji′。此時第j個面片的輻射度為：B.″j=Bj′+ρjBiFji′(8)3 擴展的逐步求精迭代方法

Eric Chen的增量輻射度算法在實際運用中被證明擁有較快的運算速度，然而仍舊不能滿足動態(tài)虛擬場景中實時性的要求，獲得所需的結(jié)果依然需要花費大量的時間。大量的CPU運算時間全部都浪費在重新計算那些在逐步求精迭代過程中已經(jīng)計算過的信息上。擴展的新算法在保留Eric Chen算法優(yōu)點的基礎上加入了一個輻射源鏈表（以下簡稱SL）和陰影—形狀因子鏈表（以下簡稱SFFL）用于記錄在光照模型預處理階段已經(jīng)計算過的信息，這樣當場景環(huán)境發(fā)生變化時可以更容易地識別和確定哪些面片的輻射度發(fā)生了變化并且加快了場景更新的速度。

下面詳細描述SL和SFFL的具體結(jié)構(gòu)組成：

所有的迭代信息都被記錄在輻射源鏈表中，而陰影和形狀因子的信息都被保存在SFFL鏈表中。輻射源鏈表是一個動態(tài)陣列，它的數(shù)據(jù)結(jié)構(gòu)組成如圖2所示：對于輻射度預處理過程中的每一次跌代t（1≤t≤n，n是跌代的總次數(shù)），迭代的相應信息都會被記錄到鏈表中的一個節(jié)點里。在某一次跌代t中，當一個輻射源面片被選中時，它相應的ID號和待輻射度都會被記錄在SL鏈表的一個節(jié)點中，如果這個面片在以后的跌代中再次被選為輻射源面片，那么它前一次被選中時的節(jié)點的next指針應該指向它下一次被選中時的節(jié)點，（如圖2所示，一個面片在第一次跌代和第三次跌代時都被選為輻射源面片，那么第一次跌代的節(jié)點的next指針就應該指向第三次跌代的節(jié)點）。SFFL項則存放著指向輻射源面片對應的SFFL鏈表的指針。節(jié)點的最后一項存儲了當場景發(fā)生改變時輻射源面片的增量輻射度。

圖2 SL鏈表如圖3在SFFL鏈表中對于每一次跌代，陰影測試線從輻射源面片的中點發(fā)出投向場景環(huán)境中的每一個面片的中點。對于所有的被輻射面片，如果它們與輻射源面片之間不存在遮擋物，那么它們與輻射源面片之間的形狀因子的信息都被存儲在SFFL鏈表中，否則給遮擋物分配一個ID號并且存儲到SFFL鏈表中。

圖3 SFFL鏈表可以看到，SFFL鏈表可以加快逐步求精迭代算法的求解過程。一旦某一面片被再次選為輻射源面片，那么它與場景中其他面片的形狀因子就可以被很快地搜索到并且被重復使用。

4 擴展算法的實現(xiàn)

下面代碼實現(xiàn)了當場景發(fā)生變化時擴展算法的處理過程：

Void FastRadiosity ( ) {

//搜索SL鏈表中的每個節(jié)點，找到增量輻射度D.j≠0的輻射源面片

for(j=1;j<=t;++j) {

if(D.j!=0)

//遍歷所有被輻射面片，將輻射源的增量輻射度傳播給面片

for(i=1;i<=PatchNum-1;++i)

{

//判斷面片i與輻射源面片間是否有遮擋

if(!SL(j)→SFFL(i)→Shadow)

{

//搜索SFFL鏈表，找到相應的形狀因子

FiSJ= SL(j)→SFFL(i)；

//改變后面片i的輻射度

B.newi=B.oldi+ρiD.jFiSj；

//改變后面片i的待輻射度

ΔB.newi=ΔB.oldi+ρiD.jFiSj；

} }

//改變后輻射源面片的待輻射度

ΔB.newj=ΔB.oldj+D.j；D.j=0；

} }

5 實驗結(jié)果

通過在個人機上使用OpenGL對算法進行實現(xiàn)和測試，得到了一些驗證算法有效性的數(shù)據(jù)。實驗以虛擬室內(nèi)環(huán)境為場景，場景由8 865個面片組成，輻射度預處理階段的迭代次數(shù)限定為100次。在繪制場景時刷新率可以達到13.1幀/秒，當在場景中移動某一物體時，重新繪制場景所需的時間為13.046 s，當改變場景的反射率時，重新繪制時間為0.7 s，符合實時繪制的要求。實驗所采用的軟硬件環(huán)境為：CPU ：AMD Athlon 2 800+1.80(GHz)；內(nèi)存：1 GB；顯卡：ATI Radeon 9550；操作系統(tǒng)：Windows XP。

6 總結(jié)與展望

新算法通過將輻射度預處理過程中產(chǎn)生的運算信息存儲在一個有效的數(shù)據(jù)結(jié)構(gòu)里，實現(xiàn)了對逐步求精迭代算法的擴展。經(jīng)過對算法進行實現(xiàn)，驗證了算法符合虛擬現(xiàn)實的要求并且適用于動態(tài)虛擬場景中的輻射度的求解，擴展后的算法更加簡潔高效，節(jié)省了大量的運算時間，使得場景更新更加流暢。由于在每次場景改變之前都必須等待上一次場景改變時產(chǎn)生的增量輻射度傳播結(jié)束，這就給場景更新造成了一定的延時，這是當前的算法還不能解決的問題，有待進一步研究。

參 考 文 獻

［1］Cohen M F，Chen S E，Wallace J.R，et al.A Progressive Refinement Approach to Fast Radiosity Image Generation［J］.Computer Graphics，1988，22:7584.

［2］Chen S E.Incremental Radiosity:An Extension of Progressive Radiosity to an Interactive Image Synthesis System\\.Computer Graphics，1990，24:135144.

［3］彭群生，鮑虎軍，金小剛.計算機真實感圖形的算法基礎［M］.北京:科學出版社，1990.

［4］Müller S，Schffel F.Fast Radiosity Repropagation for Interactive Virtual Evironments Using a ShadowFormFactorList［J］.Fifth EG Workshop on Rendering，1994:325342.

［5］Georage W D，Sillion X F，Greenberg D P.Radiosity Redistribution for Dynamic Environment［J］.IEEE Computer

Graphics and Applications，1990，10:2634.

作者簡介 王 峋 男，1981年出生，寧夏銀川人，西安建筑科技大學信息與控制工程學院，碩士研究生。主要研究方向為多媒體與網(wǎng)絡技術(shù)。

李昌華 男，西安建筑科技大學信息與控制工程學院，教授，博士生導師。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文