Jak rozwiązywać zderzenia kształtów złożonych za pomocą SAT?


16

SAT to przyzwoity sposób określania kolizji między dowolnymi wypukłymi wielokątami. Dostaniesz nawet wektor potrzebny do rozwiązania kolizji.

Aby rozwiązać kolizje między złożonymi (nie wypukłymi) kształtami, myślałem o pewnym kształcie złożonym, który składa się z kilku wypukłych wielokątów. Jeśli kolizja występuje w fazie szerokiej (np. Koło kontra koło lub AABB vs AABB), kolizja zostanie rozwiązana poprzez sprawdzenie każdego wielokąta w kształcie złożonym względem każdego wielokąta w innym kształcie złożonym.

Zastanawiam się jednak, jaki jest najlepszy sposób na oddzielenie obiektów? Naiwnym podejściem byłoby po prostu wzięcie wektora o największej wielkości i wykorzystanie go do separacji. Na poniższym zdjęciu będzie to V 2

Przykład SAT 1

Jeśli jednak wektory oddzielające wskazują różne kierunki, kolizja nie może zostać rozwiązana od razu i może wymagać kilku iteracji. Tak więc na następnym zdjęciu oddzielilibyśmy za pomocą V 1, a w innej iteracji przez V 2 (lub coś zbliżonego do V 2 , ponieważ kształt przesunąłby się o wielkość V 1 ).

Przykład SAT 2

To podejście zakończy się niepowodzeniem w przypadku oddzielania wektorów skierowanych w przeciwnych kierunkach lub w przypadku pokazanym na poniższym obrazku:

Przykład SAT 3

Tutaj powtarzalibyśmy w nieskończoność między stanem po lewej stronie a stanem po prawej stronie.

Zadajmy więc prawdziwe pytanie: jakie jest rozsądne podejście do tego problemu? Wydaje mi się, że stosowanie wielokątów złożonych do złożonych kształtów jest rozsądnym pomysłem, ale naprawdę zastanawiam się, jak w takim przypadku rozwiązać kolizje? Jak wykryć ślepą uliczkę, jak pokazano na trzecim obrazku?


Czy możesz wyjaśnić, do czego chcesz użyć tego wektora?
Czy

@Will Wektor powinien zostać użyty do rozwiązania kolizji, aby kształty nie zachodziły na siebie. Mogłem więc przesunąć żółty obiekt o powstały wektor, a dwa obiekty nie kolidowałyby.
bummzack

Odpowiedzi:


7

Myślę, że próbujesz dopasować kwadratowy klucz do okrągłej dziury, stosując SAT tak, jak jesteś tutaj. Oczywiście nie jest przeznaczony do kolizji wklęsło-wklęsłych i chociaż pochwalam twój wysiłek dostosowania go do tego celu, istnieją względy, które sprawiają, że jest mało prawdopodobne, aby działało.

Realizm

Impuls kątowy i jego efekty domina to nazwa tej gry.

Kolejność punktów kontaktowych jest ważna dla realistycznego rozwiązywania kolizji. W prawdziwym świecie jeden z tych punktów zawsze będzie uderzał przed drugim. I tylko naśladując kolejność kontaktów i reprezentowane przez nią „podklasy” można oczekiwać, że uzyskasz realistyczny wynik w symulacji. Jest to jeden z głównych powodów, dla których rozkładasz klepisko na wypukłe, po pierwsze - pozwala ono na częściowe wykrycie, która część uderzyła jako pierwsza. Oczywiście można to również naśladować zgodnie z moim komentarzem pod nagłówkiem „Mniej realizmu”.

Twoje wypukłe urządzenia łączą się, aby nadać obiektowi zarówno kontur, jak i jego środek ciężkości (i oczywiście w bardziej złożonych symulacjach każde urządzenie może również wpływać na gęstość w inny sposób). Powodem, dla którego o tym wspominam, jest to, że realistycznie rozwiązując kolizje, będziesz musiał obliczyć nie tylko liniowy, ale także kątowy impuls, po każdym „zderzeniu podrzędnym” punktów kontaktowych. Nie jest to tak proste, jak podstawowe „rozsuwanie”, które aplikujesz za pomocą SAT.

To całkowicie zmienia naturę problemu, ponieważ, jak widać, bezcelowe jest uzyskiwanie i próba użycia 2 lub więcej punktów kontaktowych, ponieważ tak naprawdę to tylko pierwszy ma znaczenie. Po rozstrzygnięciu pierwszego pod względem impulsu liniowego i kątowego konieczne będzie ponowne obliczenie dla dalszych kolizji, ponieważ orientacje każdego obiektu ulegną zmianie. Co więcej, wykrycie każdego pojedynczego kontaktu na etapie może, ale nie musi, być wykonane w ramach tego samego etapu - w zależności od czasu między stykami, gdy styka się pierwszy punkt styku obiektów, stosowany jest kolejny impuls liniowy i kątowy, drugi punkt kontaktowy dotyka i tak dalej.

Mniej realizmu

Oczywiście, zakładając, że wcale nie jesteś zainteresowany rozwiązywaniem impulsu kątowego, wtedy najlepsze, co możesz zrobić z SAT, staje się zasadniczo tym, co byś zrobił, gdybyś owinął te wielokąty jako wypukłe za pomocą czegoś takiego jak Skan Grahama: Odepchnięcie pojedynczego separatora wektor. Innymi słowy, próba rozwiązania trzech wektorów w tandemie, jak wykazano, nie ma sensu. To największa w grupie, która się liczy.

EDYTUJ w odpowiedzi na twoje pytanie

Jeśli chcesz zastosować uproszczone podejście, musisz:

  • Określ prawidłowy kierunek przemieszczenia. Najłatwiej to zrobić przez wypukłe kadłubowanie każdego i określenie normalnych do osi oddzielającej.

  • Teraz musisz określić wielkość przesunięcia . Dlaczego nie możemy po prostu użyć wielkości podanej przez SAT? Ponieważ, jeśli się nad tym zastanowić, głębokości przenikania będą potencjalnie większe dla kadłubów wypukłych, niż dla ich dopasowanych kadłubów wklęsłych - pomyślcie o dwóch E z zębami w sobie! Jak już zrobiłeś powyżej, znajdź wszystkie punkty kontaktowe dla danego kroku, ale znajdź je równolegle do normalnych osi, ponieważ jest to prawidłowy kierunek przemieszczenia. Teraz określ, który z tych równoległych wektorów nakładających się jest najdłuższy. Odsuń się, odrzuć resztę i przejdź do następnego kroku fizyki.


Myślę, że rozumiem, co masz na myśli. Więc w scenariuszu „mniej realizmu” nie oceniałbym tylko (najkrótszych) wektorów podanych przez SAT dla poszczególnych wielokątów, ale musiałbym również rozważyć inne (większe) nakładki, a w najgorszym przypadku użyć wypukłego kadłuba?
bummzack

Zobacz (ostatnia) edycja.
Inżynier
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.