大量圆的碰撞检测 [英] Collision detection of huge number of circles

问题描述

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

What is the best way to check collision of huge number of circles?
It's very easy to detect collision between two circles, but if we check every combination then it is O(n²) which definitely not an optimal solution.

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

We can assume that circle object has following properties:

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

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

Velocity is constant, but direction can change.

我提出了两个解决方案，但也许还有一些更好的解决方案.

I've come up with two solutions, but maybe there are some better solutions.

解决方案 1
将整个空间划分为重叠的正方形，并仅检查与同一正方形中的圆圈是否发生碰撞.正方形需要重叠，所以当圆从一个正方形移动到另一个正方形时不会出现问题.

Solution 1
Divide whole space into overlapping squares and check for collision only with circles that are in the same square. Squares need to overlap so there won't be a problem when a circle moves from one square to another.

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

Solution 2
At the beginning distances between every pair of circles need to be calculated.
If the distance is small then these pair is stored in some list, and we need to check for collision in every update.
If the distance is big then we store after which update there can be a collision (it can be calculated because we know the distance and velocitites). It needs to be stored in some kind of priority queue. After previously calculated number of updates distance needs to be checked again and then we do the same procedure - put it on the list or again in the priority queue.

Mark Byers 问题的答案

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

推荐答案

我假设你在做简单的硬球分子动力学模拟，对吧?我在蒙特卡洛和分子动力学模拟中多次遇到同样的问题.关于模拟的文献中经常提到您的两种解决方案.我个人更喜欢解决方案 1，但稍作修改.

I assume you are doing simple hard-sphere molecular dynamic simulation, right? I came accros the same problem many times in Monte Carlo and molecular dynamic simulations. Both of your solutions are very often mentioned in literature about simulations. Personaly I prefer solution 1, but slightly modified.

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

Solution 1
Divide your space into rectangular cells that don't overlap. So when you check one circle for collision you look for all circles inside a cell that your first circle is, and look X cells in each direction around. I've tried many values of X and found that X=1 is the fastest solution. So you have to divide space into cells size in each direction equal to:

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

除数应该大于3，否则会出错(如果太小，你应该放大你的模拟框).
那么你的算法将如下所示:

Divisor should be bigger than 3, otherwise it will cause errors (if it is too small, you should enlarge your simulation box).
Then your algorithm will look like this:

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

如果你写得正确，那么你会有一些关于 O(N) 复杂性的东西，因为 9 个单元格(2D 中)或 27 个单元格(3D 中)内的最大圆圈数是恒定的任意总圈数.

If you will write it correctly then you would have something about O(N) complexity, because maximum number of circles inside 9 cells (in 2D) or 27 cells (in 3D) is constant for any total number of circles.

解决方案 2
通常这样做是这样的:

Solution 2
Ususaly this is done like this:

1. 为每个圆创建一个距离为R 的圆列表R_max，计算我们应该更新列表的时间(关于 T_update = R_max/V_max；其中 V_max 是最大当前速度)
2. 及时采取措施
3. 检查每个圆圈与列表中圆圈的距离
4. 如果发生碰撞 - 做点什么
5. 如果当前时间大于T_update，则转到1.
6. 否则转至 2.

1. For each circle create a list of circles that are in distance R < R_max, calculate time after which we should update lists (something about T_update = R_max / V_max; where V_max is maximum current velocity)
2. Make a step in time
3. Check distance of each circle with circles on its list
4. If there is a collision - do something
5. If current time is bigger then T_update, go to 1.
6. Else go to 2.

这个带有列表的解决方案通常通过添加另一个带有 R_max_2 > 的列表来改进.R_max 和它自己的 T_2 过期时间.在此解决方案中，第二个列表用于更新第一个列表.当然，在 T_2 之后，您必须更新所有 O(N^2) 的列表.还要小心这个 T 和 T_2 时间，因为如果碰撞可以改变速度，那么这些时间就会改变.另外，如果你给你的系统引入一些力，那么它也会引起速度的变化.

This solution with lists is very often improved by adding another list with R_max_2 > R_max and with its own T_2 expiration time. In this solution this second list is used to update the first list. Of course after T_2 you have to update all lists which is O(N^2). Also be carefull with this T and T_2 times, because if collision can change velocity then those times would change. Also if you introduce some foreces to your system, then it will also cause velocity change.

解决方案 1+2您可以使用列表进行碰撞检测，使用单元格更新列表.在一本书中写到这是最好的解决方案，但我认为如果您创建小单元(如我的示例中)，那么 solution 1 会更好.但这是我的看法.

Solution 1+2 You can use lists for collision detection and cells for updating lists. In one book it was written that this is the best solution, but I think that if you create small cells (like in my example) then solution 1 is better. But it is my opinion.

其他内容
您还可以做其他事情来提高模拟速度:

Other stuff
You can also do other things to improve speed of simulation:

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 上，您可以轻松创建数以千计的线程，几乎没有成本.

1. When you calculate distance r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) you don't have to do square root operation. You can compare r^2 to some value - it's ok. Also you don't have to do all (x1-x2)*(x1-x2) operations (I mean, for all dimentions), because if x*x is bigger than some r_collision^2 then all other y*y and so on, summed up, would be bigger.
2. Molecular dynamics method is very easy to parallelise. You can do it with threads or even on GPU. You can calculate each distance in different thread. On GPU you can easly create thousends of threads almost costless.

对于硬球，还有一种有效的算法，它不及时执行步骤，而是及时查找最近的碰撞并跳转到该时间并更新所有位置.这对于不太可能发生碰撞的非密集系统很有用.

For hard-spheres there is also effective algorithm that doesn't do steps in time, but instead it looks for nearest collision in time and jumps to this time and updates all positions. It can be good for not dense systems where collisions are not very probable.

这篇关于大量圆的碰撞检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！