巨大圈子的碰撞检测

Question

检查大量圈子碰撞的最佳方法是什么？
检测两个圆之间的碰撞非常容易,但是如果我们检查每个组合,则它是O(n ²),这绝对不是最佳解决方案.

我们可以假设circle对象具有以下属性:

• 坐标
• 半径
• 速度
• 方向

速度是恒定的,但方向可以改变.

我想出了两个解决方案,但也许有更好的解决方案.

解决方案1将
整个空间划分为重叠的正方形,并仅检查与同一正方形的圆形的碰撞.正方形需要重叠,因此当圆从一个方格移动到另一个方格时不会出现问题.

解决方案2
在开始时,需要计算每对圆之间的距离.
如果距离很小,那么这些对存储在一些列表中,我们需要检查每次更新中的冲突.
如果距离很大,那么我们存储后更新可能会发生碰撞(可以计算,因为我们知道距离和速度).它需要存储在某种优先级队列中.在先前计算的更新数量之后,需要再次检查距离,然后我们执行相同的过程 - 将其放在列表中或再次放入优先级队列中.

Mark Byers的答案问题

1. 是游戏吗？
   这是为了模拟,但也可以作为游戏来对待
2. 您想要每n毫秒重新计算一次新位置,还要检查此时的碰撞情况吗？
   是的,更新之间的时间是不变的.
3. 您想找到发生第一次/每次碰撞的时间吗？
   不,我想找到每一次碰撞,并在碰撞时做"有所作为".
4. 准确性有多重要？
   这取决于你的准确度是什么意思.我需要检测所有碰撞.
5. 如果非常小的快速移动的圆圈偶尔会相互穿过,这是一个大问题吗？
   可以假设速度太小而不会发生.

Answer 1

存在" 空间索引 "数据结构,用于存储您的圆圈以便以后快速比较; Quadtree,r-tree和kd-tree就是例子.

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

更复杂的是,你的物体正在移动 - 它们具有速度.

在游戏和模拟中对象使用空间索引是正常的,但主要用于静止物体,通常是通过移动不会对碰撞做出反应的物体.

在游戏中这是正常的,你可以按设定的时间间隔(离散)计算所有内容,因此可能是两个对象相互穿过,但你没注意到因为它们移动得太快了.许多游戏实际上甚至不按严格的时间顺序评估碰撞.它们具有静止物体的空间索引,例如墙壁,以及他们详尽检查的所有移动物体的列表(尽管我按照概述的放松离散检查).

准确的连续碰撞检测以及物体对模拟中碰撞的反应通常要求更高.

这些对接近你概述的声音很有希望.您可以通过下一次碰撞对这些对进行排序,并在它们碰到相应的新位置时重新插入它们.您只需要为两个对象排序新生成的冲突列表(O(n lg n)),然后合并两个列表(每个对象的新冲突和现有冲突列表;插入新冲突,删除这些冲突)列出碰撞的两个对象的陈旧碰撞,即O(n).

对此的另一个解决方案是调整您的空间索引,以便不是严格地将对象存储在一个扇区中,而是存储自上次计算以来已经通过的每个扇区,并且离散地执行操作.这意味着在您的空间结构中存储快速移动的对象,并且您需要针对此情况对其进行优化.

请记住,链接列表或指针列表对于现代处理器上的缓存非常不利.我主张您存储圆圈的副本 - 它们在任何速率下的碰撞检测的重要属性 - 在任何空间索引的每个扇区中的阵列(顺序存储器)中,或者您在上面概述的对中.

正如马克在评论中所说,将计算并行化可能非常简单.

Answer 2

我假设你正在进行简单的硬球分子动态模拟,对吧？我在Monte Carlo和分子动力学模拟中多次遇到同样的问题.在有关模拟的文献中经常提到您的两种解决方案.Personaly我更喜欢解决方案1,但略有修改.

解决方案1
将空间划分为不重叠的矩形单元格.因此,当您检查一个圆圈是否发生碰撞时,您会查找第一个圆圈所在的单元格内的所有圆圈,并在每个方向上查看X个单元格.我尝试了很多X值,发现X = 1是最快的解决方案.所以你必须将空间分成每个方向的单元格大小,等于:

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

除数应大于3,否则会导致错误(如果它太小,则应放大模拟框).
然后你的算法将如下所示:

1. 将所有圆圈放在框内
2. 创建单元格结构并存储索引或指向单元格内的圆圈(在数组或列表中)
3. 及时(移动所有内容)并更新单元格内的圆圈位置
4. 环顾每个圆圈以进行碰撞.你应该在每个方向检查一个单元格
5. 如果发生碰撞 - 做点什么
6. 转到3.

如果你能正确地编写它,那么你就会有一些关于O(N)复杂度的东西,因为9个单元格(2D)或27个单元格(3D)中的最大圆圈数对于任何圆圈总数是恒定的.

解决方案2
Ususaly这样做是这样的:

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你必须更新所有O(N ^ 2)的列表.同时要小心这个T和T_2时间,因为如果碰撞可以改变速度,那么这些时间会改变.此外,如果您在系统中引入一些前言,那么它也会导致速度变化.

解决方案1 ​​+ 2 您可以使用列表进行冲突检测,使用单元格更新列表.在一本书中写道,这是最好的解决方案,但我认为如果你创建小单元格(就像我的例子中那样),那么解决方案1就更好了.但这是我的意见.

其他东西
你也可以做其他事情来提高模拟速度:

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上,您可以轻松地创建线程的代价几乎是无成本的.

对于硬球,还有一种有效的算法,它不会及时进行,而是在时间上寻找最近​​的碰撞并跳到这个时间并更新所有位置.对于不太可能发生碰撞的密集系统,这可能是好事.

Answer 3

一种可能的技术是在圆的中心使用Delaunay 三角剖分。

考虑每个圆的中心并应用 delaunay 三角剖分。这会将您的曲面细分为三角形。这允许您构建一个图形，其中每个节点存储三角形的中心，并且每条边都连接到相邻圆的中心。上面操作的镶嵌会将邻居的数量限制在一个合理的值（平均 6 个邻居）

现在，当一个圆圈移动时，您可以考虑碰撞的一组有限的圆圈。然后，您必须再次将曲面细分应用于受移动影响的一组圆，但此操作仅涉及非常小的圆子集（移动圆的邻居，以及邻居的一些邻居）

关键部分是第一次镶嵌，这需要一些时间来执行，以后的镶嵌不是问题。当然，您需要在时间和空间方面有效地实现图形......