一、回顾
Whitted-Style Ray Tracing使用递归的方式，做光线追踪。光线在场景中任何一个地方都可能发生弹射，在任何一个交点都要计算着色和阴影，最后加权到像素值上的原理。
解释了光线和三角形求交的方法。但是光线与三角形求交比较复杂。
然后引入轴对齐包围盒(AABB)结构，利用光线和AABB的求交，来解决光线与三角形求交复杂问题。
二、加速结构
现在我们知道了光线和AABB求交。那我们怎么利用它，来加速光线与场景求交问题？
答：使用以下两个技术来实现：
1、Uniform grids（均匀格子）
2、Spatial partitions （空间划分）
以上的方式，是在做光线追踪之前，对场景的预处理操作。
1、Uniform grids
（1）对场景预处理
（2）光线追踪
（3）格子怎么进行划分的选择？
（4）Uniform grids的问题
2、Spatial partitions
由于Uniform grids的问题，提出Spatial partitions的解决方案。
思路：Uniform grids是均匀的划分。在物体稀疏的地方不需要用很多格子划分。
下图是一些空间划分算法，KD-Tree使用最多。
1）KD-Tree
（1）KD-Tree对场景预处理
（2）KD-Tree光线追踪
（3）KD-Tree空间划分的问题
问题1：KD-Tree的建立不容易，需考虑三角形与格子的求交。
问题2：KD-Tree的划分，一个物体可能和多个格子有交集，则一个物体就会存储在多个叶子节点里。
2）BVH
为了解决KD-Tree的问题，提出Bounding Volume Hierarchy（BVH）。
从物体划分角度对场景预处理。（Object Partitions）
（1）BVH对场景预处理
解决问题1：不用考虑三角形与格子求交，只需更新包围盒。
解决问题2：一个物体只存储在一个叶子节点里。
（2）如何划分物体？
1、总是沿着最长的轴进行场景划分。
2、取中间物体进行划分。
优势：均匀，构成最小深度的树。
3）总结
