游戏场景管理（六）BVH

由 demi 提交于周一, 8 二月 2021 - 11:39

作者：隐士低手

BVH和空间划分技术不同，它并不是通过切割空间来管理场景中的物件。它是通过将物体分堆，然后在其上面包裹一层BV，达到管理场景的目的。树的根节点是一个能够包裹全部物体的BV，而树的叶子节点可能只是一个物件的BV，如下图：

BV可以选择AABB，OBB，包围球等等，往往包裹性越好的BV，相交测试越复杂，但是包裹性好可以减少相交测试的次数。这个世界有阴就有阳，计算机的二进制码也是0和1，我们生存的世界是不是也是一个虚拟的程序呢，哈哈跑题了。

父节点的包围体无需包裹子节点的包围体，但是需要包裹所有物体的BV。换句话说就是父节点无需包裹中间节点的BV，但要能包裹所有物体。

我们从树根节点开始遍历每个子节点，如果节点的BV不在视锥体中或者没有发生碰撞，那么这个节点下的所有物体都可以快速被剔除。

BVH和BSP有点像，太过灵活，虽然原理很简单，但是如何建树是一个比较头疼的问题。建树困难也就意味着这个技术不适合运行时期动态更新。BVH和BSP一样往往是在非运行时期对静态物体进行预计算。

我们不能盲目的构建一棵BVH，先把树的期望特征列出来，以这些特征为目标构建BVH。</li>
<ul><li>子树中的节点应该彼此靠近，随着深度的增加节点间应该彼此更加紧凑。</li>
<li>层次结构中的节点应该是最小的包围体。</li>
<li>全部包围体体积之和应该保持最小。</li>
<li>应谨慎处理根节点附件的节点，与深层节点相比，删除根节点附近的节点往往意味着移除更多的物体对象。</li>
<li>兄弟节点间的相交体空间应该保持最小。</li>
<li>层次结构应该尽量保持平衡树</li>
<li>最坏情况下的查询时间不应超出评价查询时间太多(防止造成游戏帧数不平滑)</li>
<li>虽然是预计算，但也要考虑预计算的时间，每次更改场景都需要重新计算，计算时间太长很容易影响工作效率。</li>
<li>BVH应尽量控制内存的使用</li></ul>

有一个性能测试公式揭示了碰撞性能的消耗：

T = NvCv + NpCp + NuCu + Co

Nv是相交测试BV的数量，Cv是每次相交测试的消耗，Np是相交测试图元的数量，Cp是每次相交测试的消耗，Nu是需要更新节点的数量，Cu是更新节点的消耗，Co是一个常量消耗。

我们需要寻找一个折衷的方案来进行碰撞检测，写一个物理库不难，写一个高效的物理库很难。

树的构建策略

BVH可以自定向下构建，也可以自底向上构建，也可以插入的方式进行构建如下图：

自顶向下构建容易，但是通常不是最佳树。

自底向上构建复杂，但是可以获得最佳树。

插入构建，可以实现运行时更新，但是该方案目前研究的比较少。

具体实现细节不写了，这个需要具体问题具体分析了。

版权声明：本文为CSDN博主（隐士低手）原创文章，遵循<a href="http://creativecommons.org/licenses/by-sa/4.0/" target="_blank" rel="noopener"> CC 4.0 BY-SA </a>版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/liran2019/article/details/107093952