Rozdzielczość kolizji w przypadku kolizji z wieloma obiektami


15

Mam obiekty statyczne i ruchome. Zderzenia są wykrywane za pomocą twierdzenia o osi oddzielającej.

Na przykład w tej sytuacji mam dwa obiekty statyczne (na czerwono):

wprowadź opis zdjęcia tutaj

i ruchomy obiekt między nimi:

wprowadź opis zdjęcia tutaj

Mój algorytm jest w stanie obliczyć kolizję między dwoma z tych obiektów, a także wyrzuca wektor doskonałej rozdzielczości (co oznacza wektor minimalnego przemieszczenia) na kolizję.

Na przykład, kiedy sprawdzam kolizję między zielonym prostokątem a prawym czerwonym prostokątem, algorytm wyrzuca wektor, który mówi mi, jak muszę przesunąć zielony prostokąt, aby rozwiązać kolizję:

wprowadź opis zdjęcia tutaj

Zauważ, że właśnie szybko narysowałem to w MSPaint, więc na tym zdjęciu może być tak, że wektor minimalnego tłumaczenia wypycha zielony prostokąt na górę, ale zakładam tutaj, że wypycham go w lewo / prawo jest w rzeczywistości krótsze.

Ogólnym sposobem podejścia do tego byłoby rozwiązanie kolizji tylko jednej kolizji na ramkę, zamiast wszystkich naraz. Ale w moim przypadku spowodowałoby to przerzucanie:

Po pierwsze, solver wykrywa dwie kolizje, ale rozwiązuje tylko kolizję między prawym prostokątem a zielonym prostokątem:

wprowadź opis zdjęcia tutaj

Następnie w następnej ramce wykrywa tylko jedną kolizję między lewym czerwonym prostokątem a zielonym prostokątem i rozwiązuje go:

wprowadź opis zdjęcia tutaj

Jak widać, tak naprawdę nie rozwiązuje to kolizji (na przykład wypychając zielony prostokąt do góry), a zamiast tego po prostu nieskończenie przerzuca klapy między dwoma stanami.

Jak mogę to rozwiązać?


W swoim przykładzie używasz prostokątów. Czy Twój algorytm kolizji rozwiązuje kolizję tylko na jednej osi? Jeśli tak, to ma sens, że opisywane zachowanie ma miejsce.
chaosTechnician

Nie, potrafi rozwiązać je dowolnymi kształtami na wszystkich możliwych osiach (nie tylko prostokątami, są one najłatwiejsze do narysowania farbą MS: P) i zawsze znajdzie najkrótszy istniejący wektor, który rozsuwa dwa obiekty .
TravisG

+1 Dobre pytanie. Usunąłem (2D) „tag” z tytułu, należy tego unikać (patrz: meta ).
bummzack,

Odpowiedzi:


7

W zależności od tego, co dokładnie próbujesz osiągnąć (wysoka dokładność fizyczna lub po prostu wystarczająco dokładna symulacja w czasie rzeczywistym), możesz spróbować użyć spekulacyjnych kontaktów.

Oto szczegóły: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

W tym artykule opisuje, co musisz wiedzieć, aby go wdrożyć, i jest to bardzo proste w porównaniu z innymi podejściami (takimi jak rzucanie kuli, a następnie sortowanie rozdzielczości kolizji według czasu uderzenia).

Jeśli potrzebujesz / chcesz więcej, możesz kupić jego kod źródłowy za (IIRC) 7 USD.

Oto wideo z mojej implementacji w 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Zauważ, jak stabilna jest symulacja za pomocą tylko jednej iteracji. Możesz łatwo użyć wielu iteracji na ramkę, aby rozwiązać wiele kolizji do stanu stabilnego, co byłoby dokładniejsze.


2

Możesz najpierw obliczyć wszystkie wektory potrzebne do rozwiązania każdego kolizji, a następnie obliczyć wynikową z nich.

Jedynym przypadkiem, w którym możesz to bajtować, jest to, że te wektory wzajemnie się niwelują, tak jak w twoim przykładzie. W takim przypadku kolizji nie można rozwiązać.


Czy dodać do kolizji mały losowy wektor o wielkości około epsilon * 10? Arytmetyka zmiennoprzecinkowa powinna zrobić resztę.
Martin Sojka,

2
Tak, to chyba działa. Ale może również powodować drgania.
Mihai Maruseac,

1
Mam nadzieję, że nadal mogę uzyskać odpowiedź na to pytanie: obliczenie wyniku rozwiązuje problem „nieskończonej pętli”, ale ponownie wprowadza problem „pęknięcia”, polegający na przesuwaniu się po ścianie wykonanej z płytek o tym samym rozmiarze, co powoduje, że ciało dostaje utknął między „pęknięciami” płytek. Czy istnieje sposób na rozwiązanie obu tych problemów?
Vittorio Romeo

Zgadzam się ... nie ma najlepszej „właściwej odpowiedzi” na rozwiązanie tak niemożliwej kolizji sztywnego ciała. Albo drży, albo dopuszczasz „papkę” w jednym lub kilku obiektach.
David Van Brink,

0

Jeśli przyjrzysz się temu uważnie, ten stan obiektów jest (lub powinien być) nieosiągalny.

Niech lewy czerwony kształt będzie kształtem R1, a prawy czerwony kształt będzie kształtem R2. Niech zielony kształt będzie G.

tzn. biorąc pod uwagę rozmiar i geometrię wszystkich trzech obiektów oraz biorąc pod uwagę, że wszystkie obiekty nie są przenikalne:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Teraz sprowadza się do tego, że jeśli algorytm odpytuje twoje obiekty jeden po drugim, jest to kwestia współbieżności, tj. W pewnym sensie algorytm ma sprawdzać WSZYSTKIE obiekty w tym samym czasie, ale algorytm ogranicza cię do zrobienia obiekty i przetwarzaj je pojedynczo ...

Jeśli G jest sprawdzane względem R1 po sprawdzeniu względem R2, wydaje się, że G legalnie znajduje się po prawej stronie R1 (jeśli G powiedzmy zbliża się do R1 z kierunkiem wektora <-1, -1> z dowolną wielkością (lub odległością) ), ponieważ pozwala na to sprawdzenie między R1 a G, i zapomina o sprawdzeniu między R2 a G, które zostało wykonane wcześniej.

Rozwiązaniem, które możesz zrobić, jest zebranie wszystkich wektorów minimalnego przemieszczenia w tablicy lub dowolnej innej strukturze danych i wybranie takiego, który okaże się legalny dla WSZYSTKICH Obiektów.

Zauważ, że w danej ramce obiekt (na przykład G) może mieć tylko JEDEN kierunek. (o rany, brzmi jak opaska chłopięca ...)

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.