【包围体层次结构】- 空间加速方法BVH (Bounding Volume Hierarchies)

BV（Bounding Volume）是包含一组物体的空间体，它比其所包含的几何物体形状要简单的多，所以对它进行碰撞检测速度比直接与物体本身求相交更快。常见的包围体有轴对齐包围盒、球体包围盒、OBB。

BVH是一种以物体BV为基础进行划分的结构。它由根节点、内部节点和叶子节点组成。其中叶子节点存放物体，每个非叶子节点都有包围体，父节点可以把子节点包围起来。

每个非叶子节点的包围体大小，是它所包含的所有物体的包围体的总和，所以它在空间上比较紧凑，非常适用于需要大量求相交测试的应用场景，如光线追踪。

BVH树的建立

比较使用BVH的有BV有包围盒和包围球，我们以包围盒举例。

对于下图这个包含了一些图元的场景，如何建立BVH树呢？

1. 求出整个场景的包围盒作为根节点的包围盒，作为根节点的包围盒。
2. 以某种依据将图元划分为两组。
3. 分别求出2分成的两组图元的包围盒，并创建两个子节点，作为他们的包围盒。

4. 对新分出来的两组图元，递归执行2和3。

5. 直到每个图元组只有1个或2个图元组，可以直接将他们分别放到左右叶子结点中。

通过上面建立这个BVH的过程，可以看到图元划分的方式不同，会导致同一层的两个节点的包围盒会有重叠。所以如何划分图元很重要，它会影响节点的包围盒大小，进而影响后续我们遍历BVH的速度。

下面来谈一下如何划分图元更好。

在这种情况下，包围盒的y轴的长度大于x轴的长度，所以选取垂直y轴的平面划分，可以使划分后的包围盒相对于垂直x轴的划分较小。

那这个平面的位置应该在选哪儿呢？

看下图的三种情况，其中蓝线表示划分的平面。

对于(a)情况，取包围盒中心是一种比较好的划分，划分后的包围盒没有交叉，非常紧凑。

对于(b)情况，取包围盒中心进行划分并不好，包围盒相对于(a)情况大了很多，且有交叉，会造成遍历BVH树性能的浪费。

对于(c)情况，将物体沿划分轴的位置排序，以中位数的物体作为划分依据，两部分的包围盒不相交，是很好的划分方式。

以中位数物体的位置作为划分依据，是比较通用的做法。

建立好BVH树之后，遍历比较简单，从根节点递归求相交就可以找到，相交的那些物体。

表面积启发式划分方法SAH（The Surface Area Heuristic）

虽然上面介绍的划分方法比较实用了，但是以包围盒中心划分会出现一颗子树的物体较多，另一颗子树的问题很少的情况，当较多物体出现重叠的时候，以中位数物体划分也会造成遍历时需要跟两棵子树相交。

我们想做的是找到一个更好的划分方法，让遍历节点和与物体求交的速度更快。

SAH的思想是这样的，某种划分，将图元分为A,B两组，与A,B两组求相交的总消耗分别为

$\sum_{n=1}^{N_A}t_{isect}(a_i)$，$\sum_{n=1}^{N_B}t_{isect}(b_i)$，

其中$a_i$，$b_i$是A、B两组的第i个物体。

这样可以建立划分的模型，

$c(A, B)= t_{trav} + p_A\sum_{n=1}^{N_A}t_{isect}(a_i) + p_B\sum_{n=1}^{N_B}t_{isect}(b_i)$

查询BVH以下几部分：

1. 遍历非叶子节点，决定往那颗子树遍历的开销，记为$t_{trav}$。
2. 遍历左右两个子树的概率分别为 $p_A$ ，$p_B$。

这样对物体尝试各种划分方法，并求出相应的 $c(A, B)$ ，开销最小的方法就是最佳的划分方法。

接下来我们把这个公式简化，便于求解。

$t_{trav}$ 是遍历非叶子节点，决定往那颗子树遍历的开销，是固定开销，各种划分方法的 $t_{trav}$ 都是相等的，直接忽略即可。

与每个图元求交的开销也可以认为是固定的，所以$\sum_{n=1}^{N}t_{isect}$可以简化为图片数量。

那 $p_A$ ，$p_B$怎么估计呢？ 我们知道，一个物体的表面积越大，那么与射线相交的概率就越大。所以我们用包围盒的表面积估计 $p_A$ ，$p_B$。假设划分前的包围盒的表面积为 $S_C$ ，划分后两组图片的包围盒为 $S_A$ ， $S_B$ 。那么可以估计。

$p_A = \frac{S_A}{S_C}$ , $p_B = \frac{S_B}{S_C}$

简化的模型可以写成下面这种形式。

$c(A, B)= \frac{(S_A * count(A) + p_B * count(B))}{S_C}$

接下来选出所有物体的总包围盒的最长轴，然后将这个轴等距离分为N份，可以得到N-1个划分平面。然后求出N-1种划分中开销最小的划分，即为最优的划分方法。

还有一些提升性能的方式，在这里简单提一下。

同一棵子树下的物体是相邻的，在遍历判断是否相交的时候，有较大的可能性临近的子树都需要判断是否相交，这样的话将图元组织到一起能够提高cache的命中率。具体做法是根据建BVH树的创建叶子节点的顺序，把叶子节点里物体加到一个数组里，叶子节点记下图元在这个数组里的索引。遍历BVH树的时候用索引访问这个数组。

上面只提到了让图元更紧凑，方面提高cache命中率。当然也可以使节点更紧凑。个人的理解，这就是LBVH（Linear Bounding Volume Hierarchies）所做的事，按照莫顿码的规律排列节点。之后有精力再详细学习。

参考

[1] pbr-book.org/3ed-2018/Pr…