小编sha*_*eve的帖子

我目前正在为物理引擎(Hobby项目)编写KDTree.

KDTree不包含点数.相反,它包含Axis Aligned边界框,它绑定环境中的不同对象.

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

方法1:始终将节点在最大轴上精确地分成两半.

• 这具有相当均匀间隔的树的优点.
• 大缺点:如果对象集中在节点的小区域中,则将创建冗余子分区.这是因为所有卷都被分成两半.

方法2:查找包含对象的节点区域.拆分平面上的节点,该节点将该区域在其最大轴上分成两半.示例 - 如果所有对象都集中在节点的底部,则它按长度方式分割,从而将底部分成两部分.

• 这解决了上述方法的问题
• 索引存在于同一平面(例如地形)上的内容时,会创建长而窄的节点.如果我稍后要添加一些不在同一平面上的其他对象,则这些细长节点提供非常差的索引.

所以我在这里寻找的是分割我的KD-Tree节点的更好方法.考虑到这将是一个物理引擎,决策需要足够简单,以便实时进行.