用于射线跟踪的KD-Tree并行构建算法研究

作     者：王康 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：郭杰;李郜伟

授予年度：2020年

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主      题：射线追踪 KD-Tree SAH GPU 并行加速 

摘      要：随着人们对实时射线追踪的要求越来越高,研究者们持续提出更高效的加速算法,设备厂商也在对硬件迭代升级。射线追踪算法本身具有天然的并行性,十分适合使用GPU进行并行加速。最初,射线追踪主要用于图像渲染,如今射线追踪被应用于电磁散射的仿真、声场仿真等各个领域。而KD-Tree是一种广泛用于射线追踪的加速结构,相对于其他结构,其对射线追踪有着较好的加速效果,但是其构建时间却较长,这一定程度上限制了 KD-Tree的应用。现有对KD-Tree的研究,大多只针对SAH算法部分进行加速,并不是全程用GPU加速。本文基于对前人构建KD-Tree算法的研究,提出了使用GPU进行全程加速计算的并行建树方案,使得KD-Tree的构建速度进一步提高。本文的主要创新点如下:一、提出了一种在GPU端进行面元指派的方法。针对现行建树方案将面元指派工作放到CPU端完成的情况,本文引入了并行求前缀和的思想,提出了一种在GPU端进行面元指派的并行方法,有效的减少了内存指派的时间,同时减少了 CPU与GPU之间传输的数据量。使用benchmark模型进行测试时,相对于在CPU端指派面元,在GPU端指派面元到子节点的总时间减少了50%以上。二、针对建树过程中重叠三角面元导致的内存增长问题,本文提出了一种预申请内存大小估计的方法。根据初始三角面元的数量预估最终三角面元数组长度,可保证在程序开始就申请到足够的内存空间。为合理利用申请的内存空间,提出了一种按子节点三角面元数量比例动态分配内存的方法,实现了对预申请内存的无冲突访问。引入了一种计算SAH值的优化算法,并结合归约算法,加速了最小SAH值的计算过程。在本文实验环境中,相比于串行算法,该方法计算最小SAH值的加速比达到了5.8 倍。三、在以上工作的基础上,针对递归建树造成CPU与GPU间频繁数据传输的问题,提出了一种基于广度优先构建KD-Tree的方法,该方法使用两个队列分别存储偶数层与奇数层的待剖分节点,并逐层进行建树,每层只往CPU端传输下一层每个待剖分节点内面元的数量。所有建树任务都在GPU上完成,CPU仅需要计算开启的线程数,显著减少了 CPU与GPU的数据交互频次,降低了由此带来的时间开销。实验结果表明:在不降低KD-Tree质量的情况下,本文所提出的GPU并行算法,在常见场景中有较快的建树速度。使用本文方法构建KD-Tree,相比传统串行算法,加速比可以达到4.1～7.9倍;相比基于空间树的构建方法,有1.2～1.3倍的加速比。