碰撞检测圈数量庞大 [英] Collision detection of huge number of circles

问题描述

什么是检查圈数量巨大碰撞的最好方法是什么？
这是很容易发现两个圆圈之间的碰撞，但如果我们检查每一个组合，那么它的为O（n ² ）这绝对不是一个最佳的解决方案。

我们可以假设圈子对象还具有以下属性：

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

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

我想到了两个解决方案，但也许有一些更好的解决方案。

解决方法1
除以整个空间成重叠广场只有用圆圈是在同一个广场检查碰撞。广场需要重叠，不会有一个问题，当从一个方形的圆移动到另一个。

解决方案2
在每对圆之间的距离，开始需要计算。
如果该距离小，那么这些对被存储在一些列表中，我们需要检查在每次更新的碰撞。
如果该距离大则我们存储之后更新可以有碰撞（它可以被计算，因为我们知道的距离和velocitites）。它需要被存储在某种优先级队列。经过previously计算需要更新距离的数量进行再次检查，然后我们做同样的过程 - 把它在名单上，又在优先级队列

答案马克·拜尔斯问题

1. 的它是一个游戏？的
   这对模拟的，但它也可以被看作是一个游戏
2. 的是否要重新计算新的岗位上n毫秒，同时检查碰撞在这个时候？的
   是的，更新的时间是恒定的。
3. 的您想寻找其中第一/每一次碰撞发生的时间？的
   不，我要找到每一次碰撞，做'东西'，当它occures。
4. 的重要的是如何准确？的
   这取决于你是什么意思的准确性。我需要检测的所有碰撞。
5. 的这是个很大的问题，如果非常小的快速移动的圆圈可以穿过对方偶尔？的
   可以假定这样的速度是如此之小，就不会发生。

解决方案

我假设你正在做简单的硬球分子动力学模拟，对不对？我来到accros同样的问题多次在蒙特卡罗和分子动力学模拟。无论您的解决方案都经常提到文学有关的模拟。本人来说我preFER 解决方案1 ​​，但稍加修改。

解决方法1
把你的空间分成矩形单元不重叠。所以，当你选中一个圈碰撞你的细胞，你的第一个圈里面各界，看看X细胞在每个方向上左右。我试过的X多个值，发现X​​ = 1是最快的解决方案。所以，你必须划分空间进入细胞的大小在每个方向等于：

 除数= SimulationBoxSize / MaximumCircleDiameter;
CELLSIZE = SimulationBoxSize /除数;
 

除数应大于3，否则会导致错误（如果是太小了，你应该扩大你的模拟箱）。
然后你的算法是这样的：

1. 把各​​界的盒子里面
2. 创建细胞的结构和存储索引或指针界的一个单元内（名单上的阵列或）
3. 请在时间的一个步骤（将一切）和更新各界对细胞内的位置
4. 在环顾四周，每个圆圈的碰撞。您应该检查在每一个方向上的一个细胞周围
5. 如果有冲突 - 做些什么
6. 转至3。

如果你正确地写它，那么你将有一些关于 O（N）的复杂性，因为里面的9个细胞（二维）或27格（三维）界的最大数量是恒定的圈中的任何数量。

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

1. 对于每一个圆圈创建圆是在距离列表 R＆LT; R_max ，计算时间之后，我们应该更新列表（一些关于 T_update = R_max / V_max ;其中V_max是最大流速）
2. 请在一步一步
3. 在其名单上的人士入住距离每圈
4. 如果有冲突 - 做些什么
5. 如果当前时间是更大然后 T_update ，进入1。
6. 否则转2。

该解决方案列出很多时候是通过增加另一个列表 R_max_2＆GT提高; R_max 并用自己的 T_2 到期时间。在该溶液中该第二列表用于更新第一列表。当然，在 T_2 你必须更新所有列出哪些是 O（N ^ 2）。另外要注意使用这个 T 和 T_2 倍，因为如果碰撞可以改变速度那么这些时间会改变。此外，如果你介绍一些foreces到您的系统，那么它也将导致速度变化。

解决方案1 ​​+ 2 可用于冲突检测和细胞列表更新列表。在一本书就写，这是最好的解决办法，但我认为，如果你创建的小细胞（如在我的例子），然后点击解决方案1 ​​更好。但是，这是我的看法。

其他的东西
你也可以做其他的事情，以提高仿真速度：

1. 当你计算距离 R =开方（（X1-X2）*（X1-X2）+（Y1-Y2）*（Y1-Y2）+ ...）你不必做平方根运算。您可以比较 R ^ 2 来一定的价值 - 它的确定。你也不必做（X1-X2）*（X1-X2）操作（我的意思是，对于所有dimentions），因为如果 X * X 大于某些 r_collision ^ 2 那么所有其他 Y *是等等，概括起来，会更大。
2. 在分子动力学方法很容易并行处理。你可以使用线程，甚至在GPU上做到这一点。你可以计算出不同的线程每个距离。在GPU可以伊斯利创建线程几乎无成本的thousends。

有关硬球也有有效的算法，并没有做及时的步骤，而是会寻找最近的碰撞时间，并跳转到了这个时候，并更新所有位置。它可以很好的不密系统中的碰撞都不是很可能的。

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:

• Coordinates
• Radius
• Velocity
• Direction

Velocity is constant, but direction can change.

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

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.

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.

Answers to Mark Byers questions

1. Is it for a game?
   It's for simulation, but it can be treated also as a game
2. Do you want to recalculate the new position every n milliseconds, and also check for collisions at this time?
   Yes, time between update is constant.
3. Do you want to find the time at which the first/every collision occurs?
   No, I want to find every collision and do 'something' when it occures.
4. How important is accuracy?
   It depends on what do you mean by accuracy. I need to detect all collisions.
5. Is it a big problem if very small fast moving circles can pass through each other occasionally?
   It can be assumed that speed is so small that it won't happen.

解决方案

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.

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;

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. Put all circles inside the box
2. Create cell structure and store indexes or pointers to circles inside a cell (on array or on a list)
3. Make a step in time (move everything) and update circles positions inside on cells
4. Look around every circle for collision. You should check one cell around in every direction
5. If there is a collision - do something
6. Go to 3.

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.

Solution 2
Ususaly this is done like this:

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.

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.

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. 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屋！