（计算机应用技术专业论文）基于双向路径追踪的metropolis全局光照算法的研究.pdf

摘要 m o n t ec a r l o 方法是全局光照计算的基础，由基本的m o n t ec a r l o 光线追踪 衍生出很多全局光照算法，这些算法的一个问题是它们对某些场景的计算效率很 差，因为这些方法对场景中从光源到视点的路径进行采样时都没有考虑到场景的 路径分布特征，都是采用随机采样的方法采样路径并计算贡献，一旦场景的路径 空间中路径分布极不均匀，就会造成效率的严重降低。 本文的主要研究内容是使用m e t r o p o l i s 抽样方法对路径空间中的路径进行 采样，以及在双向路径追踪的基础上实现m e t r o p o l i s 光线追踪器。文中首先介绍 了渲染的基本问题和m o n t ec a r l o 光线追踪的原理和特点，然后从理论上说明了 我们使用的m e t r o p o l i s 采样方法。接着，我们描述了我们如何利用m e t r o p o l i s 采 样方法对路径空间中的路径进行采样。我们从一个使用双向路径追踪选定的种子 路径出发，使用定义的转移策略不断的转移现有路径生成新的路径，然后根据计 算的接收概率选择接收新路径或接收旧路径，从而形成一条路径空间的马尔可夫 链。根据接收的路径的像素位置给相应的像素添加采样计数，根据m e t r o p o l i s 方 法的特性，随着马尔可夫链的增长，我们的采样计数分布图逐渐趋近于和结果图 像成比例的稳态分布，对其进行缩放就可以得到渲染结果。文中介绍了我们采用 的两种路径转移策略和我们如何对现有渲染系统进行改进，实现m e t r o p o l i s 渲染 器的细节。 关键词；m e t r o p o l i s m o n t ec a r l o 光线追踪双向路径追踪 a bs t r a c t m o n t ec a r l om e t h o di st h ec o r eo fg l o b a li l l u m i n a t i o n t h e r ea r em a n yg l o b a l i l l u m i n a t i o na l g o r i t h m sd e r i v e df r o mb a s i cm o n t ec a r l op a t h 仃a c i i l g b u tt h e s e m e t h o d sa r eo n l yo p t i m i z e df o raf a i r l yn a r r o wc l a s so fi n p u ts c e n e s b e c a u s et h e y d o n tk n o wt h ed i f f e r e n tp a t hd i s t r i b u t i o n si nd i f f e r e n ts c e n e sw h e ns a m p l et h ep a t h s f r o mt h el i g h ts o u r c et ot h ee y e a l lt h e s em e t h o d ss a m p l et h ep a t h sr a n d o m l y t h e y w i l lw o r ki n e f f i c i e n tw h e nt h e p a t h s i nt h ei n p u ts c e n e sd i s t r i b u t eh i g h l y n o n - u n i f o r m l y i nt h i sp a p e r , w es a m p l et h ep a t h si np a t hs p a c eu s i n gm e t r o p o l i ss a m p l i n g m e t h o d w ea l s op r o v i d eab i d i r e c t i o n a lp a t ht r a c i n gb a s e dm e t r o p o l i sl i g h tt r a c e ri n o u rp a p e r a tf i r s t , w ei n t r o d u c et h er e n d e re q u a t i o na n dm o n t ec a r l om e t h o d a n d t h e n ，w ei n t r o d u c et h eb a s i cm e t r o p o l i ss a m p l i n gm e t h o d t or e n d e rt h ei m a g e ，w e g e n e r a t eas e e dp a t hb yb i d i r e c t i o n a lp a t ht r a c i n g ，f r o mt h i ss e e dp a t h , w eg e n e r a t ea s e q u e n c eo fp a t h sb ym u t a t i n g c u r r e n tp a t hu s i n go u rm u t a t i o nm e t h o d s e a c h m u t a t i o ni sa c c e p t e do rr e j e c t e dw i t hc a l c u l a t e da c c e p t a n c ep r o b a b i l i t y w ea d da s a m p l et ot h ep i x e lw h i c ha c c e p t e dp a t hb e l o n g st o t h es e q u e n c eo fp a t hi sa m a r k o v c h a i n a st h em a r k o vc h a i ng r o w s ，o u rs a m p l ed i s t r i b u t i o nc o n v e r g e st oas t a t i o n a r y d i s t r i b u t i o np r o p o r t i o n a t et ot h ei m a g ec o n t r i b u t i o n w ec a ng e tt h er e n d e rr e s u l tb y s c a l i n gs a m p l ed i s t r i b u t i o n w ei n t r o d u c eo u rt w op a t hm u t a t i o nm e t h o d s t h ep a p e r a l s oi n c l u d e st 1 1 ed e t a i l so fo u rm e t r o p o l i sl i g h tt r a c e r k e y w o r d s ：m e t r o p o l i s ，m o n t ec a r l o ，p a t ht r a c i n g ，b i d i r e c t i o n a lp a t ht r a c i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签芍必磊也妙钇 签字日期：矽。 年f r 月f 日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘堂有关保留、使用学位论文的规定。 特授权叁鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名名纱 签字日期：沙伊7 年厂月2 ，泊 导师签名： 确、狄 签字日期：p 7 年，月2 厂日 第一章绪论 第一章绪论 近年来，计算机技术正以飞快的速度迅猛的发展，而计算机图形学的发展 速度更是令人咋舌。人们对于电影，游戏的热衷是图形学发展的最大动力，它不 仅推动了硬件厂商研制出运算速度更快功能更强大的图形加速卡，也为图形技术 的发展提供了更加广阔的舞台，同时对我们也提出了更高的要求。我们必须努力 提高我们的技术水平，不断研究各种先进的图形算法，开发各种震撼性的图形应 用，力图在计算机屏幕上再造一个真实的世界，满足人们日益高涨的需求。 1 1 研究的背景和现状 全局光照计算是计算机图形学中的一个核心组成部分，它的基本任务是使 用预先组织好的三维场景生成具有完全真实感的图像。为了达到这一目的，我们 必须模拟光线在场景中进行传播所发生的各种物理现象，如多次的反射，阴影， 焦散等。这不仅需要我们有对场景中各种物体的几何特性和材质属性的精确描 述，还要求我们具备求解计算多次反射，折射带来的无限维积分问题的能力。这 使得全局光照计算成为了一个极度复杂的问题。 全局光照计算的复杂性造成了获得一副真实感图像需要很长的时间，如何 更好的实现全局光照算法，在更短的时间内生成高质量的图像是我们努力的方 向，在这个领域，已经有很多人做了大量的工作，设计了很多全局光照算法。 k a j i y a 1 首先提出了使用m o n t ec a r l o 方法求解渲染方程的m o n t ec a r l o 光线追踪 算法。这是第一个从统计上无偏的算法。然后，a r v o 2 3 提出了一些改进，并 提出了等价的逆向粒子追踪算法。m o n t ec a r l o 方法最大的问题是由采样方差产 生的噪声，v e a c h 4 通过使用多重重要性采样策略，结合多种采样方法的优点， 极大的提高了光线追踪算法的适应性和效率。l a f o r t u n e 和w i l l e m s 5 6 和v e a c h 和g u i b a s 7 8 分别提出了双向路径追踪算法，通过生成一对眼睛子路径和光源 子路径然后连接每个结点的方法，降低了计算的方差水平，对一些以前很难计算 的场景得到了很好的计算效果。j e n s e n 9 1 0 提出了p h o t o nm a p p i n g 算法，它是 包括生成光子图和光子收集两阶段的算法，大大加速了图像的生成速度，但是它 是一个统计上有偏的算法，可以使用它计算焦散和间接光照，从而和一般的光线 追踪算法结合使用。 第一章绪论 这些全局光照算法最大的问题是它们都有不适应的场景，也就是说没有一 种方法对任意场景都起作用，因为这些方法对场景中从光源到视点的路径进行采 样时都没有考虑到场景的路径分布特征，都是采用随机采样的方法采样路径并计 算贡献。因此，一旦场景的路径空间中路径分布极不均匀，这些方法就会因为大 量的路径没有带来贡献而造成效率的极度降低，例如在间接光照主导的场景中， 光源和视点之间被严重遮挡，只有很小的通道可以通过，随机采样时，只有很少 的路径可以通过这个通道带来贡献，其他的路径只能被丢弃。为此v c a c h 1 1 首 次将最早应用在计算物理领域的m e t r o p o l i s 采样方法 1 2 】引入图形学。实际上， 早在1 9 7 0 年，【1 4 1 5 就使用在m o n t ec a r l o 采样中使用马尔可夫链。之后s z i r m a y 【1 6 】研究了m e t r o p o l i s 采样的起始偏差问题。a s h i k h m i n 1 7 对m e 缸o p o h s 光线追 踪进行了方差分析。c l i n e 和e g b e r t 1 8 1 9 提出了一种新的结合m e 仃o p o l i s 和普 通光线追踪的算法e r p t 。p a u l y 2 0 将m e t r o p o l i s 应用到参与介质的计算中。本 文介绍了一种使用m e t r o p o l i s 采样方法对全局路径空间的路径进行采样，通过获 得和最终结果图像成比例的采样分布直方图来得到渲染结果的m e t r o p o l i s 光线 追踪算法，很好的解决了这个问题。 1 2 本文的组织 在下一章，将介绍全局光照算法的基础一渲染方程，然后将简要介绍m o n t e c a r l o 方法及在光线追踪中的应用，还介绍了双向路径追踪算法。第三章描述的 是m e t r o p o l i s 采样方法的理论基础。第四章介绍了我们的m e t r o p o l i s 光线追踪方 法，介绍了我们使用的两种转移策略，双向转移策略和视点路径扰动转移策略。 第五章描述了我们m e t r o p o l i s 渲染方法的实现过程，并给出了我们的一些渲染结 果。第六章总结了我们的工作，然后对下一步的工作进行了展望。 第二章渲染方程和m o n t ec a r l o 全局光照算法 第二章渲染方程和m o n t ec a r l o 全局光照算法 渲染方程刻画了光线在场景中传播的整个物理过程，对场景进行渲染，实 际上可以转化为对渲染方程的求解。m o n t ec a r l o 方法是一种使用概率方法来求 解积分的数值计算方法，m o n t ec a r l o 方法的优良特性使其在全局光照算法中得 到了广泛的应用。下面具体介绍渲染方程和m o n t ec a r l o 方法及其在光照计算上 的应用。 2 1 渲染方程 2 1 1 基本形式 渲染方程描述了能量从光源发射，经过各种材质表面的多次反射，折射， 最后进入人眼的这一过程。在面片上某点，沿方向秒出射的辐射度可以定义如下 ( 如图2 1 ) ： l ( x jj 矽) = t ( x 7 - 9 , 矽) ? + l z ( x ，妙h 秒) 三( x 7 卜) c 。s ( 虬一，y ) d 公式伫1 这里q ，是x 点的所有半球方向集合，厶o _ 功是点x 沿p 方向发射的辐射度，z 是双向散射分布函数( b s d f ) ，l ( x 卜沙) 是点x 从 f ，方向得到的入射辐射度， e o s o v , ，y ) 是z 法向量和入射方向少的夹角余弦。 图2 1 3 第二章渲染方程和m o n t ec a r l o 全局光照算法 也可以将渲染方程从对半球方向的积分转化为对场景中所有面片面积的积 分，这样可以得到渲染方程的另外一种等价形式( 如图2 2 ) ： 图2 2 l ( x jx ) = t ( x - - 4 , 功 + z ( 矿一x 。x ) 三( ，一x ) g ( x ，x 一) 幽( x 一) 公式2 - 2 ) g ( x t , x w ) = 矿( x t , x w ) 型坠雩型公船3 ) tt t 这里函数g ( x ，) 称为几何项，其中t 是点x y 之间距离的平方，两个余弦值是 向量x h ，和点和点，表面法向量的夹角余弦，v ( x t , x 。) 是可见性函数，如 果点x 和点，相互可见，则v ( x ，x 。) 为1 ，否则为0 。 通过对上述渲染方程进行求解，可以得到场景中任意表面上的点向任意方 向的辐射度，但渲染关心的是那些直接对生成图像起作用的辐射度。为了计算每 个像素面积上的平均辐射度值，需要计算这个像素的辐射通量。这个辐射通量可 以通过对所有从该像素可见的表面点和方向的辐射度进行积分得到。如下式： ( s ) = ll 三 7 一1 5 7 ) c 。s ( 以，o ) d c o o d a ( x ) 公式( 2 - 4 ) 这里= x j x q j ，是由从该像素可见的表面点，和方向9 对组成的空间。在实际 应用中，引入了一个通量响应函数形 _ 功，如果( x ，护) s ，形 一护) 为1 ， 其他都为0 。使用这个函数，就可以将该像素的辐射通量定义为对所有表面点和 方向对的积分。如下式所示： 4 第二章渲染方程和m o n t ec a r l o 全局光照算法 ( 墨) = l 嘭力o 专o ) 1 4 x 专8 ) e o s ( 以，o ) d c o o d , 4 ( x ) 公式( 2 5 ) 这样，每个像素的平均辐射度值可以由下式得到： 嘤= 垮篙筹罴一蛾呦 也可以像渲染方程一样将像素的辐射通量从对方向的积分转化为相机接收面积 的积分，如下： ( 1 ) = 一嘭气一x 皿( z 专x ) g ( x ，) 幽( x ) 幽( x ) 公式( 2 7 ) 这里x 是相机接受面上一点。 2 1 2 路径积分形式 将渲染方程递归( 公式2 2 ) 展开，并代入辐射通量方程( 公式2 8 ) ，可以 得到如下形式： ( 孓) = ：嘭d ( 毛x o ) l e ( x , x o ) g ( x o ，五) 姒( ) 幽( 五) + ，嘭力( 五专) g ( 而，而) z ( 恐j 五一而) 公式( 2 8 ) g ( 五，吃- ，也tl 1 屯- 专五) 幽( ) 幽( 五) 姒( 恐) 、。 最终的目的是为了得到如下的形式： ( 1 ) = l 乃( _ 矽( 习 f f 式( 2 9 ) 这样，对积分方程的求解就转化为求一个积分。设q 。是长度为k 的所有路径 一x = x o x l 。 的集合。以定义为d 1 4 ( x o 以) = 幽( ) 姒( 以) ，q 定义为所有q 。 舅；二章渲染方程和m o n t ec a r l o 全局光照算法 的集合，乃称为贡献函数，是由若干g 似，) 和b s d fz 乘积，然后在路径的开 始( 眼睛一端) 乘以呒( ，专功，在路径的结束( 光源一段) 乘以丘( _ z ) 组 成的，例如：( 如图2 3 ) f j c x o x ：，2 ) = t ( 恐j 五) g ( 五，屯) z ( 恐j 五。而) g ( x o , x 1 ) 嘭，( 而寸) 公式( 2 - 1 0 ) x f ( 恐一五j 而) 图2 3 贡献函数组成 路径积分形式的好处是它把对整个场景的渲染问题转化成了对一个对由各 种长度路径组成的路径空间的采样问题。在视点和光源之间随机生成若干条路 径，估计它们的贡献值，并把贡献值加到该路径影响到的像素上，就可以得到场 景的渲染图像。双向路径追踪和m e t r o p o l i s 光线追踪都很适合采用这种路径积分 形式来描述和计算。 2 2m o n t ec a r l o 光线追踪 无论采用渲染方程的积分方程形式还是路径积分形式，得到渲染结果的最 大的困难就是对多维积分的求解，得到理论上的正确结果需要计算无穷维的积 分，而且由于被积式没有解析式，所以我们不能通过解析的方法得到正确的解。 这时候，m o n t ec a r l o 方法就成了我们唯一的选择。 2 2 1m o n t ec a r l o 方法 m o n t ec a r l o 方法是二十世纪四十年代提出的一种以概率统计为指导的一种 非常重要的数值计算方法。蒙特卡罗方法利用随机抽样来解决积分的计算问题。 使用这种方法，可以很容易解决一些在数学上难解或无解的方程。 6 第二章渲染方程和m o n t ec a r l o 全局光照算法 m o n t ec a r l o 的基本思想是：给定一个函数厂：s _ r 和一个随机变t x p ， 随机变量函数厂( x ) 的数学期望可以由随机变量样本的函数均值来近似，如下式 所示： 町( 瑚= u ( 却( 圳菇地) 馘( 2 - 1 1 ) 我们可以用函数g ( x ) 来代替厂( x ) p ( 功，这样我们得到： 聃州蒿器 蜮( 2 - 1 2 ) 这样，我们就得到了一种用多次采样取均值来近似求积分值的方法，m o n t ec a r l o 方法也同样适用于高维积分求解，只是x i 是高维空间的采样点。可以很容易地证 明，m o n t ec a r l o 方法求得的积分值是一种对实际值的无偏估计。 要得到更精确的对积分的估计，我们必须提高m o n t ec a r l o 方法中的采样点 的个数，即，同时，我们必须设法使得g ( x i ) p ( 葺) 的方差降低，也就是要设 法使得p ( 薯) 和g ( 薯) 有相似的形状，这样，会在g ( 而) 大的地方采到更多的采样， 即让更多的采样落在更重要的区域，这种策略叫做重要性采样。 m o n t ec a r l o 方法的基本过程是这样的，首先要根据所研究的问题确定一种 概率密度函数( p d f ) ，然后根据概率密度函数对所研究的问题进行采样( 可以通 过例如反函数法等方法得到符合某一概率密度的采样) ，最后对这些采样进行计 算，求均值，得到最终结果。 可以很容易的证得，m o n t ec a r l o 估计方法的标准差和1 成比例。这说 明，我们要想使估计误差降低到原来的1 2 ，我们就要付出比原来多4 倍的采样 计算量。较慢的收敛速度成为m o n t ec a r l o 方法最大的缺点。但是，m o n t ec a r l o 方法的不受积分维数限制而且收敛速度和积分维数无关的极强的适应性，以及它 的简单容易实现，使得m o n t ec a r l o 方法成为了计算全局光照问题的最好的方法。 2 2 2m o n t ec a r l o 光线追踪 m o n t ec a r l o 方法是由k a j i y a 1 在1 9 8 6 年引入到全局光照领域的，由于它 可以很好地解决间接光照，多次反射，阴影等光照现象和复杂场景的绘制问题， 而且具有简单性和广泛的适应性，所以在全局光照算法中得到了广泛的应用。 7 第二章渲染方程和m o n t ec a r l o 全局光照算法 m o n t ec a r l o 光线追踪的过程就是使用m o n t ec a r l o 方法对像素平面，反射， 折射方向，光源等进行采样来代替渲染方程中的积分的过程。基本m o n t ec a r l o 光线追踪算法描述如下： 1 ) 首先对我们所要计算的像素进行采样，有很多种采样的方法，如随机采 样，分层采样等，有时，这一过程还要包括对相机接收面的采样和对时 间的采样。 2 ) 由视点和刚才得到的采样点确定一条射线射入场景。 3 ) 找到与射线相交的最近的表面的位置，如果打到的表面是光源，则记下 光源的t 并返回，如果不是光源，则根据表面的材质属性( b s d f ) 随机 采样一个方向，并记下这次过程的和p d f 。 4 ) 重复过程2 ) ，直到打到光源为止。 基本的m o n t ec a r l o 光线追踪方法效率不高，主要原因是会出现多次反射， 折射却打不到光源的情况，特别是在光源面积比较小的地方非常明显。我们可以 通过对光源进行采样来解决这个问题。在每次射线打到物体得到交点后，我们可 以在面光源上采一个点，然后判断连接交点和光源点的阴影线是否被遮挡，如果 未被遮挡，则可以计算光源对物体表面交点的直接光照。在这个过程中要通过使 用多重重要性抽样( m u l t i p l ei m p o r t a n c es a m p l i n g ) 4 计算这次反射的硝。 基本的m o n t ec a r l o 光线追踪是从视点开始进行追踪过程的，还有一种追踪 方法与之相反，我们称之为光源光线追踪。这种方法从光源发出光线，经过表面 的多次反射，折射，寻找到一条到视点的通路，并将贡献记录在穿过的像素。这 种方法和上节我们介绍的m o n t ec a r l o 光线追踪是等价的。 实际上，这两种方法都有它们各自的局限性，对于某些场景中的特殊的情 况，它们是很难处理的。我们用下面的符号组成正则表达式【1 3 】来表示组成路径 的各个点的情况。e 代表视点，三代表光源点，d 代表漫反射表面点( 可以向任 意方向反射光线) ，s 代表镜面反射表面点( 只能向特定方向反射光线) 。从眼睛出 发的m o n t ec a r l o 光线追踪可以处理e 【( ds ) d l 这些情况，但对研( ds ) + s l 这些情况的处理不理想，而这些情况在图像中表现为焦散，而从光源发射的光源 光线追踪可以处理e d ( ds ) 弘，但是却不能很好的处理e s ( dls ) 弘，这些情 况在图像中表现为镜面反射表面。双向路径追踪是这两种光线追踪方法的结合， 它可以很好的解决这两种情况。 第二章渲染方程和m o n t ec a r l o 全局光照算法 2 3 双向路径追踪算法 双向路径追踪算法，是由v e a c h 和g u i b a s 7 8 和l a f o r t u n e 和w i l l e m s 5 6 】 分别提出的，它可以很好的生成焦散和镜面。 双向路径追踪的过程是这样的，对于每个像素，为了生成一条路径，我们 分别从视点和光源生成两条子路径。从眼睛生成长度为刀，的子路径： x 1 ，一1 ，从光源生成长度为吃的子路径儿乃儿，一1 然后，我们分别连接 这两条子路径上的每个结点，只有两个位于两条子路径上不被其他物体遮挡的结 点才可以连接。 图2 4 双向路径追踪 这样，我们可以得到不同长度的一组路径，( 如图2 - 4 所示为长度为4 的路径) ， 而且这组中相同长度的路径有多条。例如我们要得到一条长度为k 的路径，我们 可以从光源子路径中选择长度为j 的路径，然后从眼睛子路径中选择长度为 t ( t = k s + 1 ) 的路径，因为s = 0 ，1 ，七，所以对于长度为k 的路径，我们可以有 k + 1 种选择，每一种s 的选择，实际上就代表了一种不同的对路径空间的采样策 略，这些策略每一种都有它适用的情况，对于产生某种特殊的效果产生各自的作 用，将这些策略综合起来，我们就可以得到适应性更强的渲染算法，得到更好的 渲染效果。这些策略大体上可以分为三类： s = 0 ，例如x o ( e ) x , 也，这种情况是基本的m o n t ec a r l o 光线追踪，也就是 在生成眼睛子路径的过程中打到了光源。 t = 1 ，例如x o ( e ) h 儿一y o ( l ) ，这种情况是光源光线追踪，直接连接视点 和光源子路径。这条路径影响到的像素不是最初的像素，必须通过计算得到， 而且需要注意眼睛和光源子路径的端点是否可见。另外，这里f 0 ，因为在 9 第二章渲染方程和m o n t ec a r l o 全局光照算法 这里我们不考虑视点有一定面积的情况，而把视点看作是一个抽象的点。 s = 1 9 9 j j ，例如x o ( s ) x 1 。4 - ) 儿一i - i 。( 工) ，这是一般的情况，需要注意互联 的两个点是否可见。 我们可以通过多重重要性采样的方法将多种不同的采样策略综合起来。设 生成路径夏。，所使用的p d f 为见见。，可以由生成长度为j 的光源子路径的各个 p d f 的乘积乘以生成长度为f 的眼睛子路径的各个p d f 得到。我们可以由下式计 算由一对光源子路径和眼睛子路径生成的一组路径对像素，的贡献： 乃= 委孙训焉 一3 ， 这里乃( 瓦，) 是( 公式2 - 1 2 ) q 丁介绍过的贡献函数，嵋。，( 瓦，) 是多重重要性采样的权 值函数，通过结合多种采样方式，可以很好的处理各种复杂的场景和各种复杂的 光照形式。下面我们具体介绍一下比，( - 。) 的生成方式。 嵋，( 瓦。，) 的值是由生成路径墨，可能采用的s + t + 1 种采样方法的p d f 决定 的。我们定义觑为使用f 个结点的光源子路径和s + t f 个结点的眼睛子路径生成 路径瓦，的概率密度函数： p i = p i , a + t - i ( 墨，) i = o ，s + t 公式( 2 一14 ) 实际上，路径瓦，是由概率只= 只，( 夏，) 生成的，其他岛。以一。和见“。以“表明了 其他s + f 种生成路径夏。的可能的方式。 v e a c h 和g u i b a s 介绍了很多种计算权值函数嵋。，( 瓦，) 的策略，下面这种是最 有效率的一种： 叱贩，) = 卫e , p f = 豇丽1 馘( 2 - 1 5 ) 在计算时，一般取2 ，而且，由于所有的易之间的差别只是很少的几项，所以 计算易见来计算叱，( 嚣。，) 要更有效率。 1 0 第三章m e t r o p o l i s 方法 第三章m e t r o p o l i s 方法 1 9 5 3 年，m e t r o p o l i s 等人 1 2 】为了解决计算物理领域的复杂采样问题，提出 了一种新的采样方法，这就是m e t r o p o l i s 方法。他们最早使用m e t r o p o l i s 方法的 初衷是为了计算流体的材质属性，现在，m e t r o p o l i s 方法已经在物理，化学等很 多领域得到了广泛的应用，同样，我们也可以将m e t r o p o l i s 方法应用在全局光照 领域，来解决复杂的采样问题。 我们要考虑一个状态空间q 和一个定义在这个空间上的非负函数 f ：q r + 。我们处在一个初始的状态兄q ，我们的目的是要生成一个随机 过程元，置，无论以哪一个初始状态冠开始，这个随机过程都会逐渐收敛于 一个与函数厂成比例的分布，我们称之为稳态分布。 在这里，每一个状态置都是由它的前一时刻的状态置一，通过做某种随机的 改变而得到的。这种每一时刻的状态冠只与它的前一时刻的状态冠一，相关的随机 过程叫做马尔可夫链。我们可以定义转移概率k ( i _ 刀，这个概率表明从当前 状态i 在下一时刻转移到状态歹的概率。 i 每一个时刻的状态冠都是具有一定概率分布珐的随机变量，我们可以由前 一时刻的概率分布翻一。和转移概率得到当前时刻的概率分布，如下式： b ( z ) = k 够专更凌_ 1 够) 础够) 公式( 3 1 ) 随着这个过程的进行，最终会达到一个稳态分布p ，所谓的稳态分布，就是无 论进行任何类型的转移，都会保持当前的稳态分布不变，即： p ( - ) = k ( 罗寸_ ) p ( 习d ( 刃 公式( 3 2 ) 和一般的应用马尔可夫过程的方法不同，m e t r o p o l i s 方法实际是一个反向的 过程。在一般的应用中，转移概率是由物理系统本身来决定的，任给一个初始状 态，系统将向稳态转移，我们的任务是对具有某种转移概率的随机过程的稳态分 布作出预测。而m e t r o p o l i s 方法处理的情况是：知道一个函数厂，可以估计函数 厂在某处的值，为了得到函数，我们需要设计转移概率置，使得我们最终可以 达到和函数成比例的稳态分布，而且要尽量使得收敛速度达到最快。 因此，我们可以使用m e t r o p o l i s 方法对某些复杂的函数进行近似。首先从 定义函数厂的状态空间q 中的一点冠出发，根据转移概率k 生成下一时刻的状 态置，这也相当于对状态空间q 进行了一次采样。然后，我们将采样点记录在 采样分布直方图中，持续进行这一过程，虽然开始那些时刻的状态分布和稳态分 布有很大的差别也就是说我们的采样点并不是来自于稳态分布，但随着马尔可夫 链的增长，我们在每一时刻的状态分布逐渐趋向稳态分布( 这由我们下面将要介 绍的细节平衡和概率接受来保证) ，由我们的采样点组成的采样分布直方图的形 状也趋近于函数曲线，当达到一定的精度时，我们可以直接对采样分布直方图进 行缩放来得到函数厂。图3 1 表示了使用采样分布直方图累计采样，随着不停在 不同的状态之间( 如i 和罗之间) 进行转移，直方图中累计的采样点越来越多， 一开始采样分布( 绿色曲线) 和稳态分布( 红色曲线) 有一定差别，随着时间发 展，逐渐趋近于稳态分布。 3 2 细节平衡 j j + 图3 - 1 累计采样达到稳态分布 m e t r o p o l i s 算法采用一种称为细节平衡的方法来保证我们的马尔可夫过程 能够趋向于稳态分布。 假设当前时刻我们现在处在状态置一，我们可以通过下面的方法得到下一时 刻的采样z 。首先，我们可以根据我们预先约定的任意转移策略生成下一时刻 的临时采样点冠，我们采用的转移策略的转移函数定义为t ( yi 习，该函数给出 了从最，= i 转移到暑= 罗的转移概率，我们将这个转移函数r ( 夕l x - - ) 称为临时转 移函数，因为我们只是对如何进行转移进行了一次尝试，而我们的这次尝试有可 1 2 第三章m e t r o p o l i s 方法 能被接收，也有可能被拒绝，这取决我们下面将要定义的接收概率a ( y i 习。这 样，我们可以得到下一时刻的状态如下： 哥f 冠 概率为口( 冠l 墨一。) = 1 置一l概率为1 一a ( x 一；ix 一, 一。) 公式( 3 - 3 ) 现在，全部问题变成了如何定义接收概率a ( y l x - ) ，假设现在我们已经达到 了稳态，我们必须定义转移概率k ，以使得我们已经达到的稳态能够得到保持。 我们可以这样考虑，考虑采样分布直方图中的两位，也就是状态空间中的两个状 态，i 和罗，从宏观上看，我们达到了稳态，但在微观上，不同状态之间一直进 行着互相转移，但是从状态- 1 转移到状态歹的采样点数一定等于从状态歹转移回 状态_ i 均采样点数，我们称之为细节平衡方程，即下式： f ( 2 ) t ( yiz ) 口( 罗l _ ) = f ( y ) t ( 2i 歹) 口( ily ) 公式( 3 4 ) 我们可以证明，当满足这个条件的时候，稳态可以得到保持。 3 3 接收概率口( 罗i 习 ( 公式3 6 ) 给出了计算接受概率a ( y i x - ) 的方法，因为( 习是已知的，而 r 够i 习则是我们任意选取的转移策略决定的。所以我们可以得到 a ( y i 习a ( - z l y - - ) 。我们对于接收概率的要求是要在允许的情况下尽量增大接收概 率的值，这样做的目的是为了能够使得我们的过程尽快达到稳态。为了达到这一 目的，我们可以这样定义接收概率a ( yi - ) ： 口c 彳i 习= m m 0 ，厂( 刃 0 ) ，都有一定的概率可以互相转移， 即r ( 歹l 习 0 。如果这个条件得不到满足，就很可能出现我们的路径在场景的某 个区域转移却无法跳出这个区域的现象，( 如图) ，光源和眼睛之间被一个大的障 碍物阻挡，只留下两个狭小的通道，如果我们只提供添加删除一个结点这种转移 策略，我们无论如何也无法得到通过右面的通道到达光源的路径，这使得我们损 失了一部分路径空间。 图4 1 1 8 第四章m e t r o p o l i s 光线追踪 对像素平面的遍历。因为在一般情况下，一条路径只会对一个像素起作用， 我们的转移策略必须包括对路径的第一节而为的改变的转移，因为对其他节的改 变不会改变路径在像素平面上的分布。而且，我们的转移应该很快的散布到整个 图像的各个像素，我们可以采用某种形式的分层机制来做到这一点。 我们发现，很难设计一种转移策略满足我们上面提到的所有条件，因此， 我们应该设计多种转移策略，在每次转移时根据需要选择或者随机选择一种转移 策略，才能很好的完成整个任务。虽然，我们在设计转移概率时需要注意很多地 方，但比起其他的全局光照算法，m e t r o p o l i s 方法给我们提供了更大的自由，我 们可以很自由的设计转移策略，只要我们可以为每一次转移计算转移概率 丁( 歹i 习，而且我们也可以根据实际的情况选择转移策略。 4 3 我们的转移策略 根据上一节描述的设计转移策略的要求，我们下面介绍了我们实际采用的 两种转移策略，双向转移策略和视点路径扰动转移策略。通过随机使用这两种转 移策略，我们可以很好的满足上面我们介绍的条件 4 3 1 双向转移策略 双向转移策略是m e t r o p o l i s 光线追踪的基础策略，因为它能够给我们提供 大幅度转移的能力和对任意场景的很好的遍历特性，虽然在某些情况下这种转移 策略的接收概率不够高，但我们可以通过设计不同情况的转移概率来解决这一问 题。它的基本思想是对现有路径进行比较大的变化，删除某些子路径，然后通过 随机的方法添加一段子路径连接被删除子路径留下的两个端点，在删除添加的过 程中路径的长度很可能发生变化，我们下面详细介绍这种转移策略的各个步骤。 首先，我们要进行路径的局部删除工作，我们必须选出被删除的子路径。 假设我们当前的路径为i = x o x a 以，我们可以删除任意一段子路径，删除子路径 t 。的概率是办【s ，t 】( 这里，删除子路径t 五表明我们要删除的是点s 和点t 2 间不包括两个端点的子路径，包括f s 条边和t s 1 个点) 。为了确定p d b ，t 】， 我们可以分成两个步骤，我们先确定我们的这次删除要删除的子路径长度乞，然 后确定从哪个点开始删除这么长的子路径，我们用协，儿：代表对这两个事件 进行选择的概率。我们可以通过： 1 9 第四章m e t r o p o l i s 光线追踪 p d s ，幻= p d 。l p d 。垒公式( 4 8 ) 得到岛 j ，f 】。第一个事件的选择原则是删除长度较小的子路径的概率较大，删除 全部路径的概率最小。我们这样设计的目的是删除较短子路径对整个路径造成的 改变较小，从而我们可以获得比较大的接收概率，但我们也要提供删除全部路径 的可能，这样才能保证我们对整个路径空间的遍历。具体的设定如下： 以扛纠= 饿0 2 5 f ，一1 d 一1 乞= 2 其他 第二个事件的选择我们采用的是等概率选取，也就是我们可以从每一个可以删除 长度l d 的子路径的结点删除这段子路径。确定了既 1 ，p d ：之后，我们对这两 个概率进行分别采样，然后根据采样的结果对进行路径删除工作，之后我们得到 了两段剩下的子路径。j 。和五五。 下面，我们需要做的工作是随机生成新的子路径，连接删除子路径后留下 的两段剩下的子路径。和x k 。我们通过在这两段子路径的两端分别生成 长度为s 和长度为f 的路径，然后连接的方法得到新的路径。和删除子路径的情 况相同，我们也采取分两个步骤的方法确定添加子路径这一事件的概率密度函数 p o s ，明： 见【s ，川= 见，l 见，2 公式( 4 9 ) 这里，见。表示添加长度为乞的路径的概率，见：表示在哪一个端点添加多长路 径的概率。添加子路径的长度乞是这样确定的，我们赋予添加和删除子路径长度 厶同样的子路径长度乞以更大的概率，因为这时，改变前后的路径的长度是不变 的，对路径的改变比较小，可以获得比较大的接收概率。具体的设定如下； 第四章m e t r o p o l i s 光线追踪 l o = 乞 乞= 乞1 l o = 乞2 其他 我们还需要注意的一点是我们添加后的路径长度不能超过一定的长度。第二个事 件我们也采取等概率选取，例如对于添加一个长度为3 的路径，我们可以有 ( o ，3 ) ，( 1 ，2 ) ，( 2 ，1 ) ，( 3 ，o ) 这几种选择，每一种的概率都是相同的。确定了以， 以，之后，我们对根据对以，见：的采样情况决定添加在两段子路径两端的路 径长度s ，然后我们从两段子路径中的一段的端点出发，根据端点的b s d f 采 出一个随机方向( 如果一个端点是空的，我们应该根据情况使用眼睛发出的射线 方向或从光源采点发出的射线方向) ，沿该方向发出射线，找到最近的交点，然 后继续根据b s d f 采方向，持续这一过程直到添加的路径长度符合要求。然后我 们从另一段的端点添加子路径，最后我们测试两条子路径的端点是否可见，若可 见我们连接它们成为一条路径，如果不可见，我们直接拒绝这次路径转移。至此， 我们由原来的路径通过随机的删除，添加若干节路径生成了一条新的路径。 我们用上面的方法生成一条新的路径后，我们需要计算从原路径到这条新 的路径的转移被接收的概率。根据3 3 节计算接收概率的( 公式3 7 ) ，为了计算 接收概率a ( y i 习，我们需要计算厂( 习，( 刃，z ( 1 刃，r 妙l 习，我们可以使 用2 1 2 节( 公式2 1 2 ) 来计算厂( 习，厂0 ) ，因为我们需要的是，( y o f ( x - - ) ， 所以可以只计算( x - ) ，f ( y - ) 有差异的项。而r 咿i 习是从路径i 到路径y 的转移 概率，丁眵l 习可以通过计算删除子路径。的概率岛【j ，幻和生成长度为j + f ， 的子路径的概率的乘积来得到。生成长度为，+ f 的子路径的概率包括p ，】和o st 根据b s d f 采方向的p d f ，在计算这一概率时要注意的是，虽然我们添加的子路 径是由连接分别添加了s 和t 的两段子路径组成的，但计算的时候要考虑所有 ，+ f + 1 种连接了t 和蕾的方式( 多重重要性采样) 。我们可以使用同样的方法计 算丁( - iy o ，同样，丁( - l 力，t 够lx - - ) 共有的部分可以忽略不计算。 现在举一个例子说明双向转移策略作用的方式，如图4 2 ，z 是路径 x o x a x 2 x 3 x 4 ，我们删除了子路径x a x 2 x 3 ，然后通过从五点发射射线的方式找到一个 新点，然后连接和而，得到新路径歹= 而五恐五。 2 l 5 坫晒 o m ni(l i i j以 第四章m e t r o p o l i s 光线追踪 弓 图4 - 2 双向路径转移策略 我们可以这样计算f ( y - ) ，厂( _ ) ： 厂