分类目录归档:Ray Tracing

确定性的路径采样 – 微分流形在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算法非常需要的。

聊聊最近几年的路径追踪技术的进展(一)

(注:本文是对《全局光照技术:从离线到实时渲染》一书中路径追踪技术相关内容的一些高度概括和总结,本文仅讨论概念和思路,详细的内容请参考原书相关章节内容,转载请注明源自:http://www.thegibook.com)

路径追踪技术(Path tracing,PT)已经是当下工业中离线渲染使用的主流技术,不管是商业渲染器如皮克斯的RenderMan,Solid Angle的Arnold等,还是迪士尼的in-house渲染器Hyperion以及Weta Digital的Manuka都是基于路径追踪技术。路径追踪算法非常简单,它首先将光照方程表述为面积积分的形式,然后一束光线从光源经过各个物体表面及内部多次交互(反射,折射,散射)后进入图像平面的贡献值(即辐射照度)被转换为这些表面交互点形成的路径的一个积分,其被积函数为这些表面的双向散射系数(BSDF),顶点之间的积分变量变化(change of variables)以及顶点之间可见性的乘积。在统计中,积分可以很简单地使用蒙特卡洛方法进行估计,因此光照传输的问题就转化为对场景进行路径采样,然后对每条路径的贡献值进行平均求和的蒙特卡洛积分计算。

尽管自基本的路径追踪算法被提出以来,各种增强改进的方法被整合进来,然而上述路径追踪技术的“基础架构”几乎没有多少实质性的变化。对于任何行业,工业中主流的技术一般不是当下最先进的技术,而是最成熟可工业化的方案,当前工业中的路径追踪技术优化主要集中在优化算法的执行效率,主要是针对处理器硬件架构进行优化,例如针对缓存系统的优化,增强数据局部性和指令局部性,以及改进光线连贯性(ray coherence)使其能够利用SIMD指令进行高效计算等,这方面比较突出的是迪士尼的Hyperion渲染器,一些渲染器的优化更是几乎能达到某些场景复杂度范围内实时渲染,例如Embree。

然而以上这些内容却不是本文关注的重点(上述内容会在thegibook中详细讨论),本文我们要讨论的是一些路径追踪算法基础架构层面的改进,这些算法还很少出现在当前工业解决方案中,但是确实未来的重要发展趋势。

传统的路径追踪算法是一个单纯的积分问题,因此可以使用蒙特卡洛方法来估计,然而蒙特卡洛方法的每个抽样是独立的,因此很难有效快速对一些比较困难的路径进行采样,一些很难被采样的路径需要巨量的采样数才能达到“令人满意”的结果,这导致非常缓慢的收敛速度。尽管开始的收敛速度非常快(4倍采样数量可以减少1/2的误差),但是越到后面会花费更多倍的时间。传统的方差缩减技术如重要性采样,分层采样,拟蒙特卡洛方法(Quasi-Monte Carlo)仍然不能改变这个收敛速度。

要提升蒙特卡洛估计的收敛速度,直观上,我们需要能够辨识每个图像的分布特征,然后在一些高频变化区域增加采样的密度。然而,传统的蒙特卡洛方法中每个抽样之间是独立的,它并不能有效辨识这种频率变化特征,尽管梅特波利斯光照传输(Metropolis light transport,MLT)通过采样点之间的相关性能够寻找一些困难路径,本质上它仍然并不善于处理和分析频率域特征。要想能够辨识图像的分布特征,我们需要了解每个路径的局部特征,即是我们需要对路径追踪算法引入微分运算。路径的微分涉及路径与附近局部范围内光线的差值,即图像的局部特征,因此它引入了光线之间的相关性,可以从多个层面改善路径追踪算法的效率(也正是如此,我们认为这是近几年路径追踪技术领域的重大进展)。

最近几年路径追踪领域的一些重大进展正是微分几何(differential geometry)的引入,由于微分反应的是流形(manifold)的局部变化,因此非常善于寻找图像分布中的高频部分,目前路径追踪算法中的微分运用主要包括:以通过计算纹理过滤函数实现反走样的光线/路径微分(ray/path differential)和协方差追踪技术(covariance tracing);以通过计算梯度图像用于利用筛选泊松方程(Screened Poisson equation)重建目标图像的梯度域渲染(gradient-domain rendering);以及通过将微分几何结合费马定理(Fermat principle)用来寻找镜面/光泽路径的流形探索(manifold exploration),半矢量空间光照传输(half vector space light transport)等技术;此外,微分还被用于适配性采样(adaptive sampling),成为重要的降噪技术(Denoising)。

以下我们就来从概念和思路上分析上述这些技术,当然我们可以提前知道的这些技术的一个重要共同点就是:这些微分计算通常不需要通过光线追踪引入新的采样点,否则那样的计算成本就很高,这些技术通常都是利用微分几何和某些假设进行单纯的微分计算,这里主要的工具是一阶泰勒展开式(first-order Taylor approximation)和顶点处的切线平面空间(tangent space),因此,这些新技术通常都可以很容易地集成于目前主流的路径追踪技术基础架构之上,更详细的内容请参考thegibook中相关章节。

接下来我们讨论的每一种微分的运用都涉及一个相对比较独立的层面,在阅读这些内容的时候,你首先需要非常清晰的了解的是它用来解决什么问题,因此我会在每一节的开头提出这个问题,然后读者可以围绕这个问题来阅读每一小节,即每一种技术。

光照传输的局部频率域分析

微分反应的是图像的局部特征,因此其在图像渲染中最直观的运用就是用于反走样(anti-aliasing)。光线追踪算法中由于采用不足导致的走样问题可以分为两大类:对路径空间(path space)的采样不足和对纹理空间(texture space)的采样不足,本质上这都是由于路径采样的不足导致的,但是它们通常使用不同的方法来解决。一个像素区域内的光线从屏幕空间发射出去之后,随着光线在表面的各种交互这个面积可能会无限扩散,所以单纯增加路径采样的数量可能也很难弥补纹理走样(texture aliasing)的问题。所以它们分别对应路径追踪算法中两个比较独立的反走样技术:路径空间采样不足主要对应于降噪技术,纹理空间采样不足对应于纹理过滤技术。

目前降噪技术主要的思路是针对图像的分布特征进行适配性采样以及适配性重建,前者对应于在图像的高频区域放置更高的路径采样密度;后者对应于根据图像特征对不同的区域使用不同的重建过滤器(reconstruction filter)。对路径进行适配性采样的方法可以分为两类:第一种直接对光照传输方程进行分析,称为先验方法(a priori method);而第二种只对屏幕空间的图像进行分析,称为后验方法(a posteriori method)即是说与路径采样的方法无关。

光照传输的局部频率域分析可以用于纹理过滤以及作为降噪技术中的先验方法。以下我们讨论局部频率域分析的方法和思路。

路径的局部频率域分析虽然不是源自光线微分(ray differential)技术,但是跟它有很大的联系。光线微分技术的核心思路是随着光线的传播跟踪该光线对应的频率区域一个像素的大小,这称为光线的足迹(footprint),如下图所示,在路径追踪算法中追踪每条路径的时候,同时沿屏幕空间x和y方向分别发射一条一个像素大小的偏移路径,然后对每条基础路径同时跟踪两条偏移路径。路径在每个顶点处的足迹大小则可以通过积分计算出来。当然光线微分技术并没有完全利用微分几何的知识,因为它假设偏移路径和基础路径在每个路径顶点处位于同于平面-即该顶点的正切平面(tangent space)上,所以光线微分的计算大大简化了。

由于假设偏移路径和基础路径和表面的交点位于同一平面,上述光线微分技术仅适用于镜面表面(specular surface),路径微分(path differential)在此基础上将光线微分扩展到了光泽面(glossy surface)和漫反射表面(diffuse surface),它虽然有比较理论的推导,但是实践上主要使用经验方法,即根据表面的粗糙度用来缩放足迹的大小以支持光泽面和漫反射表面。

上述的光线/路径微分技术实际上是光线的一种局部特征,传统的路径追踪算法中每条光线之间的独立的,所以不能够分辨这种局部特征。然而上述方法还是有很多缺点,例如光线经过多次传播之后可能形状非常不规则,而两条偏移路径计算的四边形无法表达这种形状;其次偏移路径可能被阻挡,而光线/路径微分是忽略这种阻挡的;为了更好的追踪光线的局部特征,我们需要更完整的对光线的传输过程进行分析。

目前对光线进行局部分析的方法的思路主要是将光线的局部特征表示为一个空间-方向分布(spatial-angular distribution)的局部光照场(local light field),如下图所示,黄色的中心光线表示基础光线,周围的一些具有不同位置和方法分布的光线是一些虚拟光线,它们共同构成一个局部的空间-方向分布。例如对于摄像机光线,它的局部光照场的分布就是一个像素范围大小的一个过滤器,该过滤器对于每个不同方向和位置处的光线都具有一个不同的权重值,这个过滤器就反映了摄像机路径的局部特征;对于光源路径,如果是面积光,则局部光照场的方向为固定值,而位置分布于面积光源的各个位置。

有了局部光照场的描述,剩下的事情就是计算该光照场随着中心光线的传输。早期的思路是将光线在传输过程中的各种交互过程看做一个操作函数,例如光线的直线传输(transfer),反射,折射,阴影遮挡等,如下图所示,然后在局部光照场函数的频率空间进行交互,这样就可以跟踪局部光照场随中心光线的传播过程。

上述的傅里叶分析过程计算成本相对较高,为了简化局部光照场的传输,协方差追踪(covariance tracing)技术考虑可以将一个4D的空间-方向分布近似为一个椭圆形高斯分布(elliptical Gaussian filter),如下图所示,然后该分布可以使用该4D光照场的协方差来表示,所以局部光照场可以用其协方差矩阵(covariance matrix)来表示。然后这些对局部光照场的传播操作数就转变为矩阵操作,最后在计算足迹的时候再从协方差计算出该4D局部光照场的尺寸,这就可以用来替代上述的光线/路径微分技术用来实现纹理过滤。

协方差追踪不仅用于纹理过滤中计算局部光照场足迹的大小,还被用于适配性采样,如果我们从光源路径方向追踪光源的空间-方向分布至屏幕空间,则我们可以在屏幕空间分析图像的频率分布,进而可以用于适配性采样,如下图所示。下图的局部光照场是一个5D空间,它还包含了时间维度,因此可以用于计算运动模糊(motion blur)效果,在该图中,首先从光源发出光线经过一次表面交互(即直接光)之后投射一个椭圆形分布到屏幕空间,然后根据这些分布就可以计算出图像的频率分布,这些分布特征被用于适配性采样。

除了协方差追踪,光照传输的局部频率域分析还包括其他一些方法,但是目前协方差追踪是更简单和高效的一种技术。当然协方差追踪的限制是它将局部光照场近似为一个椭圆形的分布,实际的局部光照场分布特征可能还需要更负责的形状表述,这也是未来的优化方向。

下一篇我们将讨论梯度域渲染和流形探索或者半矢量空间光照传输。

Robust Light Transport Simulation via Metropolized Bidirectional Estimators

今年SIGGRAPH Asia上最感兴趣的莫过于这篇Robust Light Transport Simulation via Metropolized Bidirectional Estimators,看标题就很牛逼:原本比较独立的光线追踪两大经典算法BPT和MLT合体了!这里简要描述下这篇论文的思路:

传统上我们认为光线追踪有三大基础算法:BPT,PM和MLT,它们都是相对比较独立的,因为它们各自采用不同形式的光照公式,例如BPT的路径积分形式,PM的范围估计,MLT则是将整个图像看成一个分布,这些看起来都是完全独立的。然而它们各自都有优缺点,好的想法是能不能把它们组合起来。

例如BPT的缺点是不能处理SDS,PM的缺点是处理diffuse表面不如BPT,MLT由于抽样点的相关性导致处理高光表面很低效,因为Markov chain始终在高频尖锐的部分徘徊,从整个图像上看stratification不够好;

2012年的VCM/UPS算法是一个很大的突破,它开始尝试将BPT和PM结合起来,使用PM对light subpath采样,并且将算法统一到BPT中,这样BPT就可以有效处理SDS。近几年中VCM/UPS几乎成了现在主流的离线渲染解决方案(参见The Path to Path-Traced Movies这篇论文);

然而VCM/UPS的缺点是,因为它仍然是BPT的思路,eye subpath并不知道light subpath的情况,所以尽管它能处理SDS,但是两个subpath连接的时候形成的很多full path由于可见性(尤其对于复杂visibility的场景)而对光照贡献率很低,而MLT则很擅长处理Visibility的问题,所以这篇论文就基于VCM/UPS来使用MLT对light subpath进行采样,这样保证了两个subpath之间的连接更符合最终图像分布。这篇论文也就同时把BPT,PM和MLT三大基础算法组合在了一起!

具体做法就是,首先使用传统MC在图像平面生成eye subpaths,这里不使用MCMC产生eye subpath的原因是MLT在图像平面(image plane)的stratification不好;然后从这些eye subpath的位置开始产生Markov chain来产生light subpath(所以MLT在这里是用来产生一个subpath分布而不是整个图像分布)。这样整个算法能处理高光和复杂Visibility这两大难题的场景。

论文下载:http://www.ci.i.u-tokyo.ac.jp/~hachisuka/

全局光照技术进化史1-光线追踪篇

本来计划是最近一年专心写书,不要花心思和精力写博客的,因为写一篇优质的博客文章其实也要花费不少的时间构思的:单篇博客虽然文字少但是你可能需要花费更多的精力在有限的篇幅内包括更多上下文信息,以及更精简地组织内容,在我看来它的创作付出不亚于图书内容写作(当然如果作者对自己要求没那么严谨的话可能也没那么严重)。

《游戏引擎全局光照技术》采取了一种新的出版形式,它从写作第一章开始,就积极和社区互动并开始宣传,其方式和游戏发行的思路一致:即在开发阶段不断推出测试版积极和玩家互动,并收集反馈信息进行持续改进。这样做的好处是:读者较早获得试读版的信息,了解和监督了书的写作质量,从而可以做出有效判断是否值得购买,糟糕的图书质量可能在这一阶段就直接被淘汰,甚至失去了出版意义,从而保障读者利益;同时对于作者,我能够持续吸收社区反馈意见以改进内容质量,使图书的质量可以不断地形成增益,好的内容能够被社区传播扩散;这对于读者和作者都是一件共赢的事情。

为此,我已经提供了该书1,2,3三章共计157页正文的试读内容供所有对该书感兴趣的朋友免费下载,如果您还不知道可以从这里下载。然而尽管如此,从目前社区讨论的信息来看,大部分读者还是不太明白这本书跟其它同类书籍会有什么不同,尽管我已经使用一个问答的形式来简要概述这本书的特点,然而我们都知道,这些文字跟你在技术大会上那些厂商递给你的一个介绍他们公司产品的小册子上的文字一样:在你使用它们的产品之前,那些文字通常跟屁没有什么差别。

所以我需要写一点更通俗篇幅相对长一点的文章来解释这本书的内容和特点,通俗使得您可以像读其它社交信息一样很轻松地进行阅读,不需要太多思考和理解,而篇幅需要长到足以介绍这本书覆盖的内容和特点。正巧在百度贴吧的“孤岛危机吧”看到一篇想要了解各种全局光照技术的特点及联系的帖子,他所提出的问题正是本书试图去讨论的内容,所以我就想回答了他的问题其实基本上能够说明这本书的内容和特点。

学习全局光照技术(Global Illumination,以下简称GI)比较头疼的一个因素是它的方法派别太多了,每个算法可能涉及到完全不同的数学方法,而如果我们没有对方法本身的思路具有一定的理解,在运用方面也不会很顺手,尤其涉及到要进行优化或修改以满足特定需求时,你必须要比较全面的理解该方法:它的起源,历史,数学模型,新方法的优缺点,它在计算性能和图像质量方面有着怎样的折中等等;并且,通常每种方法并不像一个软件模块那样比较独立很好理解,每种GI算法往往涉及CPU/GPU的数据结构表述,内存布局以及访问,和渲染管线其它阶段(如Deferred Shading,AA等)的协作,图形接口的运用,算法处理器级别的优化等,这些因素使得GI的学习并不那么轻松。

所以我在2015年初就萌生了写作一本围绕各种GI技术来进行内容组织的书籍,它不像《Real-time Rendering》这类书籍一样基本上以各个理论知识点为中心,它以方法为中心(尽管如此,本书还是包括了将近300页的基本理论知识的介绍),着重讨论各种GI方法背后的思路以及方法之间的联系,因此它较偏理论性的书籍拥有更强的实践性。这种写作思路其实类似于《Advanced Global Illumination》(简称AGI),但是AGI基本上主要围绕路径追踪和辐射度理论两种方法来讲述,其它一些如光子映射等有一定的介绍,但是篇幅极短;本书不但会介绍路径追踪和辐射度理论等这些离线全局光照技术,还会介绍时下比较流行的距离场,体素等实时的全局光照技术,并且本书结合Unreal Engine等游戏引擎来讲述,读者更够更好地理解这些引擎的功能特性。

这篇文章,我们就来看看全局光照技术的进化史。遵循通俗的原则,本文不会包含数学公式,全部内容是以文字和配图描述,当然这样的方式肯定不可能包含很多细节,它更注重的是思路描述,更具体的信息还请您参考《游戏引擎全局光照技术》图书内容。

我们从光线追踪算法开始。光线追踪算法的起源可以早至1968年,Arthur Appel在一篇名为《Ray-tracing and other Rendering Approaches》的论文中提出的Ray Casting的概念,我们称为光线投射,如下图所示,光线投射其实只是一根单一的从一个点向一个方向发射出光线,它与场景中的物体相交时停止,Appel的算法中使用了View Ray和Shadow Ray两条光线,这计算出来的其实就是光照方程中的直接光照部分。

Ray Casting

1979年,Turner Whitted在光线投射的基础上,加入光与物体表面的交互,是光线在物体表面沿着反射,折射以及散射方式上继续传播,直到与光源相交。如下图所示,这种算法形成了一个递归的光线穿梭,因此此时不再是一根单一的光线,而是形成了一个光传输的路径,此时的算法称为递归光线追踪(Recursive Ray Tracing,或者Whitted-style ray tracing);显然,光线在多个表面上反射或折射,间接光被考虑进来,光在经过每一个表面的时候,通过该表面的反射/折射率的“过滤”,它将物体的颜色渗透到邻近物体的表面上,这就是我们所说的Bleeding。

Recursive Ray Tracing

然而Whitted的模型是基于纯高光反射的,它假设物体表面绝对光滑,这显然和大自然中大部分物质的表面属性不相符。在计算机图形学中,一个像素的尺寸远远大于光的波长,在这个微观尺寸(Microfacet)下,物体表面是不光滑的,也就是说进入一个像素的多个光线可能分别被反射到不同的方向上,根据表面粗糙度的不同,这些散射的方向呈现不同的分布,非常粗糙的表面可能比较均匀地周围反射,而比较光滑的表面反射光则集中在光滑表面的反射方向附近。在现代渲染技术中,这些反射特性通常被使用Microfacet BRDF公式表述出来,它基本上使用一个简单的粗糙度方向就可以模拟出比较真实的光反射分布。结合金属性等一些参数,这就是目前流行的基于物理的渲染模型。

ray-optics-6

通常这些不同的分布被使用漫反射和高光反射两种分布来表述,如上图所示。1984年,Cook提出了分配光线追踪(Distribution ray tracing),他使得原来一束单一的反射光变为围绕一个空间中漫反射或高光反射范围内的积分计算,如下图所示。为了计算积分方程,蒙特卡洛方法被引入,所以Cook的方法又称为随机光线追踪(stochastic ray tracing)。

Stochastic ray tracing

Stochastic ray tracing

然而,Cook的模型计算代价非常高,每一条从摄像机发出的光线在表面点是被反射至多个不同的方向,分散成多束光线,以此递归,每条光线最终形成一个光线树(a tree of rays),尤其对于间接漫反射光,它几乎要反射至整个可见空间。

Cook的模型是由光照公式递归的特性决定的,光照公式中每个入射光的值来源于其它许多表面点反射的计算结果。1986年,Kajiya统一了光照公式,并推导出了光照公式的路径表述形式,使得光照公式由一个递归的结构,变成一个路径函数的积分,因此蒙特卡洛的每个随机数只要产生一条路径即可,这些路径不需要是递归的,因此每条路径可以随机生成,然后每个路径的值作为一个随机数用于计算最终的光照结果。这种新的形式称为路径追踪(Path tracing),如下图所示。在路径追踪算法中,首先在场景中物体的表面随机产生一些点,然后将这些点和光源以及摄像机链接起来形成一条路径,每个路径就是一个路径函数的随机值。这样的路径,根据场景的复杂度,每帧可能包括上亿条光线,因此传统的路径追踪算法很难运用到实时渲染领域。

path tracing

path tracing

上述这样的产生随机路径的方式有一个问题,有相当部分的路径组合由于表面间可能被遮挡而形成无效的路径,对最终光照没有任何贡献,因此大部分实现都是以增量的形式,在每个有效的反射或折射方向上进行随机采样,已形成更多有效的路径;

另一个问题是由于光源面积相对于整个场景很小,由摄像机出发的路径最终落在光源面积内的几率很小,因此双向路径追踪(Bidirectional path tracing)被提出,它分别从光源和摄像机两个方向出发,分别经过一定的路径之后,将该两条路径的终点链接起来形成一条完整的路径,这样大大增加了光源的有效贡献,可以从下图看出两者之间的区别。

untitled

当前大部分高质量的离线渲染器基本上都是基于路径追踪算法实现的,然而路径追踪的计算成本仍然非常高昂。现代路径追踪算法的发展主要有两大方向:其一是围绕提升上亿光线之间的连贯性(coherence)来提升处理器的利用率从而大幅提升计算效率,其二是微软Metropolis算法来使采样的随机路径更接近最终图像的真实颜色分布,后者称为MLT(Metropolis Light transfer)。

光线/路径追踪算法高昂的计算成本不仅来源于蒙特卡洛积分使用的大数定律要求的巨大的光线数量,另一方面重要的因素还在于路径追踪算法及其使用的数据结构不能适应现代CPU/GPU使用的执行模型。首先是内存执行模型,由于处理器计算单元的速度和内存数据存取的速度存在巨大差异,计算单元从内存中获取数据存在巨大的延迟(Latency),现代处理器非常严重地依赖于缓存技术,即将较大一块的内存数据缓存在具有更高读取速度的缓存中,如下图所示,缓存系统通常设计为多层机构,每一层比下一层具有更高的访问速度,但是更高速度的缓存硅片的成本更高,所以更高速度的缓存往往存储的数据量更小,这样顶层的一级缓存的速度跟寄存器的访问速度比较接近,通过缓存系统,计算单元到内存的数据访问延迟就被掩藏了。

path-14

缓存系统是根据传统应用程序的特点设计的,通常,相邻指令使用的数据在内存区域也是相邻的,所以相对寄存器更大一块的数据能够被多条指令使用。当指令从上一级缓存获取不到需要的数据时,就会从下一级缓存一次性获取另一块数据,并替换原来的数据,这种情况称为缓存失效。因此应用程序必须在数据上保持一定的连贯性,才能充分利用缓存特性,以提高计算性能。而路径追踪算法显然不符合这样的条件,每一条光线可能随机穿向任意一个方向,从而与环境中任意表面进行相交,所以相邻的指令使用的数据往往分散在内存中的各个区域,大大减少缓存命中的几率。

处理器架构的另一个特点是称为单指令多数据(SIMD)的计算模型,在SIMD中,寄存器一次性读取多个数据变量,这些数据被同一条指令执行,例如传统的CPU环境中SIMD寄存器可以读取128位数据,分别可以表示4个32位的数据,如下图所示,而在GPU环境下,每个GPU线程束可以一次性计算32个线程,当这32个线程所需要的数据在内存结构上相邻时,它们可以被一次性存储,大大减少每个线程获取线程带来的事务开销。

path-16-2

所以,基于连贯性(coherence)的路径追踪技术将这些数据分组成一些小的数据包,称为光线包(ray packet),这些数据包包含多个内存相邻的数据,并能能够被同一个指令执行。传统的基于光线包的技术主要是针对主要光线(Primary rays),即摄像机向场景发射出的光线,之后的光线可能向场景随处发射,并且对性能影响更大。

2013年,迪斯尼的Christian Eisenacher等在一篇名为《sorted deferred shading for production path tracing》的论文中提出了一种改进方法,这种方法的核心思想是在实际计算之前对光线进行排序,如下图所示。

path-10

在实际处理中,这主要分为三步(如上图左边的流程):首先,在每次增量计算光线与场景相交时,首先对光线进行排序,并将这些经过排序的光线按照方向以及数量大小分成多个包,然后以这些包为单位进行计算;其次,对场景建立一个BVH的加速结构,经过打包后的光线是连贯的,所以其相交计算涉及的场景表面在空间上也是连续的,因此能够比较友好地使用缓存和SIMD处理器特性;最后,由于来自各个方向光线可能与同一表面进行相交,所以在相交计算时直接计算光照反射并不是很高效,所以迪斯尼将着色分离出来,在相交计算的时候,所有相交点与纹理信息进行关联,纹理被划分成一些区域,然后着色计算以纹理区域为单位进行计算。通过以上这些优化,如下图所示,Disney新的路径追踪渲染器渲染性能得到极大提高,这些技术连同Disney的BSDF等技术一同被首次运用在《超能陆战队》以及后续的电影中。

path-12

基于连贯性的路径追踪算法的思想能够很好地利用现代处理器的架构特征,不管什么样的路径追踪算法基本上都可以在这方面进行改善,这也是传统路径追踪技术走向实时的方向。

基于Metropolis算法的MLT方法则着重于更准确地对路径进行采样,以计算更高品质的图像,毕竟传统的路径追踪算法很多路径采样的贡献率可能很低。Metropolis算法的核心思想是使用马尔可夫链(Markov Chain),它对当前随机数进行一个适当尺度的扰动(perturbation)以产生一个新的随机数,然后使用逼近真实分布函数的概率来对新的随机点进行取舍,这样使得新的采样点满足实际分布函数的分布。

qq20161106-02x

由于路径追踪算法每个随机数产生的是一个路径计算的光照结果,因此MLT中的每一个随机数是一个路径,这个新的路径根据一定的策略对前一路径的某些部分进行扰动,以产生一条新的路径,然后计算出的该路径的光照结果就是每个随机数计算出的光照数值。

由于MLT中的每个随机数是一个路径的结果,整个路径的分布就是整个图像的颜色分布,因此MLT计算出的是整个图像的结果,然后每个像素点需要使用过滤器对每个像素周围的颜色值按照一定的权重比例进行加权平均。

qq20161106-12x

原始的MLT算法直接在路径空间(Path space)对路径中的顶点进行扰动,这样新产生的路径可能存在被遮挡的可能,因此产生非常多的无效的被舍弃的随机数,Csaba Kelemen等于2012年的论文《A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm》中提出在一个超立方体(hypercube)作用域内,即所谓的Primary space对路径进行扰动,超立方体内的每个随机数是[0,1]范围内的均匀分布产生的随机数,这个随机数使用BRDF等分布的逆向变换算法求出实际的方向或者点灯随机数,这些随机数用于产生新的路径,这样的基于Primary space产生的随机路径具有较高的接受率。

qq20161106-22x

更新的基于MLT的算法基于路径求导来产生更好的符合表面光照分布的扰动,例如对于高光,它能够在高光方向上选择更多的方向,以使MLT计算的结果更接近于真实图像的分布,如上图所示。关于路径求导,以及其它如基于梯度的MLT算法等这种使马尔可夫链产生的随机数分布更加接近图像真实分布的思路,是路径追踪技术方向目前比较热门的主题。