一种面向可编程着色器的多光源加速方法

摘要

本发明提供了一种面向可编程着色器的多光源加速方法，在可编程着色器环境下实现了Lightcuts算法，通过将光源聚类成树形结构，然后再对光源树进行裁剪，减少实际渲染的光源数目，能够将渲染时间与光源数目的关系降为亚线性，而且稳定性比较好，在大部分情况下都能有良好的加速效果。其次，实验发现对于场景中阴影部分的渲染，算法的加速效果并不理想，针对此问题进行优化。最后，本发明将同一物体上相近的点分组进行渲染，进一步提高效率。

权利要求

1.一种面向可编程着色器的多光源加速方法，其特征是，包括：(1)渲染引擎读取场景文件中的光源信息，提取Lightcuts算法所需光照参数，存入光源链表；

(2)渲染场景前，利用Lightcuts算法对光源进行聚类，遍历光源链表，对每类光源构建全局的光源树；

对光源进行聚类的方法为：

第1步：对于同一组光源的集合，寻找其中权重最小的两个光源；

第2步：为权重最小的两个光源构建一个父节点，在两光源中随机选择一个光源作为其代表光源，记录包围盒信息和总亮度值；

第3步：将父节点加入光源集合，两个子节点从光源集合中删除；

第4步：跳到第1步执行，直到该组光源的集合中只剩一个节点，即根节点，光源树构建完成；其中叶子节点为实际光源，内部节点为代表光源；

(3)渲染过程中，将几何表面上待渲染点放置于缓冲区中；对缓冲区中的渲染点聚类：同一物体上相近的点有相同材质，受相同的光源影响，因此下一步对同一物体上相近的一组渲染点求一个公共的光源割，进行渲染；

对同一物体上相近的渲染点求公共光源割的具体方法如下：

a.每一组渲染点共享一个存储光源割的堆栈；设置标记位，标记所执行的是否为该组渲染点的第一个点；

b.如果执行的是第一个点，则正常执行求光源割，结果存储到堆栈；如果不是第一个点，则从堆栈中的上一次计算的光源割开始，执行当前点的求光源割过程，结果仍存放在堆栈中；

c.不断循环执行步骤b，直到该组渲染点全部执行完毕，堆栈中的结果就是该组渲染点的公共光源割；

(4)对于每一组的渲染点，利用全局的光源树，对渲染点分组计算光源割；

(5)设定阴影域参数和背景亮度参数的值，如果当前光源节点亮度Lc小于阴影域参数值，则取其背景亮度参数值作为当前光源节点亮度的估计值，进行求光源割的计算；

(6)渲染引擎识别此光源割中的着色器文件，使用光源割代替原始光源进行照明；

(7)重复渲染过程，直到所有渲染点渲染完成，输出渲染结果图像。

2.如权利要求1所述的一种面向可编程着色器的多光源加速方法，其特征是，所述步骤(4)中，对渲染点分组计算光源割的具体方法为：

1)预估光源树中光源节点的两个值：Lc和upperbound；所述Lc表示一个光源聚类实际照射到渲染点的亮度的预估；upperbound表示理论上光源节点所代表的光源聚类照射到渲染点产生的亮度的预计最大值；

2)如果maxupperbound<0.02*∑Lc，说明堆栈内所有光源节点的upperbound值都满足小于0.02*∑Lc的条件，则堆栈内光源节点即为最后求得的光源节点，计算完毕；其中，maxupperbound为栈内所有节点的upperbound的最大值，0.02为韦伯参数；

否则，分裂该光源节点，将被分裂的节点出栈，其子节点入栈；计算新入栈节点的upperbound和Lc。

3.如权利要求1所述的一种面向可编程着色器的多光源加速方法，其特征是，所述步骤(5)中，如果使用了背景亮度后，在之后的计算过程中，预估的光源节点亮度Lc值又大于或等于了阴影域参数值时，则恢复使用预估光源节点亮度Lc进行求光源割的计算。

4.如权利要求3所述的一种面向可编程着色器的多光源加速方法，其特征是，所述阴影域参数默认取绝对感觉阈限的中值0.05，所述背景亮度参数大于或等于阴影域参数值，默认取绝对感觉阈限0.1。

5.如权利要求1所述的一种面向可编程着色器的多光源加速方法，其特征是，所述第1步中权重的计算方法如下式所示：

2 2 2

W＝Ic(ac+c(1–cosβc))

其中，Ic为两个光源亮度的和，ac为两光源轴对齐包围盒的对角线长度；对于点光源和平行光c的值为0，对于聚光灯，c是一个联系空间大小和聚光灯方向的常量，与场景包围盒的对角线长度相关；βc为这两个光源绑定角的1/2。

说明书

一种面向可编程着色器的多光源加速方法

技术领域

[0001] 本发明涉及图形学真实感渲染领域，具体涉及一种典型的基于层次结构的多光源加速方法。

背景技术

[0002] 在大规模场景的渲染中，光源数目的增长会导致渲染时间随之线性增长，对于一些复杂的光照效果，这样的渲染时间是不能接受的。本发明属于真实感渲染系统中渲染引擎研发部分的工作，引擎在渲染多光源场景时，并没有对多光源进行优化处理，导致渲染速度难以接受。为了节约成本，提高效率，本发明针对基于Renderman规范的渲染引擎，实现了多光源场景的加速方案。

[0003] 对于多光源场景渲染的优化有多种方法，文章[A general version of crow’s shadow volumes]中Bergeron提出了为光源设置一个影响半径的方法，在影响半径内的物体会受到光源照射，否则不去考虑该光源的影响，这样会导致大量低亮度光源产生的光照效果被忽视；文章[Adaptive shadow testing for ray tracing]中Ward提出了为所有光源建立一个贡献表，只考虑贡献比较大的光源。当光源的数目很多的时候，求贡献值将耗费大量时间；文章[Monte carlo techniques for direct lighting calculation]中Shirley把光源根据影响半径分为重要和不重要两类，对两类光源分别采样，不过采样数量不合适会带来走样的问题；文章[A light hierarchy for fast rendering of scenes with many lights]中Paquette提出了基于树形层次结构的优化算法，但是并不支持阴影效果，极大的限制了其使用范围。

[0004] 文章[Lightcuts in blender]中Davide对Lightcuts算法在Blender引擎中的实现方式和应用范围作出了简要的介绍。但是Blender引擎的着色器是内置的，不如可编程着色器灵活易用。文献中并没有提出在可编程着色器环境下的算法的实现方案。而且文献也提出Blender中实现的Lightcuts算法在实际应用中加速效果并不如预想的明显。

[0005] 本发明在分析和对比了多种多光源优化算法后，选择了基于层级结构的Lightcuts算法作为研究基础。该算法是基于二叉树结构的光源聚类优化方法，具有良好的加速效果，而且算法的普适性较强，对大多数场景的渲染都可以优化。算法能够通过错误阈值参数的调节来对优化程度进行控制，便于实际工程使用。

[0006] Lightcuts算法基础是韦伯原理，即人类可以感知到的最小的亮度变化大概为当前亮度的1％，算法中一般选取0.02作为误差阈值的参数，光源集合产生的光照小于0.02倍的总亮度则可以认为能够简化计算。算法在每两个光源之间计算一个权值，该权值与两光源距离和亮度相关。然后根据权值把光源聚类成一棵二叉树。在对点进行渲染时，从光源树的根节点开始，根据韦伯原理判断是否对节点进行分裂：如果当前节点对渲染点亮度的贡献值大于误差阈值而且其存在叶子节点，则将该节点向下分裂为两个子节点，否则停止分裂。当所有路径都停止分裂后，得到的所有节点的集合，就是一个光源割。之后的渲染过程使用光源割代替原始光源进行渲染。

发明内容

[0007] 本发明的目的就是为了解决上述问题，提出了一种面向可编程着色器的多光源加速方法，该方法首先在可编程着色器环境下实现了Lightcuts算法，通过将光源聚类成树形结构，然后再对光源树进行裁剪，减少实际渲染的光源数目，能够将渲染时间与光源数目的关系降为亚线性，而且稳定性比较好，在大部分情况下都能有良好的加速效果。

[0008] 为了实现上述目的，本发明采用如下技术方案：

[0009] 一种面向可编程着色器的多光源加速方法，包括：

[0010] (1)渲染引擎读取场景文件中的光源信息，提取Lightcuts算法所需光照参数，存入光源链表；

[0011] (2)渲染场景前，利用Lightcuts算法对光源进行聚类，遍历光源链表，对每类光源构建全局的光源树；

[0012] (3)渲染过程中，将几何表面上待渲染点放置于缓冲区中；对缓冲区中的渲染点聚类：同一物体上相近的点有相同材质，受相同的光源影响，因此下一步对同一物体上相近的一组渲染点求一个公共的光源割，进行渲染；

[0013] (4)对于每一组的渲染点，利用全局的光源树，对渲染点分组计算光源割；

[0014] (5)设定阴影域参数和背景亮度参数的值，如果当前光源节点亮度Lc小于阴影域参数值，则取其背景亮度参数值作为当前光源节点亮度的估计值，进行求光源割的计算；

[0015] (6)渲染引擎识别此光源割中的着色器文件，使用光源割代替原始光源进行照明；

[0016] (7)重复渲染过程，直到所有渲染点渲染完成，输出渲染结果图像。

[0017] 所述步骤(3)中，对同一物体上相近的渲染点求公共光源割的具体方法如下：

[0018] a.每一组渲染点共享一个存储光源割的堆栈；设置标记位，标记所执行的是否为该组渲染点的第一个点；

[0019] b.如果执行的是第一个点，则正常执行求光源割，结果存储到堆栈；如果不是第一个点，则从堆栈中的上一次计算的光源割开始，执行当前点的求光源割过程，结果仍存放在堆栈中；

[0020] c.不断循环执行步骤b，直到该组渲染点全部执行完毕，堆栈中的结果就是该组渲染点的公共光源割。

[0021] 所述步骤(4)中，对渲染点分组计算光源割的具体方法为：

[0022] 1)预估光源树中光源节点的两个值：Lc和upperbound；所述Lc表示一个光源聚类实际照射到渲染点的亮度的预估；upperbound表示理论上光源节点所代表的光源聚类照射到渲染点产生的亮度的预计最大值；

[0023] 2)如果maxupperbound<0.02*∑Lc，说明堆栈内所有光源节点的upperbound值都满足小于0.02*∑Lc的条件，则堆栈内光源节点即为最后求得的光源节点，计算完毕；其中，maxupperbound为栈内所有节点的upperbound的最大值，0.02为韦伯参数；

[0024] 否则，分裂该光源节点，将被分裂的节点出栈，其子节点入栈；计算新入栈节点的upperbound和Lc。

[0025] 所述步骤(5)中，如果使用了背景亮度后，在之后的计算过程中，预估的光源节点亮度Lc值又大于或等于了阴影域参数值时，则恢复使用预估光源节点亮度Lc进行求光源割的计算。

[0026] 所述阴影域参数默认取绝对感觉阈限的中值0.05，所述背景亮度参数大于或等于阴影域参数值，默认取绝对感觉阈限0.1。

[0027] 所述步骤(3)中对缓冲区中的渲染点聚类的方法为：

[0028] 第1步：对于同一组光源的集合，寻找其中权重最小的两个光源；

[0029] 第2步：为权重最小的两个光源构建一个父节点，在两光源中随机选择一个光源作为其代表光源，记录包围盒信息和总亮度值；

[0030] 第3步：将父节点加入光源集合，两个子节点从光源集合中删除；

[0031] 第4步：跳到第1步执行，直到该组光源的集合中只剩一个节点，即根节点，光源树构建完成；其中叶子节点为实际光源，内部节点为代表光源。

[0032] 所述第1步中权重的计算方法如下式所示：

[0033] W＝Ic(ac2+c2(1–cosβc)2)

[0034] 其中，Ic为两个光源亮度的和，ac为两光源轴对齐包围盒的对角线长度；对于点光源和平行光c的值为0，对于聚光灯，c是一个联系空间大小和聚光灯方向的常量，与场景包围盒的对角线长度相关；βc为这两个光源绑定角的1/2。

[0035] 本发明的有益效果

[0036] 1.本发明针对Lightcuts算法对于场景中阴影部分的渲染加速效果并不理想这一问题进行了分析并改进算法，提出了阴影域和背景亮度两个参数，对阴影部分的渲染过程进行控制，避免一些不必要的计算，加速了阴影处渲染的效率。

[0037] 2.本发明采用渲染点聚类的方法，对一组同材质、空间距离近的渲染点求取Lightcuts，减少的光源割的构建时间，提升渲染效率。

[0038] 3.为了使算法支持可编程着色器下的渲染流程，本发明设计了相关的接口，使其支持商业渲染普遍采用的可编程着色器，提高了算法可用性。

附图说明

[0039] 图1为四个光源的聚类过程示意图；

[0040] 图2为四个光源的求光源割过程示意图；

[0041] 图3为本发明实施例渲染时间对比柱状图。

具体实施方式

[0042] 下面结合具体实施例与附图对本发明作进一步说明。

[0043] Lightcuts算法主要分为光源聚类和求取光源割两个部分。

[0044] a.光源聚类：

[0045] 光源聚类过程将场景中的光源聚类成为一棵二叉树，如图1所示。步骤如下：

[0046] 1)对于所有同类光源的集合，寻找其中权重最小的两个光源，权重的计算方法如公式(1)所示：

[0047] W＝Ic(ac2+c2(1–cosβc)2) 公式(1)

[0048] 其中Ic为两个光源亮度的和，ac为两光源轴对齐包围盒的对角线长度。对于点光源和平行光c的值为0。对于聚光灯，c是一个联系空间大小和聚光灯方向的常量，与场景包围盒的对角线长度相关，βc为这两个光源绑定角的1/2。

[0049] 2)为权重最小的两个光源构建一个父节点，在两光源中随机选择一个光源作为其代表光源，记录包围盒信息和总亮度值。包围盒的意思是用体积稍大且特性简单的几何体来近似地代替复杂的几何对象。

[0050] 3)将父节点加入光源集合，两个子节点从光源集合中删除。

[0051] 4)跳到第一步执行，直到光源集合中只剩一个节点，即根节点，光源树构建完成。其中叶子节点为实际光源，内部节点为代表光源。

[0052] b.求光源割：

[0053] 要在保证渲染结果质量的前提下进行多光源的简化，在求解光源割的过程中就需要按照韦伯原理分裂节点。分裂过程中，对于光源树中的代表光源节点，都有两个值：Lc和upperbound。这两个值在查找到节点时才进行计算：

[0054] Lc表示一个光源聚类实际照射到渲染点的亮度的预估。其计算公式(2)如下：

[0055] Lc(x,w)≈Mj(x,w)Gj(x)Vj(x)∑i∈C Ii 公式(2)

[0056] 其中集合C表示一个光源聚类，x表示渲染点(包含位置，法向等信息)，w表示视点方向，M表示材质因子，G表示几何因子，V表示可见性，I表示光源亮度。i代表实际光源，j是当前聚类的代表光源。upperbound表示理论上节点所代表的光源聚类照射到渲染点产生的亮度的预计最大值(假设光源全部可见)。其计算公式与Lc的公式相同，只是计算过程中材质因子M、几何因子G以及可见性因子V要取上限值。

[0057] 具体的求光源割的过程如图2所示，包括：

[0058] 1)设立一个堆栈来存放结果。首先将根节点入栈，计算根节点的upperbound和Lc。

[0059] 2)如 果maxupperbound<0.02*∑ Lc(maxupperbound为 栈 内 所 有 节 点 的upperbound的最大值，0.02为韦伯参数)，说明栈内所有节点的upperbound值都满足小于0.02*∑Lc的条件，则栈内节点即为最后求得的节点，计算完毕。否则分裂该节点(如果存在子节点)，将被分裂的节点出栈，其子节点入栈。计算新入栈节点的upperbound和Lc。

[0060] 最终堆栈中存储的就是经过Lightcuts算法简化后的结果，即一个光源割。

[0061] 原始Lightcuts算法在场景中阴影较多的地方执行效率比较低，在大量光源都被遮挡的阴影处，光源割内光源的数目基本等于实际光源数。这些阴影处预估亮度Lc很小(有可能为0)，从而韦伯参数0.02与Lc的乘积也很小，而代表光源的上限估计值upperbound由于不考虑遮挡，一般都会大于0.02*Lc。导致求光源割过程中节点不断分裂，直到叶子节点。

[0062] 为了加快实际渲染效率，本发明提出了阴影域和背景亮度两个可选经验参数。在计算执行的光源时候，当预估的总光照值Lc小于阴影域参数值(为保证渲染效果，中和预估总光照时带来的误差，默认取绝对感觉阈限的中值0.05)时，认为该渲染点处于阴影内，对其取背景亮度参数值(一般大于或等于阴影域参数值，默认为绝对感觉阈限0.1)作为当前预估亮度Lc的值，进行求光源割的计算。如果使用了背景亮度后，在之后的计算过程中，预估的总光照值又大于或等于了阴影域参数值，则恢复使用预估亮度Lc进行计算，确保准确性。

[0063] 经过适当的增加阴影区域内渲染点的预估亮度，可以合理减少光源割内光源总数，提高阴影处渲染的效率，实际渲染的结果也符合预期，而且可以保证的图像质量。

[0064] 为了提高效率，将同一物体上相近的点分组进行渲染，只需要执行一遍材质shader，就可以渲染最多256个点。相近的点一般法向和位置相差不大，计算得到的光源割也大致相同，所以根据这个特点，采用增量计算公共光源割的方法来适应引擎对渲染点分组处理的流程，并且加快了求光源割的速度。

[0065] 可编程着色器在渲染中被广泛使用，但传统Lightcuts算法普遍不支持可编程着色器描述的光源。本发明从提取光源着色器提取Lightcuts算法所必要的参数进行传递，从而支持可编程着色器。提取的信息主要包括：光源类型、光源亮度、衰减模式、光源位置、方向、照射范围。

[0066] 在渲染引擎中实现Lightcuts算法，首先必须获取光源信息，以建立光源树。而且建立光源树的过程必须在渲染每个点之前进行，建树过程可以看做是一种预处理，全局只执行一次。渲染引擎会遍历所有光源来计算渲染点处的光照值。要应用Lightcuts算法进行加速，需要在遍历之前加入求光源割的过程，用得到的光源割去取代原来的光源进行渲染，达到加速的目的。

[0067] 本发明的面向可编程着色器的多光源加速方法包括以下步骤：

[0068] 1)渲染引擎读取场景文件中光源信息，Lightcuts解析提取所需光照参数，存入光源链表。

[0069] 2)渲染场景前，Lightcuts算法对光源进行聚类，遍历光源链表，对每类光源构建全局的光源树。

[0070] 3)渲染过程中，渲染引擎计算点的光照时，执行Lightcuts算法：

[0071] 3.1)渲染点的时候，将待渲染点放置于缓冲区中。

[0072] 3.2)对缓冲区中的渲染点聚类，同一物体上相近的点有相同材质，受相同的光源影响，将其聚类，进行渲染。

[0073] 3.3)一组256个渲染点，利用全局光源树，求解一个光源割。

[0074] 3.4)对光源割内的光源进行遍历，根据阴影域或者背景亮度参数估算光源对场景影响，忽略无影响光源。提交渲染执行光源着色器

[0075] 4)渲染引擎执行对应的光源着色器，计算光照结果。选取下一批点，重复步骤2，直到渲染完成，输出渲染结果图像。

[0076] 实现细节：

[0077] 1)可编程着色器定义的光源shader和材质shader有很大灵活性，需要定义与Lightcuts算法相配套的接口进行约束。接口设计时只提取出必要的参数进行传递，避免多余的计算，同时也防止接口参数对着色器约束过多，影响可编程着色器的灵活性。

[0078] 在上述的设计方案中，求光源割需要预估直接光照的值(Lc)，这与材质中直接光照部分的计算有很多是重复的，两遍计算导致效率降低。经过实验证实重复计算中90％以上的工作量源于可见性V的求解。可见性的计算涉及到阴影线与整个场景求交(trace函数)，与场景中面片数目相关，复杂度很高。所以设计了trace_reuse接口参数，将渲染引擎计算Lc过程中得到的求交结果传递给材质shader重用，提高加速效果。

[0079] 2)引擎渲染流程中，为了提高效率，将同一物体上相近的点分组进行渲染，这样只需要执行一遍材质着色器，就可以渲染最多256个点。相近的点一般法向和位置相差不大，计算得到的光源割也大致相同。根据这个特点，本发明采用增量计算公共光源割的方法，对渲染点分组计算光源割，加快了求光源割的速度。计算方法如下：

[0080] 1.一组点共享一个存储光源割的堆栈。设置标记位，标记所执行的是否为一组点的第一个点。

[0081] 2.如果执行的是第一个点，则正常执行求光源割，结果存储到堆栈。如果不是第一个点，则从堆栈中的上一次计算的光源割开始，执行当前点的求光源割过程，结果仍存放在堆栈中。

[0082] 3.不断循环执行第二步，直到一组点全部执行完毕，堆栈中的结果就是这组点的公共光源割。

[0083] 对于一个渲染算法，即是将一个三维场景转化为图片的过程，场景中包括了摄像机，几何体，光源，材质，贴图纹理等信息。在渲染任务开始前，将一个三维场景在建模软件中的表达转化为渲染引擎可以读取和识别的数据表达方式，在转化程序里，按照本发明所述，在可编程着色器中实现Lightcuts算法以及相关改进。之后用户提交一个包含完整信息的场景数据文件包，渲染引擎可以识别这些文件中所描述的摄像机，几何体，光源等信息。在将整个场景数据读入后，开始渲染，着色过程中执行算法，输出图像。

[0084] 浦东夜色场景是一个渲染实例，该场景包含11万三角面片，724个光源，所有几何体、光源、材质均采用符合Renderman规范，光源、材质使用可编程着色器描述。具体场景信息数据如表1所示

[0085] 表1

[0086]

[0087]

[0088] 本发明Lightcuts算法集成渲染引擎进行如下步骤处理：

[0089] 1)用户提交渲染场景数据，渲染引擎读取场景数据，Lightcuts解析提取所需光照参数，存入724个光源组成的光源链表，解析用户背景亮度经验参数估值。

[0090] 2)渲染场景前，Lightcuts算法对光源进行聚类，遍历光源链表，构建724个光源组成的全局光源树，用于求解光源割。

[0091] 3)渲染过程中，渲染引擎计算某个面片材质是，需要计算该面片光照，则执行Lightcuts算法：

[0092] 3.1)将面片上的所有点放置于缓冲区中。

[0093] 3.2)对缓冲区中的渲染点聚类，同一物体上相近的点有相同材质，受相同的光源影响，将其聚类，进行渲染。

[0094] 3.3)一组256个渲染点，利用全局光源树，求解一个光源割。

[0095] 3.4)对光源割内的光源进行遍历，根据阴影域或者背景亮度参数估算光源对场景影响，忽略无影响光源。提交渲染执行光源着色器

[0096] 4)渲染引擎执行对应的光源着色器，计算光照结果。选取下一批点，重复步骤2，直到渲染完成，输出渲染结果图像。

[0097] 在浦东夜色场景中，传统的渲染方法，每个渲染点平均处理光源数量为724个，使用文章[Lightcuts:a scalable approach to illumination]原始方法平均处理光源数量275个，本方法平均处理光源数量为149个。相比较原始的多光源优化算法，其加速百分比大约在30％到40％之间。采用原始算法与本发明改进算法的具体统计数据对比如表2所示。未加速、采用原始算法加速与采用本发明改进方法加速的渲染时间对比如图3所示。

[0098] 表2

[0099]

[0100]

[0101] 上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。