月度归档:2017年08月

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等这些保驾护航。