2D 碰撞 n 体模拟（大量球的快速碰撞检测）
我想编写一个程序来模拟 2D 平面上大量（N = 1000 - 10^5 及更多）物体（圆圈）的运动。所有物体都具有相同的尺寸，它们之间唯一的相互作用是弹性碰撞。
我想要得到类似 
的东西，但规模更大，有更多的球等等平面的密集填充（不是这里的气体模型，而是类似沸水模型的东西）。
因此，我需要一种快速方法来检测编号 i 的球在其路径上 2*radius+V*delta_t 距离内是否有任何其他球。我不想对每个 i 球进行与 N 个球的碰撞的完整搜索。 （此搜索将为 N^2。）
PS 抱歉，循环动画 GIF。只需按 Esc 即可停止。 （在 Chrome 中不起作用）。
I want to write a program for simulating a motion of high number (N = 1000 - 10^5 and more) of bodies (circles) on 2D plane. All bodies have equal size and the only interaction between them is elastic collision.
I want to get something like but in larger scale, with more balls and more dense filling of the plane (not a gas model as here, but smth like boiling water model).
So I want a fast method of detection that ball number i does have any other ball on its path within 2*radius+V*delta_t distance. I don't want to do a full search of collision with N balls for each of i ball. (This search will be N^2.)
PS Sorry for loop-animated GIF. Just press Esc to stop it. (Will not work in Chrome).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
物理模拟的第一步是宽相碰撞检测。这里概述了几种方法使用 CUDA 进行宽相碰撞检测，但是这两种方法基础知识是：
This first step in physics simulation is the broad-phase collision detection. There are several approaches outlined here Broad-Phase Collision Detection with CUDA but the two basics ones are:
显然，您希望避免 (N1-)*N 检查每次迭代的冲突。一种简单的方法是将区域划分为二维单元网格，然后进行一次遍历来计算出每个球在当前迭代中经过哪些单元。然后，每个球仅检查与穿过它所经过的单元格的球的碰撞。
我确信还有更复杂的方法，但这可能是一个好的开始。
Obviously you want to avoid (N1-)*N checks for collisions with each iterations. A simple approach would be to divide the area into a 2D grid of cells and then make a single pass to work out which cells each ball passes through in the current iteration. Each ball then only checks for collisions with balls passing through the cells it passes through.
I am sure there are more sophisticated approaches, but this might be a good start.
网格宽度/长度应大于或等于它们的半径，并且搜索应在第一个邻居（8+中心=9个网格）上。
在最小网格尺寸的情况下，粒子计算数量是十到十五倍。
Grid width/length should be greater than or equal to the radius of them and search should be on the 1st neighbours(8+center=9 grids).
With minimal grid size, it is ten to fifteen times the number of particles calculations.