数字动漫与影视产业是信息技术和人文艺术结合的内容创意产业,是本世纪经济潜力巨大的新兴产业,也是我国近年来大力发展的战略性新兴产业。作为智力密集型、无污染、高附加值的新兴产业,数字动漫影视产业不仅对一个国家的经济发展有重要意义,而且对各国民族文化的宣传发扬、国家形象的塑造和提升也具有重要意义。三维渲染技术在动漫作品的制作中发挥着至关重要的作用。据统计,从2001到2011这十一年的票房冠军无一不是三维渲染的杰作。三维渲染是一种对虚拟场景进行观察并生成图像的过程。根据应用的侧重点不同,渲染算法可分为两类,即面向快速图像生成的实时渲染,以及面向高质量图像生成的离线渲染。渲染中通常使用帧(frame)表示在某一时刻对场景的一次观察,而动画则由一组内容连续的帧组成。影视作品为了保证动画的视觉连贯性,通常要求帧速率不低于每秒24帧。因此,一部两小时的动画至少要包含172,800帧。即使按一帧的平均渲染时间为一分钟算,也需要120天才能完成。为了实现高度真实的光影效果,动漫制作过程通常需要引入全局光照模型。作为一种重要的全局光照算法,光线跟踪方法通过模拟光在虚拟空间的发射和散射的过程来生成具有真实感的图像。然而,高度复杂的物体、光源以及光线传播模型对光线跟踪算法的运行时间提出了挑战。用于全局光照的光线跟踪算法可进一步分为递归光线跟踪、分布式光线跟踪以及蒙特卡罗光线跟踪。递归光线跟踪可实现直接光照、镜面反射和折射效果。分布式光线跟踪引入了随机采样的思想,实现了区域光源、软阴影、景深以及运动模糊效果。更完整的全局光照效果,可以通过光能传递方程描述。但是,由于很难为其中的环境入射光函数给出准确形式化描述,因而使用解析的方式求解该方程是不可行的。蒙特卡罗光线跟踪算法使用光线对光传递方程的解空间进行离散采样,以计算对真实光照结果的近似。常用的蒙特卡罗光线跟踪算法包括路径跟踪、双向路径跟踪以及Metropolis方法。为了降低从光线样本中恢复的光照信息的误差(噪声),蒙特卡罗光线跟踪算法必须发射大量的光线,以保证对场景中所有可能的光照效果的全面覆盖。围绕一条光线所进行的操作包括两部分,即计算光线与物体的交点,以及计算交点的颜色。前者的计算过程被称为可见性判定,后者的计算过程被称为着色计算。可见性判定的核心是寻找光线与场景中物体的交点。它通常有两种类型,即寻找最近交点(Closest Hit)和寻找任意交点(Any Hit).光线可使用参数方程R(t)=O+tD进行定义。其中,O和D分别代表光线的起点和方向。光线所找到的每个交点都确定了一个t值。其中,t值最小的交点被称为最近交点。寻找最近交点的操作主要用于为着色过程提供输入。而寻找任意交点的操作主要用于遮挡判定。为了找到一个交点,最直接的算法是让光线与场景中的每个物体做相交判定。设物体的总数为N,则这种搜索的时间复杂度就是O(N)。为每条光线都进行一次O(N)的搜索显然是不可接受的,除非面对的是极为简单的场景。可见性判定通常借助一种称为加速结构的空间索引结构来提高交点搜索的效率。KD树和包围盒层次结构是最为常用的加速结构。前者是空间二分搜索树(Binary Space Partitioning, BSP)的一种特殊形式。它按照轴对齐的方式对空间进行划分,形成一种对几何体的树形检索结构。包围盒层次结构并不划分空间,而是直接聚类物体。两者通常以二叉树的形式出现,因而可将搜索的复杂度降为O(LogN)。KD树和BVH通常使用表面积启发方法(Surface Area Heuristic, SAH)[1]确定最优分割。SAH是一种贪心算法,它对一个节点各种划分方式做出评估,并选择能够使树形结构质量达到最优的那一种划分。虽然这种按照贪心方式生成的树结构只是理论上的次优解,但是现存的其他算法都无法给出更好的解。因而,SAH是目前保证KD树和BVH质量的最好方法。对KD树和BVH的遍历过程,可以理解为以光线作为关键字,在树形索引结构中查询与之具有特定位置关系的一个几何体的过程。离线渲染通常需要借助大量光线来降低噪声,以提高图像质量。虽然高质量的加速结构已经在理论上降低了每条光线的平均遍历代价,但是遍历算法所面对的是海量的光线数据,因而其运行时间依然较长。另一方面,离线渲染通常会在场景中引入高精度模型。这就使加速结构建立算法所面对的物体数量巨大。因而,算法的运行相当耗时。对于可见性判定给出的最近交点,光线跟踪需要进一步判定其颜色,即进行着色计算。在离线渲染中,这一过程通常是通过独立的着色语言来描述的。场景中的每个物体在建模阶段都被赋予了一个使用着色语言编写的程序,即着色程序。着色阶段根据交点所在的物体获取着色程序,并使用相应的着色语言解释器来完成对程序的解释执行。使用独立的语言,可以将艺术设计过程,例如材质和灯光的设计,从渲染算法中分离出来。这一方面为艺术设计者提供了灵活的创作工具,另一方面避免了艺术设计与软件开发的相互影响。其劣势在于,着色程序解释执行的效率较低。通常,一条简单着色指令的执行时间大部分都用于了解释,而真正用于所需功能的时间只占其中一小部分。可见,如果一个着色程序由大量简单指令组成,则整个程序的绝大部分时间都将花费在解释的步骤上。复杂着色指令例如trace,由于其主要功能的执行时间较长,使得解释步骤所占的时间可以忽略不计。在实践中,着色程序通常是由大量简单指令与少量复杂指令组合而成。因而,整个执行过程消耗在解释上的时间将是相当可观的。当今的并行技术发展异常迅速,新硬件与新标准层出不穷。因此如何在渲染中有效地吸收并行领域的发展成果,将其转化为渲染效率的提升,就成为了渲染领域的研究热点。随之而来的,便是新式并行渲染算法的不断提出。针对离线渲染中全局光照计算量大的问题,本文提出了三个并行优化算法。第一,本文针对大规模场景的加速结构建立速度较慢的问题,提出了一种基于双层并行模型的KD树和BVH建立算法。算法将树节点的建立作为基本任务单元。并行模型的上层对整体任务进行粗粒度的划分以形成若干任务子集,并为每个任务子集的处理分配单独的常规工作线程。我们为每个上层线程分配独立的任务队列,并提供了工作窃取机制实现任务的动态调度,以便达到负载均衡的目的。每个上层线程在处理一个节点建立任务的过程中,会将其中计算量最大的步骤,即根据SAH确定最优分割的计算过程,调度至并行度更高的下层。并行模型的下层包含大量轻型线程,它能够高效的完成针对海量数据的单一的操作。SAH过程正是对大量平面数据进行的一种代价评估计算,因而可以较好的利用这种计算资源。实验表明,我们的算法可以有效的降低KD树和BVH的建立时间。第二,本文针海量光线遍历加速结构速度较慢的问题,提出了一种针对KD树和BVH的混合式并行遍历算法。混合式模型包含了并行度不同两个单元。并行度较低的任务调度单元负责光线数据的生成和储存。而并行度较高的任务执行单元负责大量光线遍历树形结构的任务。前者将收集到的光线提交给后者,并随后将后者返回的交点信息传递给后续的渲染阶段。我们为BVH遍历过程提出了面向SIMD模型的进一步优化,通过将任务单元进一步细分和重组来发掘指令级别的相似性,从而提高对SIMD处理的利用率。实验表明,我们的算法可以有效的降低遍历时间。第三,本文针对着色程序解释执行代价较高的问题,提出了一种面向大规模SIMD处理器阵列的并行着色解释算法。首先,我们为算法提出了一种适合于模块化描述的新式着色语言,即着色图。它可被等价的表示为一个双层DAG。低层DAG描述了基本着色程序模块中着色指令间的依赖关系,其中每个节点代表一条指令。高层DAG描述了基本块间的依赖关系,其中每个节点代表一个基本块。着色图向指令序列的翻译过程需要分两步进行。第一步,通过拓扑排序将各低层DAG转换成独立的指令序列。第二步,对高层DAG进行拓扑排序,并将各指令序列按照高层的拓扑排序结果串连在一起。基本块间的连接被翻译为数据复制指令,插入到基本块之间,以便将一端的输出结果传递到另一端的输入变量。解释算法一次性接收大量着色点作为输入,并反复从各着色点所对应的着色指令序列中收集并成批处理就绪指令。算法将收集到的指令按照操作符分组。每组又被细分成基本任务单元。算法将基本任务单元成批提交到SIMD处理器阵列进行处理。实验表明,我们的算法可以有效降低着色计算的执行时间。