algorithm - AABB 碰撞检查物理引擎的最佳数据结构是什么？

Question

我需要一个由轴对齐边界框 (AABB) 填充的世界组成的引擎。将执行连续循环，执行以下操作:

for box_a in world
    box_a = do_something(box_a)
    for box_b in world
        if (box_a!=box_b and collides(box_a, box_b))
            collide(box_a, box_b)
            collide(box_b, box_a)

问题是，显然，这是 O(n^2)。我已经设法使这个循环更快地将空间分成 block ，所以这变成了:

for box_a in world
    box_a = do_something(box_a)
    for chunk in box_a.neighbor_chunks
        for box_b in chunk
            if (box_a!=box_b and collides(box_a, box_b))
                collide(box_a, box_b)
                collide(box_b, box_a)

这要快得多但有点粗糙。鉴于有这样一个不需要太多努力的更快的算法，我敢打赌有一个我不知道的数据结构概括了我在这里所做的事情，为这个算法提供了更好的可扩展性。

那么，我的问题是:这个问题的名称是什么，实现它的最佳算法和数据结构是什么？

Answer 1

这确实是计算机科学的一个普遍问题:空间划分。

它用于光线追踪、路径追踪、光栅渲染、物理、IA、游戏，并且非常肯定地用于 HPC、数据库、矩阵数学，任何科学(分子、药学......)，我敢打赌还有成千上万的其他东西.

没有 1 个最好的 结构，我有一个 friend 在他的硕士类(class)中研究了一种算法，用于分割从激光扫描仪(数十亿数据)中出来的云点，在他的情况下最好的数据结构是将一组制服 3D 网格与一些八叉树混合。

对于其他人来说，kd-tree 是最好的，对于其他人来说，BVH 树是最好的。

我喜欢网格系统，但如果空间太宽，它就无法工作，因为所有单元格都必须存在。

有一天，我什至使用 HashMap 实现了一个稀疏网格系统，它起作用了，我没有费心去分析或调查性能，所以我不知道它是否是一种很好的方法，但我知道它是一种方法。

为此，您创建一个 KEY 类，它基本上是一个 3D 位置向量哈希器，首先您对坐标应用整数除法以定义一个网格单元的大小。然后你愚蠢地将所有坐标散列到一个散列中并提供一个 hash_value 方法或 friend 方法。一个相等运算符，然后它可用于 HashMap 。

您可以使用 google::sparse_map 或类似的东西。我个人使用了 boost::unordered，这对我来说已经足够了。

然后要考虑的是 AABB 存在于多个细胞中。您可以在 AABB 覆盖的每个单元格中存储一个引用，这只是每个算法中需要注意的一点:“单元格引用和 AABB 之间没有一对一的关系。”就这样。

祝你好运