大量圆的碰撞检测

  • Z时代
  • 2024-01-10
  • 分类：问答

检查大量圆的碰撞的最佳方法是什么？

检测两个圆之间的碰撞非常容易，但是如果我们检查每个组合，则 绝对不是最佳解决方案。

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

  • 座标

  • 半径

  • 速度

  • 方向

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

我提出了两种解决方案，但也许有一些更好的解决方案。

整个空间分成重叠的正方形，并仅检查与同一正方形中的圆是否发生碰撞。正方形需要重叠，因此当圆从一个正方形移动到另一个正方形时不会有问题。

在开始时，需要计算每对圆之间的距离。

如果距离很小，那么这些对将存储在某个列表中，并且我们需要在每次更新中检查冲突。

如果距离很大，则我们存储更新，之后可能会发生冲突（可以计算出来，因为我们知道距离和速度）。它需要存储在某种优先级队列中。在需要重新计算先前计算的更新数量之后，然后执行相同的步骤-

将其放在列表中或再次放入优先级队列中。

  1. 是为了游戏吗？

    它是用于模拟，但也可以视为游戏

  2. 您是否要每n毫秒重新计算一次新位置，并且此时还要检查是否有碰撞？

    是的，两次更新之间的时间是恒定的。

  3. 您是否要查找第一次/每次碰撞发生的时间？

    不，我想查找每一次碰撞并在发生碰撞时进行“处理”。

  4. 准确性有多重要？

    这取决于您所说的准确性。我需要检测所有碰撞。

  5. 如果很小的快速移动的圆圈偶尔会穿过彼此，这是一个大问题吗？

    可以假设速度太小以至于不会发生。

回答：

我假设您正在执行简单的硬球分子动力学模拟，对吗？我在蒙特卡洛（Monte

Carlo）和分子动力学模拟中多次遇到相同的问题。关于模拟的文献中经常提到这两种解决方案。我个人更喜欢 ，但稍加修改。

将您的空间划分为不重叠的矩形单元。因此，当您检查一个圆是否发生碰撞时，您会在第一个圆所在的单元格中查找所有圆，并在每个方向上查找X个单元格。我尝试了许多X值，发现X

= 1是最快的解决方案。因此，您必须在每个方向上将空间划分为等于：

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

除数应大于3，否则将导致错误（如果值太小，则应扩大仿真框）。

然后您的算法将如下所示：

  1. 将所有圆圈放入框内

  2. 创建单元格结构并存储指向单元格内圆的索引或指针（在数组或列表上）

  3. 及时走动（移动所有内容）并更新单元格内部的圆圈位置

  4. 环顾四周寻找碰撞。您应该在每个方向检查一个单元

  5. 如果发生碰撞-采取措施

  6. 转到3。

如果正确书写，则可能会带来 复杂性，因为9个像元（在2D中）或27个像元（在3D中）内的最大圆数对于任何总数的圆都是恒定的。

通常，这是这样完成的：

  1. 为每个圆创建一个距离较远的圆的列表R < R_max，计算之后应更新列表的时间（大约T_update = R_max / V_max；其中V_max是最大当前速度）

  2. 及时行动

  3. 用列表中的圆圈检查每个圆圈的距离

  4. 如果发生碰撞-采取措施

  5. 如果当前时间较大T_update，请执行1。

  6. 否则转到2。

通常，可以通过添加另一个列表R_max_2 >

R_max以及带有其自身的T_2到期时间的列表来改进此解决方案。在此解决方案中，此第二列表用于更新第一列表。当然，在T_2您必须更新所有列表

。还要注意这一点T和T_2时间，因为如果碰撞可以改变速度，那么那些时间就会改变。同样，如果在系统中引入一些先兆，那么也会引起速度变化。

您可以将列表用于冲突检测，将单元格用于更新列表。一本书中写道，这是最好的解决方案，但是我认为，如果您创建小单元格（如我的示例），那么

会更好。但这是我的意见。

您还可以执行其他操作以提高仿真速度：

  1. 计算距离时r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...)，不必进行平方根运算。您可以比较r^2一些值-没关系。另外，您不必执行所有(x1-x2)*(x1-x2)操作（我的意思是，对于所有尺寸），因为如果x*x大于某个操作，r_collision^2则所有其他操作y*y等等，总之，会更大。

  2. 分子动力学方法很容易并行化。您可以使用线程甚至在GPU上进行操作。您可以计算不同螺纹中的每个距离。在GPU上，您可以轻松创建几乎无成本的线程数。

对于硬球，还有一种有效的算法，它不及时执行步长，而是在时间上寻找最近​​的碰撞并跳转到该时间并更新所有位置。对于不太可能发生碰撞的不密集系统，这可能会很好。

以上是 大量圆的碰撞检测 的全部内容， 来源链接： utcz.com/qa/400260.html

回到顶部