Czy wykrywanie kolizji jest zawsze O (n ^ 2)?

Czy silnik fizyki jest w stanie zmniejszyć tę złożoność, na przykład grupując obiekty znajdujące się blisko siebie i sprawdzając kolizje w tej grupie zamiast ze wszystkimi obiektami? (na przykład odległe obiekty można usunąć z grupy, patrząc na jej prędkość i odległość od innych obiektów).

Jeśli nie, to czy kolizja jest trywialna dla sfer (w 3d) lub dysku (w 2d)? Czy powinienem utworzyć podwójną pętlę, czy zamiast tego utworzyć tablicę par?

EDYCJA: Czy w przypadku silnika fizyki, takiego jak pocisk i box2d, wykrywanie kolizji jest nadal O (N ^ 2)?

Podział przestrzenny jest zawsze w najgorszym przypadku O (N ^ 2) i na tym polega złożoność informatyki.

Istnieją jednak algorytmy działające w czasie liniowym O (N) . Wszystkie oparte są na jakiejś linii zamiatania.

Zasadniczo musisz posortować obiekty według jednej współrzędnej. Powiedzmy, że X. Jeśli wykonujesz sortowanie za każdym razem przed wykryciem kolizji, złożoność będzie wynosić O (N * logN). Sztuką jest sortowanie tylko wtedy, gdy dodajesz obiekty do sceny, a później, gdy coś się zmienia. Sortowanie po ruchu nie jest trywialne. Zobacz poniższy link, aby zapoznać się z algorytmem, który wprawia w ruch i nadal działa w czasie liniowym.

Następnie zamiatasz od lewej do prawej. Za każdym razem, gdy linia przeciągnięcia przecina początek obiektu, umieszczasz go na liście tymczasowej. Za każdym razem, gdy linia przeciągnięcia wychodzi z obiektu, wyjmujesz go z listy. Kolizje są uwzględniane tylko na tymczasowej liście.

Naiwna linia przeciągania to O (N ^ 2) również w najgorszym przypadku (sprawiasz, że wszystkie obiekty rozciągają się na całą mapę od lewej do prawej), ale możesz zrobić to O (N), czyniąc ją mądrzejszą (patrz link poniżej). Naprawdę dobry algorytm będzie dość złożony.

Oto prosty schemat działania linii przeciągnięcia:

Linia przesuwa się od lewej do prawej. Obiekty są sortowane według współrzędnej X.

• Przypadek pierwszy: Sprawdzane są pierwsze dwa obiekty. Nie ma niczego ważniejszego.
• Przypadek drugi: pierwszy obiekt został sprawdzony i zniknął z listy. Dwa i trzy są sprawdzane.
• Przypadek trzeci: nawet jeśli ten obiekt koliduje, nie sprawdzamy.
• Przypadek czwarty: Ponieważ sprawdzamy w tym przypadku!

Algorytmy tego typu mają złożoność O (C * N) = O (N).

Źródło: Dwa lata kursów geometrii obliczeniowej.

W wykrywaniu kolizji nazywa się to zwykle Sweep and Prune , ale rodzina algorytmów linii Sweep jest przydatna w wielu innych dziedzinach.

Dalsza zalecana lektura, która moim zdaniem jest poza zakresem tego pytania, ale mimo to interesująca: Wydajne wielkoskalowe metody przeciągania i przycinania z wstawianiem i usuwaniem AABB - W tym artykule przedstawiono ulepszony algorytm przeciągania i przycinania, który wykorzystuje wyrównane do osi ramki ograniczające (AABB ) z sortowaniem uwzględniającym ruch. Algorytm przedstawiony w pracy działa w czasie liniowym.

Zauważ teraz, że jest to najlepszy algorytm w teorii . To nie znaczy, że jest używany. W praktyce algorytm O (N ^ 2) z podziałem przestrzennym będzie miał lepszą wydajność pod względem prędkości w typowym przypadku (zbliżonym do O (N)) i pewne dodatkowe wymagania dotyczące pamięci. Wynika to z faktu, że stała C w O (C * N) może być bardzo wysoka! Ponieważ zwykle mamy wystarczającą ilość pamięci, a typowe przypadki mają obiekty rozmieszczone równomiernie w przestrzeni - taki algorytm wykona LEPIEJ. Ale O (N) jest odpowiedzią na pierwotne pytanie.

Nie. Wykrywanie kolizji nie zawsze jest O (N ^ 2).

Załóżmy na przykład, że mamy przestrzeń 100 x 100 z obiektami o rozmiarze 10x10. Możemy podzielić tę przestrzeń na komórki 10x10 za pomocą siatki.

Każdy obiekt może znajdować się w maksymalnie 4 komórkach siatki (może zmieścić się w bloku lub znajdować się „między” komórkami). Możemy przechowywać listę obiektów w każdej komórce.

Musimy tylko sprawdzić, czy w tych komórkach nie ma kolizji. Jeśli istnieje maksymalna liczba obiektów na komórkę siatki (powiedzmy, nigdy nie ma więcej niż 4 obiektów w tym samym bloku), to wykrywanie kolizji dla każdego obiektu to O (1), a wykrywanie kolizji dla wszystkich obiektów to O (N).

To nie jedyny sposób na uniknięcie złożoności O (N ^ 2). Istnieją inne metody, bardziej odpowiednie dla innych przypadków użycia - często wykorzystujące struktury danych oparte na drzewach.

Algorytm, który opisałem, jest jednym rodzajem podziału przestrzeni , ale istnieją inne algorytmy podziału przestrzeni. Zobacz Rodzaje struktur danych partycjonujących przestrzeń, aby uzyskać więcej algorytmów, które unikają czasowej złożoności O (N ^ 2).

Zarówno Box2D, jak i Bullet obsługują mechanizmy, aby zmniejszyć liczbę sprawdzanych par.

Z instrukcji , rozdział 4.15:

Przetwarzanie kolizji na etapie fizyki można podzielić na fazę wąską i fazę szeroką. W fazie wąskiej obliczamy punkty styku między parami kształtów. Wyobraź sobie, że mamy N kształtów. Używając brutalnej siły, musielibyśmy wykonać fazę wąską dla par N * N / 2.

Klasa b2BroadPhase zmniejsza to obciążenie, używając drzewa dynamicznego do zarządzania parami. To znacznie zmniejsza liczbę połączeń w fazie wąskiej.

Zwykle nie wchodzisz w interakcję bezpośrednio z fazą szeroką. Zamiast tego Box2D tworzy wewnętrznie fazę szeroką i zarządza nią. Ponadto b2BroadPhase został zaprojektowany z myślą o pętli symulacyjnej Box2D, więc prawdopodobnie nie nadaje się do innych przypadków użycia.

Z Bullet Wiki :

Istnieją różne rodzaje algorytmów szerokofazowych, które ulepszają naiwny algorytm O (n ^ 2), który zwraca pełną listę par. Te zoptymalizowane fazy szerokopasmowe czasami wprowadzają jeszcze więcej nie kolidujących par, ale równoważy to ich ogólnie poprawiony czas wykonania. Mają różne charakterystyki wydajności i żadna nie przewyższa innych we wszystkich sytuacjach.

Dynamiczne drzewo AABB

Jest to zaimplementowane przez btDbvtBroadphase w Bullet.

Jak sama nazwa wskazuje, jest to dynamiczne drzewo AABB . Jedną użyteczną cechą tej fazy jest to, że struktura dynamicznie dostosowuje się do wymiarów świata i jego zawartości. Jest bardzo dobrze zoptymalizowany i jest bardzo dobrą szerokofazową funkcją ogólnego przeznaczenia. Obsługuje dynamiczne światy, w których wiele obiektów jest w ruchu, a dodawanie i usuwanie obiektów jest szybsze niż SAP.

Sweep and Prune (SAP)

W Bullet jest to zakres klas AxisSweep. Jest to również dobra faza ogólna ogólnego zastosowania, z ograniczeniem, że wymaga ustalonej wielkości świata, znanej z góry. Ta szerokopasmowa faza ma najlepszą wydajność w typowych światach dynamiki, w których większość obiektów ma niewielki ruch lub nie ma go wcale. Zarówno btAxisSweep3, jak i bt32AxisSweep3 kwantyzują punkty początkowe i końcowe dla każdej osi jako liczby całkowite zamiast liczb zmiennoprzecinkowych, aby poprawić wydajność.

Poniższy link jest ogólnym wprowadzeniem do Broadphase, a także opisem algorytmu Sweep i Prune (chociaż nazywa to „Sort and Sweep”):

http://www.ziggyware.com/readarticle.php?article_id=128

Zobacz także stronę Wikipedii:

http://en.wikipedia.org/wiki/Sweep_and_prune

O (N ^ 2) odnosi się do faktu, że jeśli masz N obiektów, zastanawianie się, co koliduje z najgorszym przypadkiem obliczeń kolizji N ^ 2. Powiedz, że masz 3 przedmioty. Aby znaleźć „kto uderza kogo”, musisz znaleźć:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

To 6 kontroli kolizji lub kontroli N * (N-1). W analizie asymptotycznej rozwiniemy wielomian i przybliżymy go jako O (N ^ 2). Jeśli miałbyś 100 obiektów, to byłoby to 100 * 99, co jest wystarczająco blisko 100 * 100.

Jeśli więc na przykład podzielisz przestrzeń za pomocą oktetu, średnia liczba porównań między ciałami zostanie zmniejszona. Jeśli jest możliwe, aby wszystkie obiekty zgromadziły się na bardzo małym obszarze (powiedzmy, że wykonujesz jakąś symulację przepływu cząstek, gdzie cząstki mogą gromadzić się w tym samym obszarze), wówczas O (N ^ 2) może nadal występować w punkty w symulacji (w których punktach spowolnienie).

Tak więc cały punkt O (N ^ 2) wynika z natury każdego ciała sprawdzającego każde inne ciało w scenie. Taka jest natura obliczeń. Wiele rzeczy może jednak pomóc uczynić to tańszym. Nawet wykres sceny (powiedzmy wykrywanie między obiektami tylko w tym samym pomieszczeniu ) znacznie zmniejszy liczbę obliczeń kolizji, które należy wykonać, ale nadal będzie to O (M ^ 2) (gdzie M jest liczbą obiektów w pomieszczeniu wykryta kolizja). Sferyczne objętości graniczne sprawiają, że początkowa kontrola jest bardzo szybka ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), więc nawet jeśli wykrywanie kolizji to O (N ^ 2), obliczenia sfery granicznej prawdopodobnie nastąpią bardzo szybko.