C# 中的动态边界体积层次结构。

下载

• 从 GitHub 下载 ssBVH 实现源代码

引言

在本文中，我们将快速回顾三维空间划分，解释为什么边界体积层次结构在三维空间划分应用（如三维游戏和光线追踪）中越来越受欢迎。然后，我们将展示一个可重用的、公共领域许可的 C# BVH 实现，该实现使用增量树重新拟合和旋转来快速处理增量更新，如 [1. kopta] 中所述。

在我们的示例中，BVH 允许 CPU 快速确定场景中 40,000 颗小行星中的哪一颗被用户点击。当鼠标点击时，一道光线从相机投射到场景中，我们不是将光线与每一颗小行星进行测试，而是遍历 BVH 包含的体积，只需执行 log2(N) 次比较来确定哪些小行星可能被点击，并只测试这些小行星。在这种情况下，log2(40,000)，或大约 15 次比较。

 

什么是空间划分？

大多数三维软件，无论是三维游戏、三维建模器还是其他形式的三维工具，在某个时候都将受益于空间划分系统。对于初学者来说，空间划分是我们用来讨论组织**占据体积**的对象的术语。这与排序结构不同，排序结构只能对没有体积的对象进行排序。

例如，将数字 1、4 和 7 升序排序很容易。但是，您将如何排序范围 1-10、1-5、2-3 和 3-7？

因为范围占据体积，所以没有一个普遍有用的简单“升序”排列方式。

空间划分是一组算法，用于组织在某些或所有维度上可以**相互重叠**的体积。空间划分不是像排序那样“排序”它们，而是划分和组织空间体积。这使得可以快速遍历划分的空间以回答几何查询。在三维空间划分的情况下，这通常意味着快速返回接触线、三角形或球体的三维对象。

划分空间

空间划分方案的关键区别之一在于它们如何划分空间。

许多三维空间划分算法，例如八叉树、kd 树和 BSP 树，使用平面三维平面来划分三维空间。分裂平面创建两个子体积，并且对象被排序到它们接触的子体积中。这种搜索效率很高，但是当对象重叠分裂边界时会带来挑战。

**排他性分割平面。**在预计算的 BSP 树中，会进行昂贵的预计算以确定有效的分割平面，当三角形穿过平面时，它们会在边界处被切割成更小的三角形。显然，这使得在计算平面后移动几何体变得相当昂贵。

**非排他性分割平面。**在八叉树或 kd 树的动态应用中，对象可以放置到它们接触的所有子体积中。这在移动对象时需要额外的工作，并且在遍历空间时需要额外的测试来处理重复的对象出现。

BVH 以不同的方式解决了这个问题，因为它不使用分割平面。相反，一个体积通过定义两个**可能重叠的子体积**来细分。这些体积可以用任何几何体定义，包括球体、椭球体、边界框或轴对齐边界框。为了使分割高效，包含的对象通过最小化包含这两个集合的子体积的表面积来分成两组，该表面积由表面积启发式 (SAH) 估算。

当以二进制方式使用时，如我们在实现中所做，每个体积恰好有两个子体积。因为子体积是任意的包围体积，遍历 BVH 意味着检查任何匹配体积的两个子体积。然而，增加的成本带来了更大的灵活性。子体积可能相距很远，更有效地划分空间，或者它们可能重叠。

子卷重叠的能力是 BVH 能够高效处理动态更新的主要原因。当物体仅短距离移动时，唯一需要的调整是快速调整其包围卷的边界。即使这些卷重叠，BVH 仍将正常运行，尽管效率略有降低。

当变化导致显著重叠时，BVH 树可能需要重组——这意味着对象可能需要移动到树中的不同位置，以使体积更有效。想象一下我们的小行星 BVH 树，然后想象一个物体穿过小行星场——我们希望移动的物体在穿过空间时“跳过”这些体积，而不是仅仅将其初始体积扩展以填充整个空间。

我们的实现通过使用树旋转（类似于二叉树旋转）来执行这种重组。然而，它们不是用于平衡树，而是用于在体积之间移动对象以降低总体 SAH 成本，有时通过使树不平衡。我们使用的方法由 Kopta 等人描述 [1]。

实例化 BVH

ssBVH<GO> 由它所持有的“游戏对象”类型（GO=游戏对象）参数化。为了处理任何对象类型而不引入类型或接口依赖于您的游戏对象，它需要一个适配器接口，SSBVHNodeAdaptor<GO>。源代码包含一个 SimpleScene 场景管理器对象的示例适配器实现。节点适配器需要做几件事：(a) 请求对象的中心，(b) 请求对象的包围球半径，以及 (c) 维护游戏对象与对象当前所在的 ssBVH 叶节点之间的映射。如果需要，可以将游戏对象到 ssBVHNode<GO> 叶节点的映射实现为从游戏对象到 ssBVHNode<GO> containingLeaf 的指针，或者您可以使用外部映射（例如哈希表）将游戏对象映射到 containingLeaf。

    public interface SSBVHNodeAdaptor<GO> {
        ssBVH<GO> BVH { get; }
        void setBVH(ssBVH<GO> bvh);

        Vector3 objectpos(GO obj);   // read the object position of a GO object
        float radius(GO obj);        // read the bounding sphere radius of a GO object

        void mapObjectToBVHLeaf(GO obj, ssBVHNode<GO> leaf);   // map a GO to a BVH leaf
        void unmapObject(GO obj);                              // unmap a GO from it's BVH leaf

        void checkMap(GO obj);                                 // assert that there is leaf mapping
        ssBVHNode<GO> getLeaf(GO obj);                         // retrieve the leaf mapping
    }

一旦为您的对象类型实现了适配器，就可以实例化 ssBVH。您可以一次性提供要批量添加的对象列表（这样更快），也可以一次添加一个。当对象添加到或从场景中移除时，您还需要将场景连接到调用 ssBVH<GO>.addObject(GO obj) 和 ssBVH<GO>.removeObject(GO obj)。以下是 BVH 如何使用 SimpleScene SSObject 实例化的示例。

if (addObjectInBulk) {
    // full BVH build
    worldBVH = new ssBVH<SSObject>(new SSObjectBVHNodeAdaptor(),mainScene.Objects);
} else {
    // incremental BVH build...
    worldBVH = new ssBVH<SSObject>(new SSObjectBVHNodeAdaptor(), new List<SSObject>());
    mainScene.objects.ForEach( o => worldBVH.addObject(o) );
}

处理动态更新

如果您希望 BVH 处理动态更新，那么每次您的对象移动时，您都需要在其 BVH 叶上调用更改通知函数：`ssBVHNode.refit_ObjectChanged(ssBVHNodeAdaptor adaptor, GO obj)`，这会快速且保守地扩展 BVH 以处理节点更新，但会牺牲效率。还提供了一个附加函数 `ssBVH.optimize()`，它尝试执行树旋转以优化 BVH，以应对对象移动足够远以创建低效体积重叠的情况。虽然 `optimize()` 非常快，但进行多次更改然后执行一次优化比在每次对象更新后进行优化更高效。例如，在游戏循环中，您每帧只调用 `optimize()` 一次。下面是一个游戏式更新循环的示例，包括 BVH 优化。

void OnUpdateFrame(FrameEventArgs e) {
   float fElapsedTimeMS = (float)(e.Time * 1000.0);

   // update 3d objects.. 

   mainScene.Update(fElapsedTimeMS);

   // restructure the BVH.. only once per frame
   worldBVH.optimize();
}

执行 BVH 加速查询

现在 BVH 已经构建并针对任何更新进行了优化，它可以加速对三维体积的查询。例如，要查找可能被射线击中的对象，ssBVH<GO>.traverse(SSRay) 返回一个与射线相交的 ssBVHNode<GO> 列表，这些节点又包含可以考虑进行相交的对象。当对象数量庞大时，这比测试场景中的所有对象效率高得多。例如，在一个包含 8 万个对象的测试中，traverseRay 通常只击中 100 个 BVH 节点，导致击中测试次数减少了 800 倍。

   List<ssBVHNode<GO>> hits = gameMode.worldBVH.traverse(ray);

ssBVH<GO>.traverse() 的其他重载提供了与轴对齐边界框 (AABB) 的相交，以及一个函数式遍历，其中可以提供任何匹配测试委托函数。

其他有用的工具

SimpleScene 还提供了示例代码，用于渲染 BVH 节点，并可选地高亮显示其中的一组节点。例如，此代码投射一条光线，然后使用提供的 SSBVHRender 类高亮显示光线触及的每个 BVH 节点。

   var hits = gameMode.worldBVH.traverseRay(ray);
   gameMode.worldBVH_visual.highlightNodes.Clear();
   Console.WriteLine("click hit {0} BVH nodes", hits.Count);
   foreach ( var hit in hits ) {                    
      gameMode.worldBVH_visual.highlightNodes.Add(hit);
   }

备注和未来工作

ssBVH 处理每个叶节点多个 GO 对象（LEAF_OBJ_MAX），但是，如果 BVH 每个叶节点只有一个节点，动态更新才能高效工作。未来的工作将包括分割和合并叶节点的代码，以允许当每个叶节点包含多个对象时，树重组能够有效工作。

参考文献

• [1] 动画场景中快速有效的 BVH 更新
• 空间划分：八叉树 vs BVH