10. Instant Radiosity(进行中)

发表在 章节介绍 | 留下评论

9. Radiosity(已完成)

一些涉及的术语:

Finite element methods,geometrical view factor/form factor, hemi-cube, local/global line, integral geometry, iterative methods, Jacobi method, Gauss-Seidel method, global transfer operator, N-body problem, hierarchical radiosity, wavelets analysis, wavelet radiosity, Lebesgue space, Gelerkin method, orthogonal projection, orthogonal complement, haar wavelet, multiresolution analysis, discontinuity meshing, visual events, line swaths, global visibility, visibility complex, visibility skeleton, line-data refinement, point gathering, lazy wavelet transform, lifting scheme, constrained Delaunay triangulation, ppreceptually-based refinement, Enlighten, bilinear interpolation, linear extrapolation, adaptive refinement, incremental radiosity, radiosity redistribution, progressive redistribution, cross redistribution radiosity…

发表在 章节介绍 | 留下评论

反向路径采样在MLT算法中的运用

今年的SIGGRAPH还是蛮有趣的,以下介绍可能是有史以来SIGGRAPH同一年同时出现三篇思路非常类似的论文:

Reversible Jump Metropolis Light Transport using Inverse Mappings
Fusing State Spaces for Markov Chain Monte Carlo Rendering
Charted Metropolis Light Transport

故事要从PSSMLT和MMLT讲起。自从1997年Eric Veach的MLT(Metropolis Light Transport)算法发表以来,这个被称为影响20世纪科技发展最重要的马尔可夫蒙特卡洛方法(MCMC,Markov Chain Monte Carlo)算法被引入到渲染领域,与传统的蒙特卡洛方法(例如路径追踪)不同的是,它通过利用样本之间的相关性来更好地探索一个分布函数,使得一些非常困难的路径可以更轻易被采样到,然而MLT算法依赖于非常好的突变策略,原始的MLT算法依赖于完全的随机采样,根本无法了解场景的一些几何信息,突变路径的接受概率极低,使得MLT算法在相当一段时间并没有太大进展。

时间到了2002年,Csaba Kelemen提出了PSSMLT算法(Simple and Robust Mutation Strategy for Metropolis Light Transport Algorithm),如下图所示,考虑到路径采样其实就是以增量的方式从每个顶点的BSDF分布从采样得到一个方向,然后使用光线投射找到该方向与表面的交点,重复迭代直到一条路径连接光源和摄像机,这个采样的过程实际上是对多个[0,1]的随机数的采样过程,这些[0,1]随机数构成一个高维的单位超立方体(unit-hypercube),这称为原采样空间(Primary sample space),所以如果直接对该空间采样,也能够得到一条路径。于是PSSMLT(Primary sample space Metropolis light Transport)算法转而对该原采样空间进行突变,这带来一些好处,例如状态转移是对称的,另外最重要的是因为使用重要性采样,原采样空间的被积函数为f/p接近为一个常数,这使得原采样空间的被积函数更平坦,采样的方差更低,考虑传统的MLT算法并没有使用重要性采样。

然而PSSMLT也是有缺点的,其中最重要的一点是它将“路径采样”当做一个黑盒子:它直观给你一些随机数,不管你使用什么方法给我一条路径就可以,例如可以使用路径追踪或者光子映射来产生一条突变路径,这种原采样空间和原始路径空间的隔离关系使得原采样空间并不会估计路径空间的特征,例如原采样空间给定一个10个[0,1]随机数,路径采样器用到第2个时发现路径以及偏离种子路径很远了,如下图所示,这种结果称为涟漪效应( ripple e ects),因为基于出射方向采样的路径追踪无法预测后续顶点的分布,某个顶点一个微小的突变可能导致后续路径发生较大的变换,从而使种子路径和突变路径差异太大而丧失相关性,进而接受率变低。由此,PSSMLT算法在将近10年间并无太大进展。

MLT算法被提出来后最重大的一个进展要数2014年Toshiya Hachisuka提出的MMLT算法(Multiplexed Metropolis Light Transport),表面上看,MMLT只是将重要性采样引入到原采样空间,例如下图左边包含三个原采样空间,每个原采样空间对应一种特定的采样技术,技术路径采样的长度,这使得可以实现这样的功能:当有些路径突变长时间无法被接受时,我们有可能通过改变采样技术太快速找到突破的路径。在下图中,路径除了在每个原采样空间内部执行突变,还可以在不同采样技术之间执行突变。

但从知识理论角度来讲,MMLT的重要意义在于它将统计中的模拟回火(simulated tempering)的思路引入到了MLT算法中,特定地,这里使用的思路主要来自序列回火(serial tempering),回火的思路源自于模拟退火(simulated annealing),模拟退火本来用于解决最优质问题,由于物体加温之后分子状态之间的转移更活跃,因此状态更易于在全局转移,而随着温度逐渐降低,状态之间的转移就逐渐减弱。所以为了求最优值,如下图中的最大值,我们首先将温度升高,然后让其慢慢冷却,在其过程中不断寻找最大值,随着温度降低,最终将停留在最大值处。

模拟回火则是借鉴了模拟退火的思路,实际上它们并无太大联系(除了名字),模拟回火就是将模拟退火中的温度看成一个离散的函数,不同的离散温度值对应着整个状态空间的一种划分,这样状态可以在每个子状态内部转移,也可以在不同状态(即温度)之间转移。在MMLT算法中,温度即是采样技术,不同的采样技术将原采样空间划分为多个子空间。

至此,MMLT算法中路径空间和原采样空间仍然是相对隔离的,虽然MMLT算法中可以在原采样控制路径使用的采样技术,但是仅限于此。也由于这种隔离,另一个问题来了,即采样技术之间的突变也可能导致涟漪效果,如下图所示,当由摄像机向光源方向的单向路径采样转变为由光源向摄像机方向的路径采样时,由于桌子的遮挡,其突变路径将产生非常大的差异,从而很难被接受。

于是,我们本文的主角出现了。在上述情况中,当采样技术发生改变时,虽然所有的[0,1]随机数并没有发生变化,但是由于使用了不同的采样技术,这些随机数被使用的方式也完全不同了,从而到时路径发生了很大的变化。因此,理想情况下,我们希望在改变采样技术时,能够保持路径不变。因此, Benedikt Bitterli于今年提出的RJMCMC(Reversible Jump Metropolis Light Transport using Inverse Mappings)使用一个反向映射方法,当从采样技术1向采样技术2转移时,它将状态1对应的原采样空间的路径在对应路径空间中的形式,通过一个反向映射转换到采样技术2对应的原采样空间,这个过程是决定性(deterministic)计算的,不含任何采样的结果,由于它们在各自的原采样空间虽然具有不同的值,但是在路径空间它们的值是相同的,因此在计算MLT算法中的接受率时,所有项被约掉,接受率变为1。由此,我们通过一个确定性的方法产生了一个不同状态之间的转移,并且它完全被接受,这种采样技术之间的转移太高效了。

而今年的另一篇论文, Jacopo Pantaleon的CMLT(Charted Metropolis Light Transport)几乎也与上述思路类似,但是强调更泛化的概念,即将原采样空间按某种标准划分成多个不同的子空间,然后在不同子空间之间进行转移,在转移的过程中使用反射映射来保持路径不变。

HISANARI OTSU的Fusing State Spaces for Markov Chain Monte Carlo Rendering在算法上稍微不同于上述两篇论文,但是其使用的核心概念,即由路径空间向原采样空间的反向映射是一致的。HISANARI OTSU的核心思路在于组合路径空间和原采样空间的优势,例如对于路径空间的Manifold Exploration,其由于探索路径的局部流形空间的特征,因此突变路径的采样效率很高,然而它却不能有效考虑路径的全局特征,例如该路径使用的采样技术的权重。因此HISANARI OTSU将当前路径的状态保存在原采样空间,这包括路径使用采样技术的权重,但是它并不直接对原采样空间执行突变,而是使用流形探索对路径执行突变,但是与流行探索直接使用突变路径不同,HISANARI OTSU将突变的结果通过反向映射转换会原采样空间,然后提取其权重值,使得可以按全局对路径的采样结果给予评估,同时兼顾局部和全局特征。

今年这几篇论文质量还是可以的,并且更是有Wojciech Jarosz,Wenzel Jakob, Carsten Dachsbacher, Anton S. Kaplanyan等这些保驾护航。

发表在 Global Illumination | 标签为 , , , | 留下评论

确定性的路径采样 – 微分流形在MLT算法中的运用

介绍一篇路径采样的论文,作者Wenzel Jakob是PBRT的作者之一,他2016年获得Eurographics Young Researcher Award多半是因为这篇论文,该奖项每年仅有2个名额,用于奖励过去在相关领域做出重大贡献的人(敬礼)。

Manifold Exploration: A Markov Chain Monte Carlo Technique for Rendering Scenes with Difficult Specular Transport,以及后续的相关论文:The Natural-Constraint Representation of the Path Space for Efficient Light Transport Simulation

先总结一下,这两篇论文的本质是将传统的完全随机的路径采样转变为使用微分几何确定性地计算出一条“相似”路径,这种思路在路径采样中算是一种小小的变革吧,表现在两个方面:

  1. 从路径采样方法来讲,传统的无论是基于MC的(BD)PT还是基于MCMC的MLT,PSSMLT或MMLT等,本质上每条路径的采样都是使用Ray Tracing的方式从每个顶点的BRDF函数中对方向进行随机地(randomly)采样并连接起来形成一个路径,而Manifold Exploration是确定性地(deterministic)计算出一条路径。
  2. 从光照积分公式方面看,它从欧几里得空间转变到了流形上进行研究。

传统的路径采样是完全随机的,这里的随机可以理解为采样器不会考虑任何关于场景的几何特征而“盲目的”在路径空间行走;因此,对于那些存在于很小的区域,但是被积函数的贡献值非常大的“困难”路径,往往会由于采样概率非常低而使其估计不精确;虽然MLT算法引入了路径之间的相关性,但是本质上它只是通过限制一条突变路径各个顶点的取值在欧几里得空间的某个范围内,其使用的路径采样(例如双向路径采样)仍然是盲目的,其效率仍然非常低;然而MLT算法提供了一种绝对的优势,即一旦找到一条重要路径,我们可以更小心地探索该路径附近也可能具有同样重要性的路径。

很显然,要想有效地探索这些困难路径,我们必须了解并利用路径的一些局部几何信息,这是前面流形探索以及本节半矢量空间光照传输的核心内容。然而,要想让路径采样器(这里的路径采样器是指传统的根据光线追踪的路径采样,它几乎也是目前我们介绍的以及离线渲染中使用的唯一的路径采样器)直接能够感知整个场景中的几何信息显然是不可能的,要知道,光线追踪依赖于首先随机选择一个方向,然后对该方向使用光线投射来寻找其与表面的交点并取得几何数据,而不是先根据某种场景的几何特征选择一个方向。

这种不可能事先知道场景几何特征的采样方法,使得我们转向另一种思路:即首先通过传统的路径追踪得到一条随机的合法路径,然后提取出该路径的几何特征,进而利用这些几何特征来寻找一条该路径离开附近的路径。这种思路依赖于一条已知路径,显然它不能成为一种独立的路径采样方法,然而它却正好可以用在MLT算法中,因为MLT算法寻找一条相对于当前路径的突变路径。然而需要注意的是,局部特征的表述的精确性往往被限定在很小的局部范围(如前面镜面流形表述所描述的那样),因此这些算法必须很好地保证全局遍历性的要求。

那么,应该怎样提取一条合法路径的局部几何信息呢,费马定理提供了答案。1657年,费马提出著名的最小时间原理,即自然界的行为永远以路程最短为原则。按照这个原理,光永远是选这样一条路走,以使它在最短时间内抵达目的地,这就是费马定理(Fermat principle)。费马定理描述了光照传输的特征,如果已知一条合法的光线路径,它当然满足费马原理,因此可以从中提取与光照交互有关表面的几何信息。

然而费马原理是全局的,它用于描述一条完全的路径,直接推导出这种全路径与多个表面交互的关系是非常困难的。幸运的是,局部的反射定律和折射定理与费马定理是完全等效的,局部的反射和折射定理提供了路径顶点及方向关于这些顶点局部几何信息(如位置,法线以及这些量的导数)的关系,从而我们能够从一条已知路径推导出该路径的局部几何信息。

然后,已知了一条路径的局部几何信息了,该如何利用它们来产生一条“相似”路径呢,这时牛顿方法提供了答案。我们已知的顶点局部信息是关于对应表面在该顶点处的位置和法线关于局部坐标系的导数,导数能够被运用于一阶泰勒近似中用来表述局部的函数分布,然而这种近似不能直接用来作为采样值,我们需要精确值,而牛顿方法正式利用一阶导数用迭代的方式逼近某个设定的真实函数值。

于是我们能够通过一条已知路径获得一条“相似”或“近邻”路径,这条路径在MLT算法中具有较高的接受率,因为它探索了路径的局部几何特征。更为重要的是,上述的采样过程是确定性的:给定一条当前路径,我们没有依赖任何随机过程,而是使用微分几何相关的知识直接计算出一条“相似”路径,这种由随机向确定性的转变,提升了MLT算法的效率。

这里提到两篇论文Manifold Exploration和Half Vector Light Transport正式使用了上述思路,它们都是借助费马定理将一条已知路径和其对应的局部几何信息建立起了联系,然后利用微分几何以及牛顿迭代法确定性地计算一条”相似“路径,只不过这里Manifold Exploration通过降维的方式将路径空间转变到镜面流形上,而Half Vector Light Transport将其转换到半矢量空间。

其实就是什么意思呢,如上视频所示,给定一条初始路径,它能够不需要任何随机过程直接计算出所有满足初始路径类似的几何配置,并自动满足每个顶点处反射折射定理的相邻相似路径,而这正是MLT算法非常需要的。

发表在 Ray Tracing | 标签为 , , , , | 留下评论

8. Metropolis Light Transport(已完成)

80页,一些名词:

MLT,PSSMLT,MMLT,MEMLT,HSLT,Simulated/serial/parallel tempering,replica exchange,AMCMCVCM/UPS,Adaptive MCMC,Manifold Exploration,differential geometry,Reversible jump,reverse path sampling…

发表在 章节介绍 | 留下评论