2D сталкивающееся моделирование n-тела (быстрое Обнаружение коллизий для большого количества шаров)
Я хочу записать программу для моделирования движения высокого количества (N = 1000 - 10^5 и больше) тел (круги) на 2D плоскости. Все тела имеют равный размер, и единственное взаимодействие между ними является упругим соударением.
Я хочу получить что-то как
, но в более широком масштабе, с большим количеством шаров и более плотного заполнения плоскости (не газовая модель как здесь, но что-то как модель кипящей воды).
Таким образом, я хочу быстрый метод обнаружения то число шара i действительно имеет любой другой шар на его пути в 2*radius+V*delta_t расстояние. Я не хочу делать полный поиск коллизии с шарами N для каждого из i шар. (Этот поиск будет N^2.)
PS Извините за анимированный циклом GIF. Просто нажмите Esc для остановки его. (Не будет работать в Chrome).
2 ответа
Этот первый шаг в моделировании физики - обнаружение столкновений в широкой фазе. Существует несколько подходов, описанных здесь Broad-Phase Collision Detection with CUDA, но два основных:
- пространственное разбиение: разделение объектов на сетку
- sort-and-sweep: сортировка всех объектов вдоль двух осей
Очевидно, что вы хотите избежать (N1-)*N проверок на наличие столкновений с каждой итерацией. Простой подход будет заключаться в том, чтобы разделить область на 2D-сетку ячеек, а затем сделать один проход, чтобы выяснить, через какие ячейки проходит каждый шар в текущей итерации. Каждый шар затем проверяет только столкновения с шарами, проходящими через клетки, через которые он проходит.
Я уверен, что есть более сложные подходы, но это может быть хорошим началом.