一种基于GPU的混合树并行构建方法

技术领域

本发明涉及图形实时渲染技术领域，尤其涉及一种基于GPU的混合树并行构建方法。

背景技术

虚拟现实技术(Virtual Reality-VR)技术，也称灵境技术或人工环境，20世纪八十年代 由美国Jaron Lanier教授首次提出这一概念。主要是利用计算机模拟产生一个三维空间的虚 拟世界、提供使用者关于视觉、听觉、触觉等感官的模拟，是计算机对复杂数据进行可视化 操作与交互的一种技术。

光线跟踪技术是一种在图形绘制领域广泛应用的技术。它的最大的优势是产生高质量的 图像，绘制出高真实感的平滑的反射、折射、软影等全局光照效果，但是它的计算量很高， 因此以往这种技术只能应用在非实时绘制领域中。可见性判断及剔除技术。该技术是在三角 形面片被送往渲染管线之前，通过算法或者硬件支持，提前判断出面片的可见性，并将不可 见的部分剔除，以减轻渲染管线的工作量，达到加速绘制的效果。但是场景中的面片数通常 都要达到百万量级，实时的对场景中的面片进行可见性判断几乎无法完成。为了提高虚拟现 实中一些算法的执行效率，提出了场景划分技术。

场景划分技术的组织通常是层次结构的。宽泛地说，就是最高层次包含它下面的层次， 后者又包含再下面的层次，如此类推。因此，这种结构具有嵌套和递归的特点。使用层次结 构的原因是，可以明显地提高不同类型的查询速度，计算复杂度通常从O(n)提高到O(logn)。 同时需要注意，大多数场景管理技术的构造开销都比较大，虽然也可以在实时过程中进行渐 进更新，但是通常需要作为一个预处理过程来完成。不同类型的空间数据结构有：包围体层 次(BVH)、各种二元空间分割树(BSP)、多维空间的二叉树(KD)，以及八叉树(Octree) 等。

GPU(Graphic Processing Unit)最初应用于图形显示的加速，GPU的单指令多数据流 (SIMD:Single Instruction Multiple Data)的处理方式可并行地对大规模的数据进行操作，可 大大缩短计算时间。GPU上的可编程语言出现以后，研究人员将一部分运算交由GPU来执 行，以加快程序运行的速度。基于该思路，使用GPU进行场景节点的面片分布计算，可以 有效的提高场景划分的速度。

传统的八叉树构造根据三个垂直坐标轴x、y、z方向上对象的中间位置对场景进行划分， 这种划分方式尽管简单快速，但其粗糙的质量造成了大量无效的遍历和相交操作，也造成了 大量的空节点而浪费存储空间，使得八叉树逐渐被构建质量更高的KD树所取代。而KD树 的划分虽然具有高效的结构特征，但其划分的计算复杂度远却远高于八叉树，导致划分的预 处理时间难以满足动态场景的实时光线跟踪计算要求。另一方面，当前的GPU架构包含多 个多核处理器，需要同时运行上万个线程才能充分利用这些处理器的计算能力，而KD树等 加速结构在其构建过程中节点的产生速度慢，大大浪费了GPU的计算资源，进而影响构造 速度。

发明内容

本发明提供一种基于GPU的混合树并行构建方法，构建高质量的加速结构，同时充分利 用硬件的并行计算能力，提高加速结构的构造速度，以达到动态场景计算的实时性。

本发明采用的技术方案为：一种基于GPU的混合树并行构建方法，在需要进行渲染的 模型空间的X、Y、Z三个坐标轴方向中选取一个面片分布方差最大的，计算该坐标轴的垂 直切面位置，使得切面两边的面片数相等，对模型空间中的场景数据逐级进行KD树划分， 然后对划分后的叶节点依次进行八叉树划分；其中划分场景数据的具体步骤如下：

步骤a)、在存储区域中建立两个队列，一个存放等待处理的场景节点数据，一个存放已 经处理过后的场景节点数据，一个存放等待处理的八叉树根节点；

步骤b)、将第一个队列中的场景节点数据依次取出，如果节点数据满足停止划分的条件， 则将节点放入第三个队列中；否则进行KD树的空间划分，将处理后生成的孩子节点放入第 二个队列中；

当前节点的深度为k，则该节点的孩子节点的编号为10^k+i(i＝1,2)(其中如果是左节点， 则i＝1；如果是右节点，则i＝2；

步骤c)、当第一个队列中的所有场景节点处理完毕后，将第一队列清空，逐个处理第二 队列中的场景节点，并将生成的孩子节点放入第一个队里中；

步骤d)、循环步骤b)、步骤c)，直至完成所有场景节点的KD划分；

步骤e)、将第三队列中的节点放入第一队列中，并清空第三队列，然后进行八叉树的划 分。依次取出第一队列中的节点进行八叉树划分，其具体过程与KD树类似，其中节点的编 号为10^k+i(i＝1,2,...8)。

进一步的，KD树停止划分的条件为三个坐标轴的面片分布方差接近相等，即最小的方 差值大于最大的方差值的80％，或者是节点内的面片数为全场景的面片总数的(如果KD 树为第二种情况停止划分，则不再进行八叉树的划分)；八叉树停止划分的条件为节点内的 面片数为全场景的面片总数的

进一步的，对每一个场景节点进行划分时，GPU的每一个线程块分别处理一个场景节 点，在相互对应的线程块和场景节点中，线程块中的每一线程计算节点中不同面片离中心位 置的距离，最后通过硬件支持的归约操作，得到场景的面片分布方差。

进一步的，场景的面片在p方向上的分布方差

n为节点中的面片总数；

p方向为x、y、z三个方向；

x_i为第i个面片的中心点在p方向上的位置值；

x为场景中的所有面片的中心点在p方向上的位置值的平均。

附图说明

图1为本发明一种基于GPU的混合树并行构建方法的流程图示意图；

图2为本发明中KD树划分流程图；

图3为本发明中八叉树划分流程图。

具体实施方式

下面介绍本发明的具体实施方式。

一种基于GPU的混合树并行构建方法，在需要进行渲染的模型空间的X、Y、Z三个坐 标轴方向中选取一个面片分布方差最大的，计算该坐标轴的垂直切面位置，使得切面两边的 面片数相等，对模型空间中的场景数据逐级进行KD树划分，然后对划分后的叶节点依次进 行八叉树划分；其中划分场景数据的具体步骤如下：

步骤a)、在存储区域中建立两个队列，一个存放等待处理的场景节点数据，一个存放已 经处理过后的场景节点数据，一个存放等待处理的八叉树根节点；

步骤b)、将第一个队列中的场景节点数据依次取出，如果节点数据满足停止划分的条件， 则将节点放入第三个队列中；否则进行KD树的空间划分，将处理后生成的孩子节点放入第 二个队列中；

当前节点的深度为k，则该节点的孩子节点的编号为10^k+i(i＝1,2)(其中如果是左节点， 则i＝1；如果是右节点，则i＝2；

步骤c)、当第一个队列中的所有场景节点处理完毕后，将第一队列清空，逐个处理第二 队列中的场景节点，并将生成的孩子节点放入第一个队里中；

步骤d)、循环步骤b)、步骤c)，直至完成所有场景节点的KD划分；

步骤e)、将第三队列中的节点放入第一队列中，并清空第三队列，然后进行八叉树的划 分。依次取出第一队列中的节点进行八叉树划分，其具体过程与KD树类似，其中节点的编 号为10^k+i(i＝1,2,...8)。

进一步的，KD树停止划分的条件为三个坐标轴的面片分布方差接近相等，即最小的方 差值大于最大的方差值的80％，或者是节点内的面片数为全场景的面片总数的(如果KD 树为第二种情况停止划分，则不再进行八叉树的划分)；八叉树停止划分的条件为节点内的 面片数为全场景的面片总数的

进一步的，对每一个场景节点进行划分时，GPU的每一个线程块分别处理一个场景节 点，在相互对应的线程块和场景节点中，线程块中的每一线程计算节点中不同面片离中心位 置的距离，最后通过硬件支持的归约操作，得到场景的面片分布方差。

进一步的，场景的面片在p方向上的分布方差

n为节点中的面片总数；

p方向为x、y、z三个方向；

x_i为第i个面片的中心点在p方向上的位置值；

x为场景中的所有面片的中心点在p方向上的位置值的平均。

本发明采用的构造方式可以迅速产生出大量数据供成千上万的GPU线程使用，使它们 一直保持满负荷工作状态；其次，由于我们先在三个维度上进行KD树划分，使得划分后的 节点在三个维度上的面片分布越来越均匀。

借助硬件强大的并行计算能力，本发明采用的混合树加速结构凝结了传统加速结构的优 点：第一，与传统的八叉树加速技术相比，本发明提出的方法，在前期的场景划分的过程中 采用的是KD树的划分策略，使得每个孩子节点中的面片分布均匀，为后期的八叉树划分提 供了质量的保证，其结果是大大减少了无效遍历和相交操作；第二、与传统的KD树加速技 术相比，本发明提出的方法，在后期的场景划分的过程中采用的是八叉树的划分策略，其一 是加速了加速结构的生成速度，其二是大大减少了层次结构的深度，为应用阶段的节点判断 节省了大量时间。另外，在KD树的划分过程中需要进行庞大的计算开销，传统的方法是基 于CPU的串行计算，计算效率低。而GPU具有高效的浮点运算能力，并且KD树每个节点的 计算具有高度的独立性，本发明提出的方法利用GPU的高效并行处理能力，有效地提高了KD 树划分的效率。

本发明未详细阐述部分属于本领域技术人员的公知技术。