Autor Wątek: Dokładna kolizja prostokątów, punkt kolizji  (Przeczytany 2526 razy)

Offline C'mons

  • Użytkownik

# Styczeń 28, 2011, 21:02:01


Szukam metody na sprawdzenie czy i w którym miejscu nastąpiła kolizja, dane mam:
-wektor przesunięcia
-dwa prostokąty

Jak wyżej na rysunku, widzimy że prostokąt może podczas jednej klatki symulacji przejść za ten drugi prostokąt, i nawet nie będzie wiadomo czy na tej trasie winny kolidować. Myślę, że dobrym sposobem jest po prostu znaleźć punkt przecięcia, ale na podstawie jakich danych? I jak wyliczyć wtedy punkt gdzie nastąpiła ta kolizja na trasie? Jakoś nie mogę ogarnąć myśli więc zwracam się do was. Dodam, że prostokąty się nie obracają, definiowane są na podstawie (x,y) oraz szerokość, wysokość, gdzie x i y to lewy górny róg prostokąta.

Mógłbym w zasadzie sprawdzać przecięcia linii (wierzchołek, wierzchołek po przesunięciu) z liniami prostokąta drugiego, ale może zaistnieć też taka sytuacja:



No i wtedy te linie nie przetną linii prostokąta drugiego.

A więc pytaniem jest, jak sprawdzić czy nastąpiła kolizja dwóch prostokątów gdzie jeden z nich przesuwa się o dany wektor, a może podczas jednego przesunięcia ominąć ten drugi prostokąt, oraz jak wyznaczyć punkt w którym nastąpiła kolizja?
« Ostatnia zmiana: Styczeń 28, 2011, 21:05:26 wysłana przez C'mons »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Will

  • Użytkownik

# Styczeń 28, 2011, 22:04:17
Zrób sobie multisampling. Testuj wielokrotnie po linii ruchu obiektu do docelowej pozycji.

Offline _OskaR

  • Użytkownik

# Styczeń 28, 2011, 22:10:39
Możesz po prostu sprawdzać, czy doszło do przecięcia się samych odcinków - parami - tak, aby w każdej parze był jeden poziomy i jeden pionowy odcinek. Pierwszy warunek - czy ypoziomego jest w przedziale y1,y2 pionowego, a potem na odwrót - czy xpionowego leży w przedziale x1,x2 poziomego. Oba warunki spełnione - odcinki się przecinają.
Chyba, że przesunięcie będzie na tyle duże, że jeden wskoczy do drugiego - ale można np. dodatkowo sprawdzać odległość między środkami prostokątów.

Offline counterClockWise

  • Użytkownik

# Styczeń 28, 2011, 22:49:18
Możesz po prostu sprawdzać, czy doszło do przecięcia się samych odcinków - parami - tak, aby w każdej parze był jeden poziomy i jeden pionowy odcinek. Pierwszy warunek - czy ypoziomego jest w przedziale y1,y2 pionowego, a potem na odwrót - czy xpionowego leży w przedziale x1,x2 poziomego. Oba warunki spełnione - odcinki się przecinają.
Chyba, że przesunięcie będzie na tyle duże, że jeden wskoczy do drugiego - ale można np. dodatkowo sprawdzać odległość między środkami prostokątów.

Jeśli chodzi o odcinki zawierające boki, to nie jest dobre rozwiązanie, bo ominie sytuację, gdy w jednym kroku symulacji prostokąt przeskoczył za drugi lub wskoczył do drugiego.

Ja widzę dwa rozwiązania - liczyć tak zwaną obwiednie ruchu, czyli kształt jaki utworzy poruszający się kontur i policzyć przecięcie owych obwiedni, a nie bazowych prostokątów.

Wprowadzić jakąś strukturę podziału przestrzennego, dla której w łatwy sposób będzie można sprawdzić czy między poszczególnymi krokami nastąpiła potencjalna kolizja.

Offline głos

  • Użytkownik

# Styczeń 29, 2011, 01:09:57
hasło do poszukania w google: CCD (Continuous Collision Detection)

Offline C'mons

  • Użytkownik

# Styczeń 31, 2011, 20:21:37
Poczytałem, ale ostatecznie uznałem że próbuję strzelać z armaty do komara, więc pokusiłem się o prostszy model fizyki do mojej gry. Mam teraz inne pytanie. Jak znaleźć punkt zderzenia się w pionie dwóch prostokątów mając dane:
  • Stan początkowy (x,y)
  • Przesunięcie (sx,sy)

dla obu prostokątów.

W załączniku nieco zobrazowane o co mi chodzi.

Offline Will

  • Użytkownik


Offline Liosan

  • Redaktor

# Luty 01, 2011, 12:19:52
Jak znaleźć punkt zderzenia się w pionie dwóch prostokątów mając dane:
  • Stan początkowy (x,y)
  • Przesunięcie (sx,sy)
Równanie na t: Ya + t * SYa = Yb + Hb + t * SYb, linia zderzenia to Ya + t * SYa, zakładając że a to ten dolny. Come on, to nie jest rocket science...

Liosan

Offline yorp

  • Użytkownik
    • ProfessionGG Project

# Luty 15, 2011, 16:40:47
nie mialem czasu czytac forum, generalnie jest banalny sposob uporania sie z kazdym z tych problemow, mianowicie sprowadzenia prostokata do punktu. Jak to uczynic? Obtocz sobie jeden prostokat drugim, w taki sposob zeby srodek prostokatu (zalozmy A), ktory slizga sie po krawedzi drugiego (prostokat B) wyznaczyl nowy obrys. Powstanie w taki sposob figura, ktorej przeciecie sie jednej z krawedzi z oodcinkiem wyznaczonym przez srodek prostokata + wektor przesuniecia, to punkt kolizji, a zarazem czas zderzenia i maksymalne przesuniecie.

Metoda ta jest metoda sumy Minkowskiego. Odrazu dodam, ze polowe krawedzi mozesz odrzucic odrazu poprzez iloczyn skalarny wektora przesuniecia z normalna krawedzi. Dla prostokatow minimalna ilosc testow to 1, maksymalna 3.

Pozdrawiam,
Krzysztof Zgondek

Edit: zapomnialem ze poza tym nie musisz tworzyc calego obrysu, co zmiejszy ilosc krawedzi do odrzucenia ;)
« Ostatnia zmiana: Luty 15, 2011, 16:45:55 wysłana przez yorp »