基于虚拟光源和自适应稀疏矩阵还原的全局光照绘制方法

摘要

本发明公开了一种基于虚拟光源和自适应稀疏矩阵还原的全局光照绘制方法，包括：确定待绘制场景的视觉采样器、虚拟光源以及各个虚拟光源的光源信息；所述的视觉采样器包括摄像机在待绘制场景的几何网格表面的渲染点以及在待绘制场景的介质中的视线段，所述的虚拟光源包括虚拟点光源和虚拟线光源；构建待绘制场景的光传递矩阵，根据虚拟光源的光源信息建立相应的光树，依据光树中对光传递矩阵按列进行稀疏矩阵还原：将各个像素点对应的视觉采样器的光照值进行加权求和，以加权求和结果作为该像素点的亮度值。本发明能够实现带介质的场景的绘制，且对于每个光传递矩阵利用部分元素进行稀疏矩阵还原，大大提高了绘制效率。

说明书

技术领域

本发明涉及图像技术领域，尤其涉及一种基于虚拟光源和自适应稀疏矩阵还原的 全局光照绘制方法。

背景技术

全局光照是计算机图形学中非常重要的研究领域，通过对大自然中光照情况的模 拟，捕捉真实环境中的光的多次传播、折射、反射所产生的软影、间接折射等光照效果，这些 效果能大大加强渲染效果的真实感。这一技术常用于电影、动画、三维模型的渲染中。全局 光照有多种实现方法，例如辐射度、光线追踪、环境光遮蔽、光子贴图。

大量光源(Many-light)的方法是其中一类重要的全局光照技术，它在场景中生成 大量虚拟光源，包括虚拟点光源(VirtualPointLight，VPL)和虚拟线光源(VirtualRay Light,VRL)，通过分别计算各视角采样器被这些虚拟光源照亮的程度来获得全局光照效 果，其中视角采样器包括渲染点(ShadingPoints)和视线段(EyeRay)。通过把复杂的多次 传播问题简化为采样器被虚拟光源直接照亮问题，为全局光照问题提供了一个统一的数学 框架，并且拥有很高的灵活性，可以根据实际需要调节算法的复杂度。

为进一步提高绘制速度，提高实时性，Wald等人发明了基于大量点光源框架的光 割(lightcuts)方法，将虚拟点光源建立层次结构并使用层次结构树的一个割集代表所有 虚拟点光源，减少运算量并加快了运算速度。

Novák等人发明了虚拟线光源(VirtualRayLight,VRL)方法，使用虚拟线光源模拟 介质(比如雾)的光能贡献，扩大了多光技术的应用范围。

近年来，随着不同研究者对光割方法的不断完善，大量光源框架已经成为了实现 全局光照方法中效率很高的一种。但是，光割方法仍然需要进行大量计算，平均每个视角采 样点需要计算几百到上千个虚拟光源对它的贡献，严重制约了绘制速度，实时性差。因此可 以看出，效率仍然是限制其应用发展的主要瓶颈。

针对该问题，公开号为CN103971397A和CN105335995A的中国专利申请中公开了一 种基于光割技术的多光渲染方法，其使用全局的稀疏矩阵还原法加快了多光渲染速度，提 高光渲染效率，但是，由于受到光割技术的限制，该渲染方法只能适用于不带介质的场景 中。

发明内容

针对现有技术的不足，本发明提供了一种基于虚拟光源和自适应稀疏矩阵还原的 全局光照绘制方法，才使用自适应矩阵还原技术，可以结合虚拟线光源(VirtualRay Light,VRL)方法渲染带有介质的场景，具有更高的普适性，且渲染速率快。

一种基于虚拟光源和自适应稀疏矩阵还原的全局光照绘制方法，包括如下步骤：

(1)确定待绘制场景的视觉采样器、虚拟光源以及各个虚拟光源的光源信息；所述 的视觉采样器包括摄像机在待绘制场景的几何网格表面的渲染点以及在待绘制场景的介 质中的视线段，所述的虚拟光源包括虚拟点光源和虚拟线光源；

(2)构建待绘制场景的光传递矩阵，所述光传递矩阵的行与视觉采样器一一对应， 列与虚拟光源一一对应；

(3)根据虚拟光源的光源信息建立相应的光树，以光树的根节点作为当前节点，通 过如下步骤对光传递矩阵进行按列的稀疏矩阵还原：

(3-1)以光传递矩阵中与光树中当前节点包含的叶节点所对应的列为列采样集， 对该列采样集进行列稀疏采样得到采样列；

(3-2)针对每个采样列，选取若干元素作为参考元素并计算各个参考元素的值，然 后利用参考元素的值对该列进行稀疏还原求解该采样列；

(3-3)根据所有求解的采样列的计算当前节点的误差，若误差小于预设的误差阈 值，则计算当前节点对应的虚拟光源对各个视觉采样器的光照值；

否则，则针对光树中当前节点的左、右子节点分别执行返回步骤(3-1)～(3-3)；

(4)根据各个视觉采样器的对应像素点标记，确定各个像素点对应的视觉采样器， 将各个像素点对应的视觉采样器的光照值进行加权求和，以加权求和结果作为该像素点的 亮度值。

循环步骤(3-1)～(3-3)时会存在执行到叶子节点，此时不考虑误差大小一旦达叶 子节点即结束循环。

本发明的全局光照绘制方法中首先需要以下输入以下信息：

目标绘制场景(即待绘制场景)的几何网格(即一些三角面片)，以及各个几何网格 的法向量；绘制场景中的介质信息(即包含介质信息的空间网格)，一系列虚拟光源，包括各 个虚拟光源的材质信息、位置信息(实际上包括在目标绘制场景中的中位置，以及方向)和 能量信息，以及摄像机的空间信息(包括摄像机的位置和方向)。

本发明中采用SBVH方法(空间分割包围盒，Spatialsplitsinboundingvolume hierarchies，SBVH)构建几何网格的空间加速结构，并利用所述的空间加速结构和摄像机 的位置信息，采用光线追踪法确定摄像机在几何网格中的视觉采样器，并确定各个视觉采 样器的采样信息。所述步骤(2)中构建的光传递矩阵中所有元素均未知，可以理解为构建的 光传递矩阵中每个元素均为空。每一对应一个的虚拟光源，虚拟光源可以是打到几何表面 上的虚拟点光源或者一段通过介质(比如烟雾)的虚拟线光源。且光传递矩阵的元素可分为 四类，分别如下：

(a)用于表示虚拟点光源到渲染点的贡献值：

V(x，y)G(x，y)f(x，y)L(1)

其中x表示渲染点，y表示虚拟点光源，V(x,y)表示两点间的广义可见项，G(x,y)表 示两点间的几何项，L表示虚拟点光源y的强度，f(x,y)表示渲染点x到虚拟点光源y(即向着 虚拟点光源y方向)的材质项。

(b)用于表示虚拟点光源到视线段的贡献值：

$$ {\int }_0^{u}V(x,y)G(x,y)L\left(y\right)f(x,y)dt---\left(2\right)$$

其中x＝a+td表示视线段上的一个点，u为视线段的长度，d为视线段的方向，a为视 线段的起始位置，y表示虚拟点光源，V(x,y)表示两点间的广义可见项，G(x,y)表示两点间 的几何项，L表示光源y的强度，f(x,y)表示x到y的材质项；

(c)用于表示虚拟线光源到渲染点的贡献值：

$$ {\int }_0^{v}V(x,y)G(x,y)L\left(y\right)f(x,y)ds---\left(3\right)$$

其中y＝b+si表示虚拟线光源上的一个点，v为虚拟线光源的长度，i为虚拟线光源 的方向，b为虚拟线光源的起始点，x表示渲染点，V(x,y)表示两点间的广义可见项，G(x,y) 表示两点间的几何项，L表示光源y的强度，f(x,y)表示x到y的材质项。

(d)用于表示虚拟线光源到视线段的贡献值：

$$ {\int }_0^u{\int }_0^{v}V(x,y)G(x,y)L\left(y\right)f(x,y)dsdt---\left(4\right)$$

其中x＝a+td表示视线段上的一个点，u为视线段的长度，d为视线段的方向，a为视 线段的起始点，y＝b+si表示虚拟线光源上的一个点，v为虚拟线光源的长度，i为虚拟线光 源的方向，b为虚拟线光源的起始点，x表示渲染点，V(x,y)表示两点间的广义可见项，G(x, y)表示两点间的几何项，L(y)表示光源y的强度，f(x,y)表示x到y的材质项。

作为优选所述步骤(1)中还包括确定各个视觉采样器的采样信息；

对于渲染点，所述的采样信息包括该渲染点的位置、材质和对应像素点标记；对于 视线段，所述的采样信息包括该视线段的位置、介质和对应像素点标记，其中，渲染点的位 置包括位置和法向量；视线段的位置包括起始位置，方向和长度。

所述步骤(1)还包括根据各个视觉采样器的位置分别对渲染点和视线段单独进行 聚类，相应的，所述步骤(2)中针对每一类视觉采样器分别构建相应的光传递矩阵，所述步 骤(3)针对每个光传递矩阵按列进行稀疏矩阵还原。

本发明的全局光照绘制方法中，采用使用大量点虚拟光源模型构建待绘制几何场 景的光树，并对视觉采样器进行聚类，分类处理各类视觉采样器，根据聚类结果针对每一类 视觉采样器构建光传递矩阵，且对于每一类视觉采样器处理时，构建该类视觉采样器的光 传递矩阵。这样分类处理，有效减小了光传递矩阵的秩，降低了计算量(降低了稀疏采样的 采样率)。

通过对视觉采样器进行聚类，根据聚类结果针对每一类视觉采样器构建光传递矩 阵，大大降低了光传递矩阵的秩，有利于降低计算量，提高渲染效率。作为优选，针对每一类 视觉采样器对应的光传递矩阵可并行稀疏矩阵还原。

所述步骤(3-1)中对列采样集进行列稀疏采样时采样的列数为10～100。

所述步骤(3-2)中针对每个采样列选取总元素的10％～20％作为参考元素。

所述步骤(3-3)中根据所有求解的采样列的计算当前节点的误差ε：

$$ ϵ={\Sigma }_k^K{(E-\frac{l_k}{pdf\left(l_k\right)})}^2,$$

其中，l_k为采样列，pdf(l_k)为对光传递矩阵进行列稀疏采样时以l_k作为采样列的 概率，K为采样列的总列数，E为当前节点的贡献值，根据如下公式计算：

$$ E=\underset{k}{\overset{K}{\Sigma }}\frac{l_k}{pdf\left(l_k\right)}.$$

所述步骤(3-3)中预设的误差阈值为0.0001～0.01。

本发明中的视觉采样器包括摄像机在待绘制场景的几何网格表面的渲染点以及 在待绘制场景的介质中的视线段，所述的虚拟光源包括虚拟点光源和虚拟线光源，这样使 该渲染方法能够实现带介质的场景的绘制。且对于每个光传递矩阵，通过自适应选择一些 列，并随机采样被选择的列的部分元素并计算选择元素的取值，然后利用部分元素进行稀 疏矩阵还原，进一步计算得到各个视点采样器亮度值(即贡献值)。

具体实施方式

下面将结合具体实施例对本发明进行详细说明。

利用本实施例的基于虚拟光源和自适应稀疏矩阵还原的全局光照绘制方法进行 场景绘制时首先需要以下输入以下信息：

目标绘制场景(即待绘制场景)的几何网格(即一些三角面片)，以及各个几何网格 的法向量；绘制场景中的介质信息(即包含介质信息的空间网格)，一系列虚拟光源，包括 各个虚拟光源的材质信息、位置信息(实际上包括在目标绘制场景中的中位置，以及方向) 和能量信息，以及摄像机的空间信息(包括摄像机的位置和方向)。

进行绘制时依次进行如下步骤：

(1)确定待绘制场景的视觉采样器、虚拟光源以及各个虚拟光源的光源信息；视觉 采样器包括摄像机在待绘制场景的几何网格表面的渲染点以及在待绘制场景的介质中的 视线段，所述的虚拟光源包括虚拟点光源和虚拟线光源；

采用SBVH方法(空间分割包围盒，Spatialsplitsinboundingvolume hierarchies，SBVH)构建几何网格的空间加速结构，并利用空间加速结构和摄像机的位置 信息，采用光线追踪法确定摄像机在几何网格中的视觉采样器，并确定各个视觉采样器的 采样信息。采样信息包括对应视点采样器的位置(视觉采样点的几何位置和视觉采样线的 中点)、方向(视觉采样点的法向量和视觉采样线的平均介质粒子方向)、材质和对应像素点 标记。对于渲染点，采样信息包括该渲染点的位置、材质和对应像素点标记；对于视线段，采 样信息包括该视线段的位置、介质和对应像素点标记，其中，渲染点的位置包括位置和法向 量；视线段的位置包括起始位置，方向和长度。

根据待绘制场景的光照信息确定相应点光源和线光源，每个虚拟点光源的光源信 息包括位置信息、材质信息和能量信息，虚拟线光源的光源信息包括位置信息、方向信息， 介质信息和能量信息。

根据各个虚拟点光源的位置信息、材质信息和能量信息，建立光树；根据各个虚拟 线光源的位置信息、方向信息，介质信息和能量信息，建立光树；

(2)构建待绘制场景的光传递矩阵，光传递矩阵的行与视觉采样器一一对应，列与 虚拟光源一一对应；

为提高渲染速率，本实施例中首先将所有视觉采样点分类，然后根据分类结果，针 对每一类视觉采样点构建相应的光传递矩阵。

本实施例通过聚类对视觉采样点进行分类，具体如下：

根据视觉采样器的位置分别针对渲染点和视线段进行聚类，本实施例中采用K-均 值(K-means)进行聚类。聚类时每次迭代的距离函数为：

$d=\alpha ||x_i-x_k||+\sqrt{2-2({\overrightarrow{n}}_i·{\overrightarrow{n}}_k)},$

其中，α为常数，

x_k为第k类视角采样器的位置均值，为第k类视角采样器的方向均值，k＝1, 2，……，K，K为每一次迭代得到的类的总数，

x_i为当前被聚类的视觉采样点的位置，为当前被聚类的视觉采样器的法向量，i ＝1,2……，I，I为第k类视角采样器中视觉采样器的总数；

每一簇的大小为512～1024。

常数α的取值为0.5～1，用于在聚类过程中各次迭代时，控制距离与角度相对重要 度。

每一次迭代得到类的总数根据聚类方向确定，若为自顶向下聚类，则第一次迭代 得到的类的总数K＝2，第二次迭代得到的类的总数K＝4，此后依次递推，第l次迭代得到的 类的总数K＝2^l，l＝1,2，……，L，L为聚类时的迭代总次数，根据实际情况确定。

视觉采样器的聚类对最终的绘制效果影响较大，帮采用更保守但是质量较高的传 统聚类方法，聚类中使用的距离函数同时考虑位置和法向，较大的簇可以增加矩阵还原时 的稳定性和准确性。

(3)根据虚拟光源的光源信息建立相应的光树，以光树的根节点作为当前节点，通 过如下步骤对光传递矩阵按列进行稀疏矩阵还原：

(3-1)以光传递矩阵中与光树中当前节点的叶节点所对应的列为列采样集，对该 列采样集进行列稀疏采样得到采样列；

(3-2)针对每个采样列，选取若干元素作为参考元素并计算各个参考元素的值，然 后利用参考元素的值对该列进行稀疏还原求解该采样列；

(3-3)根据所有求解的采样列的计算当前节点的误差，若误差小于预设的误差阈 值，则计算当前节点对应的虚拟光源对各个视觉采样器的光照值；

否则，则针对光树中当前节点的左、右子节点分别执行返回步骤(3-1)～(3-3)；

根据各个虚拟光源的位置信息(虚拟点光源的几何位置和虚拟线光源的中点)、材 质信息和能量信息，利用文献“AMatrixSampling-and-RecoveryApproachforMany- LightsRendering，Huo,Wang,Jin,Liu,&Bao,2015”中公开的方法建立相应的光树。本实 施例中光树的高度为32～64。

本实施例中针对虚拟点光源和线光源单独建立光树，即根据所有虚拟点光源的位 置信息、材质信息和能量信息，建立VPL光树；根据所有虚拟线光源的位置信息、方向信息， 介质信息和能量信息，建立VRL光树。相应的，步骤(2)中可以分别针对VPL光树和VRL光树构 建光传递矩阵。本实施例中不考虑，即针对虚拟点光源和虚拟线光源构建为一个光传递矩 阵。

由于采用稀疏还原的方法，需要实际计算的矩阵元素大量减少，因此可以建造更 深、更精确的光树结构来支持百万级的虚拟光源，进行高质量的场景绘制。

针对构建的多个光传递矩阵分别执行步骤(3)，完成相应的列稀疏矩阵还原。

为了加速计算光传递矩阵的贡献，稀疏地随机采样一部分矩阵的列，并使用蒙托 卡洛方法来计算整个子光传递矩阵的贡献。然后选择这棵树上的一个割集来近似整棵树的 贡献。

对于光树上的任意一个节点，其贡献的计算公式如下：

$$ E=\underset{k}{\overset{K}{\Sigma }}\frac{l_k}{pdf\left(l_k\right)}---\left(1\right)$$

其中l_k表示子光传递矩阵的一列，pdf(l_k)表示采这一列的概率，K是一共采的列的 数目，E是一个树节点的列加和得到的向量，它的行就是对应视觉采样器接受到这个树节点 的贡献，这些亮度累加到视觉采样器对应的像素点就可以产生最终的图片。

计算某一列l_k的值时，稀疏地随机采样这一列上一定比例的行(本实施例中的比 例为10％)，然后使用文献“OnthePowerofAdaptivityinMatrixCompletionand Approximation，Krishnamurthy&Singh,2014”的方法使用这些稀疏的元素将整列还原出 来，从而达到减少采样的目的。

因为使用一部分列来逼近树节点的贡献会产生误差，计算每个节点的误差并动态 地为每个子光传递矩阵寻找合适的割集。算法的整体流程为，对于每个光传递矩阵，首先输 入光树的根节点，将该根节点推入一个优先队列中。然后程序循环地取出该优先队列中误 差最大的节点，并把这个节点分为它的两个子节点(即左右子节点)，如果新生成的子节点 的误差小于一个用户给定的误差上限参数(即误差阈值)，则将此子节点的贡献累加到图 片的像素中，否则就把该子节点推入优先队列中以进行进一步细分。

本实施例中步骤(3-3)中根据所有求解的采样列的计算当前节点的误差ε：

$$ ϵ={\Sigma }_k^K{(E-\frac{l_k}{pdf\left(l_k\right)})}^2,$$

其中，l_k为采样列，pdf(l_k)为对光传递矩阵进行列稀疏采样时以l_k作为采样列的 概率，K为采样列的总列数，E为当前节点的贡献值，根据如下公式计算：

$$ E=\underset{k}{\overset{K}{\Sigma }}\frac{l_k}{pdf\left(l_k\right)}.$$

(4)根据各个视觉采样点的对应像素点标记，确定几何网格中各个像素点对应的 视觉采样器，将各个像素点对应的视觉采样器的光照值进行加权求和，以加权求和结果作 为该像素点的亮度值。

以上所述的具体实施方式对本发明的技术方案和有益效果进行了详细说明，应理 解的是以上所述仅为本发明的最优选实施例，并不用于限制本发明，凡在本发明的原则范 围内所做的任何修改、补充和等同替换等，均应包含在本发明的保护范围之内。