algorithm - KD树 split

Question

我目前正在为物理引擎(爱好项目)编写 KDTree。

KDTree 不包含点。相反，它包含轴对齐边界框，用于绑定(bind)环境中的不同对象。

我的问题是决定当 KDTree 节点满时如何拆分它们。我正在尝试两种方法:

方法 1:始终在最大轴上将节点精确地分成两半。

• 这有一个非常均匀分布的树的优势。
• 最大的缺点:如果对象集中在节点的小区域，则会创建冗余的分割。这是因为所有卷都被精确地分成两半。

方法2:找到包含对象的节点区域。拆分平面上的节点，该节点将该区域在其最大轴上分成两半。示例 - 如果所有对象都集中在节点的底部，那么它将纵向 split ，从而将底部一分为二。

• 上面的方法解决了这个问题
• 当索引存在于同一平面上的事物(例如地形)时，它会创建长而窄的节点。如果我稍后要添加一些不在同一平面上的其他对象，这些细长的节点提供的索引非常差。

所以我在这里寻找的是一种更好的方法来拆分我的 KD-Tree 节点。考虑到这将是一个物理引擎，决策需要足够简单以便实时做出。

Answer 1

“表面积启发式”(SAH) 被认为是构建 kd 树的最佳 split 方法，至少在光线追踪社区内是这样。这个想法是添加平面，使两个子空间的表面积(由每个子空间中的对象数加权)相等。

关于这个主题的一个很好的引用是 Ingo Wald's thesis ，特别是第 7.3 章，“高质量 BSP 构建”，它比我能更好地解释 SAH。

目前我找不到合适的链接，但您应该四处寻找有关“binned”SAH 的论文，这是对真实 SAH 的近似，但速度要快得多。

综上所述，边界体积层次结构 (BVH) 又名 AABB 树，如今似乎比 kd 树更受欢迎。同样，Ingo Wald's publication page是一个很好的起点，可能是“基于 SAH 的边界体积层次结构的快速构建”论文，尽管我已经有一段时间没有阅读它了。

OMPF forums也是讨论这类事情的好地方。

希望对您有所帮助。祝你好运!