计算机图形学中BVH的构建和动态修改

计算机图形学中BVH的构建和动态修改摘要：光线追踪中射线与物体的求交运算需要线性的时间复杂度，而可交互粒子系统中的碰撞检测更是达到了平方级的时间复杂度，只是缓存友好是不够的，因此它们都需要用空间结构来优化，而一种很好的树形结构就是BVH（Boundingvolumehierarchy）。BVH的核心思想就是用体积略大而几何特征简单的包围盒来近似描述复杂的几何对象，并且这种包围盒是嵌套的，只需要对包围盒进行进一步的相交测试，就可以越来越逼近实际对象，从而达到加速的目的。关键词：BVH；加速结构；光线追踪；碰撞检测；射线检测一、基本结构BVH是一个二叉树，它每个节点中的基本元素是包围盒，只需存储两个向量即下界和上界作为成员，即可表示一个包围盒。合并两个包围盒只需对二者的下界取最小，上界取最大，即可得到一个新的包围盒。对于每个需要添加进BVH的物体，我们需要用击中点坐标和法线向量来标识它。执行光线追踪的最简单方法是逐个检查每个物体并求解，如果物体数量很少那么这样是可行的，但如果物体形状很复杂或物体数量很多，那么在检测这些复杂的物体之前，先检测射线是否与包围盒相交是很值得的。包围盒的检测会比物体的检测快很多，因为我们不需要知道击中点坐标或法线向量，我们只需要知道光线是否与包围盒重叠。我们可以尝试将更多的物体分组到更大的包围盒内，这样就可以在很多情况下跳过整个子树。我们可以很轻易获得BVH中每个包围盒的表面积，因为它就是这个包围盒的上界减去下界所得向量的模长。一旦使用了不止一层的包围盒，就必须要制作一整棵二叉树，这就是一个BVH。不只可以用包围盒表示树中的每个节点，其他形状也是可以的，例如包围球或包围椭球。这棵树由内部节点和叶节点组成，叶节点中存储了具体的碰撞物体，而内部节点中只存储了包围盒，内部节点只是为了加速查询而存在，注意在实际应用中我们常常将需要检测的静态物体和动态物体区分开。BVH不仅可用在光线追踪和射线检测中，还常用于加速碰撞检测，这就需要先对BVH进行构建，再对划分好的BVH进行动态修改，于是接下来我们就来研究如何对BVH进行构建及动态修改。二、BVH的构建方式有很多种构建二叉树的方式，而BVH有它独特的构建方式。对于BVH来说，每层节点之间的相对顺序是完全没有任何影响的的。我们可以在任何节点处交换它的左右子树，所得的BVH与原始BVH是完全等价的。我们想要使用一种表面积启发式的方法来构建BVH，而这首先需要提出一种判断节点是否足够好的衡量标准，也就是权重。同一组叶节点可以构造出很多种不同的BVH，这些BVH中所有叶节点的表面积均相同，根节点的表面积也相同，只有内部节点的表面积不同，而这个不同就是评判构建出来的BVH是否足够好的关键标准。这里我们基于的假设是，对于光线求交来说，包围盒表面积越大，与它碰撞的概率就越大。从传播消耗的角度看，这是完全正确的。除此之外，该节点下的子节点数量越多，遍历该节点的传播消耗也一定越大，因为遍历到它的次数很可能就越多，计算次数也就越多。表面积影响的是子节点被遍历到的概率，而每个节点下模型的三角形个数就是要求交的次数。但是在构建BVH前，我们并不知道某个节点的子节点数量，因为很有可能不会划分到每个叶节点都只有一个物体这么细微的程度，所以这里我们实际使用的是当前节点所包含的物体数量而不是子节点数量，用它来分别计算传播消耗和碰撞概率，这两者分别用包含的物体数量和包围盒表面积表示，而每个节点的消耗就表示为这两者的乘积。一棵BVH的总权重是所有节点的权重之和，表示为对传播消耗与碰撞概率的乘积求和。一种最直接的做法是，首先根据莫顿码或快速选择算法对三个坐标轴之一进行排序，然后遍历BVH中的每个节点，计算将当前节点划分为两个子节点所产生的权重。当每个节点都有一个权重之后，找到使划分后两子节点的权重和最小的划分方式，如果划分之后的权重仍大于划分之前的，那么就不继续划分了，最后递归这个过程直至划分完成即可。注意这是一个贪婪算法，并不能保证全局最小。光线击中物体的概率与物体的表面积成正比，使用表面积函数，我们可以计算任何BVH的总权重。到底是继续划分还是直接遍历求交，需要分别计算划分后再遍历的效率和直接遍历的效率，也可以选不同的划分位置，按两个子节点被选择的概率计算效率并比较来找出最佳划分点，因为当评估BVH的遍历效率时，每个个节点下子节点的层数只是原因之一，还有个必须考量的因素是每个节点下左右子树的包围盒的重叠程度。在实际计算时需要找到光线与每个包围盒的交点中最近的交点，而且在没有额外的信息知道两个子节点是否重叠的情况下，也需要分别计算与两个子节点的交点的来找出最近交点。但是实际上，可以有一些优化操作在里面，比如在构建BVH时，可以用二进制位来标记一个包围盒是否与其他同级别包围盒重叠，对于没有重叠的包围盒，第一个碰到的，必然是最近的。另外，很多时候是不需要找到最近交点的，只需要判断是否有遮挡就可以了，比如阴影投射光线，这时连额外的信息都不需要了。三、BVH的动态修改动态修改包括对象移动、对象创建和对象销毁，方法仍是表面积启发式，所以仍需要一种计算插入节点的成本的方法，其中一种方法是新节点的表面积即直接成本加上所有祖先节点增加的表面积即继承成本，这就是新添加到树中的表面积，每个节点的成本是直接成本和继承成本之和。树中的每个叶节点都是新节点的潜在父节点。每个选择都会为树添加不同的表面积。我们想找到为树增加最少表面积的潜在父节点，不幸的是，评估每个潜在父节点的成本是昂贵的，所以采用分支定界算法，通过递归的方法使全局搜索更快，并跳过不可能更好的子树。我们还想确定探索该节点的子节点是否是有必要的，即是否应继续探索该节点的子树？该节点的子节点的下限是该节点的表面积加上继承成本。如果该节点的成本优于最佳成本，则更新最佳成本。如果子树的下限成本低于最佳成本，那么值得探索这些子树并将它们推入优先队列。否则可以从搜索中修剪以该节点为根的整个子树，这极大地提高了性能。为了在选择了潜在父节点后修改树的所有细节，必须依次处理边缘情况，处理新节点的创建和连接，之后还要调整新叶祖先的包围盒，这叫做改装。排好序的输入会破坏BVH。想象一下，我们连续有几个对象，它们按排好序的顺序插入到树中，这会导致BVH变成链表。在这种情况下，增量无法提供良好的树。老实说，很难找到一个不会失败的合理成本指标，所以需要树旋转，即重新排列树以降低成本。树旋转一般用于二叉平衡树，但这里它们还可用于限制体积层次结构，以减少BVH的表面积并减轻排序输入带来的问题，所以可使用树旋转来解决BVH的顺序输入问题。这是一个局部操作，可以在重新改装祖先包围盒时优化树。参考文献：•J.Goldsmith(1987)-AutomaticCreationofObjectHierarchies•S.Omohundro(1989)-FiveBalltreeConstructionAlgorithms•A.Kensler(2008)-TreeRotationsfor