elvish ray 原型系统的架构及实现
Len3d
【摘要】本文详细论述了elvish ray 渲染器原型系统（以下简称原型）的架构及实现，包括原型的光线追踪框架、自适应采样、半蒙特卡罗算法与多线程并行机制，以及如何对REYES 算法进行改进以集成到该框架中，并讨论了原型中全局照明等功能所使用的相关算法及实现细节。随后阐述了如何基于原型，重新设计一个更优雅与完善的架构，包括任意几何体的光线追踪、几何实例化与大场景处理的统一框架，以及elvish ray 独特的着色语言接口的实现，给出了该架构的详细描述及重写elvish ray 新版本（以下简称新版）过程中具体问题的解决方法。
【关键词】光线追踪；全局照明；REYES ；渲染器
1. 引言
照片真实感图像的生成一直是计算机图形学的研究热点，而真实世界具有非常复杂的几何结构和光照环境，想要令人信服的模拟其效果往往涉及巨大的数据量和计算量，必须通过一个统一、高效、灵活的渲染架构及其中包含的各种实用的算法才能克服该困难。而当今，对真实感图形的需求已经深入许多领域，包括电影特效工业、建筑与室内设计行业、工业设计、游戏与虚拟现实行业等。elvish ray 渲染器正是为了满足这样的需求而诞生的。笔者于2006年9月开始编写该渲染器项目，2007年6月发布为开源项目，经过一年多的开源开发，2008年8月基本完成了原型，将开发重点转移到完全重写的新版本，2009年2月，新版本顺利运行，目前还在继续开发中。虽然现在市场上已经存在不少非常强大的商业渲染器，包括Pixar ’s RenderMan, mental ray, V-Ray 等，但是这些渲染器并不开放源代码，我们仅能使用，并不能从根本上拥有渲染的核心技术，因此不能通过对核心技术的掌握，提供更大的灵活性与更高层次的创造力，elvish ray 项目的意义正是在于弥补了这个缺憾。
elvish ray 拥有一个混合的架构，将各种主流的渲染技术和算法集成在一个统一的框架中，并对原始算法做了调整和改进，以适应elvish ray 独特的架构。本文第2节介绍了elvish ray 中用到的主要算法，
第3节介绍了elvish ray 的渲染管线与光线追踪框架，第4节描述了REYES 算法是如何集成到现有管线中的，第5节描述了全局照明的实现，第6节描述了我们重写后的新版本的架构设计，第7节介绍了系统的使用方法、跨平台设计与开发工具，第8节是现有实现的测试结果与比较，第9节展望了未来可能的改进，最后第10节是结论。
2. 相关工作
2.1. 渲染方程
Kajiya 提出的渲染方程[1]给出了光能在场景中不断传播所产生的全局照明现象的数学描述。渲染方程可以表示为在任意点对场景中所有表面发射出的光能的积分：
2'''cos 'cos )','()',,()',(),(x x dA x L x x x g x L S x -=
?∈θθωωωρω (2-1)
其中x 是当前采样点，S 是场景中所有表面的集合，'x 是
S 中的任意点，ω是x 处光能出射的方
向，'ω是'x到x的入射方向，θ是'x处表面法线与'ω方向的夹角，是'x处的微面元，是两点间的几何遮挡函数，ρ是表面的BRDF，是表面上某点沿某一方向的出射光能。
2.2.分布式光线追踪算法
Cook等提出的分布式光线追踪算法[2]利用蒙特卡罗积分来求解渲染方程。这项技术提供了一个统一而简单的框架来模拟面积光源、运动模糊、景深、模糊反射/折射等效果。
分布式光线追踪允许按照一定的分布规律在空间中分布一定数量的光线，通过加权平均这些光线的采样结果来得到最终样本的值。例如光线可以在时间轴上分布以生成运动模糊效果，在摄像机镜头上分布以生成景深效果，根据BRDF分布以产生模糊反射效果等。
Cook等并不是对图象空间的一个采样点发射数条光线，而选择每个采样点仅发射一条光线，并在其递归光线追踪过程中仅派生一条光线，而通过增加图象空间的样本数目来处理走样问题。
2.3.Photon Mapping
Jensen等提出的用于模拟全局照明效果的Photon Mapping算法[3]是一种典型的两步求解技术，并且所得的全局照明解不依赖于场景几何。算法在第一遍时，从光源分布式的向场景中发射一定数量的携带了光源一部分光能的光子，在场景中经过表面的多次反射/透射，最终生成一个记录了场景大致光能分布的点集，称为Photon Map。Photon Map被储存为类似堆结构的kd-tree形式，在第二遍时供着色点快速查询当前位置的间接照明光能。该算法可以将渲染方程中不同的照明分量分多次计算并储存在多个独立的Photon Map中，使用起来十分灵活。
2.4.Irradiance Gradients
如果利用蒙特卡罗方法为每个采样点计算间接照明，计算量往往非常巨大，所以一个可行的优化是只对采样点中的一部分计算间接照明光亮度，而对其余采样点进行插值，当场景中的间接照明光亮度变化较为平缓时，这种方法可以非常显著的减少渲染时间，并取得同样好的结果。Ward与Heckbert提出了基于Irradiance Gradients的插值方法[4]，能够让插值结果更为平滑。该方法主要利用了蒙特卡罗方法在半球域采样过程中得到的除光亮度之外的信息，包括方向角和交点距离，构造出光亮度的旋转梯度和位移梯度，在后续插值中，运用这些信息对光亮度及其梯度进行插值。由于只是利用了半球域采样过程中得到的额外信息做了更高阶的插值，所以该算法在得到显著更好的结果时并不会带来明显的额外开销。
2.5.Adaptive Sampling
由于光线追踪计算量较大，所以Whitted等在文献[5]中建议先对图象平面上一个粗糙网格的节点处进行采样，接着递归细分网格并在新增加的节点处采样，直至每个网格的四个角点处的颜色值之差小于给定阈值，这显著减少了所需要计算的样本数目。
2.6.Quasi-Monte Carlo Sampling
Keller提出了一个基于Quasi-Monte Carlo方法的采样框架[6]用于对任意维度进行分布式光线追踪、Photon Mapping计算以及Final Gathering的计算。Quasi-Monte Carlo算法去掉了纯Monte Carlo算法中各采样点的分布必须相互独立的假设，让采样点之间满足一定的约束关系来加快整体的收敛速度。Keller 的采样框架利用了低差异度序列生成算法的特点，在分布式光线追踪中，令图象空间的每一个采样点对应低差异度序列的一个instance number，而让蒙特卡罗积分中的每一重积分，对应于低差异度序列的一个维度，在分布式光线追踪过程所对应的光线树中，每条子光线都被根据其父光线的instance number
与维度赋予新的instance number与维度，采样时根据当前instance number与维度生成采样点。由于所有采样点的位置都是由初始光线所对应的像素位置唯一确定的，所以该算法是确定性的，可以很容易的在多核心或多处理器系统上并行。
2.7.REYES扫描线算法
由于光线追踪算法与传统的扫描线算法都不能很好的满足电影特效制作对于速度和质量的要求，Cook等在文献[7]中提出了REYES扫描线算法，该算法假设所渲染的景物必须满足可以用有限大小的包围盒包起来，并可以不断分割为更小的子物体，最终转换为微多边形网格。算法是一个递归分割物体的过程，直至物体的包围盒满足一定限制，即将物体转换为微多边形网格，在微多边形网格的顶点处进行广度优先的并行着色，最终利用文献[8]中描述的随机采样方法光栅化为图象。文献[9]中描述了对原始REYES算法的一些重要改进，包括将图像平面分割为多个图块以减少当前数据集大小，以及根据已渲染的景物的位置和深度建立层次结构来对未渲染的景物进行快速的遮挡裁剪等。
2.8.RenderMan接口规范
由于工业级电影特效制作对渲染器功能和灵活性的要求，Pixar制订了RenderMan接口规范[10]。该规范包括场景描述语言与着色语言的定义。对于场景描述语言，RenderMan使用与OpenGL[11]类似的graphics state概念，用一个栈结构维护当前渲染器的内部状态，使用者可以不断改变当前状态，将状态绑定到当前景物，然后恢复上一个状态。但RenderMan提供了更强大的灵活性，每个景物与顶点都可以绑定任意多个用户变量，在着色语言中可以访问这些变量。RenderMan的着色语言的语法非常类似C，但是提供了对color, point, vector, normal这些图形学中常用数据类型的表达式操作，同时预定义了一组着色器变量来描述当前着色点的信息，还可以使用illuminance, illuminate, solar, gather等方法直观的进行场景中光照的计算，而不用关心渲染器具体的实现细节。
2.9.mental ray场景描述语言与着色语言
mental ray的mi2规范[12]使用了与RenderMan规范截然不同的概念。mi2的场景描述语言基于DAG(Directed Acyclic Graph)结构，景物可以独立的定义，随后通过一定方式连接到一起，并且支持场景的渐进式修改，不用像RenderMan一样每帧重新定义一遍所有场景元素，而可以只修改每帧中相对于上一帧变化了的那部分场景元素。mi2直接使用C语言作为着色语言，着色器需要被编译成DLL/DSO 以链接到mental ray，由于编写和编译时需要涉及到很多系统底层的细节，所以使用上比RenderMan更为困难与不直观，但是提供了对渲染器更灵活的控制能力。
3.渲染管线与光线追踪框架
3.1.渲染管线
渲染管线是一个渲染器的核心部分。原型目前基于一个自动通过多线程机制并发执行的任务管理系统，可以在多核或者多处理器的系统上获得相应的速度提升。渲染管线分为多个阶段顺序执行，但是每个阶段内部可以向这个任务管理系统登记多个相对独立的任务，例如Photon Emission[3]阶段的光子发射任务、Final Gathering[4]预计算阶段的Final Gather Points（以下简称FG Points）计算任务、以及主渲染阶段的eye ray发射任务等，并准备好这些任务各自需要的输入数据，随后启动并发执行，主线程进入等待状态，直到所有任务完成，任务管理系统自动将各个任务输出的结果数据合并到全局数据库中，接着进入渲染管线的下一个阶段，如图3-1所示：
图3-1 多线程任务执行流程
原型的渲染管线大致是分如下几步进行的：
(1)从API接受场景的描述，并且组织成内部数据结构，这些数据我们称为Persistent Data Layer（以下
简称PDL），而其他一些数据，比如Raytraceable Object Data，属于基于这些数据计算和转化出来的数据，渲染中是可以丢弃的，因为总能再重新计算出来，我们称为Derived Data Layer（DDL）。
相对于DDL，PDL总是优先被放在内存中，方便数据的重建，而当内存不足时，DDL最可能被从内存删除。
(2)在建立了PDL之后，开始预处理阶段，包括将图像划分为很多小块，称之为bucket，渲染的时候，
每个线程都按照Hilbert曲线的顺序，不断从任务队列中抢占未被渲染过的bucket逐个渲染。这样的好处是节省内存，因为只有一部分数据需要存放在内存中。这个阶段还创建BSP加速结构，并且从PDL创建DDL，比如为每个景物创建相应的Raytraceable Object Data并填充到BSP中。(3)在渲染每个bucket的过程中，先建立相应的buffer用于存储图像和其他缓存信息。随后开始如前
所述的Adaptive Sampling[5]过程，分为Basic Sampling和Super Sampling两部分。第一步，Basic Sampling过程中，根据场景的渲染选项设置，调用sample函数对每个象素网格的角点发射eye ray （如果是scanline模式，则发射reyes ray），采样场景，获得样本信息（通常是颜色）并放入缓存。
第二步，开始Super Sampling过程，检查缓存中相邻样本的颜色差异是否超过用户给定阈值，如果是，就在相邻样本之间插入新的采样点，进一步采样。我们将用户给定阈值除以2的Super Sampling 深度次幂，用于判断当前采样层次的相邻样本的颜色差异是否过大。最后，所有采样点被统一通过用户指定的滤波函数重建成最终的图像。为了提高过滤的效率，过滤只在有被采样过的点处进行，而不是对一张大的图像进行缓慢的过滤，所以我们在buffer中储存的并不是样本信息，而是指向样本信息的指针，并且要求精确的计算每个样本点的权重，这个权重不但包含滤波器的权重，还包含样本点的覆盖面积，测试表明这种方法速度快且效果很好。为了避免对每个象素重新计算滤波器的权值，我们预先建立好离散的滤波器，储存在一个二维数组中，并且忽略随机采样带来的jittering 对该值的微小影响，最终过滤的时候直接按照样本位置与被影响象素位置的二维位移向量查表即可。
(4)最后，渲染完毕，做一些后置处理，比如基于后置处理的Depth Of Field。然后输出结果，释放资
源等。
3.2.光线追踪框架
原型在追踪光线时，先初始化一些数据，建立一个叫做RayState的结构，这个结构用于记录光线的当前状态，并且储存交点相关的信息，然后光线进入场景的根结点，通过一个循环来代替递归以遍历BSP，建立了一个叫做BSPStack的栈数据结构来自己管理栈，因为如果不自己管理，递归到达一定深度后，会因为局部变量用尽系统的栈空间而崩溃弹出，而且自己管理速度也更快一些。
另外，对于BSP的划分算法，原型有两种划分模式，一是balance，所谓平衡划分，自动寻找平衡的分割平面使得结点的求交代价较小，另一个是middle，就是简单的选择中面作为分割平面。普通的场景，两种模式差别不大，但是理论上balance更好一些。对于balance，有两种划分实现，一是遍历所有景物，排序，估计所有可能的分割平面的代价，选择代价最小的分割平面，这个算法的复杂度是O(N2)，虽然理论上有更好的O(NlogN)的算法[13]，但是我们并没有采用，因为该算法实现上并不简单直观，并且光线追踪的主要代价通常在于遍历阶段，构建BSP阶段的开销在整体开销中所占的比例往往很小。而且，对于景物过多的结点，我们用了另一种基于鸽巢排序的次优算法，先将景物按位置分类到1024个鸽巢中，再从这些鸽巢的端点中选择代价最小的分割位置，复杂度是O(N)，这样基本上可以满足快速划分的需求。
3.3.Quasi-Monte Carlo Sampling
Quasi-Monte Carlo Sampling被运用于整个系统中涉及采样的各个部分，基于如前所述的一套完整的采样理论框架[6]，是整个渲染系统的基础。我们限制系统的最大积分维度为128，然后预先根据van der Corput序列[14]与Faure方法生成前128个素数及其各自对应的scrambling permutations，并储存在查找表中。实际渲染中，我们根据当前光线的维度和instance number，通过这一查找表计算其对应的Halton 序列或Hammersley序列，用于生成实际的采样点。
对于Adaptive Sampling，每个图象平面上的采样点都对应于最大采样深度所确定的网格上的一个角点，我们利用角点的整数坐标，计算出当前采样点所对应的instance number，用于生成后续分布式光线追踪的光线树中的一系列instance number。为了加快渲染速度，我们还预计算了一个以2为基的van der Corput序列，储存在查找表中。
3.4.Adaptive Sampling and Image Reconstruction
Adaptive Sampling是通过比较相邻样本之间的颜色差异是否过大，进而决定是否需要继续采样并添加新的样本的过程，而Image Reconstruction是通过Filtering从采样点集信息重建出原始图象信号的过程。由于使用Adaptive Sampling，采样点在图像平面上的分布并不均匀，因此不能按普通的图象滤波的方式重建最终画面，在实际测试中我们发现，如果按照最大采样深度所对应的象素网格滤波，当滤波半径较大时，速度慢到不可接受，并且由于大部分网格点未被真实采样点填充，浪费了大量储存空间。
于是，我们建立两个buffer。一个buffer的大小为最大采样深度所对应的象素网格的大小，称为sample buffer。另一个buffer的大小为最终图象所对应的实际象素网格大小，称为pixel buffer，pixel buffer 的每个象素点储存一个样本列表。每次采样得到一个新的样本时，我们都根据该样本的位置，将该样本的实际数据插入pixel buffer中最近象素点的样本列表中，而将指向该样本数据的指针填入sample buffer 上对应的位置中去。
在Adaptive Sampling过程中，由于我们需要快速查找与某个样本相邻的样本以比较它们之间的颜色差异，可以先计算出相邻样本的位置，再直接按照位置获得sample buffer中对应的样本数据指针，进而访问样本，时间复杂度为O(1)，但是由于不需要在未采样的位置处储存实际样本数据，极大减少了内存用量。
在Image Reconstruction过程中，我们对于最终画面上的每一个象素，计算其滤波半径范围内覆盖了pixel buffer中的哪些点，从而让这些点处的样本列表中的所有样本对当前象素的颜色值按照权重做出一定的贡献。和按照普通图象的滤波方式相比，这避免了在实际采样点很稀少的地方对大量象素进行加权平均，在实际测试中，特别当滤波半径较大时，极大的提高了过滤的速度。
3.5.Multi-threading
由于使用Quasi-Monte Carlo Sampling方法，所有采样点的位置看似具有一定的随机性，但实际上都是完全确定性的，因此可以保证在并行的时候不同线程所计算生成的采样点完全一致，线程之间不需要任何信息交换，所以非常适合并行处理。
另外，对于Image Reconstruction，由于需要Filtering，相邻的bucket之间会有一些采样点重叠，但是我们在这里强制对这些重叠的采样点进行重复采样，避免bucket之间共享样本所带来的同步开销。通常在滤波半径不大时，强制重复采样所带来的额外开销是可以忽略的，一般小于线程同步所带来的开销。
4.REYES算法的集成
REYES算法被集成到了elvish ray的渲染框架中，用于处理视域直接可见景物的光栅化。为了利用elvish ray统一的Adaptive Sampling与Quasi-Monte Carlo Sampling采样框架（以下简称Adaptive QMC Sampler），保证使用光线追踪模式与使用REYES模式所得到的采样结果基本一致，我们使用了改进后的REYES算法。系统的架构如图4-1：
图4-1 统一光线追踪与REYES采样框架
下面介绍对原地REYES算法所作的改进，以及这些改进如何影响算法的集成与整个系统的架构。
4.1.Splitting Loop and Bucketing
原地REYES算法[7,9]仅有一个Splitting Loop，该Splitting Loop不断抛弃不在视域之内的primitive，并将无法透视投影或者投影后在屏幕上面积过大的primitive分割为sub-primitive，直到所有primitive 都足够小，并且能够转换为Micro-polygons为止，随后对Micro-polygons做vertex shading，最后使用Stochastic Sampling算法光栅化这些Micro-polygons并过滤输出图象。事实上，原地REYES算法一次只取出一个primitive，让它经过以上所有流程后，绘制到屏幕上，所以非常节约内存。但是为了利用Adaptive QMC Sampler，我们扩展了光线追踪的概念，Adaptive QMC Sampler只负责确定采样点所在的位置、时间等初始信息，发射采样光线，而实际的消隐工作则由具体的光线追踪模块或者REYES模块负责，因此，我们的管线并不能像原地REYES算法的概念那样，将景物逐个绘制到画面上，相反的，我们预先确定好采样光线，然后让光线与场景求交，通过获取交点信息来生成样本信息。对于REYES 模块，采样光线实质上对应于屏幕采样点的二维坐标与Quasi-Monte Carlo算法所确定的采样时间，求交过程实际上对应于当前采样点的二维坐标与投影在屏幕上的二维多边形（我们选择三角形作为基本图元）进行包含测试。由于使用Adaptive Sampling，我们无法预先知道采样点的数目，不能像Stochastic Sampling那样预先确定好sample pattern，并且，和光线追踪中的概念类似，一条光线可能与整个场景求交，因此我们不能像原地REYES算法那样逐个取出primitive，而是一次性将所有当前bucket中的景物均处理成Micro-polygons，之后与采样点做包含测试，如果采样点位于Micro-polygons之内，则类似
Z-Buffer算法，检查交点的深度是否比已有采样点更近，如果是，则记录当前交点。
为了避免使用过多的内存，我们并不是一次将所有primitive都处理为Micro-polygons，而是预先进行一个全局的Splitting Loop，首先检查当前primitive是否在视域内，不是则抛弃，是则检查该primitive 能否被投影到屏幕上，如果能，则投影该primitive，根据投影的包围盒确定该primitive覆盖了哪些bucket，将该primitive添加到对应bucket的待处理primitive列表中，否则，分割该primitive为更小的sub-primitive 直至全部primitive均被抛弃或者投影为止。随后，我们进行各个bucket中的局部Splitting Loop，这里和原地REYES方法类似，只是我们会将生成的Micro-polygons储存在一个列表中，而不是像原地REYES 算法那样，绘制好一个Micro-polygon之后就立即删除它，因为我们利用采样的概念来统一渲染框架，已经没有绘制的概念了。另外，由于各个bucket内部的Splitting Loop和求交计算是相互独立的，我们可以利用已有的任务管理系统来并行各个bucket的渲染。
4.2.Binary Dicing
因为REYES算法会将primitive分割为sub-primitive，当两个相邻的sub-primitive的细分出的Micro-polygons数目不一致时，它们之间就会留出裂缝。为了处理这种裂缝问题，我们使用Binary Dicing 方法，即强制景物的沿着共享边细分出的Micro-polygons数目必须是2的幂次，这样细分得更精细的一边总能通过把顶点移动到细分得更粗糙的一边上，来填补裂缝。
4.3.Grid Acceleration Structure and Sampling
如果让采样点与当前bucket中所有Micro-polygons求交，计算量依然过大，所以我们按照bucket 的象素分辨率建立网格结构，按照Micro-polygons的包围盒将其添加到它所覆盖的网格中，在求交时，先按照采样点的位置确定其位于哪个网格中，再仅与网格中的Micro-polygons做求交测试。
5.全局照明的实现
5.1.Photon Mapping and Caching
原型的GI基于Photon Mapping算法[3]，也是基于光线追踪。首先要有这样的概念，场景中的间接照明光能，最终要转化为漫反射能量才能被人眼看到，否则如果是镜面反射，那么到达人眼的概率是0，所以最终GI都是算在漫反射项里面的，而其中间过程允许任意次的镜面反射或漫发射。
Photon Mapping算法是典型的两步法。第一阶段，称为Photon Emission，先调用场景中光源的Photon Emitter Shader，分别发射GI光子和Caustics光子。光子随着光线，在场景中进行光线追踪，一旦击中景物，就调用该景物的Photon Shader，这个shader决定是否储存到达表面的光子到Photon Map中去，如果是，则储存光子，如果不是，就通过Russian Roulette算法决定是否继续传播光子，并且决定光子的类型，然后发射相应类型的光子。
为了让Photon Emission支持多线程，应考虑到Monte Carlo算法的影响。其主要过程是一个循环，每次随机的选择一个光源并发射一个光子，直至光子全部用完或Photon Map已满，由于各个光子的传播是相互独立的，所以我们可以把循环分解为几个小循环，在不同线程中实现，只要把单线程的实现照搬到多线程情况就行了，但要注意，给全局对象加访问锁，比如Photon Map，已发射光子计数器等。
还有一些Photon Mapping的优化在原型中实现了，比如用Projection Map排除无交区域，用RGBE 格式的颜色值来压缩Photon的大小。
最终，光子在场景中的传播过程结束，则在第二阶段，也就是真正的渲染开始后，每次shade表面上一点的时，Surface Shader可以获得当前点的间接照明分量，然后合成到最终颜色值中去。有两种方法获得间接照明分量，一是通过简单的查询Photon Map，搜索最临近当前点的几个光子，对当前点的间接照明做贡献，这称为Density Estimation，对于Caustics效果总是使用这种方法。而对于GI，当Final Gathering关闭的时候，用的也是Density Estimation，当Final Gathering打开的时候，则自动在当前点法
线所指的半球区域内发射Final Gather Rays（以下简称FG Rays），将采样所得的颜色值平均作为当前点的间接照明值。FG Rays击中景物时，会调用被击中景物的Surface Shader，这个shader可能再次查询当前点的间接照明，但这次我们就限制只能使用Density Estimation获取间接照明值，因为Final Gathering 计算代价昂贵，我们以此避免递归调用产生的开销。在没有打开GI的时候，Final Gathering也能工作。因为逐点计算Final Gathering太昂贵了，所以用了Irradiance Caching，将计算过的点（称为FG Points）储存在一颗八叉树中，则可以通过插值附近的FG Points来近似当前点的颜色值，详见文献[4]。
由于Photon Map在内存中的表示是一个连续的内存块，实际上是一种非常类似堆结构的数组，所以可以很容易的利用我们现有的Caching机制来处理超出物理内存大小的大规模Photon Map，只需要将连续的内存块划分成一定粒度的可以动态换入换出的小块，交给elvish ray底层的Caching模块处理即可。
5.2.Progressive Final Gathering with Irradiance Caching
Final Gathering的基本原理是对每个可见的点在位于其法线所指的半球空间内随机的发射一定数量的光线，平均这些光线的采样结果作为当前点的间接照明，用于代替Global Illumination的Density Estimation，获得更自然的过渡效果，对Caustics不进行Final Gathering。但这种计算是非常昂贵的，所以需要优化，可以用Irradiance Caching来共享相邻点的计算结果。Final Gathering支持多重漫反射和镜面反射/透射，对每种类型只衍生一条光线。
我们改进了原有的Final Gathering算法，使用一种逐步求精的方式来计算FG Points。算法首先根据用户的设置，在屏幕空间上以一定的间隔分布一系列根据Quasi-Monte Carlo方法生成的采样点，从视点向这些采样点发射光线（这种类型的光线称为Probe Ray）与场景求交，在所得交点处进行半球域采样，生成新的FG Points。然后启动逐步求精过程，这是一个多遍的过程，每一遍都将采样点间隔减半，生成一系列新的更稠密的采样点，再从视点向这些采样点发射Probe Ray，在与场景求交所得的交点处，先尝试按照用户设置插值周围的FG Points，如果满足插值条件，则插值取得当前采样点的间接照明值，绘制到屏幕上以提供给用户即时的反馈，否则，进行半球域采样生成新的FG Points。算法一直继续，直到采样点间隔足够小，通常取小于一个像素的边长。
这种算法保证了初始时FG Points之间有一定的间隔，在光亮度变化缓慢的地方取较少的采样点，而又逐步求精，根据插值条件，在光亮度变化较大的地方取较多的点，因此是一种自适应的算法。并且，该算法非常易于并行，因为仍然可以按照图块的顺序来多遍渲染，新添加的FG Points可以先储存在线程私有的储存空间中，待当前遍结束之后，再合并入全局的储存空间。
6.新的架构设计
原型仅使用了最简单的基于分阶段的渲染管线，然而新的架构设不会这么简单了，这是一些需求导致的。
首先，系统资源是有限的，尤其是内存资源，而渲染器大部分的时间不是花在计算上，很多时候是花在内存上，同样，错误也大多是在内存上。所以我们需要一套高级的动态资源管理系统，这套系统允许基于一定的策略，动态的换入换出内存，这类似操作系统的磁盘交换，但是我们不能让操作系统来替我们做这个事情，因为操作系统缺乏渲染的具体知识，它只能按照一般情况来管理，而不能理解渲染器内部正在发生的事情，所以我们要自己管理资源。实现这套机制的主要思想有，一是只加载需要的资源，按需加载，二是资源的流式管理，内存不足的时候只保留最重要的资源在内存中，而把其他部分写入磁盘缓存（这常常是DDL中的一部分），并且要让我们至少在理论上可以用给定限度的内存量，就能快速渲染无限大的场景。
另外，原先由于渲染管线是分阶段执行的，下一个阶段的任务必须等到前一个阶段的所有任务全部执行完毕后才能开始执行，用户不能立即看到渲染反馈，而要花相当长的一段时间等待预处理结束。因此我们需要一种更灵活的任务管理机制，可以在某个任务所依赖的条件都满足时，就立即启动该任务执
行。这要求我们预先建立好所有任务之间的依赖关系，构成DAG，各个并发线程在任务队列中获取一个新任务时，检查其所依赖的任务是否均完成，如果是，则直接执行该任务，否则先执行一个该任务所依赖的任务，如此循环直至所有任务都被执行，一个简单的任务DAG如图6-1：
图6-1 简单的任务DAG（箭头指向所依赖的任务）
6.1.Geometry Instancing
Geometry Instancing使得我们在渲染成千上万个相同物体的实例时只需要大约一个该物体的内存用量，我们依然获取每个物体的包围盒，按照包围盒分割并构造kd-tree。因为一个包围盒的数据量几乎和一个三角形的数据量一样多，为每个三角形储存其包围盒并不能减少多少内存用量，因此我们不为物体实例储存三角形的包围盒，而是在需要时重新计算它。
该方法的主要特点有：
(1)不使用紧缩的包围盒，而直接在建立叶结点时利用结点的包围盒对三角形进行裁剪（虽然更复杂，
但是毕竟只进行一次）。
(2)运用了两遍法使得GPIT(Geometric Primitive Indexing Table)连续顺序储存的实现成为可能。所谓的
两遍法，即我们在分割（分割在本文中指将结点中景物按分割平面归类，建立子结点的过程）景物到kd-tree的子结点中去的时候，对景物进行两次遍历，第一次先统计有多少景物被分割到了左子树，多少景物被分割到了又子树。第二次遍历之前，我们便可以一次性分配好左右子树各自需要的内存，在第二次遍历中，我们只需简单的填充左右子树的数据，而不需要反复的进行内存分配。
(3)使用GPIT，并将光线变换回景物局部空间求交。对Motion Blur，先按shutter open和shutter close
的矩阵变换光线，再对所得光线本身插值。
算法的数据结构如图6-2：
图6-2 基于GPIT的Geometry Instancing数据结构
6.2.Ray-tracing of Arbitrary Geometry
为了光线追踪任意的几何体（假设是该几何体总能转换为Micro-polygon，最终转换为triangles或motion triangles，因为我们选择kd-tree作为光线追踪核心的加速结构，因此这里的讨论均是针对kd-tree 的），我们不可能预先细分生成足够精度的三角形逼近，随后再建立kd-tree，并进行光线追踪，因为在高质量渲染中，完全细分产生的三角形数量往往过于巨大而难以直接处理，所以我们需要一个动态的光线追踪框架，它能够根据当前光线指定的精度要求（通过ray differentials[15]计算），动态的改变几何体的细节等级，即动态的改变所生成的三角形的数量和形状，而这又导致kd-tree的结构必须做出相应的调整。并且我们应当适当的控制内存使用量，既不能使用过分多的内存，也不能每次都重新细分(Re-tessellation)几何体，导致大量的计算，这就要求我们有适当的caching策略。最好的情况就是可以将内存用量限制在一定的范围，而在此范围中，可以渲染无限制大小的场景，并且将渲染时间最大化，为了实现这一点，我们有一个全局的geometry cache，当渲染中需要申请新的内存块，而内存用量又超出用户预设的限制时，我们则通过Least Recently Used(LRU)算法[16]，移除旧的内存块，而让新的几何体使用这块内存。很明显，这要求我们将算法中动态生成的几何体，作为cache的一部分，可以按需求删除和重建。假设我们已经有了这样一套cache系统，现在来考虑要对系统做什么改变，并引入了什么新算法。
我们将首先描述GPIT算法时如何实现Geometry Instancing的，随后针对动态光线追踪对其进行扩展。因为这部分扩展尚未实现，我们将在未来工作部分对其进行描述。
GPIT是Geometric Primitive Indexing Table的缩写，作为一张表，其最显著的特点就是它在内存中确实是一张连续存放的表，即它是一块连续的内存块，这样很明显的好处就是访问起来更加高效，而且只需要为每个带有GPIT的结点分配一次内存，明显提高了光线追踪的效率。GPIT中并不储存真正的几何数据，而是连续储存表示几何数据相对于基地址的索引值，和基地址本身。这样虽然增加了一次间接寻址，比直接储存几何数据访问起来慢一些，但是因为GPIT本身比较小，很可能完全位于CPU的高速缓存中，而且其中储存了下一个几何体的位置，所以总能通过CPU的预取指令提前预取下一个几何数据，提高缓存命中率，进而提高几何数据的访问速度。GPIT正是通过储存几何数据的索引值来轻松的实现Geometry Instancing的。在光线追踪过程中，我们遍历GPIT，通过间接寻址访问几何数据，每次遇到一个新的物体实例（Object Instance），我们都将光线按照物体实例的camera to object矩阵变换到物体的局部坐标系，如果物体实例有transform motion blur，即有通过对物体实例的空间变换产生的运动模糊，则我们可以先对camera to object矩阵与motion camera to object矩阵按照光线所对应的时间进行插值，然后再变换光线。但由于对矩阵本身进行插值比较复杂[16]，需要分解矩阵为不同的变换部分，按各自的特点分别进行不同类型的插值，再组合起来，而对矩阵做简单的线性插值又会产生扭曲的结果，所以我们先分别按照这两个矩阵对光线进行变换，再对得到的两条光线按照时间做球面线性插值（Spherical Linear Interpolation）[17]或直接线性插值（球面线性插值较为复杂，实际中往往使用直接线性插值就能得到足够好的结果），获得局部坐标系中的光线后，即可与GPIT中索引值所指的几何数据
进行求交。这样，无论一个物体有多少个物体实例，只需要储存多个GPIT，而不需要储存多个真实的几何数据，而GPIT本身相对较小，所以这极大的节省了内存。
6.3.elvish ray Scene Description Language
elvish ray Scene Description Language（以下简称ESDL）是一种用于描述场景几何、灯光与材质属性的语言。该语言实际上是一系列C++函数，可以方便的导出到其它脚本语言，如Python等。
ESDL与前述的mi2标准非常类似，基于DAG结构，有一组函数用于定义场景元素（包括几何、灯光、材质等），还有一组函数用于将已在之前定义好的元素连接在一起。DAG还有一个特性，在父结点定义的属性，会自动被子结点继承，但是子结点可以定义自己的属性来覆盖其中的值。
为了支持大规模的几何数据，ESDL在相关的几何描述函数被调用时，先以流的方式将几何数据写入硬盘中，形成几何缓存文件，在渲染时，再利用Geometry Caching系统动态的将硬盘上的几何数据读入内存。
ESDL还有两个强大的特性，一个特性是Primitive Variable，即ESDL所支持的primitive，包括顶点、面、物体等，都可以附加任意多个任意类型的用户数据，这些数据会被自动插值，供下文将讨论的elvish ray Shading Language访问。另一个特性是类似RIB[9]的变长参数表，允许用户在单个函数调用中直观的按照参数名称指定任意个参数的值，相比于mi2的需要调用参数设置函数多次的方法更为优雅。
ESDL还支持类似mi2的Shader Graph和Shader List特性。其中，Shader Graph就是可以将任意shader 的参数输出作为任意shader的参数输入，即将一个shader的输出连接到另一个shader的输入，这允许我们编写一些简单的shader，然后通过连接这些shader结点，构成更复杂的shader。实现Shader Graph 特性时，我们允许shader的延迟执行，即只有当一个shader的某个参数依赖于另一个shader的某个参数时，另一个shader才会被执行，这避免了执行不必要的shader，提高了执行效率。Shader List特性允许多个shader按顺序依次作用于同一个场景元素，也是一种通过组合简单的shader来构成复杂shader 的方式。
不仅如此，ESDL还支持渐进式的场景修改，可以只修改每帧中相对于上一帧变化了的那部分场景元素，不需要每帧重新定义一遍所有场景元素，这个特性非常适合动画的渲染。
6.4.elvish ray Shading Language
elvish ray Shading Language（以下简称ESL）是一套用于描述景物表面材质属性，自定义渲染方法的语言。ESL直接使用C++作为着色语言，提供了一套封装的非常友好的接口及相关的类库和函数库，方便用户编写自己的shader，通过一系列函数与渲染内核进行交互，并且可以通过前述的ESDL将shader 绑定到场景元素上。
ESL的主要特点是利用一套封装的很友好的C++接口及库，来提供非常类似RSL[9]的直观易用的shader编写环境，编写出的相同功能的shader代码，比mi2的代码更加简单、易读和优雅，极大的方便了艺术家类型用户的使用。
此外，ESL提供了比RSL更丰富的shader类型，包括surface shader, light shader, shadow shader, photon shader, photon emitter shader, imager shader, lens shader等，支持对分布式光线追踪与全局照明功能的灵活的自定义，同时，由于直接使用C++作为着色语言，用户不用局限于ESL库所提供的功能，而可以高度灵活的使用C++丰富而强大的各种库，用户几乎可以在shader里做任何事。
7.系统的应用与实现细节
7.1.系统的使用方法
elvish ray是一个高度可编程的系统，其内核是一个动态链接库，并且提供了相关的头文件与lib文件，客户端程序能够通过链接到这个库来调用elvish ray的渲染功能或开发自定义的功能。elvish ray的
可编程接口主要分为三部分：
(1)elvish ray Scene Description Language如前所述，实际上是一系列C++函数，用于描述场景中的几何
数据与材质节点的连接。
(2)elvish ray Shading Language如前所述，是一套灵活的可编程接口，用户可以通过它编写自己的代码
来自定义渲染流程。其语法非常类似RSL，十分友好易用。
(3)Connection在elvish ray中是一个特殊的概念，实际上是一个C++中包含了一系列虚函数的类，客户
端可以通过继承这个类，实现相关的虚函数，来自定义渲染器的行为，实现客户端与渲染核心的数据交互。实际上，通过继承这个类，我们已经实现了与著名3D动画制作软件Autodesk 3ds Max的集成，允许作为3ds Max的渲染器插件直接在3ds Max中通过图形化的界面使用，这个插件称为MaxConnection，其图形界面如图7-1：
图7-1 MaxConnection的图形界面
与3ds Max的成功集成表明，elvish ray具有足够灵活与通用的设计，来担任与各种客户端程序，特别是3D动画制作软件进行交互的工作。
7.2.跨平台设计
elvish ray的内核拥有跨平台的设计，能够支持Windows, Linux与MacOS等主流的操作系统，以及支持32位与64位的软硬件环境。这要得益于elvish ray的Platform Abstraction Layer（以下简称PAL）的设计。PAL抽象出了各个平台上共有的一些基本系统功能，包括动态链接库的加载、多线程的执行与等待、互斥锁与读写锁的使用、事件的使用、系统时间与环境变量的获取、文件与目录操作、内存的分配与释放等，为系统上层，也就是纯粹的逻辑层，提供了一套统一的调用接口，如图7-2：
图7-2 跨平台的架构设计
可见，只要保证在逻辑层不使用任何PAL所提供的功能之外的系统调用，就可以保证系统的可移植性。
7.3.相关开发工具
elvish ray使用Microsoft Visual Studio .net编写与编译，使用Google Code提供的SVN服务与Issue Tracking系统，其中SVN用于源代码控制，Issue Tracking用于任务分配与管理。elvish ray拥有良好的源代码目录结构，将代码、项目文件与生成结果分开存放在不同的目录中，方便了开发环境的升级与跨平台的实现。
8.测试与比较
本节我们对elvish ray中实现的经过改进的一部分算法进行测试，对比它们与原始方法之间在效果和速度上的差异。我们所使用的测试机器的配置为Intel Pentium D 2.19 GHz, 1.98 GB RAM, Windows XP Service Pack 3。
8.1.Ray-traced Motion Blur与REYES Motion Blur
因为我们统一了Ray-tracing与REYES二者的采样框架，所以我们对比二者的运动模糊效果是否一致。
图8-1 光线追踪运动模糊
图8-2 REYES运动模糊
图8-1是使用Ray-tracing渲染的，用时2分55秒，图8-2是使用REYES渲染的，用时20秒，Shading Rate为1。可以看到二者运动模糊的效果几乎一致，但是REYES远远快于Ray-tracing。
8.2.Progressive Final Gathering与改进前的Final Gathering
我们对比Progressive Final Gathering与改进前的Final Gathering在效果上的差异。
图8-3 未开启Final Gathering
图8-4 开启Progressive Final Gathering
图8-5 非Progressive的Final Gathering
图8-3没有开启Final Gathering，场景中只有直接照明，可以看到场景很暗，渲染时间为7秒。图8-4使用了Progressive Final Gathering，渲染时间是6分40秒，可以看到间接照明引起场景中光影颜色的微妙变化，图8-5没有使用Progressive Final Gathering，设置参数相同，渲染时间为1分20秒，可以看到图像上有很明显的瑕疵。
8.3.Irradiance Gradients与Quasi-Monte Carlo Sampling
我们对比使用Irradiance Gradients对Final Gather Points进行插值前后，以及Monte Carlo方法与
Quasi-Monte Carlo方法在效果上的区别。
图8-6 Quasi-Monte Carlo与Irradiance Gradients对Final Gathering的影响
从图8-6我们可以看到，使用Quasi-Monte Carlo以后，图像明显更加平滑。在进一步使用了Irradiance Gradients插值后，能够更好的反映景物底部阴影中的细节。三张图的渲染时间几乎相同。
8.4. Quasi-Monte Carlo Sampling对区域阴影效果的影响
我们对比Monte Carlo方法所得到的区域阴影与Quasi-Monte Carlo方法所得到的结果之间的差别。
图8-7 Quasi-Monte Carlo对区域阴影的影响
图8-7中，左右两图的渲染时间和所使用的采样点数目是一致的，但是由于Quasi-Monte Carlo方法可以得到更好的采样点分布，所以图像效果上明显更加平滑，噪点更少。
8.5. REYES Displacement Mapping
我们测试使用REYES的Displacement Mapping的效果。
图8-8 基于REYES的Displacement Mapping效果
从图8-8中可以看到茶壶表明的几何根据细胞纹理做了改变。
8.6. 基于Photon Mapping的Caustics效果
我们测试基于Photon Mapping算法的Caustics效果，使用了100万个光子。
图8-9 基于Photon Mapping的Caustics效果
从图8-9中可以看到光能经过戒指镜面反射到桌面上产生明亮的光斑。
9.未来工作
9.1.Ray-tracing of Arbitrary Geometry with Ray Differentials
下面我们讨论如何扩展GPIT（eXtended GPIT，以下简称XGPIT），使之能够处理动态光线追踪。
XGPIT及相关数据结构如图9-1所示：
图9-1 XGPIT的数据结构
MTGP是Multiresolution Tessellated Geometric Primitives的缩写，每个primitive对应一个MTGP，其中包含了该primitive各个细节层次的镶嵌表示。需要保证MTGP中每次Retessellation后生成的三角形顺序均与之前的顺序相同。可以考虑增量式细分，即后一层次的细分表示在前一层次的细分表示的基础上生成，只计算并储存那些新加入的顶点。
(1)生成在相应结点包围盒内的sub-GPIT。
(2)为了加速，可以将静态的triangles和motion triangles合并到sub-GPIT中。
(3)将sub-GPIT放入对应的kd-tree结点中分割，建立sub-tree。
(4)各个primitive相互独立的细分，生成各自对应的MTGP。
光线追踪时，对动态部分进行两步查找，先按primitive ID找到primitive，然后在primitive中按当前光线的ray differentials决定的细分层次寻找相应的sub-triangle ID指示的三角，与之求交，这里去掉了指针的概念，因为flushable几何体均可以重建，所以先按ID查找，若不存在则重建（通过Retessellation）。
XGPIT将几何体分为两部分储存，静态和动态部分。这样的好处是改变动态部分时，静态部分不受影响，因为只有动态部分需要重建，这允许我们单独处理动态部分，而且可以很方便的将静态部分合并到动态部分中去统一处理。静态部分即不会再改变的triangles和motion triangles部分，而动态部分是我们讨论的重点，这里面可以包括任意的高级几何体，这是一个指向高级几何体指针的列表，为了增强
系统的灵活性，可以泛化对高级几何体的操作，这样我们便拥有了一个能够任意添加新的几何体类型的
开放系统（类似REYES[7]），我们在这里将所有高级的Geometric Primitives统称为primitive，这可以包括Parametric Surfaces, NURBS Surfaces和Subdivision Meshes等。首先，我们看看kd-tree现在的基本结构如图9-2：
图9-2 基于XGPIT的kd-tree结构
因为我们只是扩展了GPIT，所以不必改变kd-tree结点的结构，而且对于XGPIT所指的sub-tree，可以重用同样的原先为kd-tree写的建立与遍历代码。
现在的光线追踪过程为，首先，primitives得到其包围盒，因此primitive需要一个抽象的Bound操作，随后按照primitives的包围盒建立kd-tree的静态部分，直到所有primitives都被放入叶结点指向的GPIT或XGPIT中（若不存在需要动态光线追踪的高级几何体，则XGPIT退化为GPIT，这个性质保证了中小规模的渲染速度不受影响），对于XGPIT，每次追踪光线时，判断子树是否已建立，若已建立，则按ray differentials与shading rate的比较结果来选择合适的细分层次，若相应的结点未建立，则遍历primitives，调用其抽象操作Tessellate(level)，生成相应层次的细分后三角形（这样设计具有灵活性，因为primitive之间相互独立细分，便于并行，但是具体的细分方法却没有限制，而且与kd-tree的具体结构无关，所以可以使用任何可能的细分方法。并且primitive未必就是数学表示上的单块patch，可以根据performance选择多块patch甚至整个surface作为primitive来一起细分，所以究竟以什么作为细分操作的基本单位可以灵活的选择），将这些三角形与叶结点的包围盒做测试，将位于该包围盒中的三角形加入sub-GPIT中，建立起sub-GPIT，并将叶结点中的静态部分合并进去，然后使用通常的kd-tree建立方法生成子树，并让XGPIT中相应层次的node指针指向该子树，若子树未建立，则估算所有可能层次的shading rate并写入XGPIT中（可以通过包围盒大小估算，也可以做试探性的细分，进行更精确的估算），之后按已建立子树的情况处理。
9.2.Physically Based Rendering
目前elvish ray综合Photon Mapping与Final Gathering来求解渲染方程的方式，是一种有偏的算法，即利用了某些不符合物理的技巧来加速求解，所得的全局照明解未必能够收敛于精确解。而另一类完全基于物理的算法，称为Physically Based Rendering[18]，是无偏的，即所得的全局照明近似解的期望一定等于精确解。这类算法的特点是只要有足够的渲染时间，输入精确的真实世界中的物理参数，总能得到与真实世界中的景象完全一致的渲染效果，即使渲染时间不够，生成的图象在整体上也能给人一种符合