一种基于GPU的八叉树并行构建方法

摘要

本发明公开了一种基于GPU的八叉树并行构建方法，在需要进行渲染的模型空间的三个坐标轴上分别选取若干个采样分割点，计算每个采样分割点的SAH花费，然后选取每个坐标轴上SAH花费最小的分割点，将选取的这三个分割点作为分割平面，对模型空间中的场景数据逐级进行划分，直至划分到每个节点所含面片数不多于10个。本发明由于在三个维度上同步进行基于SAH的选择划分，使得这个改良后的八叉树结构质量更高，大大减少了无效的遍历和相交操作，尤其适合大光线包的遍历。

主权项

一种基于GPU的八叉树并行构建方法，其特征在于，在需要进行渲染的模型空间的三个坐标轴上分别选取若干个采样分割点，计算每个采样分割点的SAH花费，然后选取每个坐标轴上SAH花费最小的分割点，将选取的这三个分割点作为分割平面，对模型空间中的场景数据逐级进行划分，直至划分到每个节点所含面片数不多于10个；其中划分场景数据的具体步骤如下：a)在存储区域中建立两个队列，分别用来存放等待进行划分的场景节点；b)从第一队列中依次取等待进行划分的场景节点进行划分，并将产生的新的场景节点放入第二队列；其中对第一队列中编号为k的场景节点进行划分所产生的新的场景节点在第二队列中的编号分别为8×k+t，t＝0，1，...7；场景节点在队列中的编号也对应了该场景节点在存储区域中的位置；c)当第一队列中等待进行划分的场景节点处理完毕后，清空第一队列中所有的场景节点数据，从第二队列中依次取等待进行划分的场景节点进行划分，并将产生的新的场景节点放入第一队列，直至第二队列中等待进行划分的场景节点都处理完毕；其中对第二队列中编号为j的场景节点进行划分所产生的新的场景节点在第一队列中的编号分别为8×j+t，t＝0，1，...7；场景节点在队列中的编号也对应了该场景节点在存储区域中的位置；d)循环步骤b)、步骤c)，直至完成所有场景节点的划分；所述的步骤b)、步骤c)中当每个队列中等待进行划分的场景节点划分完毕后，通过硬件支持的紧凑操作清除该队列中的空场景节点；对每一个场景节点进行划分时，GPU的每一个线程块分别处理不同的场景节点，在相互对应的线程块和场景节点中，线程块中的每一线程分别计算不同采样分割点的SAH花费，最后通过硬件支持的归约操作，选取每个坐标轴上SAH花费最小的分割点。