KD树分裂
我目前正在为物理引擎（业余爱好项目）编写 KDTree。
KDTree 不包含点。 相反，它包含轴对齐边界框，用于限制环境中的不同对象。
我的问题是决定当 KDTree 节点已满时如何拆分它们。 我正在尝试两种方法：
方法1：始终在最大轴上将节点精确地分成两半。
- 这样做的优点是树的间距相当均匀。
- 大缺点：如果对象集中在节点的小区域内，则会创建冗余的细分。这是因为所有卷都被正好分成两半。
方法2：查找包含对象的节点区域。分割平面上的节点，该节点在其最大轴上将该区域分成两半。示例 - 如果所有对象都集中在节点的底部，那么它会纵向分裂，从而将底部一分为二。
- 这解决了上述方法的问题
- 当对同一平面（例如地形）上存在的某些内容进行索引时，它会创建又长又窄的节点。如果我稍后要添加一些不在同一平面上的其他对象，这些拉长的节点会提供非常差的索引。
所以我在这里寻找的是一种更好的方法来分割我的 KD-Tree 节点。 考虑到这将是一个物理引擎，决策需要足够简单才能实时做出。
I am currently writing a KDTree for a physics engine (Hobby project).
The KDTree does not contain points.
Instead it contains Axis Aligned bounding boxes which bound the different objects in the environment.
My problem is deciding on how to split the KDTree nodes when they get full.
I am trying 2 methods:
Method1: Always split the node exactly in half on the biggest axis.
- This has the advantage of a pretty evenly spaced out tree.
- Big disadvantage: If objects are concentrated in small area of the node, redundant sub-divisions will be created. This is because all volumes are split exactly in half.
Method2: Find the area of the node which contains objects. Split the node on the plane which splits that area in half on it's biggest axis. Example - If all objects are concentrated on the bottom of the node then it split length-wise thereby dividing the bottom in two.
- This solves the problem with the method above
- When indexing something that exists on the same plane (terrain for example), it creates long and narrow nodes. If I am to add some other objects later which are not on the same plane, these elongated nodes provide very poor indexing.
So what I'm looking for here is a better way to split my KD-Tree node.
Considering that this is going to be a physics engine the decision needs to be simple enough to be made in real time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
“表面积启发式”（SAH）被认为是构建 kd 树的最佳分割方法，至少在光线追踪社区内如此。这个想法是添加平面，以便两个子空间的表面积（按每个子空间中的对象数量加权）相等。
关于这个主题的一个很好的参考是Ingo Wald 的论文，特别是章节7.3，“高质量 BSP 构建”，它比我更好地解释了 SAH。
我目前找不到好的链接，但您应该四处寻找有关“binned”SAH 的论文，它是真实 SAH 的近似值，但速度要快得多。
话虽如此，边界体积层次结构 (BVH) 又名 AABB 树，现在似乎比 kd 树更流行。同样，Ingo Wald 的出版物页面 是一个很好的起点，可能与“On fast Construction of SAH based Bounding Volume Hierarchies”论文，尽管我已经有一段时间没有阅读它了。
OMPF 论坛也是讨论此类问题的好地方。
希望有帮助。祝你好运！
The "surface area heuristic" (SAH) is considered the best splitting method for building kd-trees, at least within the raytracing community. The idea is to add the plane so that the surface areas of the two child spaces, weighted by the number of objexts in each child, are equal.
A good reference on the subject is Ingo Wald's thesis, in particular chapter 7.3, "High-quality BSP Construction", which explains SAH better than I can.
I can't find a good link at the moment, but you should look around for papers on "binned" SAH, which is an approximation to the true SAH but much faster.
All that being said, bounding-volume hierarchies (BVH) a.k.a. AABB trees, seem to be much more popular than kd-trees these days. Again, Ingo Wald's publication page is a good starting point, probably with the "On fast Construction of SAH based Bounding Volume Hierarchies" paper, although it's been a while since I read it.
The OMPF forums are also a good place to discuss these sorts of things.
Hope that helps. Good luck!
当然，对于以大量移动几何体为前提的物理引擎，bvh 可能是更好的选择，它们的遍历速度不那么快，但构建速度要快得多，并且更容易在每个帧上改装/重组框架基础上，并且通常不需要对每个框架进行完全重建（可以在一系列框架上并行完成，同时重新安装的 bvh 就足够了，再次参考 wald）。
物理学中的一个例外可能是，当您处理没有体积的实体（例如粒子或光子）时，由于您不需要解析单个图元的边界，因此简化了 kd 树的构建。这实际上取决于应用程序。一个好的物理引擎应该使用空间加速结构的平衡组合，通常的做法是使用浅八叉树来解决更广泛的相位划分，然后使用更适合您正在做的事情的性质的另一种方案来扩展叶节点，BSP 是理想的选择静态几何，特别是在二维中并且当结构不改变时，最好的办法是尝试尽可能多的不同方案和结构，并了解它们如何以及何时发挥最佳作用。
Certainly for a physics engine where the premise is lots of moving geometry, a bvh is probably the better choice, they don't traverse quite as quickly but they are much faster to build, and are much easier to refit/restructure on a frame per frame basis, and offen don't need a complete rebuild, every frame (something that can be done in parallel over a series of frames while the refitted bvh suffices in the meantime, again, refer to wald).
An exception to this in physics could be when you're dealing with entities that have no volume such as particles or photons, the building of the kd tree is simplified by the fact that you don't need to resolve the bounds of the individual primitive. It really depends on the application. A good physics engine should use a balanced combination of spatial acceleration structures, it's common practise to resolve broader phase partitioning with say a shallow octree then extend the leaf nodes with another scheme that better fits the nature of what you are doing, BSPs are ideal for static geometry, especially in 2d and when the structure isn't changing, the best thing to do is experiment with as many different schemes and structures and get a feel for how and when they work best.