二维碰撞检测的四叉树

Question

我正在尝试使用四叉树进行2D碰撞检测，但我对如何实现它感到有些困惑。首先，我会有一个四叉树，其中包含四个子树（每个象限都代表一个），以及一组无法放入单个子树中的对象。

在树中检查碰撞物体时，我会像这样做（感谢QuadTree for 2D collision detection）：

1. 检查当前节点中的任何物体是否与该物体发生碰撞。
2. 对于空间与对象重叠的任何子树，都要进行递归。

在四叉树中查找所有碰撞的步骤如下：

1. 将当前节点中的每个对象与当前节点中的其他对象进行碰撞检查。
2. 将当前节点中的每个对象与每个子树进行碰撞检查。

将对象插入四叉树时：

1. 如果该对象适合多个子树，则将其添加到当前节点并返回。
2. 否则，递归到包含该对象的子树中。

更新四叉树的方法如下：

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

这样做可以吗？有什么优化的空间吗？

- bfops

---

按照你描述的方式进行实现，我已经按这种方式和Dave O.的方式实现了，这种方式更容易编码和更快。管理更多的列表以跟踪所有叶子会增加可避免的开销。这是我其中一个版本的源代码（使用Java）：Steerio。 - ClickerMonkey

Answer 1

你的四叉树结构不够优化。每个节点存储4个子树是正确的，但实际对象应该仅存储在叶节点中，而不是内部节点。因此，持有实际对象的集合需要移动到叶节点中。

让我们来看看操作的实现：

1. 将对象插入四叉树中:
   检查对象是否与当前节点相交。如果相交，则递归执行。如果已经达到叶节点，则将对象插入集合中。
2. 从四叉树中删除对象:
   执行与插入对象完全相同的步骤，但是当已到达叶节点时，从集合中删除对象。
3. 测试一个对象是否与四叉树内的任何对象相交:
   执行与插入对象完全相同的步骤，但是当已到达叶节点时，检查其是否与集合中所有对象发生碰撞。
4. 测试四叉树内所有对象之间的所有碰撞:
   对于四叉树中的每个对象执行单个对象碰撞测试。
5. 更新四叉树:
   从四叉树中删除所有位置已更改的对象，并再次将它们插入。

这具有几个优点：

• 仅在叶节点中存储对象，因此非常容易处理四叉树的操作（特殊情况更少）
• 四叉树可以具有不同深度的叶子，从而允许您根据其所覆盖的空间区域调整四叉树的密度。此适应性可以在运行时发生，从而保持对象/节点比例最优。

唯一的缺点：

• 对象可能属于四叉树内的多个集合。您将需要一个额外的线性集合，在四叉树之外枚举每个对象而不产生重复。

- Dave O.

---

我担心的是这种额外的劣势。这难道不会导致添加额外的代码（例如线性集合在四叉树之外），以确保A只与B碰撞一次，即使B可能在多个子树中？ - bfops

@RobotGymnast 碰撞不是问题，因为您只返回 true/false，如果一个对象属于多个集合，则在这些集合中仍然是相同的。枚举是个问题。您不能使用四叉树遍历所有对象，因为您会多次访问其中一些对象。 - Dave O.

这可能有点天真，但是给对象添加一个touched()类型的函数怎么样？这样在遍历过程中，当检查到一个对象时，您可以设置一个touched标志，因此如果它再次出现，则可以忽略它。我知道这可能不是完美清晰甚至优雅的方法，但它似乎足够简单，并且我已经在我的四叉树实现中成功使用了它。 - leeor_net

我刚刚发现的另一个缺点是，如果你有四个大对象，比如覆盖整棵树，它会一直细分，直到达到深度限制。再加上第五个对象，如果没有一些复杂的边缘情况处理，它就会崩溃。 - Rei Miyasaka

另一个原因是，对于许多对象（线、圆、矩形甚至多边形），计算边界矩形要比计算交集便宜得多且简单。 - Rei Miyasaka

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-Tree，网格或线段树）相比表现较差。

- Mikola

---

这些博客文章非常出色。在这个主题上，我发现它们是最好的信息之一。 - Asad-ullah Khan

Answer 3

我不确定它的CPU效率如何，但在我的Eclipse核心双重处理器上似乎运行良好，仍以超过2400 fps的速度运行lol..

基本上，我向可碰撞对象添加了一个列表，用于存储我已将对象与之关联的四叉树节点对象的引用（通过插入到四叉树中）。我还向每个四叉树节点添加了一个列表，用于存储被认为在该节点范围内的任何对象的引用。因此，每个节点只会有一个对象的出现。每个节点还存储其父节点的引用，以便在初始节点后导航到附近的节点，以获得进一步的碰撞准确性。

很容易获取一个单元格中所有其他对象的引用：

list temp_checklist = object.cells[cell_index].objects
//('objects' being some sort of array or list of object references as described above)

希望这能帮到某个人；）

- Lazouskie