二維碰撞n體模擬（大量球的快速碰撞檢測）

Question

我想編寫一個程序，用於模擬2D上高數量（N = 1000 - 10^5個以上）物體（圓）的運動平面。所有的身體都有相同的尺寸，它們之間唯一的相互作用是彈性碰撞。

我想得到類似於的東西，但是在更大的範圍內，有更多的球和更密集的飛機填充物（不是像這裏的氣體模型，而是像沸水模型一樣）。

所以我想要一個快速的檢測方法，球號碼i在2 *半徑+ V * delta_t距離內的路徑上確實有任何其他球。我不想用N球對i球進行全面搜索。 （此搜索將是N^2。）

PS對不起，爲循環動畫GIF。只需按Esc即可停止。 （在Chrome中無法使用）。

Answer 1

物理模擬的第一步是寬相碰撞檢測。這裏有幾種方法http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html，但是兩個基本的方法是空間分割，將對象分成網格或排序和掃描，其中包括沿着兩個軸對所有對象進行排序。

Answer 2

顯然你想避免（N1 - ）* N檢查與每次迭代的衝突。一個簡單的方法是將區域劃分爲二維網格單元格，然後進行一次單獨遍歷以確定每個球在當前迭代中通過哪些單元格。然後每個球只檢查與穿過它的細胞的球碰撞。

我相信有更復雜的方法，但這可能是一個好的開始。

Answer 3

網格寬度/長度應大於或等於它們的半徑，搜索應該在第1個鄰居（8 + center = 9個網格）上。使用最小的網格尺寸，它是粒子計算數量的十到十五倍。