快速辐射度算法的实现研究

摘 要：当虚拟场景发生变化时，扩展的逐步求精算法作为一种快速的辐射度算法，大量减少了重新计算辐射度所花费的时间。对扩展的逐步求精算法进行研究，并利用OpenGL对算法进行了实现。通过在实验中对虚拟场景的表面反射率和几何属性进行改变，获得了一些证明算法有效性的数据，从而验证了该算法的有效性。

关键词：虚拟场景；辐射度；扩展的逐步求精算法；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

辐射度方法作为一种实现照片级渲染效果的重要工具，在虚拟现实系统中已经得到越来越广泛的应用，特别是在建筑物虚拟展示和内部装修设计中的作用显得尤为突出。但是在一个由若干个几何元素描述的场景中，独立视点的光照模型需要在预处理过程中进行计算并且颜色值也要分配到每一个面片的各个顶点上。这些虚拟场景看上去都很逼真，但是当进行交互式操作或是虚拟漫游时，由于场景几何元素的变动，整个光照模型的处理过程都需要被重复进行，用于辐射度的计算将会产生昂贵的时间消耗。所以辐射度算法的性能优良与否直接决定了虚拟现实系统的运行速度与场景质量。

1 逐步求精迭代算法

逐步求精迭代算法［1］很好地解决了在复杂漫射环境中求解全局光照模型的问题，在每一次迭代t中，拥有最多待辐射度的面片被选作辐射源面片（以下用St表示）ΔB.t－1St=max{ΔB.t－1i}。在每一次迭代t中每一面片iУ姆射度和待辐射度分别可以用以下方程表示：

辐射度：ИB.ti=B.t－1i+ρiΔB.t－1StFiSt(1)И 待辐射度：ИИΔB.ti=ΔB.t－1i+ρiΔB.t－1StFiSt(2)И其中面片i的初始值为：B.0i=ΔB.0i=Ei，当一次迭代结束后辐射源面片的待辐射度ΔB.tSt=0。

如图1所示的树形结构图可以很直观地表示出逐步求精迭代算法的运算过程。

图1 逐步求精迭代算法树形结构图图1显示了在3次迭代中求解面片i的辐射度的过程，其中面片的ID号用下角标表示，迭代次数用上角标表示。辐射源面片用StП昙牵其中t的值表示是第几次迭代，每次迭代中被选中的辐射源面片的待辐射度都用圆圈进行标记。

2 基于动态场景的辐射度算法

逐步求精迭代算法用于静态场景的辐射度求解时性能良好，但是在交互式设计的场景中，每次场景的改变都可能引起场景几何、光源、表面材料属性的变化，此时单纯的逐步求精迭代算法就无法胜任。于是在逐步求精迭代算法的基础上，产生一些适用于动态场景的辐射度算法。

2.1 基于表面属性改变的算法

由于形状因子为纯几何量，当场景中仅光源色彩、发光强度以及景物表面的反射率发生改变时，各景物面片间的形状因子值将维持不变。此时，就没有必要对形状因子进行重复计算。Eric Chen给出了一个统一处理表面属性和光源照明属性变化的增量辐射度算法［2］。当场景中只有少数几个面片的漫反射系数改变时，先计算该面片的辐射度增量，然后像逐步求精辐射度算法那样，将这些新增的辐射度能量向周围环境辐射，直至环境中的光能分布重新趋于平衡。辐射度的增量值在一些情况下可能是负的。例如，当关闭一光源时，算法即从该光源向场景辐射负能量，每一个面片都要减掉由于该光源辐射所接受的来自该光源的能量［3］。

假设初始面片的辐射度解由以下方程确定：ИBi=Ei+ρi∑Nj=1BjFij(3)И其中Bi为面片i所具有的总辐射度；Ei为面片i自身所具有的辐射度；ρi为漫反射系数；Bj为面片j向面片i辐射的能量；Fij为面片j对面片i的形状因子。

设第i个面片的自身所具有的辐射度和漫反射系数分别改变为Ei′和ρi′,则第iЦ雒嫫的新辐射度为：ИBi′=Ei′+ρi′∑Nj=1BjFij(4)И 将式（3），（4）两式相减得到第i个面片的辐射度增量为：ИИΔBi=Bi′－Bi=(Ei′－Ei)+(ρi′－ρi)∑Nj=1BjFij

=(Ei′－Ei)+(ρi′－ρi)ρi(Bi－Ei)(5)И 本式有意义的条件是Е血iП匦胛非零值，即初始个面片的漫反射率限定为非零。

2.2 基于场景几何改变的算法

场景几何元素的改变会引起大部分形状因子的改变,因而当场景中发生类似变化时辐射度的求解过程几乎需要从头开始。但当只有少数景物的几何位置发生改变时，一些加速算法还是非常有效的。

Baum等曾经提出一个基于动态环境的辐射度算法［3］，该算法假设景物的移动路径已经被预先定义好，该方法利用半立方体算法标识由于物体的运动而可能改变的形状因子，虽然该算法的效率是每次只需更新少量的形状因子，但是由于它限定了物体的运动路径，所以在实际应用中很难有用武之地。

Eric Chen提出一个有效的动态场景的辐射度算法［2］。它的基本思想是，当场景几何发生改变时，所有已向场景辐射过能量的面片都要被逐一回溯。对于每一面片，首先在旧的场景几何条件下将它曾做出的场景贡献消除，然后根据新的场景几何将面片的总辐射度全部辐射出去。当所有这类面片处理完毕时，就可以继续使用逐步求精迭代算法进行辐射度求解［3］。

对光能重新分布的计算过程如下：ИB.Si=B.i－B.ui(6)И 其中Bi为第i个面片的总辐射度；B.ui为待辐射度；B.Si为单位面积已向场景辐射过的能量。

场景的每一面片j上需要消除第iЦ雒嫫所贡献的辐射度，则修正后的面片辐射度为:ИBj′=Bj－ρjB.SiFji j=1，2,…,N，j≠i(7)И 然后依据新的场景几何，重新计算面片i对面片j的辐射度贡献，设在新的场景中面片j对面片i的新的形状因子为F′ji，则第j个面片的辐射度增量为ρjB.iFji′。此时第jЦ雒嫫的辐射度为：ИB.″j=Bj′+ρjBiFji′(8)И3 扩展的逐步求精迭代方法

Eric Chen的增量辐射度算法在实际运用中被证明拥有较快的运算速度，然而仍旧不能满足动态虚拟场景中实时性的要求，获得所需的结果依然需要花费大量的时间。大量的CPU运算时间全部都浪费在重新计算那些在逐步求精迭代过程中已经计算过的信息上。扩展的新算法在保留Eric Chen算法优点的基础上加入了一个辐射源链表（以下简称SL）和阴影―形状因子链表（以下简称SFFL）用于记录在光照模型预处理阶段已经计算过的信息，这样当场景环境发生变化时可以更容易地识别和确定哪些面片的辐射度发生了变化并且加快了场景更新的速度。

下面详细描述SL和SFFL的具体结构组成：

所有的迭代信息都被记录在辐射源链表中，而阴影和形状因子的信息都被保存在SFFL链表中。辐射源链表是一个动态阵列，它的数据结构组成如图2所示：对于辐射度预处理过程中的每一次跌代t（1≤t≤n，n是У代的总次数），迭代的相应信息都会被记录到链表中的一个节点里。在某一次跌代t中，当一个辐射源面片被选中时，它相应的ID号和待辐射度都会被记录在SL链表的一个节点中，如果这个面片在以后的跌代中再次被选为辐射源面片，那么它前一次被选中时的节点的next指针应该指向它下一次被选中时的节点，（如图2所示，一个面片在第一次跌代和第三次跌代时都被选为辐射源面片，那么第一次跌代的节点的next指针就应该指向第三次跌代的节点）。SFFL项则存放着指向辐射源面片对应的SFFL链表的指针。节点的最后一项存储了当场景发生改变时辐射源面片的增量辐射度。

图2 SL链表如图3在SFFL链表中对于每一次跌代，阴影测试线从辐射源面片的中点发出投向场景环境中的每一个面片的中点。对于所有的被辐射面片，如果它们与辐射源面片之间不存在遮挡物，那么它们与辐射源面片之间的形状因子的信息都被存储在SFFL链表中，否则给遮挡物分配一个ID号并且存储到SFFL链表中。

图3 SFFL链表可以看到，SFFL链表可以加快逐步求精迭代算法的求解过程。一旦某一面片被再次选为辐射源面片，那么它与场景中其他面片的形状因子就可以被很快地搜索到并且被重复使用。

4 扩展算法的实现

下面代码实现了当场景发生变化时扩展算法的处理过程：

Void FastRadiosity ( ) {

//搜索SL链表中的每个节点，找到增量辐射度D.jА0的辐射源面片

for(j=1;j

if(D.j!=0)

//遍历所有被辐射面片，将辐射源的增量辐射度传播给面片

for(i=1;i

{

//判断面片i与辐射源面片间是否有遮挡

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

{

//搜索SFFL链表，找到相应的形状因子

FiSJ= SL(j)SFFL(i)；

//改变后面片i的辐射度

B.newi=B.oldi+ρiD.jFiSjВ

//改变后面片i的待辐射度

ИΔB.newi=ΔB.oldi+ρiD.jFiSjВ

} }

//改变后辐射源面片的待辐射度

ИΔB.newj=ΔB.oldj+D.jВ华D.j=0；

} }

5 实验结果

通过在个人机上使用OpenGL对算法进行实现和测试，得到了一些验证算法有效性的数据。实验以虚拟室内环境为场景，场景由8 865个面片组成，辐射度预处理阶段的迭代次数限定为100次。在绘制场景时刷新率可以达到13.1帧/秒，当在场景中移动某一物体时，重新绘制场景所需的时间为13.046 s，当改变场景的反射率时，重新绘制时间为0.7 s，符合实时绘制的要求。实验所采用的软硬件环境为：CPU ：AMD Athlon 2 800+1.80(GHz)；内存：1 GB；显卡：ATI Radeon 9550；操作系统：Windows XP。

6 总结与展望

新算法通过将辐射度预处理过程中产生的运算信息存储在一个有效的数据结构里，实现了对逐步求精迭代算法的扩展。经过对算法进行实现，验证了算法符合虚拟现实的要求并且适用于动态虚拟场景中的辐射度的求解，扩展后的算法更加简洁高效，节省了大量的运算时间，使得场景更新更加流畅。由于在每次场景改变之前都必须等待上一次场景改变时产生的增量辐射度传播结束，这就给场景更新造成了一定的延时，这是当前的算法还不能解决的问题，有待进一步研究。

参 考 文 献

［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年出生，宁夏银川人，西安建筑科技大学信息与控制工程学院，硕士研究生。主要研究方向为多媒体与网络技术。

李昌华 男，西安建筑科技大学信息与控制工程学院，教授，博士生导师。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文