DBVT

好的，我来详细介绍 Bullet Physics 库中 DBVT (Dynamic Bounding Volume Hierarchy) 的构建和更新过程。

Bullet 的 DBVT（在代码中通常是 btDbvtBroadphase 的核心）是一种为动态环境高度优化的二叉树结构，其设计目标是实现 $O (lo g N)$ 复杂度的快速更新，而不是像静态 BVH 那样追求初始构建时的全局最优。

🏗️ 1. DBVT 的构建策略：贪婪插入

DBVT 的构建是增量式 (Incremental) 的，意味着物体是逐个插入到树中的，而不是一次性进行全局分割。这使得它的构建过程和更新过程本质上是相同的 “插入操作”。

DBVT 的构建策略不使用中位数分割，因为它的计算成本过高 ( $O (N)$ )。它采用的是一种贪婪的自顶向下插入策略，以确保每次插入操作的局部最优性。

起始点： 当一个新的刚体需要加入 DBVT 或一个移动的物体需要更新时，它的新 AABB $A_{n e w}$ 被传递给插入算法。
遍历与评估： 算法从树的根节点开始向下遍历，在每个内部节点 $P$ 处，它会评估将 $A_{n e w}$ 插入到左子节点 $L$ 或右子节点 $R$ 的成本。
成本函数：成本被定义为新 AABB 导致的父节点 AABB 的体积增量。算法选择成本最小的路径继续向下：

$Cost (L) = Volume (A_{L} \cup A_{n e w}) - Volume (A_{L})$

$Cost (R) = Volume (A_{R} \cup A_{n e w}) - Volume (A_{R})$

其中， $Volume (A)$ 是 AABB 的体积， $Volume (A \cup B)$ 是同时包围 AABB $A$ 和 $B$ 的最小 AABB 的体积。
贪婪选择： 算法总是选择 $min (Cost (L), Cost (R))$ 的分支进行递归。
创建新节点： 当遍历到达一个叶子节点 $L_{o l d}$ 时，它执行以下操作：
- $L_{o l d}$ 被替换为一个新的内部节点 $P_{n e w}$ 。
- $P_{n e w}$ 的两个子节点是 $L_{o l d}$ 和新的叶子节点 $L_{n e w}$ （包含 $A_{n e w}$ ）。

这种策略牺牲了初始构建的全局最优性和完美平衡性，以换取 $O (lo g N)$ 级别的快速插入/更新，这对动态物理模拟至关重要。

DBVT 的更新机制是为了处理不断移动的刚体，它的目标是延迟更新，并在必要时进行高效重构。

这是 DBVT 应对动态性的关键优化。

扩展 AABB：每个叶子节点（代表一个刚体 $o bj$ ）的 AABB $A_{o bj}$ 都会被扩展一个预设的边界 $ϵ$ （“增肥因子”），形成更大的增肥 AABB $A_{f a t}$ 。

$A_{f a t} = Expand (A_{o bj}, ϵ)$
更新条件： 只有当刚体移动到其增肥 AABB $A_{f a t}$ 之外时，才需要触发树的更新。
作用： 大多数物体的微小移动都不会导致 $A_{o bj}$ 移出 $A_{f a t}$ ，从而避免了频繁的树结构修改，节省了大量的计算资源。

一旦物体移动触发了更新（即 $A_{o bj}$ 超出 $A_{f a t}$ ），Bullet 执行以下操作：

在重新插入叶子节点后：

传统的 BVH 依赖 树旋转 来维持平衡，但 Bullet 的 DBVT 通常不依赖显式的树旋转。

隐式平衡： DBVT 的平衡性主要通过贪婪插入策略和增量更新来维护。高效的插入策略旨在找到局部最优，这有助于防止树结构在局部变得过于倾斜。
快速重建 vs. 旋转： 在动态环境中，进行 $O (lo g N)$ 的移除和重新插入操作通常比复杂的旋转操作更稳定、更易实现，且能够更好地结合体积启发式来维持几何紧凑性。

总结来说，Bullet 的 DBVT 是一个为 实时性 优化的数据结构，它通过 增肥 AABBs 减少更新频率，通过 最小体积增长启发式 保证更新的高效性和几何紧凑性。