大量圆形的碰撞检测

Question

大量圆形的碰撞检测

algorithmcollision-detectiongeometry

56

什么是检测大量圆形碰撞的最佳方法？检测两个圆之间的碰撞很容易，但如果我们检查每种组合，则时间复杂度为O(n^2)，这绝对不是最优解。

我们可以假设圆形对象具有以下属性： - 坐标 - 半径 - 速度 - 方向

速度恒定，但方向可能会改变。

我想出了两种解决方案，但可能还有更好的解决方案。

解决方案1：将整个空间分成重叠的正方形，并仅检查与同一正方形中的圆形的碰撞。正方形需要重叠，以便当圆形从一个正方形移动到另一个正方形时不会出问题。

解决方案2：在开始时需要计算每对圆之间的距离。如果距离很小，则将这些对存储在某个列表中，并且我们需要在每次更新中检查碰撞。如果距离很远，则我们存储可以发生碰撞的更新后的时间（因为我们知道距离和速度）。它需要存储在某种优先级队列中。在之前计算的更新次数之后，需要再次检查距离，然后执行相同的过程-将其放在列表中或再次放入优先级队列。

批准者Mark Byers提出的问题的答案：

1.这是为游戏吗？这是用于模拟，但也可以视为游戏。

2.您是否想每n毫秒重新计算新位置，并在此时检查碰撞？是的，更新之间的时间是恒定的。

3.您是否想找到发生第一/每个碰撞的时间？不是，我想找到每次碰撞并在其发生时执行“某些操作”。

4.准确性有多重要？这取决于您所说的“准确性”是什么意思。我需要检测所有碰撞。

如果非常小而快速移动的圆形偶尔会相互穿过，这会是一个大问题吗？
可以假定速度非常慢，不会发生这种情况。

- Tomek Tarczynski

1

这是一个有趣的问题，但您能否提供更多背景信息？这是为了游戏吗？我注意到你的圆正在移动。您是否想每n毫秒重新计算新位置，并在此时检查碰撞？您是否想找到第一次/每次碰撞发生的时间？准确性有多重要？如果非常小而快速移动的圆偶尔穿过彼此，这会是一个大问题吗？ - Mark Byers

2

@Mark：我已经回答了你所有的问题。 - Tomek Tarczynski

方向是如何计算的？在建模物理对象时，通常会有一系列力向量，物体可以沿曲线移动。 - Will

@Will：我想要一个一般性的答案，其中我们不知道方向是如何计算的。 - Tomek Tarczynski

我有点困惑。除非作者指的是恒定速度而不是恒定速度，否则这个问题没有意义？ - AnnanFay

显示剩余3条评论

9个回答

16

我假设您正在进行简单的硬球分子动力学模拟，是吗？在蒙特卡罗和分子动力学模拟中，我也遇到过同样的问题。关于模拟，通常都会提到你两种解决方案。个人而言，我更喜欢解决方案1，但有所修改。 解决方案1
将空间划分为不重叠的矩形单元格。因此，当您检查一个圆是否碰撞时，您要查找第一个圆所在的单元格内所有圆，并向每个方向查找X个单元格。我尝试了许多X值，并发现X = 1是最快的解决方案。因此，您需要将空间分成每个方向大小相等的单元格：

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

除数应大于3，否则会导致错误（如果太小，您应该扩大模拟框）。然后您的算法将如下所示：

将所有圆放入框中
创建单元格结构并在单元格内存储圆的索引或指针（在数组或列表上）
进行时间步进（移动所有内容）并更新单元格内的圆位置
查看每个圆周围的碰撞。您应该在每个方向上检查一个单元格
如果有冲突-做些什么
转到3。

如果您编写正确，则最大圆数在9个单元格（2D）或27个单元格（3D）内是恒定的，因此您将获得约为O（N）的复杂度。 解决方案2 通常是这样做的：

对于每个圆，创建一个距离R < R_max的圆列表，计算我们应该在其后更新列表的时间（大约为T_update = R_max / V_max;其中V_max是当前最大速度）
进行时间步进
检查每个圆与其列表上的圆的距离
如果有冲突-做些什么
如果当前时间大于T_update，转到1。
否则转到2。

通过添加另一个具有R_max_2 > R_max和其自己的T_2过期时间的列表来改进此列表的解决方案非常常见。在此解决方案中，使用第二个列表更新第一个列表。当然，在T_2之后，您必须更新所有列表，这是O（N ^ 2）。还要注意这些T和T_2时间，因为如果碰撞可以改变速度，则这些时间将更改。此外，如果向系统引入某些力，则还会导致速度变化。 解决方案1+2 您可以使用列表进行碰撞检测，并使用单元格更新列表。在一本书中写道，这是最佳解决方案，但我认为如果您创建小单元格（就像我的示例一样），那么解决方案1更好。但这是我的意见。 其他内容 您还可以执行其他操作以提高模拟速度：

当你计算距离 r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) 时，不必进行平方根运算。可以将 r^2 与某个值进行比较 - 这是可以的。另外，你也不必对所有维度（即 x、y、z 等）都执行 (x1-x2)*(x1-x2) 操作，因为如果 x*x 大于某个 r_collision^2 值，则所有其他的 y*y 等求和结果也一定更大。
分子动力学方法非常易于并行化。你可以使用线程或者甚至在 GPU 上运行。你可以在不同线程中计算每个距离。在 GPU 上，你可以轻松地创建成千上万的线程而几乎没有额外代价。

对于硬球来说，还有一种有效的算法，它不按时间步长来做，而是寻找最近的碰撞时间，并跳转到该时间并更新所有位置。这对于碰撞不太可能发生的稀疏系统非常有效。

- klew

+1，实际上我不是在处理分子动力学，而是在处理人群动力学，但出乎意料地它们有很多共同之处。 - Tomek Tarczynski

6

一种可能的技术是在圆心上使用Delaunay三角剖分。考虑每个圆的中心并应用Delaunay三角剖分，这将把你的表面分成三角形。这允许您构建一个图形结构，其中每个节点存储一个三角形的中心，每条边连接到相邻圆的中心。上述操作将限制相邻圆的数量为合理值（平均6个相邻圆）。

现在，当一个圆移动时，您只需要考虑有限的一组圆来进行碰撞检测。然后，您需要再次对受到移动影响的圆集应用三角剖分，但此操作仅涉及很小的一部分圆（移动圆的邻居和一些邻居的邻居）。

关键部分是第一次的三角剖分，这将需要一些时间来执行，后续的三角剖分不是问题。当然，您需要一个高效的图实现来处理时间和空间...

- Adrien Plisson

1

只是补充一下：Delaunay三角剖分需要O(n log n)的时间，因此即使您每次都执行此操作而不是以某种方式更新三角剖分，它也比朴素的O(n^2)算法更快。 - Rex Kerr

1

问题在于每种情况下O的数量。Delaunay三角剖分涉及的操作比朴素的成对比较要复杂得多。Delaunay三角剖分的优点在于后续的镶嵌可以在所有点的一个小子集上执行。 - Adrien Plisson

我明白这一点，但对于大问题（这可能是一个大问题，否则发帖人就不会关心n^2），复杂度的增加远不及n/log n那么昂贵。当然，如果可能的话，本地更新仍然更好。 - Rex Kerr

+1，Delaunay三角剖分是一个非常好的解决方案，但我需要思考一下如何在O(n)时间内更新图形——我认为这是可能的。 - Tomek Tarczynski

@tomek tarczynski：您没有指定目标语言。您可以查看 GTS（http://gts.sourceforge.net/），它是一个实现 Delaunay 三角剖分的 C 库。我还在 Java 中找到了一些实现（http://www.cs.cornell.edu/home/chew/Delaunay.html）。 - Adrien Plisson

4

将您的空间细分为区域，并维护一个列表，其中包含每个区域中心的圆。即使您使用非常简单的方案，例如将所有圆放在列表中，按 center.x 排序，也可以大大加快速度。要测试给定的圆，您只需要针对列表中它两侧的圆进行测试，一直到达一个 x 坐标超过半径的圆。

- Rik Heywood

3

您可以制作一个“球树”的二维版本，这是Will建议的“空间索引”的一种特殊（且非常易于实现）情况。其思想是将圆“合并”到一个“包含”圆中，直到您得到一个“包含”“大量圆”的单个圆。

仅为了说明计算“包含圆”的简单性（在我脑海中）： 1）将两个圆的中心位置（作为向量）相加并缩放1/2，即为包含圆的中心 2）减去两个圆的中心位置（作为向量），加上半径并缩放1/2，即为包含圆的半径

- S.C. Madsen

3

最有效的答案取决于圆的密度。如果密度较低，则在地图上放置低分辨率网格，并标记包含圆的网格元素可能是最有效的方法。每次更新大约需要O(N*m*k)，其中N是圆的总数，m是每个网格点平均包含的圆的数量，k是一个圆覆盖的平均网格点数。如果一个圆每次移动超过一个网格点，则必须修改m以包括已经扫过的网格点数。

另一方面，如果密度非常高，则最好尝试使用图形遍历方法。让每个圆包含距离R内的所有邻居（对于每个圆半径r_i，R > r_i）。然后，如果您移动，您将查询“向前”方向的所有圆以获取其邻居，并抓取任何将在D范围内的圆；然后您会忘记所有“向后”方向的圆，因为它们现在比D更远了。现在，完整的更新将需要O(N*n^2)，其中n是在半径R内的平均圆的数量。对于像紧密间隔的六边形晶格这样的东西，这将比上面的网格方法给出更好的结果。

- Rex Kerr

1

一个建议 - 我不是游戏开发者为何不在碰撞发生前预先计算正如您所指定的

我们可以假设圆形对象具有以下属性：

-坐标

-半径

-速度

-方向

速度恒定，但方向可以改变。

然后随着一个对象的方向改变，重新计算受影响的那些对。如果方向不会太频繁地改变，这种方法是有效的。

- MaLio

但是它的时间复杂度为O(n^2)，因为你不知道哪对圆之间会发生碰撞。 - Tomek Tarczynski

初始计算可能是O(n^2)，但更新变得更简单，因为只有在圆改变方向时才重新计算。还可以针对跟踪哪些圆受到方向改变的优化，即仅检查朝向方向改变的圆，或者根据变化的规模在某个范围内检查。 - Kelly S. French

这与我提出的解决方案2基本相同。 - Tomek Tarczynski

每当一个圆改变方向时，您需要重新检查它与每个其他圆的碰撞情况。如果碰撞频繁发生，这将给您带来麻烦。 - Alan

1

正如Will在他的回答中提到的那样，空间分区树是解决这个问题的常见方法。然而，这些算法有时需要进行一些调整才能有效地处理移动对象。您需要使用宽松的桶装规则，以便大多数移动步骤不需要对象更改桶。

我曾经看到过您所谓的“解决方案1”用于解决这个问题，并被称为“碰撞哈希”。如果您处理的空间足够小且您期望对象至少近似均匀分布，则可以很好地工作。如果您的对象可能聚集在一起，那么问题就显而易见了。在每个哈希框内使用某种类型的分区树的混合方法可以帮助解决这个问题，并将纯树方法转换为更容易同时扩展的方法。

重叠区域是处理跨越树桶或哈希框边界的对象的一种方法。更常见的解决方案是测试任何穿过边缘的对象与相邻框中的所有对象的交集，或将对象插入两个框中（尽管这需要一些额外的处理来避免破坏遍历）。

- Alan

1

如果你的代码依赖于“tick”（并测试以确定对象在tick时是否重叠），那么：

当对象移动“太快”时，它们会在不碰撞的情况下跳过彼此
当多个对象在同一个tick中发生碰撞时，最终结果（例如它们弹回的方式、承受的伤害量等）取决于检查碰撞的顺序而不是碰撞发生的顺序。在极少数情况下，这可能导致游戏锁定（例如，在同一个tick中有3个对象发生碰撞；调整object1和object2的碰撞后，再调整object2和object3的碰撞，导致object2再次与object1碰撞，因此必须重新进行object1和object2之间的碰撞，但这会导致object2再次与object3碰撞，如此往复...）。

注意：理论上，第二个问题可以通过“递归刻度细分”来解决（如果超过2个对象发生碰撞，则将刻度长度减半并重试，直到只有2个对象在该“子刻度”中发生碰撞）。这也可能导致游戏锁定和/或崩溃（当3个或更多的对象在完全相同的瞬间发生碰撞时，您会得到一个“无限递归”场景）。

此外，有时当游戏开发人员使用“刻度”时，他们还会说“1个固定长度的刻度= 1 / 可变帧速率”，这是荒谬的，因为应该是固定长度的东西不能依赖于某些可变的东西（例如，当GPU无法达到每秒60帧时，整个模拟会慢动作进行）；如果他们不这样做，而是改用“可变长度的刻度”，那么“刻度”的两个问题都会显著加剧（特别是在低帧速率下），模拟就会变得非确定性（这可能对多人游戏有问题，并且可能导致玩家保存、加载或暂停游戏时出现不同的行为）。

唯一正确的方法是添加一个维度（时间），并为每个对象分配一个线段，描述为“起始坐标和结束坐标”，再加上“结束坐标后的轨迹”。当任何对象改变其轨迹（无论是因为发生了不可预测的事件还是到达了其“结束坐标”）时，您需要通过对于已改变的对象和每个其他对象进行“两条线之间的距离 <（object1.radius + object2.radius）”的计算来找到“最快”的碰撞；然后修改两个对象的“结束坐标”和“结束坐标后的轨迹”。

外部的“游戏循环”应该是这样的：

    while(running) {
        frame_time = estimate_when_frame_will_be_visible(); // Note: Likely to be many milliseconds after you start drawing the frame
        while(soonest_object_end_time < frame_time) {
              update_path_of_object_with_soonest_end_time();
        }
        for each object {
            calculate_object_position_at_time(frame_time);
        }
        render();
    }

请注意，有多种优化方法，包括：

将世界分成“区域” - 例如，如果您知道对象1将通过区域1和2，则它不能与不通过区域1或区域2的任何其他对象发生碰撞
将对象保存在“end_time％bucket_size”的桶中，以最小化查找“下一个即将到来的结束时间”的时间
使用多个线程并行处理每个对象的“calculate_object_position_at_time（frame_time）;”
将“将模拟状态提前到下一帧时间”的所有工作与“渲染（render（））”并行处理（特别是如果大部分渲染由GPU完成，使CPU / s空闲）。

为了提高性能：

当碰撞不经常发生时，它可以比“滴答声”快得多（您可以在相对较长的时间内几乎不工作）；而当您有空闲时间（出于任何原因-例如，因为玩家暂停了游戏），您可以机会地进一步计算未来（有效地“平滑”时间开销以避免性能峰值）。
当碰撞频繁发生时，它将给您正确的结果，但可能比一个错误的笑话慢，在相同的条件下给您不正确的结果。

它还使得“模拟时间”和“真实时间”之间的任意关系变得微不足道——例如快进和慢动作不会导致任何问题（即使模拟运行得尽可能快或者非常缓慢以至于很难看出是否有任何东西在移动）；而且（在没有不可预测性的情况下）您可以提前计算到未来的任意时间，并且（如果在过期时不将旧的“对象线段”信息丢弃而是储存它）您可以跳转到过去的任意时间，而且（如果只在特定时间点存储旧信息以最小化存储成本）您可以跳回到由存储信息描述的时间，然后向前计算到任意时间。这些组合也使得像“即时慢动作重播”之类的事情变得容易。

最后；对于多人游戏场景，它也更为方便，您不需要浪费大量带宽在每个周期向每个客户端发送每个对象的“新位置”。

当然，缺点是复杂性——一旦你想处理加速度/减速度（重力、摩擦、颠簸运动）、平滑曲线（椭圆轨道、样条）或不同形状的物体（例如任意网格/多边形而不是球体/圆形），计算最早碰撞发生的数学问题会变得更加困难和昂贵；这就是为什么游戏开发者会采用比N个球体或圆形具有线性运动更复杂的模拟时，使用劣质的“刻度”方法。

- Brendan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will · Accepted Answer

有 "空间索引" 数据结构可用于存储您的圆形以便稍后快速比较；Quadtree、r-tree 和 kd-tree 是其中的例子。

解决方案1似乎是一个空间索引，而解决方案2在每次重新计算配对时都会受益于空间索引。

为了使事情更加复杂，您的对象正在移动 - 它们具有速度。

在游戏和模拟中，通常使用空间索引来处理对象，但主要是用于静止对象，通常是不通过移动来响应碰撞的对象。

在游戏中很正常，你需要在设定的时间间隔（离散）内计算所有内容，所以可能两个对象互相穿过，但你没有注意到，因为它们移动得太快。许多游戏实际上甚至不按严格的时间顺序评估碰撞。他们针对静态对象（如墙壁）使用空间索引，并为所有移动对象创建列表，然后进行详尽的检查（尽管进行了放松的离散检查，如我所述）。

准确的连续碰撞检测和对象在模拟中响应碰撞通常要求更高。

你提出的成对方法听起来很有前途。你可以按照下一次碰撞的顺序将这些成对物体排序，并在它们以适当的新位置发生碰撞时重新插入它们。您只需对两个对象生成的新碰撞列表进行排序（O(n lg n)），然后合并两个列表（每个对象的新碰撞和现有碰撞列表；插入新碰撞，删除列出相互碰撞的两个对象的那些陈旧碰撞），这是O(n)。

另一个解决方案是将空间索引调整为不仅在一个区域内严格存储对象，而是存储它自上次计算以来穿过的每个区域，并进行离散处理。这意味着将快速移动的对象存储在您的空间结构中，并且需要针对此情况进行优化。

请记住，在现代处理器上，链接列表或指针列表非常不利于缓存。我建议您在任何空间索引的每个区域中，或者在上述成对物体中，在数组（连续内存）中存储圆的副本，至少存储用于碰撞检测的其重要属性。

正如Mark在评论中所说，将计算并行化可能非常简单。