Algorytmy wykrywania kolizji w wąskich fazach

Istnieją trzy fazy wykrywania kolizji.

1. Broadphase : Pętla między wszystkimi obiektami, które mogą oddziaływać, dozwolone są fałszywe alarmy, jeśli przyspieszyłoby to zapętlenie.

2. Narrowphase : Określa, czy się zderzają, a czasem, jak, nie ma fałszywych trafień

3. Rozdzielczość : rozwiązuje kolizję.

Pytanie, które zadaję, dotyczy wąskiej fazy. Istnieje wiele algorytmów różniących się złożonością i dokładnością.

1. Przecięcie Hitboksa : jest to algorytm a posteriori, który ma najniższą złożoność, ale także nie jest zbyt dokładny,

2. Przecięcie kolorów : Przecięcie Hitboksa dla każdego piksela, a-posteriori, piksele idealne, niedokładne pod względem czasu, większa złożoność

3. Twierdzenie o separacji osi : jest używane częściej, dokładniej dla trójkątów, jednak a-posteriori, ponieważ nie może znaleźć krawędzi, biorąc pod uwagę ostatnią klatkę, jest bardziej stabilna

4. Liniowy raycasting : Algorytm A-priori, przydatny w fizyce o pół realistycznym wyglądzie, znajduje punkt przecięcia, nawet bardziej dokładny niż SAT, ale o większej złożoności

5. Interpolacja splajnu : A-priori, jeszcze bardziej dokładna niż promienie liniowe, jeszcze większa podwójność.

Prawdopodobnie jest wiele innych, o których zapomniałem. Pytanie brzmi, kiedy lepiej używać SAT, kiedy promienie, kiedy splajny i czy jest coś lepszego.

Dwa, których mi brakuje, a które od razu mnie wyróżniają, to GJK i MPR.

GJK jest algorytmem znajdującym najbliższy punkt dwóch wypukłych wielokątów. Przy odrobinie dodatkowej pracy możesz go użyć, aby znaleźć punkty incydentów dla przecinających się obiektów, a tym samym obliczyć kolektor kolizji. Odbywa się to poprzez obcinanie wielokątów, podobnie jak w przypadku SAT, ale GJK oszczędza ci kilku kroków (ponieważ będziesz już miał najbliższe punkty).

MPR (Minkowski Portal Refinement) to kolejny algorytm podobny do GJK (oba używają spacji Minkowskiego). Nie może znaleźć najbliższego punktu między nie przecinającymi się obiektami, takimi jak GJK, ale ma wiele innych fajnych właściwości w grach i jest sposobem na uzyskanie rozmaitości kontaktów.

MPR jest jedną z bardziej popularnych gier. Jest bardzo wydajny, stabilny numerycznie i łatwy do wdrożenia.

Inne wąskie fazy są częściej używane w specjalistycznych grach. Gry wyścigowe zwykle wykorzystują odlewanie promieniowe do modelowania rzeczywistych opon, a uzyskanie realistycznych (a nawet po prostu zabawnych) zachowań nie jest jeszcze możliwe przy użyciu tradycyjnego modelu kolizji i modelowania rozdzielczości. Platformarze zazwyczaj wykorzystują również wysoce spersonalizowane zderzenia i fizykę, ponieważ preferowana fizyka „podobna do Mario” nie jest modelowana za pomocą tradycyjnych algorytmów fizyki. Często widzisz także różne metody zderzeń i fizyki płynów, choć mniej o nich wiem.

Widzieć:

• http://www.codezealot.org/archives/tag/gjk
• http://xenocollide.snethen.com/

Chciałem powiedzieć, że to test Osi Oddzielających , a nie Twierdzenie.

Używałbyś SAT na nieporuszających się wielokątach (2D), chociaż możesz go rozszerzyć, aby poradzić sobie z względnym ruchem liniowym.

http://elancev.name/oliver/2D%20polygon.htm#tut3

Nie używaj GJK w 2D, uważam, że jest on wolniejszy niż brutalne zmuszanie SAT.

Inną techniką, którą możesz zastosować, jest Różnica Minkowskiego, która zmniejsza jeden obiekt do jednego punktu i „rośnie” na drugim kształcie. Następnie testujesz połączony obiekt względem punktu, który jest o wiele łatwiejszy - daje to odległość penetracji i normalną. Uważam, że to narzędzie jest koncepcyjnie bardzo przydatne do rozwiązywania nowych problemów związanych z wykrywaniem kolizji; łatwiejszy do wizualizacji niż SAT.

Do przesuwania i obracania wielokątów (i wielościanów) możesz użyć Postępu zachowawczego, aby znaleźć dokładny czas i punkt kontaktu.

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Możesz przeczytać więcej o tych technikach w tym blogu, który napisałem jakiś czas temu:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Mam nadzieję, że to pomaga!

Na zdrowie, Paul.

To zależy od rodzaju posiadanej gry. Każda z powyższych metod ma swoje własne kompromisy.

Jednak SAT jest dość standardowym doświadczeniem dla bibliotek fizyki ogólnej, np. Box2D korzysta z niego intensywnie (Angry Birds i wiele innych gier korzysta z Box2D).

Warianty przecięcia kolorów zmieszane ze skrzyżowaniem SAT lub Hitbox są używane w grach takich jak Sonic, Megaman z dobrymi wynikami.

Jednak niewiele wiem o punktach 4 i 5.