我目前正在写一KDTree的物理引擎（业余爱好项目）。

I am currently writing a KDTree for a physics engine (Hobby project).

的KDTree不包含分。 相反，它包含轴对齐包围其中结合了不同的对象在环境中拖曳。

The KDTree does not contain points. Instead it contains Axis Aligned bounding boxes which bound the different objects in the environment.

我的问题是决定如何分割KDTree节点，当他们得到充分的。 我尝试2种方法：

My problem is deciding on how to split the KDTree nodes when they get full. I am trying 2 methods:

方法1：总是在最大轴分割节点恰好一半

Method1: Always split the node exactly in half on the biggest axis.

方法2：发现包含对象节点的区域。各执其拆分该区域的一半就可以了最大的轴平面上的节点。例如： - 如果所有对象都集中在节点然后将它分割长度方向从而将底部两个的底部

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.

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

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.

推荐答案

表面区域启发式（SAH）被认为是最好的方法分割建筑KD树，至少在光线追踪社区内。这样做是为了增加平面，使得两个子空间的表面区域，通过在每个子objexts数加权，是相等的。

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.

关于这个问题的一个很好的参考是英戈沃尔德的论文，特别是第7.3， 高品质的BSP建设，这也解释了SAH比我好的人。

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.

我找不到此刻一个很好的链接，但你应该主动寻找的分级SAH，这是一个近似真实的SAH，但速度要快得多。

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.

之所以这么说，边界体积层次（BVH）又名AABB树，似乎要比KD树更受追捧。此外，英戈沃尔德的出版物页面是一个很好的起点，很可能与在快速建设蛛网膜下腔出血基于包围盒层次结构的论文，尽管它已经有一段时间，因为我读了它。

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.

href="http://ompf.org/forum/"> OMPF论坛也是一个好地方来讨论这些事情的