基于OpenCL的实时KD-Tree与动态场景光线跟踪

摘要

光线跟踪是一种可以实现高质量全局光照明效果的算法。该算法因为简单而被广泛应用。由于其算法复杂度较高，在实际应用中难以达到实时绘制的要求。因此，实时光线跟踪一直是计算机图形学研究领域追求的目标。通过使用加速结构、设计并行算法来提高光线跟踪的速度是近年来的一个研究热点。本文提出了一个基于OpenCL并且可以跨平台运行的动态场景实时光线跟踪绘制算法。通过对通用GPU并行处理性能的发掘和对多核CPU计算性能的评估，我们将光线跟踪的三个组成部分KD-Tree建立、场景遍历和绘制三个过程均设计在GPU上，而CPU则负责其中各模块调度和参数计算，从而充分利用了各部件的计算性能，并有效降低了数据传输开销。算法的核心是实时KD-Tree建树算法。通过设计并行分区、并行SAH、紧密的数据管理以及区间性叶结点存储等算法，可以在GPU中高效、高质量地建立动态场景的KD-Tree，同时高质量KD-Tree也有效地加速了场景的遍历速度。本文的算法较以前的多核CPU算法有更高的并行性，较以往的CUDA GPU算法有更强的通用性，在建树算法上亦有较低的算法复杂度。实验结果表明，本文的方法可以在NVIDIA GTX465和 AMD HD5850显卡上对中等规模的动态场景实现实时光线跟踪绘制。

目录

文摘

英文文摘

图目录

表目录

第1章 绪论

1.1 课题背景

1.1.1 光线跟踪

1.1.2 加速结构

1.1.3 并行计算

1.2 本章小结

第2章 相关研究工作介绍

2.1 常用的加速结构

2.1.1 网格结构

2.1.2 八叉树结构

2.1.3 层次包围盒结构

2.1.4 二叉空间剖分树结构

2.1.5 混合结构

2.1.6 本节小结

2.2 KD-Tree光线跟踪

2.2.1 传统的KD-Tree构建算法

2.2.2 多核CPU上的KD-Tree构建算法

2.2.3 GPU上的KD-Tree构建算法

2.2.4 GPU上的KD-Tree遍历算法

2.2.5 GPU上的光亮度计算

2.2.6 本节小结

第3章 通用并行算法的设计

3.1 不同的计算设备

3.1.1 CPU与GPU

3.1.2 AMD GPU与NVIDIA GPU

3.1.3 木桶原理的限制和解决的方法

3.2 本章小结

第4章 通用的KD-Tree光线跟踪

4.1 基本思想

4.1.1 算法总揽

4.2 通用的KD-Tree构建算法

4.2.1 GPU分区算法

4.2.2 并行SAH分割平面计算

4.2.3 紧致的数据管理

4.2.4 停止分割的条件

4.2.5 区间性叶结点的存储

4.2.6 数据重组

4.3 通用的KD-Tree遍历算法

4.4 通用的基于KD-Tree的光线跟踪

4.5 本章小结

第5章 基于OpenCL的通用KD-Tree光线跟踪

5.1 使用OpenCL

5.2 设备的选取

5.3 系统测试

5.4 基于OpenCL的通用的KD-Tree构建

5.4.1 GPU分区算法

5.4.2 并行SAH与VH分割平面计算

5.4.3 紧致的数据管理

5.4.4 GPU函数的控制

5.5 基于OpenCL的通用的KD-Tree遍历

5.6 基于OpenCL的通用的KD-Tree光线跟踪

5.7 Debug时需要注意的问题

5.8 本章小节

第6章 实验结果与统计数据

第7章 总结与未来的工作

参考文献

攻读硕士学位期间主要的研究成果

致谢