我目前正在为物理引擎（爱好项目）编写 KDTree。
KDTree 不包含点。相反，它包含 Axis Aligned 边界框，用于绑定环境中的不同对象。
我的问题是决定如何在 KDTree 节点满时拆分它们。我正在尝试两种方法：
方法1：始终在最大轴上将节点精确地分成两半。
方法2：找到包含对象的节点区域。拆分平面上的节点，该平面在其最大轴上将该区域分成两半。示例 - 如果所有对象都集中在节点的底部，则它会纵向拆分，从而将底部一分为二。
所以我在这里寻找的是一种更好的方法来分割我的 KD-Tree 节点。考虑到这将是一个物理引擎，决策需要足够简单以便实时做出。
“表面积启发式”（SAH）被认为是构建 kd 树的最佳分割方法，至少在光线追踪社区内如此。这个想法是添加平面，以便两个子空间的表面积（由每个子空间中的对象数量加权）相等。
关于这个主题的一个很好的参考是Ingo Wald 的论文，特别是第 7.3 章，“高质量 BSP 构建”，它比我更好地解释了 SAH。
目前我找不到好的链接，但您应该四处寻找有关“分箱”SAH 的论文，这是真正的 SAH 的近似值，但速度要快得多。
话虽如此，边界体积层次结构 (BVH) 又名 AABB 树，如今似乎比 kd-trees 更受欢迎。同样，Ingo Wald 的发布页面是一个很好的起点，可能是“基于 SAH 的边界体积层次结构的快速构建”论文，尽管我已经有一段时间没有阅读它了。
OMPF论坛也是讨论这类事情的好地方。
希望有帮助。祝你好运！
当然，对于以大量移动几何为前提的物理引擎，bvh 可能是更好的选择，它们的遍历速度不那么快，但构建速度要快得多，并且更容易在每帧上进行改装/重组框架基础，而且不需要完整的重建，每一帧（可以在一系列框架上并行完成，同时改装的 bvh 就足够了，再次参考 wald）。
物理学中的一个例外可能是当您处理没有体积的实体（例如粒子或光子）时，kd 树的构建由于您不需要解析单个基元的边界而被简化. 这真的取决于应用程序。一个好的物理引擎应该使用空间加速结构的平衡组合，通常的做法是用浅八叉树解决更广泛的相位划分，然后用另一种更适合您所做工作性质的方案扩展叶节点，BSP 非常适合静态几何，尤其是在 2d 中，当结构没有改变时，最好的办法是尝试尽可能多的不同方案和结构，并了解它们如何以及何时工作得最好。