games101 ray-tracing加速结构改进 BVH+SAH

发布时间 2023-06-15 11:17:04作者: ahab1016

加速结构改进 BVH + SAH

两者都是空间划分算法,使用这些算法是为了节省光线逐个与包围盒做交浪费的性能。

 

Bounding Volume Hierarchy

  BVH是基于图元(Primitive)的空间划分索引结构,划分物体再分别求他们的包围盒,这样就避免了一个同样的物体出现在不同的格子里。但问题在于对空间的划分不够严格,包围盒有可能相交。这样做实际问题也不大。使用bvh构建树,叶节点是对单个物体构建的包围盒。

做划分的方法:

  1. 沿着长轴做划分 ,以及选定一条轴以后,沿着这条轴选择第中位数个三角形做划分(选择中位数三角形做划分能保证树的叶子节点分布平衡,分布平衡的好处是根节点到叶子节点的平均长度短,实际结构基础知识了)。沿轴的排序通过重心来排序,但并不需要真做排序只需要使用快速选择的思想求出第N大的点就够了(快排的思想)。划分到一个AABB当中有5个点就差不多了。

  虽然是说划分到AABB当中有5个点就差不多了,但是实际操作当中是直接划分到每个包围盒中有一个物体了。(更彻底的空间换时间了)

    2. 沿着长轴做划分 ,以及选定一条轴以后,沿着这条轴选择中间位置做划分。

-----------------------------------------------------------------------------------------

Surface Area Heuristic,SAH

BVH的问题在于图元位置分布不均匀时,上面两种划分效果很差。所以提出与