2D zderzająca symulacja n-body (szybkie wykrywanie kolizji dla dużej liczby kulek)

Question

Chcę napisać program do symulacji ruchu dużej liczby (N = 1000 - 10^5 i więcej) ciał (kół) w 2D samolot. Wszystkie ciała mają jednakową wielkość, a jedyną interakcją między nimi jest kolizja elastyczna.

Chcę uzyskać coś w rodzaju , ale w większej skali, z większą liczbą kulek i gęstszym wypełnieniem samolotu (nie taki model gazowy jak tutaj, ale coś jak wrzący model wody).

Tak więc chcę szybkiej metody wykrywania, że ​​numer kulki i ma jakąkolwiek inną piłkę na swojej ścieżce w promieniu 2 * promienia + odległość V * delta_t. Nie chcę przeprowadzać pełnego wyszukiwania kolizji z kulkami N dla każdej z kulki i. (To wyszukiwanie będzie N^2.)

PS Przepraszamy za animację w formacie GIF. Wystarczy nacisnąć Esc, aby go zatrzymać. (Nie będzie działać w Chrome).

Answer 1

Pierwszym krokiem w symulacji fizyki jest wykrywanie kolizji w szerokim zakresie. Istnieje kilka podejść opisanych tutaj: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html, ale dwie podstawowe to partycjonowanie przestrzenne, dzielenie obiektów na siatkę lub sortowanie i przeciąganie, które polega na sortowaniu wszystkich obiektów wzdłuż dwóch osi.

Answer 2

Oczywiście należy unikać (N1 -) * N sprawdza kolizje z każdą iteracją. Prostym podejściem byłoby podzielenie obszaru na siatkę 2D komórek, a następnie wykonanie pojedynczego przejścia, aby określić, które komórki każda piłka przechodzi w bieżącej iteracji. Każda piłka sprawdza tylko pod kątem kolizji z kulkami przechodzącymi przez komórki, przez które przechodzi.

Jestem pewien, że istnieją bardziej wyrafinowane podejścia, ale może to być dobry początek.

Answer 3

Szerokość/długość siatki powinna być większa lub równa od ich promienia, a wyszukiwanie powinno dotyczyć 1 sąsiadów (8 + środek = 9 siatek). Przy minimalnym rozmiarze siatki jest to od dziesięciu do piętnastu razy większa liczba obliczeń cząstek.