一、回顾

Whitted-Style Ray Tracing使用递归的方式，做光线追踪。光线在场景中任何一个地方都可能发生弹射，在任何一个交点都要计算着色和阴影，最后加权到像素值上的原理。

解释了光线和三角形求交的方法。但是光线与三角形求交比较复杂。

然后引入轴对齐包围盒(AABB)结构，利用光线和AABB的求交，来解决光线与三角形求交复杂问题。

二、加速结构

现在我们知道了光线和AABB求交。那我们怎么利用它，来加速光线与场景求交问题？
答：使用以下两个技术来实现：
1、Uniform grids（均匀格子）
2、Spatial partitions （空间划分）
以上的方式，是在做光线追踪之前，对场景的预处理操作。

1、Uniform grids

（1）对场景预处理

1627892730860-a7155ecc-e443-49c7-9937-6208554be23f.png

（2）光线追踪

1627892989493-080ae082-3eed-4a1a-ad0b-fc5cc67cd0bf.png

（3）格子怎么进行划分的选择？

1627893416873-c53efef8-ff20-455e-a7ca-b9924bafc43e.png

（4）Uniform grids的问题

1627893875004-b7e32720-7408-4db0-9a29-a7a458fe5d1c.png

2、Spatial partitions

由于Uniform grids的问题，提出Spatial partitions的解决方案。
思路：Uniform grids是均匀的划分。在物体稀疏的地方不需要用很多格子划分。
下图是一些空间划分算法，KD-Tree使用最多。

1627894090480-e306dd9b-16c9-4ce3-8528-27dbf76330eb.png

1）KD-Tree

（1）KD-Tree对场景预处理

1627894373003-3bdfd6fe-a1df-4947-b971-82a4b2dacc03.png

（2）KD-Tree光线追踪

1627894844265-83edc006-f345-429d-bd84-145dce401e7a.png

（3）KD-Tree空间划分的问题
问题1：KD-Tree的建立不容易，需考虑三角形与格子的求交。
问题2：KD-Tree的划分，一个物体可能和多个格子有交集，则一个物体就会存储在多个叶子节点里。

1627895213616-d7fae998-99f7-41e0-9761-1b9b57d65cfa.png

2）BVH

为了解决KD-Tree的问题，提出Bounding Volume Hierarchy（BVH）。
从物体划分角度对场景预处理。（Object Partitions）
（1）BVH对场景预处理

1627895742765-868d494c-2cf1-496f-818b-50facbe64ed9.png

解决问题1：不用考虑三角形与格子求交，只需更新包围盒。
解决问题2：一个物体只存储在一个叶子节点里。

（2）如何划分物体？
1、总是沿着最长的轴进行场景划分。
2、取中间物体进行划分。
优势：均匀，构成最小深度的树。

3）总结

1627896142418-c2f899de-19be-4774-b367-d1236b0fe48c.png