《年人力资源知识新算法框架》由会员分享，可在线阅读，更多相关《年人力资源知识新算法框架（10页珍藏版）》请在金锄头文库上搜索。
1、elvish ray新算法框架Version 2.0.0.0Len3dCopyright 2007 Len3d.All rights reserved.前言本文描述了一种渲染器的新算法框架，只是我个人对elvish ray的建议，仅供参考。需求分析mental ray是一个极其优秀的混合渲染器，尤其是它的光线追踪功能，做得非常好，非常智能，尽量用最少的光线取得最好的结果（很好的采样分布算法和自动减少无效采样），但它依然是基于传统的光线追踪算法框架发展而来的，按我的使用经验，这带来很多问题。在mental ray中，对不同的光线类型，如eye ray, shadow ray, reflected
2、 ray, refracted ray, finalgather ray等，都要分别做不同的优化，导致算法非常复杂，而各种光线的表现又不尽相同，导致使用时很难预测各种光线的行为，也就很难预测达到的效果与渲染时间，这对于产品级的制作是很大的麻烦，意味着开支预算变得困难。虽然mental ray尽量让参数的变化直接与渲染时间的变化呈线性关系，但对于reflected ray和refracted ray，众所周知，其递归光线追踪的过程构成一颗二叉树形式，称为光线树，这样对于K次反射/折射，R个象素，总供需要计算的光线数目近似于(2k+1-2)R条，这是呈指数增长的，所以递归层数K一深，整个渲染过程马
3、上就慢下来了，更糟糕的是，如果再开启阴影，每个交点处至少发射一条阴影测试光线，更一般的，开启区域阴影时，不妨设每个交点处平均发射m条shadow ray，则所需的光线总数约为(2k+1-2+m(2k-1)R条，这种增长非常可怕，而且不同的特效同时开启时，速度的变慢不是简单的线性组合，而是会相互影响，这就是为什么单独打开mental ray的某一种特效，速度尚可接受，但同时打开几种特效时，速度就慢得让人难以忍受了，所以想要用mental ray达到很好的效果和渲染时间的平衡，需要大量的试验和人工参数调整，需要使用者有非常丰富和老道的使用经验，即使如此，调整mental ray诸多的复杂而神秘的参
4、数，依然是一种痛苦的折磨。总结起来，mental ray在这方面的缺点主要有：1. 基于传统的光线追踪算法框架，各种特效增加的渲染时间与象素（包括自适应采样产生的子象素）数目成正比。因此，假如你只想增加景物边缘的反走样，而不在乎反射/折射的精细程度，mental ray依然发射更多的反射/折射光线，忠实的增加渲染时间。2. 各种光线类型的优化方法不统一，算法复杂维护困难，且对于产品级的应用，难以预测渲染时间的开销，难以预测并保证最终效果，总是要求用户试了才知道。3. 无论mental ray如何优化其算法，反射/折射光线，依然与反射/折射层次数呈指数增长关系。4. 同时开启多种效果时，渲染时间
5、不是单独开启各种效果时渲染时间简单的线性组合，而是会相互影响。例如，射/折射层次增加亦会使阴影光线数目呈指数增长。5. 参数复杂而且神秘，难于调整，需要极为丰富的使用经验。想要达到效果和渲染时间的平衡，需要大量反复的调整和试验，影响制作效率。针对这些问题，我设计了如下这种新算法框架，希望能有助于解决这些问题，其实该架构也非常简单，其核心思想依然是分而治之的思想，我借鉴了Reyes的思想，并对Reyes与光线追踪算法中各自的一些概念进行了推广，提供了一种统一的架构。算法框架描述1. 光线类型的推广Reyes算法只处理一种光线类型，就是mental ray中称为eye ray的光线，它只渲染观察者
6、直接可见的景物，Reyes还有一个区别于mental ray这类光线追踪渲染器的主要特点，就是将Hidden Surface Removal（简称hiding）和shading过程分开，这样的好处是，增加物体边缘的反走样，不会增加多少渲染时间，因为更耗时的shading过程由另一个与象素数目（由采样数目控制）无关的参数shading rate控制。我将shading rate的概念由eye ray推广到各种光线类型，reflected ray, refracted ray, shadow ray, finalgather ray等都有各自的shading rate，且规定它们的shading
7、rate均不小于eye ray的shading rate，这样我们为每块由细分和镶嵌生成的microgrid，匹配一系列分别对应于各种光线类型的irradiance cache（这里借用并推广了irradiance cache的概念），每当一块microgrid被某条光线击中时，便对整张microgrid上的每个顶点进行针对视点的shading（这虽然可能导致浪费一部分shading结果，但是可以充分利用SIMD并行计算加速，甚至可以利用GPU），这就涉及到如何执行用户编写的shader程序的问题了。因为我们规定其余各种光线的shading rate总不小于eye ray的shading ra
8、te，所以在Reyes针对视点细分生成的microgrid上的每个顶点进行shading总是正确的。然而，以reflected ray为例，对microgrid上的每个顶点都计算反射往往是不必要的，所以我们可以根据reflected ray的shading rate，只对microgrid上的一部分顶点计算反射，这部分顶点通过在microgrid上按相应间隔取隔行和隔列的顶点获得。若要利用SIMD并行shading，我们需要有RenderMan一样的编译器与SIMD虚拟机，shader代码执行到调用trace_reflect函数的时候，便收集microgrid上需要计算反射的点（这些点被称为r
9、eflected points，相应的有refracted points, shadow points, finalgather points等），利用基于SIMD的并行光线追踪一次性得到计算结果，而对于microgrid上剩余的未计算反射的点，则由microgrid良好的性质可以简单的通过插值相邻的reflected points获得，同样由trace_reflect函数返回插值结果，这样，我们不必为finalgather rays构建特别的基于八叉树或其它特殊数据结构的irradiance cache，而将irradiance cache的概念推广到所有光线类型，统一了它们的处理方法，这同
10、时也是对Reyes算法的一种扩展。值得注意的是，irradiance cache的值，对不同的光线类型，可能是view-dependent的，也可能是view-independent的。对于view-dependent的那些，比如reflected irradiance cache, refracted irradiance cache，它们都仅是针对场景中唯一的视点（eye rays）有效，而对于从其它点发射出的光线则是不正确的，因此对于secondary rays与景物相交时的shading，我们则按传统的方法单独为该点计算反射/折射等效果，并不使用irradiance cache中的值，
11、当然，参考Razor架构的做法，对于shading language的predefined variables中那些view-independent的变量，如N, dPdu, dPdv等（如果我们假设shading总发生在camera space中的话），我们可以像irradiance cache一样一次计算好并储存下来反复使用，而对于其中那些view-dependent的变量，如P, I等，则每次均重新计算。对于那些view-independent的irradiance cache，如shadow irradiance cache, finalgather irradiance cache，
12、无论光线从哪个视点发出，都可以使用cache中的值，这样避免了重复计算，同时由于我们只在有光线击中某块microgrid时，才对该microgrid计算光线所需的irradiance cache值，这是lazy evaluation或说deferred shading的思想。2. Russian Roulette方法的推广前述对光线类型的推广，有望在我们前面对mental ray的算法复杂度的分析中，以一定比例减小R这个因子，设有n种光线类型，则相当于将R分解为R1, R2, , Rn的线性组合，且各种光线的Ri因子中，由各自的shading rate决定，但这依然只是降低了复杂度中的线性因子
13、，而复杂度中更主要也更可怕的真正反映光线追踪特性的递归光线追踪部分的因子，却没有降下来，即2k+1-2+m(2k-1)这部分。回顾Photon Mapping算法中很重要的Russian Roulette方法，每次获得一个交点时，只是随机的根据光照模型中各项系数因子的大小选择一种光线类型，且只发射一条光线，如果我们借用这种方法（允许类似mental ray通过shader实现），那么递归光线追踪部分的因子就会降为K，整体的复杂度可以近似表示成K(R1+R2+Rn)。然而应注意到，Russian Roulette方法虽然可以通过理论证明是正确的，但当R不够大（超采样不足）时，产生的图像会有很多噪
14、点。为了解决这个问题，回顾Photon Mapping中使用Russian Roulette为什么会正确，因为最终渲染时，需要使用density estimation或final gather等技术来估计表面上各点的间接照明值，这实际上可以理解成一种filtering过程，考虑microgrid本身的结构，很容易进行相邻顶点的irradiance cache中的值的filtering，这可以理解为推广的irradiance filtering技术，这种技术有一个缺陷，由于一个物体很可能会被分割成多个相对独立的microgrid，对microgrid边界处的顶点进行irradiance filt
15、ering会造成瑕疵，当然这可以通过保持microgrid分割边界之间的连接关系来解决，但这样使得各个microgrid不能独立处理，注意到Reyes中计算microgrid边界处的dPdu, dPdv等值时，也会遇到类似的困难，我们可以借用类似的解决方法，比如让每块microgrid稍微比实际的大一些即可。另外，对于final gather，由于microgrid本身的良好结构，很容易实现相邻顶点间的neighbor clamping算法，以消除景物边角处的光亮度瑕疵，而不用设计特别的数据结构。3. Multi-resolution Geometry Caching与Ray Differen
16、tials基于观察，我认为可以得到这样一个事实：近处较大（近大远小的道理）的景物，其被反射的影像在渲染图像中一般也较大，远处较小的景物，其被反射的影像在图像中一般也较小。或者可以阐述成景物的照明属性通常对其周围的景物影响最大，而对距之较远的景物影响较小，即具有照明属性的局部性，允许粗糙的近似甚至忽略不计。除了一些特殊的情况，比如拿一个放大倍率很高的放大镜，看极远处的一个小景物。因此我们一般可以按Reyes算法对场景中所有景物进行细分（或镶嵌，下同），而对于反射/折射等光线，可以直接使用同一份细分几何数据，而不需要另外细分，这通常不会因细分不足而在图像上产生瑕疵，而且仅使用一份细分几何数据（称为single geometry cache），同时节省了计算量与内存用量，并且不会产生由于相邻多条光线各自对应的细分层次不一致而在图像上造成裂痕的问题，对内存的使用量及细分所需时间的预测也变得容易了一些。注意到Reyes只处理位于视棱域（
