KDTree分裂

Question

我目前正在为一个物理引擎(霍比项目)编写一个KDTree。

KDTree不包含点。相反，它包含了Axis对齐边界框，它们绑定了环境中的不同对象。

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

Method1:总是在最大轴上精确地将节点分成两半。

• 这有一个优势，一棵相当均匀的树。
• 大缺点:如果对象集中在节点的小区域，就会产生冗余的子分区。这是因为所有的卷都被分割成两半。

Method2:查找包含对象的节点区域。将平面上的节点分开，在其最大轴上将该区域分成两半。例如，如果所有的对象都集中在节点的底部，那么它就会将长度分开，从而将底部分成两部分。

• 这解决了上述方法的问题。
• 当索引在同一平面上存在的东西(例如地形)时，它会创建长而窄的节点。如果以后我要添加一些不在同一平面上的其他对象，那么这些拉长的节点提供了非常糟糕的索引。

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

Answer 1

“表面积启发式”(SAH)被认为是建造kd-树的最佳分割方法，至少在光线跟踪社区中是如此。这样做的目的是增加平面，使两个子空间的表面积，按每个子空间中的objexts数加权，是相等的。

关于这一主题的一个很好的参考是英戈·沃尔德的论文，特别是第7.3章，“高质量的BSP建设”，它比我更好地解释了SAH。

我现在找不到一个很好的链接，但是你应该四处看看关于“二进制”SAH的论文，这是一个近似于真正的SAH，但要快得多。

所有这一切，边界卷层次结构(BVH) a.k.a。AABB树，现在似乎比kd树更受欢迎。再说一遍，英戈·沃尔德出版网页是一个很好的起点，可能是“基于SAH的快速构建的包围卷层次结构”的论文，尽管我已经有一段时间没有读过它了。

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

希望这能有所帮助。祝好运!

Answer 2

当然，对于物理引擎来说，前提是大量的移动几何，bvh可能是更好的选择，它们的遍历速度不太快，但构建起来要快得多，而且在每帧的基础上进行重构/重构要容易得多，而且每个框架都不需要完全重建，每个框架都可以并行完成(一些可以在一系列帧上并行完成的操作，同时，重新改装的bvh就足够了，请参见wald)。

这在物理学中的一个例外是，当你处理没有体积的实体时，比如粒子或光子，kd树的构建就简化了，因为你不需要解析单个原语的边界。这取决于应用程序。一个好的物理引擎应该使用空间加速结构的平衡组合，通常的做法是用浅层八叉树来解决更广泛的相位划分问题，然后用另一种方案扩展叶节点，这个方案更适合你正在做的事情，BSP是静态几何的理想选择，特别是在2d，当结构不发生变化时，最好的做法是试验尽可能多的不同方案和结构，并了解它们如何和什么时候工作得最好。