我目前正在为物理引擎(爱好项目)编写 KDTree。
KDTree 不包含点。相反,它包含 Axis Aligned 边界框,用于绑定环境中的不同对象。
我的问题是决定如何在 KDTree 节点满时拆分它们。我正在尝试两种方法:
方法1:始终在最大轴上将节点精确地分成两半。
- 这具有相当均匀间隔的树的优点。
- 大缺点:如果对象集中在节点的小范围内,会产生多余的细分。这是因为所有卷都被精确地分成两半。
方法2:找到包含对象的节点区域。拆分平面上的节点,该平面在其最大轴上将该区域分成两半。示例 - 如果所有对象都集中在节点的底部,则它会纵向拆分,从而将底部一分为二。
- 这解决了上面方法的问题
- 当索引存在于同一平面(例如地形)上的东西时,它会创建又长又窄的节点。如果稍后我要添加一些不在同一平面上的其他对象,这些细长节点提供的索引非常差。
所以我在这里寻找的是一种更好的方法来分割我的 KD-Tree 节点。考虑到这将是一个物理引擎,决策需要足够简单以便实时做出。