用于2D碰撞检测的四叉树

Question

我正在尝试使用四叉树进行二维碰撞检测,但我对如何实现它感到有点困惑.首先,我有一个四叉树,其中包含四个子树(一个代表每个象限),以及一个不适合单个子树的对象集合.

当检查对象在树中的碰撞时,我会做这样的事情(感谢QuadTree用于2D碰撞检测):

1. 检查对象是否与当前节点中的任何对象发生冲突.
2. 对于其空间与对象重叠的任何子树,递归.

要查找四叉树中的所有碰撞:

1. 检查当前节点中的每个对象与当前节点中的每个其他对象.
2. 根据每个子树检查当前节点中的每个对象.

要插入四叉树:

1. 如果对象适合多个子树,则将其添加到当前节点,然后返回.
2. 否则,递归到包含它的子树.

要更新四叉树:

1. 递归到每个子树.
2. 如果当前节点中的任何元素不再完全适合当前树,请将其移动到父节点.
3. 如果当前节点中的任何元素适合子树,请将其插入子树中.

这好吗？可以改进吗？

Answer 1

您的四叉树结构不是最佳的.您每个节点存储4个子树是正确的,但实际对象应该只存储在叶子内部,而不是内部节点.因此,需要将保存实际对象的集合移动到叶子上.

我们来看看操作的实现:

1. 将对象插入到四叉树中:
   检查对象是否与当前节点相交.如果是这样,递归.如果已达到叶级别,请将对象插入集合中.
2. 从四叉树中删除一个对象:
   执行与插入对象完全相同的步骤,但是当您到达叶级时,将其从集合中删除.
3. 测试对象是否与四叉树内的任何对象相交:
   执行与插入对象完全相同的步骤,但是当您到达叶级时,检查是否与集合中的所有对象发生碰撞.
4. 测试四叉树内所有对象之间的所有碰撞:
   对于四叉树中的每个对象,执行单个对象碰撞测试.
5. 更新四叉树:
   删除位置已被修改的四叉树中的所有对象,然后重新插入.

这有几个好处:

• 通过仅在叶子中存储对象,可以很容易地处理四叉树上的操作(更少的特殊情况)
• 四叉树可以具有不同深度的叶子,因此您可以根据其覆盖的空间区域调整四叉树的密度.这种适应可以在运行时发生,从而保持对象/节点比率最佳.

只有不利条件:

• 对象可以属于四叉树内的多个集合.您将需要在四叉树外部使用额外的线性集合来枚举每个对象而不重复.

Answer 2

四叉树并不总是用于碰撞检测的最佳数据结构.四叉树的开销可能是无限的(如果你不限制树的深度),并且在最坏的情况下根本不提供任何加速.相反,您可能需要考虑使用稀疏网格,这样可以提供比四叉树更好的性能,而无需遍历多个树级别的额外开销.

还有其他完全不同的方法甚至可能更好.例如,您可以尝试实现Zomorodian和Edelsbrunner的算法,就像我在以下模块中所做的那样:

• https://github.com/mikolalysenko/box-intersect

以下是我写的一些文章,更详细地讨论了这些问题:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

特别是,如果你看一下上一节中的基准测试,你将会看到所有被调查的图书馆,与其他碰撞检测方法(如R-Trees,网格或细分树)相比,四叉树往往表现不佳.