Warsztat.GD

Programowanie => Matematyka i fizyka => Wątek zaczęty przez: cruelmatt w Grudzień 06, 2008, 10:29:00

Tytuł: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 06, 2008, 10:29:00
witam,
chcialbym sie spytac jak mozna wykryc i odpowiedziec na kolizje rysowanych kwadratow jesli mam 2 kwadraty, ktorym sa przypisane zmienne na wszystkie wierzcholki(x1,y1,x2,y2,x3,y3,x4,y4) ??

Matt.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: compawo w Grudzień 06, 2008, 11:55:36
Kolizje na prostokątach (w szczególności kwadratach) testujesz sprawdzając, czy jeden z wierzchołków pierwszego znajduje się w polu drugiego prostokąta.

@2xdown udowodniono wadę tej techniki
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 06, 2008, 12:10:23
wiem, ale czy moglbym dostac jakis przykladowy kod na taka kolizje?

Matt.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: skoti w Grudzień 06, 2008, 12:43:43
Kolizje na prostokątach (w szczególności kwadratach) testujesz sprawdzając, czy jeden z wierzchołków pierwszego znajduje się w polu drugiego prostokąta.
(http://img408.imageshack.us/img408/5743/73663528ry0.th.png) (http://img408.imageshack.us/my.php?image=73663528ry0.png)
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: skalniak w Grudzień 06, 2008, 12:56:14
Cześć możesz zrobić to na wiele sposobów - dwa przytoczę na poczekaniu. Pierwszy to rozpatrywać wiele przypadków - wszystkie które mogą zaistnieć czyli:
1) czy któryś z pkt. jest w polu drugiego itp
2) osobno przypadek z rys. wyżej

Drugim sposobem jest sprawdzanie czy proste się przecinają i czy ma to miejsce na odcinkach łączących wierzchołki.

--
skalniak

Do poczytania:
PS. na forum znalazłem także wątek, który może Ci pomóc: http://forum.warsztat.gd/index.php/topic,1420.0.html
PS2: http://wiki.warsztat.gd/Kolizje_mi%C4%99dzy_prostok%C4%85tami_na_p%C5%82aszczy%C5%BAnie
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: counterClockWise w Grudzień 06, 2008, 14:16:07
witam,
chcialbym sie spytac jak mozna wykryc i odpowiedziec na kolizje rysowanych kwadratow jesli mam 2 kwadraty, ktorym sa przypisane zmienne na wszystkie wierzcholki(x1,y1,x2,y2,x3,y3,x4,y4) ??

Matt.

Ja proponuję tak:

1. Test czy kolidują kule opisane - jeden prosty warunek na promienie. NIE: nie ma kolizji. TAK: idziemy dalej.
2. Test czy kolidują kule wpisane - TAK: jest kolizja. NIE: idziemy dalej.
3. Test na przecięcie (odcinek-odcinek) dla każdego boku kwadrata. Raptem 16 testów, które odpalane będą rzadko, bo wcześniej testujemy kulami :)

wydaje mi się, że to najlepsze i optymalne.


Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Reg w Grudzień 06, 2008, 14:54:02
Jeśli dane są dwa prostokąty r1 i r2, a każdy ma określone mniejsze i większe współrzędne jako odpowiednio left, right, top, bottom, to funkcja która sprawdza czy dwa prostokąty mają część wspólną (kolidują) wygląda tak:

inline bool RectToRect(const RECTF &r1, const RECTF &r2)
{
return
(r1.left <= r2.right) &&
(r1.right >= r2.left) &&
(r1.top <= r2.bottom) &&
(r1.bottom >= r2.top);
}
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Spider100 w Grudzień 06, 2008, 14:57:45
Tylko SAT.. to zaledwie 8 iloczynów skalarnych i parę porównań i wiemy czy cokolwiek się nakłada.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 06, 2008, 15:07:27
no wlasnie w tym problem jak uzyskac prosta skoro rysuje kwadrat samymi wierzcholkami? Mam odejmowac od siebie pozycje wierzcholkow aby uzyskac dlugosc boku?
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: smajler w Grudzień 06, 2008, 15:14:02
ktos keidys dal mi tu na forum funkcje do testowania kolizji prostokat prostokat:
struct OBIEKT{
float x,y,x2,y2;
};

bool Kolizja(OBIEKT kto,OBIEKT z_kim)                 //funkcja do sprawdzania kolizjii
{
     if((kto.x>z_kim.x2)||(kto.x2<z_kim.x)||(kto.y>z_kim.y2)||(kto.y2<z_kim.y)) return false;
     return true;
}

Jeszcze raz podziekuje temu komus:P wtedy uratowal mi zycie ;)
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 06, 2008, 15:22:42
ale ja uzywam do rysowania prostokatow : x1 y1, x2 y2, x3 y3, x4 y4 czyli wspolrzedne kazdego wierzcholka.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: poopa w Grudzień 06, 2008, 16:07:52
No właśnie panowie... To nie muszą być prostokąty równoległe do siebie przecież.

Generalnie do opisu takiego prostokąta nie potrzebujesz aż 4 punktów... wystarczą 3,a  nawet 2 i zwrot ale co tam.

Polcam to samo co Spider... nic innego nie wymyślisz, bo nie warto nawet.

Mniej więcej coś takiego(z głowy):
struct Rect
{
float3 a,b,c,d;
};
/////////////////////
Rect rectA,rectB;
float3 dir=rectA.b-rectA.a;
float length=dir.Length();
float3 point=rectB.a-rectA.a;
float result=Float3::Dot(&point,&dir);
if (result<length)
  if(result>=0.f)
  {
    point=rectB.b-rectA.a;
    result=Float3::Dot(&point,&dir);
    if(result<length)
      if(result>=0.f)
      {
      //itd. itp. ... jak to rozpiszesz to sobie ładnie popatrz i skróć gdzie się da.
      }
  }
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 06, 2008, 16:16:31
nie rozumiem, jestem poczatkujacy i poprostu chcialem sobie napisac mini-ponga, a tak wyglada u mnie rysowanie kwadratu:

glBegin(GL_QUADS);

glTexCoord2f(0.0f, 0.0f);
glVertex3f(player.x1, player.y1, 0.0f);
glTexCoord2f(1.0f, 0.0f);
glVertex3f(player.x2, player.y2, 0.0f);
glTexCoord2f(1.0f, 1.0f);
glVertex3f(player.x3, player.y3, 0.0f);
glTexCoord2f(0.0f, 1.0f);
glVertex3f(player.x4, player.y4, 0.0f);

glEnd();
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Zielony w Grudzień 06, 2008, 16:34:57
No właśnie panowie... To nie muszą być prostokąty równoległe do siebie przecież.
[...]
Polcam to samo co Spider... nic innego nie wymyślisz, bo nie warto nawet.

Oj zaraz nie wymyślisz. Jest bardzo fajna metoda badania z użyciem sumy Minkowskiego, która sprowadza kolizję dwóch n-wymiarowych brył do kolizji punktu (0,0,...,0) z bryłą. Co prawda daleko zbyt skomplikowana dla tego przypadku, ale jest ;]
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: counterClockWise w Grudzień 06, 2008, 19:48:06
Jeśli dane są dwa prostokąty r1 i r2, a każdy ma określone mniejsze i większe współrzędne jako odpowiednio left, right, top, bottom, to funkcja która sprawdza czy dwa prostokąty mają część wspólną (kolidują) wygląda tak:

inline bool RectToRect(const RECTF &r1, const RECTF &r2)
{
return
(r1.left <= r2.right) &&
(r1.right >= r2.left) &&
(r1.top <= r2.bottom) &&
(r1.bottom >= r2.top);
}

A jak prostokąty się poruszają i obracają? Za każdym razem nazywasz współrzędne na nowo?
A jak np. prostokąt przypomina symbol Karo - stoi na jednym z wierzchołków (przekątna pionowo), to co jest wtedy left, right, top, bottom?

(http://thesaurus.maths.org/mmkb/media/png/Rectangle.png)

Jeżeli left i right będą takie jakby ten prostokąt stał na podstawie to mam kontrprzykład,pokazujący że Twoja metoda niestety nie działa :)
Moja metoda działa dla dowolnej transformacji afinicznej prostokąta.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Spider100 w Grudzień 06, 2008, 20:26:22
counterClockWise twoja metoda jest mało optymalna. w dodatku gdy jeden prostokąt jest wewnątrz drugiego nic nie wykryje.

Tak jak wcześniej wspominano SAT albo ostatecznie GJK jeśli ktoś się nudzi :P Jak dla mnie koniec tematu.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: counterClockWise w Grudzień 07, 2008, 00:17:56
counterClockWise twoja metoda jest mało optymalna. w dodatku gdy jeden prostokąt jest wewnątrz drugiego nic nie wykryje.

Jeśli kwadrat (jak w temacie) to jak najbardziej wykryje :) Kula wpisana będzie w kuli wpisanej większego.

Jeśli jest w środku to nie ma kolizji :) No chyba, że traktujemy wnętrze kwadratu jako coś solidnego.

Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: poopa w Grudzień 07, 2008, 06:50:54
Ale test z okręgami wymaga nie taniego pierwiastkowania, generowania na żywo czy tez wcześniej tych okręgów, kółek (mianowicie środka i promienia). W tym wypadku to niepotrzebny narzut. A SAT-em możesz sobie ładnie to pogrupować... A i bardziej przewidywalne to jest.


PS. Kula w dwóch wymiarach? To jakaś nowość, najwiekszym jeszcze to nie wyszło. ;P Of kors żartuje, pewnie chochliki ci coś popsuły. ;)

Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Spider100 w Grudzień 07, 2008, 11:39:00
Aby sprawdzić czy okręgi się nakładają nie potrzebujemy liczyć pierwiastków można przechowywać kwadraty długości promienia i kwadrat odległości miedzy nimi liczyć.

Test okręgów jest jak najbardziej na miejscu przed przejściem do SAT. Co do podziału kolizji na test ogólny i szczegółowy to już pisałem i zapraszam do lektury:
http://forum.warsztat.gd/index.php/topic,6155.0.html :)

Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: Reg w Grudzień 07, 2008, 15:30:35
counterClockWise: To to ja wiem, tylko kwestia czy wcześniej ustaliliśmy że mówimy o kolizji między prostokątami axis-aligned (ja tak sądziłem), czy oriented :P

Cytat: cruelmatt
nie rozumiem, jestem poczatkujacy i poprostu chcialem sobie napisac mini-ponga, a tak wyglada u mnie rysowanie kwadratu:
To w takim razie tym co czeka Cię teraz do nauki jest pojęcie, że rysowanie nie ma nic wspólnego z liczeniem kolizji. Masz w swojej głowie, a także w pamięci gdzieś w jakiejś strukturze danych (tablicy, wektorach, zmiennych, polach klasy) dane tego prostokąta i osobny kod go rysuje, a osobny liczy jego kolizję z innym prostokątem. OpenGL kolizji nie policzy ani też z liczeniem kolizji nie ma nic wspólnego, czy do rysowania używasz OpenGL czy np. DirectX.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 07, 2008, 16:15:13
wiem, ale wlasnie mowie ze mam dane tylko X i Y dla kazdego wierzcholka... Jak je wykorzystac to wykrycia kolizji?
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: counterClockWise w Grudzień 07, 2008, 18:28:29
Ale test z okręgami wymaga nie taniego pierwiastkowania, generowania na żywo czy tez wcześniej tych okręgów, kółek (mianowicie środka i promienia). W tym wypadku to niepotrzebny narzut.

Można wygenerować raz przy utworzeniu prostokąta i przechowywać. Jeśli gra ma 60 fps, to nawet tego nie zauważy, a złożoność pamięciowa w tak małych problemach w dzisiejszych czasach w ogóle nie jest brana pod uwagę :)


PS. Kula w dwóch wymiarach? To jakaś nowość, najwiekszym jeszcze to nie wyszło. ;P Of kors żartuje, pewnie chochliki ci coś popsuły. ;)

Ja używam określeń kula, kostka oraz sympleks do nazwania dowolnego n-wymiarowego kształtu, który w dwóch wymiarach jest odpowiednio kołem, kwadratem i trójkątem.
To powszechne użycie, mogę Ci podać źródła w literaturze, w których jest odniesienie do dwuwymiarowej kuli.

Kula w przestrzeni metrycznej jest zbiorem elementów tej przestrzeni, których odległość (metryka) od pewnego wyróżnionego punktu zwanego środkiem jest niewiększa od promienia.
Czy R^2 nie jest przestrzenią metryczną? Jak najbardziej istnieje 2-wymiarowa kula. Zauważ, że definicja działa dla n-wymiarów i wszystkie chochliki o tym wiedzą.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: cruelmatt w Grudzień 07, 2008, 21:16:47
wasze klotnie mi nie pomagaja... Nadal nie wiem jak wykryc kolizje maja tylko dane o wierzcholkach prostokatu!!!
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: poopa w Grudzień 07, 2008, 22:54:19
Zostało już to napisane... kartka papieru i/lub twoje IDE. Ew. google, podręcznik od matematyki...

Baa nawet masz tutaj kod... a masz głowę? Więc nią rusz. :P

Taki kod to nie tylko klepanie w klawiaturę... To ta najprostsza część. ZRozpisz testy i lecisz. Nie ma drogi na skróty jeśli jej szukasz.
Tytuł: Odp: wykrywanie i odp. kolizji w kwadracie
Wiadomość wysłana przez: yorp w Grudzień 08, 2008, 03:02:02
przechowuj sobie prostokąt jako srodek plus cztery punkty, potem obtaczasz jeden prostokat drugim (to jest cos jak suma minkowskiego...) i robisz test punkt + wektor przesuniecia * prostokat wiekszy.. jak zczaisz o co biega, to jest to bardzo wydajna metoda