内容-加速结构

加速寻找相交点

Uniform Spatial Partitions （Grids）

进一步细分包围盒，形成一个加速结构
假设：

  • 光线于盒子求交是十分快的
  • 光线与物体求交是十分慢的

    预处理 Build Acceleration Grid

    image.png

    光线追踪 Ray-Scene Intersection

    image.png
    先光栅化一条线，知道光线与哪些格子相交。
    然后对于相交且有物体的格子，光线与其物体进行三角形的光线追踪计算，判断是否有交点

Grid Resolution 与 算法效率

image.png
一个经验平衡法去决定格子的划分大小

比较适用与场景中物体很多而且大小和分布比较均匀的情况
image.png
不适用于“Teapot in a stadium”的情况 大场景，分布不均匀
实际上很多GPU算法还是用的格子

Spatial Partitions

格子虽然很好用，但是任然有很多不足，接下来就是对这些不足进行一个优化，让划分与物体的分布更加适配
image.png

  • Oct-Tree 八叉树，不好在于根维度相关，三维是8 二维是4 一维是2
  • KD-Tree k维树 ，与八叉树很类似，但是它每次找到一个格子，只沿着一个轴砍一刀，砍成两半。水平和竖直还有z轴交替划分，让划分基本是一个均匀的
  • BSP-Tree 二叉空间分割树，每次选一个方向把树砍开，根KD-Tree类似。在维度高的时候不好计算

KD-Tree

在做光线追踪之前建立好的一个加速结构
image.png

  • 所有物体只存在于叶子节点上
  • 用前序遍历进行区域遍历并求交，父节点相当于是包围盒的包围盒，还是那个逻辑（如果包围盒都没有交点，那么里面的物体更加没有交点）

存在的问题：

  1. 子包围盒如何知道它与哪些三角形有交集（很难写对）

可能出现的案例：三角形的三个顶点都不在盒子里，但是与盒子是相交的。

  1. 物体可能存在于多个盒子里，比如图上的3 4 5

冗余的储存

因此，也是现在用的越来越少

Object Partitions & Bounding Volume Hierarchy （BVH）

如果划分空间有诸多问题，那么可以划分物体
现在几乎都是用BVH，它解决了KD-Tree的两个问题

他可以说的KD-Tree的升级，因为BVH的划分方式与其是一致的，只是

  • BVH划分的是物体
  • KD-Tree划分的是空间

因此首先就解决了同一个物体出现在不同的划分结构中的问题，另外包围盒也很好计算
image.png
但是它引起了另外的问题：包围盒空间是可能相交的

构建BVH

要想尽可能划分好，那就是让重叠区域尽可能小
image.png
如何划分来构建BVH，也就是如何建立一颗尽可能平衡的树（平衡的树最大深度k小，平均搜索次数小）：
快速选择算法，找到第k大的数
image.png
如果物体动了，那就要重新来划分BVH了

查找BVH过程

递归实现
image.png

空间划分 VS 物体划分

image.png