我想编写一个小程序，模拟多粒子碰撞，在2D第一次启动（我将它扩展到3D以后），到（三维）模拟收敛对玻尔兹曼分布，也看到了分布在2D如何演变。
我还没有开始编程，所以请不要问了代码示例，这是一个相当普遍的问题，应该帮助我上手。 有对我来说没有任何问题这个问题背后的物理学，它是相当的事实，我将不得不模拟至少200-500颗粒，以达到一个相当不错的速度分布。 我想这样做，在实时性。
现在，每一次步，我会先更新所有粒子的位置，然后检查是否有冲突，以更新新的速度矢量。 然而，这包括了很多checkings的，因为我也必须看到，如果每一个粒子经历与所有其他粒子发生碰撞。 我发现这个职位或多或少同样的问题，使用的方法也有唯一一个我能想到的。 我很害怕，但是，这并不会实时很好地工作，因为它会涉及太多的碰撞检测。
所以现在：即使这种方法将工作性能明智的（让说40FPS），有谁能够想到的方式，以避免不必要的碰撞检查？
我自己的想法是分手了董事会（或3D：空间）为正方形（立方体）具有至少颗粒的直径尺寸和仅实现碰撞检测的方式，如果两个粒子的中心是adjecent格内在网格中...
我会很高兴听到更多的想法，因为我想为我所能，仍然有一个实时计算/模拟回事增加颗粒的量。
编辑：所有的碰撞是纯粹没有任何其他力量对颗粒做的工作弹性碰撞。 我将实现初始情况由用户选择的选择随机起始位置和速度一些变量来确定。
EDIT2：我发现了粒子碰撞的模拟一个很好的和非常有益的纸在这里 。 希望它可以帮助一些人有兴趣更深入。
Answer 1:
如果你想起来了，移动的计划颗粒是一个真正的3D系统，其中三个维度x ， y和时间（ t ）。
比方说，一个“时间步长”从去t0到t1 。 每个粒子中，将创建3D线段从去P0(x0, y0, t0)至P1(x1, y1, t1)基于当前粒子的位置，速度和方向。
分区在3D网格的三维空间，并且每个3D线段链接到它越过细胞。
现在，每个网格单元应进行检查。 如果它连接到0或1段，就不需要进一步的检查（标记为选中）。 如果它包含2个或多个片段，你需要检查他们之间的碰撞：计算3D碰撞点Pt ，缩短了两段在这一点上结束（并删除链接到细胞中，它们已经不交叉），创建两个新段从去Pt到新计算P1根据颗粒的新的方向/速度点。 这些新线段添加到网格和标记细胞的检查。 添加一个线段到电网把所有的交叉细胞未选中状态。
当在网格没有更多的未选中的细胞，你解决你的时间步长。
编辑
- 对于三维粒子，适应上述溶液至4D。
- 八叉树是三维空间划分网格的造型美观在这种情况下，你可以在“冒泡”检查/ unnchecked状态快速找到需要注意的细胞。
Answer 2:
空间划分的一个很好的高水平的例子是考虑乒乓的球和一个桨之间的游戏，并检测冲突。
说桨是在屏幕的左上角，球靠近屏幕的左下角...
--------------------
|▌ |
| |
| |
| ○ |
--------------------
这是没有必要每个球移动时检查碰撞。 相反，分裂比赛场地分为两权拦腰。 在现场的左侧的球吗？ （矩形算法内简单点）
Left Right
|
---------|----------
|▌ | |
| | |
| | |
| ○ | |
---------|----------
|
如果答案是肯定的，再次分裂的左手边，这个时候水平，所以我们有一个左上和左下分区。
Left Right
|
---------|----------
|▌ | |
| | |
----------- |
| | |
| ○ | |
---------|----------
|
这是球在屏幕桨的相同左上角？ 如果不是，没必要检查的碰撞！ 仅驻留在相同的分区中的对象需要用于彼此碰撞进行测试 。 通过这样做一系列的检查矩形里面简单又便宜的点，你可以很容易地从做一个更昂贵的形状/几何碰撞检查保存自己。
您可以继续向下分裂的空间成越来越小的块，直到对象跨越两个分区。 这背后是BSP（早期3D游戏首创像地震技术）的基本原理。 有理论的有关空间分割在网络上一大堆在2米3的尺寸。
http://en.wikipedia.org/wiki/Space_partitioning
在2个维度，你会经常使用BSP或四叉树。 在3个维度，你会经常使用八叉树。 但是基本原则是一样的。
Answer 3:
你可以沿着“分而治之”的行认为。 我们的想法是，以确定正交参数与不相互影响。 例如，一个可在2D（在3D 3轴）的情况下，沿轴2分割认为动量分量的和独立地计算碰撞/位置。 另一个以鉴定此类参数的方式可以被分组在垂直于彼此运动的粒子。 因此，即使他们影响，沿着这些线路的净势头不会改变。
我同意上面并没有完全回答你的问题，但它传达它可能对你有用这里基本思想。
Answer 4:
让我们说，在时间t，每个粒子，你必须：
P position
V speed
和N *（N-1）的粒子（A）（i）和A（j）的之间的信息/ 2阵列，其中i置于<J; 您使用对称性来评估一个上三角矩阵，而不是一个完整的N *（N-1）的网格。
MAT[i][j] = { dx, dy, dz, sx, sy, sz }.
这意味着，在相对于粒子Ĵ，粒子j之后距离由三个部件DX，DY和DZ的; 和由dt的multipledΔ-VEE为SX，SY，SZ。
要根据自己的速度移动到时刻t + DT你姑且更新所有粒子的位置
px[i] += dx[i] // px,py,pz make up vector P; dx,dy,dz is vector V premultiplied by dt
py[i] += dy[i] // Which means that we could use "particle 0" as a fixed origin
pz[i] += dz[i] // except you can't collide with the origin, since it's virtual
然后，你检查整个N *（N-1）/ 2阵列和暂定计算每两颗粒之间的新的相对距离。
dx1 = dx + sx
dy1 = dy + sy
dz1 = dz + sz
DN = dx1*dx1+dy1*dy1+dz1*dz1 # This is the new distance
如果DN <d ^ 2与颗粒的直径d，你有过在DT刚刚过去的碰撞。
然后，计算出究竟在何处发生这种情况，即你计算确切的碰撞D'T，你可以从旧的距离的平方做D2（DX * DX + DY * DY + DZ * DZ）和新的DN：这是
d't = [(SQRT(D2)-D)/(SQRT(D2)-SQRT(DN))]*dt
（所需时间，以减少在覆盖的距离SQRT（D2）-SQRT（DN）在时间dt的速度从SQRT（D2）到d，距离）。 这使得假设，即颗粒Ĵ，从颗粒i的refrence帧看到的那样，还没有“overshooted”。
这是一个沉重的多计算的，但你只需要它，当你得到一个碰撞。
知道D't和d“T = DT-d't，则可以使用重复上Pi和点Pj的位置计算DX * D'吨/ DT等，将获得的颗粒i和j的准确位置P在时刻碰撞;你更新的速度，那么它整合为剩余d“T和在时间dt年底拿到的位置。
需要注意的是，如果我们停止在这里这种方法会破坏如果一个三粒子碰撞发生，并且将只处理两个粒子碰撞。
因此，而不是运行计算，我们刚刚纪念发生碰撞的D'牛逼发生了颗粒（I，J），并在运行结束时，我们将保存最小D'T取代它发生了冲突，并为之之间。
即，说我们检查颗粒25和110，并找到在0.7 DT碰撞; 那么，我们在0.3 DT找到110和139之间的碰撞。 有没有比0.3 DT早期碰撞。
我们进入碰撞更新阶段，而“碰撞” 110和139，并更新自己的位置和速度。 然后重复2 *（N-2）计算，对每个（I，110）和（i，139）。
我们会发现，有可能仍是颗粒25的碰撞，但是现在在0.5 DT，也许，说，另一个139和80之间为0.9 DT。 0.5 dt为新的最小值，因此，我们重复碰撞计算25和110之间，并重复，痛苦的算法对每个碰撞轻微的“慢下来”。
因此实现，唯一的风险，现在是“鬼碰撞”的，即，颗粒是在d>直径从目标在时刻t-DT，并且在d> 在另一侧直径在时间t。
这只能通过选择一个DT所以没有颗粒旅行过任何给定的DT自己的直径超过半数避免。 其实，你可以使用基于粒子最快的速度自适应DT。 鬼一眼冲突仍然是可能的; 进一步的改进是基于任何两个颗粒之间的最近距离，以减少DT。
通过这种方式，它是真实的，该算法在碰撞附近大幅减慢，但它极大地加速时，碰撞的可能性并不大。 如果两个粒子之间的最小距离（这是我们在循环过程计算在几乎没有成本）是这样的（这也是我们发现，在几乎没有成本）最快的粒子不能掩盖它以不到50和DTS，这是一个4900 ％的速度递增那里。
总之，在没有冲突的情况下一般我们现在已经做了5个总和（其实更像34由于数组索引），三种产品和几个任务为每个粒子的情侣。 如果我们包括（K，K）夫妇考虑到粒子更新本身，我们有成本的一个很好的近似为止。
此方法具有是O（N ^ 2）的优点 - 它与颗粒的数磅秤 - 代替为O（M ^ 3） - 与所涉及空间的体积缩放。
我期望在现代处理器C程序，以便能够实时地管理成千上万的顺序号的颗粒。
PS：其实这是非常相似，萨科Repiquet的做法，其中包括多次碰撞的4D附近放缓的必要性。
Answer 5:
直到两个粒子之间的碰撞（或颗粒和壁之间），会发生，整合是微不足道的。 这里的方法是计算第一碰撞时，整合到那时，再计算第二碰撞等的时间。 让我们定义tw[i]作为时间的i个粒子取命中第一壁。 这是很容易计算，但必须考虑到球体的直径。
时间的计算tc[i,j]两个粒子间的碰撞i和j花费一点时间，并在它们的距离的时间的研究如下d ：
d^2=Δx(t)^2+Δy(t)^2+Δz(t)^2
我们研究，如果存在t正，使得d^2=D^2 ，作为D的颗粒的直径（或颗粒的两个半径的总和，如果你想他们不同）。 现在，考虑总和的第一项在RHS，
Δx(t)^2=(x[i](t)-x[j](t))^2=
Δx(t)^2=(x[i](t0)-x[j](t0)+(u[i]-u[j])t)^2=
Δx(t)^2=(x[i](t0)-x[j](t0))^2+2(x[i](t0)-x[j](t0))(u[i]-u[j])t + (u[i]-u[j])^2t^2
当出现定义两个粒子的运动规律的新条款x坐标，
x[i](t)=x[i](t0)+u[i]t
x[j](t)=x[j](t0)+u[j]t
和t0是初始配置的时间。 让然后(u[i],v[i],w[i])是的速度的三个分量i个粒子。 做同样的其他三个坐标和总结，我们得到一个2阶多项式方程在t ，
at^2+2bt+c=0 ，
哪里
a=(u[i]-u[j])^2+(v[i]-v[j])^2+(w[i]-w[j])^2
b=(x[i](t0)-x[j](t0))(u[i]-u[j]) + (y[i](t0)-y[j](t0))(v[i]-v[j]) + (z[i](t0)-z[j](t0))(w[i]-w[j])
c=(x[i](t0)-x[j](t0))^2 + (y[i](t0)-y[j](t0))^2 + (z[i](t0)-z[j](t0))^2-D^2
现在，有许多标准来评价一个真正的解决方案等的存在...你可以，如果你想优化它，后来评估。 在任何情况下，你获得tc[i,j]如果是复杂的或消极的，你把它设置为正无穷大。 要加快，要记住tc[i,j]是对称的，而且你也想设置tc[i,i]到无穷大的便利。
然后你取最小值tmin阵列的tw和矩阵的tc ，并及时整合的时间tmin 。
现在，您减去tmin到的所有元素tw和tc 。
与壁的弹性碰撞的情况下i个粒子，你只翻转该粒子的速度，并重新计算仅tw[i]和tc[i,k]对于所有其他k 。
在两个粒子之间的碰撞的情况下，重新计算tw[i],tw[j]和tc[i,k],tc[j,k]对于所有其他k 。 在3D的弹性碰撞的评价是不平凡的，也许你可以使用这个
http://www.atmos.illinois.edu/courses/atmos100/userdocs/3Dcollisions.html
关于如何做的生产规模，你有一个初步的开销是O(n^2) 然后2个时间步长之间的集成是O(n)和碰壁或碰撞，需要O(n)重新计算。 但真正重要的是碰撞之间的平均时间是如何与尺度n 。 而且应该有一个答案的地方在统计物理这一:-)
如果你想暗算时间属性，则不要忘记添加另外的中间时间步长。
Answer 6:
可以定义颗粒之间的排斥力，正比于1 /（距离的平方）。 在每次迭代中，计算所有粒子对之间的力，添加所有作用于每个粒子的力，计算粒子加速，则粒子的速度和最终粒子的新位置。 碰撞自然会以这种方式来处理。 但是，处理的颗粒和墙壁之间的相互作用是另一个问题，必须以其他方式处理。
文章来源: An efficient way to simulate many particle collisions?
