基于KD-tree的并行光线跟踪算法在CPU/GPU异构平台中的研究

作     者：张培承 

作者单位：上海大学 

学位级别：硕士

导师姓名：许华虎

授予年度：2017年

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

主      题：光线跟踪算法 CPU/GPU异构平台 KD-tree Morton Code 

摘      要：光线跟踪算法是全局光照明模型经典的算法之一,为计算机图形学领域提供了一种通过渲染获得真实感图形的解决方案。KD-tree加速结构是光线跟踪算法中常用的空间剖分策略,基于KD-tree的光线跟踪算法在CPU和GPU上都已经分别得到很多改进,取得了很大发展。但现有的基于KD-tree的光线跟踪算法仍然存在着KD-tree构建并行度不高,场景遍历效率较低的问题;而且在CPU/GPU异构平台中,现有光线跟踪算法无法同时高效的利用CPU与GPU的计算能力。本文以CPU/GPU异构平台中的并行光线跟踪算法为研究对象,提出了加速结构KD-tree多层分阶段的构建思想和在KD-tree的遍历前增加路径压缩预处理操作的概念,并结合CPU/GPU异构平台特点对光线跟踪算法流程进行改进。最后辅以实验,对本文提出的CPU/GPU异构平台中光线跟踪算法的改进进行验证。本文的主要研究工作如下:(1)鉴于现有的基于GPU的光线跟踪算法存在着加速结构KD-tree构建并行度较差,耗费时间较长的问题,提出一种多层次的KD-tree构建算法,将均匀栅格划分、基于分区的近似SAH划分和基于精确SAH划分的空间划分策略结合起来,对不同阶段的KD-tree节点采用合适的划分策略,从而加快了高质量KDtree的构建速度。(2)目前基于KD-tree的光线跟踪算法中,加速结构KD-tree的遍历过程中可能遇到大量不包含物体的空白节点,对这些节点的遍历将导致不必要的计算。针对这一问题,本文在构建KD-tree的过程中引入Morton Code,并根据路径压缩思想将空白节点剔除,从而减少无用的遍历求交计算,提高KD-tree的遍历速度。(3)单纯对CPU或GPU优化的光线跟踪算法渲染过程中任务并行度较低,CPU资源利用不充分。本文基于CUDA并行编程架构,并结合光线跟踪算法的改进,提出CPU/GPU异构平台中并行光线跟踪算法的完整渲染流程及过程中的任务数据分配策略,加快了三维模型的图像渲染速度。为了验证关于光线跟踪算法的改进及其在CPU/GPU异构平台中的实现,本文设计了两组实验。由实验结果可以得到以下结论:首先,在相同条件下,改进的KD-tree构建与遍历算法能较大提高光线跟踪算法的效率。其次,在相同条件下,本文方法在CPU/GPU异构平台中的渲染速度要明显高于只针对CPU或GPU的优化算法。综上所述,本文提出的针对CPU/GPU异构平台中基于KD-tree的并行光线跟踪算法的改进取得了预期的结果,较大地提高了光线跟踪算法的渲染速度。