Autor Wątek: [c++/2d] Kolizja odcinka i wielokąta.  (Przeczytany 3139 razy)

Offline eggman

  • Użytkownik

# Sierpień 12, 2008, 18:51:37
Witam serdecznie!

Piszę aktualnie obsługę kolizji w C++ i szukam najefektywniejszego sposobu na sprawdzenie, czy jest kolizja między wielokątem i odcinkiem (mam już sposób "działający, acz niewydajny").

Ogólnie, najważniejsze założenia algorytmu (wymagane przez program):
1). Odcinek i wielokąt podane jako zbiór punktów kontrolnych (wierzchołków) (x,y).
2). Punkty wielokąta są podane w tablicy sekwencyjnie, tj. punkt[4] leży w bezpośrednim sąsiedztwie punktu punkt[3] i punkt[5].
3). Punkty nie są uporządkowane względem żadnej osi, tj. punkt[0] odcinka/wielokąta może równie dobrze leżeć bardziej na prawo, co na lewo względem punktu punkt[1]

Funkcja ma jedynie sprawdzić, czy nastąpiła kolizja, nie ma wyznaczać punktu przecięcia.
Jeśli jednak jest szybka możliwość na jego bezbolesne wyciągnięcie, proszę o tego zaznaczenie.
 
Gdyby ktoś częstował kodem, o oto dane wejściowe w c++:
struct Point{
short x;
short y;
};

std::vector<Point> poly; //nasz wielokat

Point segment [2]; //nasz odcinek
« Ostatnia zmiana: Sierpień 12, 2008, 18:55:06 wysłana przez eggman »

Offline Mr. Spam

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

Offline menajev

  • Użytkownik
    • Karate Inowrocław

# Sierpień 12, 2008, 18:56:49
Nie wiem, czy jest to najwydajniejsza metoda, ale ja podzieliłem wielokąt na odcinki [wg wierzchołków] i sprawdzałem kolizję metodą Sarrusa [czy jak to się tam zwało].

Offline eggman

  • Użytkownik

# Sierpień 12, 2008, 19:10:52
Chodzi Ci o coś w stylu sprawdzanie dla każdego boku wielokąta kolizji odcinek-odcinek macierzami?

Jeśli tak to chyba nie jest to za wydajne, a poza tym nie działa gdy np. odcinek zawiera się w całości w wielokącie (ale to akurat możemy pominąć).

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Sierpień 12, 2008, 21:16:14
Wydaje mi się, że do kolizji odcinka z wielokątem, tak jak do każdej kolizji brył wypukłych, można użyć Separating Axis Theorem.

Odcinek nie koliduje z wielokątem wtedy i tylko wtedy, gdy wszystkie wierzchołki wielokąta leżą po jednej stronie prostej wyznaczonej przez ten odcinek lub oba końce odcinka leżą po dodatniej/ujemnej stronie (zależnie od przyjętej konwencji) prostej wyznaczonej przez którykolwiek z boków wielokąta. W przeciwnym wypadku kolizja zachodzi.

Offline Spider100

  • Moderator
    • Strona domowa

# Sierpień 12, 2008, 21:28:07
SAT lub GJK sto razy to samo powtarzać a i tak nikt się nie nauczy szukać w tym co już jest na forum...

Offline eggman

  • Użytkownik

# Sierpień 13, 2008, 14:15:36
A ja przypomne że ani razu nie mówiłem o jedynie wypukłych wielokątach...
Sprawdzany wielokąt może być równie dobrze wypukły jak i wklęsły, więc raczej odpada taki SAT np...

I proszę mnie tu nie oskrażać, szukałem po forum  [foch] ;)
Ale mi właśnie chodzi o dokładnie ten przypadek, który opisałem, gdzie punkty nie są uszeregowane wzdłuż osi, a wielokąt może być dowolny (czyli też wklęsły...)
« Ostatnia zmiana: Sierpień 13, 2008, 14:21:29 wysłana przez eggman »

Offline Xion

  • Redaktor
    • xion.log

# Sierpień 13, 2008, 15:00:48
Wystarczy sprawdzić, czy zachodzi jeden z przypadków:

1) Co najmniej jeden z punktów odcinka zawiera się w wielokącie.
2) Odcinek przecina którąś z krawędzi wielokąta.

Jak to sprawdzić, to już mam nadzieję że wiesz lub potrafisz znaleźć/wymyślić.

Offline Haxy.M

  • Użytkownik

# Sierpień 13, 2008, 15:18:09
Ja bym zrobił tak, że podzieliłbym wielokąt na trójkąty i sprawdzał kolizje krańców odcinka z trójkatami. Plusem jest to, że testy są naprawdę szybkie, ale misem jest to, że musiałbyś trochę zmodyfikować wejściowy model (nie wiem na ile to może stanowić problem), nie wykryjesz kolizji gdy oba krańce odcinka sa poza wielokatem (ale wtedy mozesz jeszcze powiedzmy podzielić odcinek na mniejsze odcinki i mieć więcej punktów)

inline bool colisiontest(point p1,point p2,point p3, point p)
{
 //obliczamy wektory
 double px1 = p.x - p1.x;
 double py1 = p.y - p1.y;
 double pz1 = p.z - p1.z;
 double px2 = p.x - p2.x;
 double py2 = p.y - p2.y;
 double pz2 = p.z - p2.z;
 double px3 = p.x - p3.x;
 double py3 = p.y - p3.y;
 double pz3 = p.z - p3.z;
 double x2x1 = p2.x - p1.x;
 double y2y1 = p2.y - p1.y;
 double z2z1 = p2.z - p1.z;
 double x3x2 = p3.x - p2.x;
 double y3y2 = p3.y - p2.y;
 double z3z2 = p3.z - p2.z;
 double x1x3 = p1.x - p3.x;
 double y1y3 = p1.y - p3.y;
 double z1z3 = p1.z - p3.z;
 //mnożenie wektorowe
 double x1x = (y2y1 * pz1) - (z2z1 * py1);
 double y1y = (z2z1 * px1) - (x2x1 * pz1);
 double z1z = (x2x1 * py1) - (y2y1 * px1);
 double x2x = (y3y2 * pz2) - (z3z2 * py2);
 double y2y = (z3z2 * px2) - (x3x2 * pz2);
 double z2z = (x3x2 * py2) - (y3y2 * px2);
 double x3x = (y1y3 * pz3) - (z1z3 * py3);
 double y3y = (z1z3 * px3) - (x1x3 * pz3);
 double z3z = (x1x3 * py3) - (y1y3 * px3);
 //mnożenie skalarne
 double l1 = (x1x * x2x) + (y1y * y2y) + (z1z * z2z);
 double l2 = (x2x * x3x) + (y2y * y3y) + (z2z * z3z);
 double l3 = (x3x * x1x) + (y3y * y1y) + (z3z * z1z);
 //sprawdzamy wynik
 if ((l1 < 0.0) || (l2 < 0.0) || (l3 < 0.0))
 {
  return false;
 }
 return true;
}

Edit:
Punkty p1, p2, p3 to wierchołki trójkąta, a punkt p to sprawdzany punkt.
Troche to zawiłe, ale w smie proste ;)
« Ostatnia zmiana: Sierpień 13, 2008, 15:20:39 wysłana przez Haxy.M »

Offline eggman

  • Użytkownik

# Sierpień 13, 2008, 19:26:00
Wystarczy sprawdzić, czy zachodzi jeden z przypadków:

1) Co najmniej jeden z punktów odcinka zawiera się w wielokącie.
2) Odcinek przecina którąś z krawędzi wielokąta
No to akurat jest fundament ogólny i wspólny ;P
A mi właśnie chodzi o najszybszą metodę na sprawdzenie, czy te warunki zachodzą...

Co do metody z podziałem na trójkąty - dla mnie wygląda na bardziej obciążającą, niż sprawdzanie kolizji odcinek - każdy bok wielokąta (w wypadku gdy 1) nie jest spełnione, bo jak jest, to wszystko już jasne).
A wygląda mi na wolniejszą, bo:
1). Wykonuje te same operacje co kolizja odcinek - bok wielokąta PLUS dodatkowe boki powstałe w wyniku podziału na trójkąty.
2). Wprowadza dodatkowe obliczenia (podział na trójkąty) lub od razu wprowadza nadmiarowe dane (współrzędne niektórych wierzchołków występują w kliku trójkątach lub jednym wielokącie).

Offline Haxy.M

  • Użytkownik

# Sierpień 13, 2008, 23:00:56
Cóż od biedy jeśli nadal sprawdasz punkty odcinka to możesz wziąć dowolną półprostą i sprawdzać ile razy się z karawędziami wielokąta przecina (parzysta - jesteś na zewnątrz, nieparzysta - jesteś w środku).

Offline eggman

  • Użytkownik

# Sierpień 14, 2008, 17:52:31
Cóż od biedy jeśli nadal sprawdasz punkty odcinka to możesz wziąć dowolną półprostą i sprawdzać ile razy się z karawędziami wielokąta przecina (parzysta - jesteś na zewnątrz, nieparzysta - jesteś w środku).
No to jest inaczej podany sposób na sprawdzenie należenia punktu do wielokąta (tyle że ja dla uproszenia zawsze półprostą daję równoległą do osi OY).

Czyli widze, że jednak mój "działający, acz niewydajny sposób" jest jednak najwydajniejszy ;P
A powiem, że sam na niego wpadłem i nawet nie wiedziałem, że to ogólny kanon ;P

Ogólnie dzięki za pomoc przy główkowaniu, teraz wiem, że moja metoda rzeczywiście jest ok :-)
Czyli jak coś to podaje przepis, jakby ktoś jeszcze chciał znać końcowy wynik nie grzebiąc w temacie (pseudokod ;):

dane wejściowe: odcinek AB, wielokąt

if (A e wielokąt [metoda półprostej || OY, zliczanie odcników powyżej])
 JEST KOLIZJA
else if(B e wielokąt)
 JEST KOLIZJA
else
 dla każdego boku wielokąta
  if(AB i bok się przecinają [metoda macierzowa na prostych, zawężenie dziedzin do odcinków])
    JEST KOLIZJA