我目前正在为物理引擎（Hobby项目）编写KDTree。

KDTree不包含点。取而代之的是，它包含“轴对齐”边界框，该边界框对环境中的不同对象进行边界。

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

方法1：始终将节点在最大轴上精确地一分为二。

• 这样的好处是树的间距相当均匀。
• 很大的缺点：如果对象集中在节点的较小区域中，则会创建多余的细分。这是因为所有卷都被精确地分成两半。

方法2：查找包含对象的节点的区域。在平面上拆分节点，该节点在最大轴上将该区域拆分为一半。示例-
如果所有对象都集中在节点的底部，则它将沿长度方向拆分，从而将底部一分为二。

• 这解决了以上方法的问题
• 当索引同一平面上存在的某物（例如地形）时，它将创建长而窄的节点。如果以后要添加其他不在同一平面上的其他对象，则这些拉长的节点将提供非常差的索引。

因此，我在这里寻找的是拆分KD-Tree节点的更好方法。考虑到这将成为物理引擎，因此决策必须足够简单以实时进行。