2D симуляция столкновения n-body (быстрое обнаружение столкновения для большого количества шаров)

Question

Я хочу написать программу для моделирования движения большого числа (N = 1000 - 10 ^ 5 и более) тел (окружностей) на плоскости 2D. Все тела имеют одинаковый размер, и единственное взаимодействие между ними - упругое столкновение.

Я хочу получить что-то вроде , но в большем масштабе, с большим количеством шаров и более плотным заполнением плоскости (не модель газа, как здесь, но что-то вроде модели кипящей воды).

Итак, я хочу быстрый метод обнаружения, что у шара с номером 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

Ширина / длина сетки должны быть больше или равны их радиусу, и поиск должен выполняться по первым соседям (8 + центр = 9 сеток). При минимальном размере сетки, это в десять-пятнадцать раз превышает количество вычисленных частиц.

Answer 3

Очевидно, что вы хотите избежать (N1 -) * N проверок на столкновения с каждой итерацией. Простой подход - разделить область на двумерную сетку ячеек, а затем сделать один проход, чтобы определить, через какие ячейки проходит каждый шарик в текущей итерации. Каждый шар проверяет только столкновения с шарами, проходящими через клетки, через которые он проходит.

Я уверен, что есть более сложные подходы, но это может быть хорошим началом.