Autor Wątek: SAT - Detekcja MTD  (Przeczytany 3886 razy)

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 12:10:54
Witam!

Ostatnio zająłem się trochę detekcją kolizji z użyciem SAT'a. Samo wykrywanie kolizji działa bez zarzutu, problem pojawił sie przy wyznaczaniu wektora minimalnego przesunięcia [ MTD - minimum translation distance ] aby nie było kolizji. Problem odkryłem dopiero przy ustalaniu punktów kolizji i dodałem do kodu kilka drawLine() żeby było widać co się tam dzieje. Efekt jest taki, że czasem MTD wyliczany jest dobrze, a czasem beznadziejnie ;) Tutaj kilka screenów:
Krzaki:

A tutaj wyliczone jest dobrze

LEGENDA:
niebieski, biały - obiekty kolidujące
czerwone punkty - punkty najbliższe kolizji. Wyliczane za pomocą wektora MTD dlatego też się krzaczą.
żółta linia - to jest właśnie linia obrazujaca wektor MTD przesunięty tak żeby zaczynał się w punkcie tworzącym kolizję [ czerwony punkt białego obiektu ]

---

Tutaj mam kawałek kodu odpowiedzialny za znalezienie MTD:

Kod: (cpp) [Zaznacz]
ageVector minVec = axes[0];
da = axes[0].sqrLength();
for( int i=1; i < axisCount; i++ )
{
db = axes[i].sqrLength();
if( db < da )
{
minVec = axes[i];
da = db;
}
}
 
axes to wektory wskazujące od punktu powodującego kolizję białego obiektu do ścian niebieskiego obiektu. Oczywiście prostopadłe do tych ścian.

Zupełnie nie wiem gdzie może leżeć problem... Może jest jakiś lepszy sposób na znajdowanie MTD?
No i totalnie nie wiem o co chodzi w kodzie wyznaczającym MTD z tego przykladu: http://uk.geocities.com/olivier_rebellion/Polycolly.zip . Żeby tam chociaż były opisane zmienne które są używane w funkcji... :|

Dzięki za przeczytanie i ew odpowiedzi!

Offline Mr. Spam

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

Offline revo

  • Użytkownik

# Lipiec 06, 2007, 12:23:36
W Pollycolly robione to jest tak, że podczas sprawdzania SAT, liczone są rzuty na poszczególne osie i wyliczany jest czas po jakim nastąpi kolizja na danej osi. Więc najpierw znajdujemy pierwszą kolizję w czasie od 0 do t. Jeśli znaleźliśmy, to normalizujemy wektor osi na którą było robione rzutowanie. Tak możemy zrobić  tylko wtedy, kiedy kolizja nastąpi 'w czasie', pozostaje jeszcze przypadek kiedy wielokąty na siebie nachodzą - wtedy spradzamy jakiej długości są rzuty na poszczególne osie i wybieramy tą, na której rzut jest najmniejszy  - przynajmniej tak to powinno działać, bawiłem się tym kodem już jakiś czas temu.

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 12:25:38
wtedy spradzamy jakiej długości są rzuty na poszczególne osie i wybieramy tą, na której rzut jest najmniejszy  - przynajmniej tak to powinno działać, bawiłem się tym kodem już jakiś czas temu.

Właśnie problem leży w tym, że ten kod który dałem wyżej własnie to powinien robić, a nie robi ;)

Offline ziomber

  • Użytkownik

  • Zbanowany
# Lipiec 06, 2007, 13:39:53
z tych obrazkow da sie wywnioskowac, ze mozna zrobic test dla kazdego odcinka i wybrac najblizszy odcinek.

function ClosestPointOnLine (vA, vB, vPoint : t3dpoint) : t3dpoint;
//Returns the closest point on a line to a given point

var
  vVector1, vVector2, vVector3 : t3dpoint;
  vClosestPoint : t3dpoint;
  D, T : Single;

begin
  //First, we create a vector from our end point vA to our point vPoint
  vVector1.X := vPoint.X - vA.X;
  vVector1.Y := vPoint.Y - vA.Y;
  vVector1.Z := vPoint.Z - vA.Z;

  //Now we create a normalized direction vector from end point vA to end point vB
  vVector2.X := vB.X - vA.X;
  vVector2.Y := vB.Y - vA.Y;
  vVector2.Z := vB.Z - vA.Z;
  vVector2 := Normalize (vVector2);

  //Now we use the distance formula to find the distance of the line segment
  D := n3ddistance(vA, vB);

  //Using the dot product, we project the vVector1 onto the vector vVector2. This essentially
  //gives us the distance of our projected vector from vA
  T := Dot(vVector2, vVector1);

  //If our projected distance from vA, "t",  is greater than or equal to 0, it must be closest to the end point
  //vA.  So we return this end point.
  if (T<=0) then
  begin
    Result := vA;
    exit;
  end;

  //If our projected distance from vA, "t", is greater than or equal to the magnitude or distance of the line
  //segment, it must be closest to the end point vB, so we return vB.
  if (T >=D) then
  begin
    Result := vB;
    exit;
  end;

  //Here we create a vector that is of length T and in the direction of vVector2
  vVector3.X := vVector2.X * T;
  vVector3.Y := vVector2.Y * T;
  vVector3.Z := vVector2.Z * T;

  //To find the closest point on the line, we just add vVector3 to the original end point vA
  vClosestPoint.X := vA.X + vVector3.X;
  vClosestPoint.Y := vA.Y + vVector3.Y;
  vClosestPoint.Z := vA.Z + vVector3.Z;

  Result := vClosestPoint;
end;

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 15:12:32
z tych obrazkow da sie wywnioskowac, ze mozna zrobic test dla kazdego odcinka i wybrac najblizszy odcinek.

Problem w tym, ze nie mam punktu bo on jest wyznaczany za pomocą własnie tego wektora który się krzaczy! ;p

Offline ziomber

  • Użytkownik

  • Zbanowany
# Lipiec 06, 2007, 15:26:56
ale masz boki tego face'a, a tylko te boki są potrzebne i ten punkt co jest w środku tego face'a reszta sama sie obliczy - czyli ten punkt najbliższy (na odpowiednim boku ściany)

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 15:30:26
ale masz boki tego face'a, a tylko te boki są potrzebne i ten punkt co jest w środku tego face'a reszta sama sie obliczy - czyli ten punkt najbliższy (na odpowiednim boku ściany)

No nie mam tego punktu w srodku obiektu. Gdybym mial to wiedzialbym jak to zrobic ;)

// EDIT: twój post podsunal mi pomysl, ze moze zle mam napisane wyznaczanie tych wierzcholkow a nie MTD i okazalo sie ze tak wlasnie jest ;)
Teraz tylko postaram sie rozgryzc dlaczego tamto nie dziala jak nalezy.
« Ostatnia zmiana: Lipiec 06, 2007, 15:33:25 wysłana przez Moriturius »

Offline ziomber

  • Użytkownik

  • Zbanowany
# Lipiec 06, 2007, 15:51:02
<- a to to co? Punkt w środku

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 16:07:16
a to to co? Punkt w środku
tak ale jest wyznaczany na podstawie MTD ktore podobno mi sie pierniczylo.

Ale sie okazalo ze to wlasnie wyznaczanie punktow mam zle a nie wyznaczanie MTD wiec teraz musze przejrzec moj kod do wyznaczania najnizszego punktu w okreslonym kierunku.

BTW: macie jakies pomysly na konkretny algorytm do tego majac dana os i wspolrzedne punktow?
« Ostatnia zmiana: Lipiec 06, 2007, 16:19:05 wysłana przez Moriturius »

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 17:19:50
Wiem ze 2 posty pod rzad to istny skandal, ale dalem zeby bylo wiadomo, ze jest cos nowego ;)

Wymyśliłem sobie taki algorytm do znajdowania tych punktów leżących najniżej w którymś kierunku:

Kod: (cpp) [Zaznacz]
float dpTable[], mind = point[0].dotProduct( axis );
for( int i=0, i < pointCount; i++ ) // policz odleglosci rzutow od poczatku osi i znajdz najmniejsza
{
dpTable[i] = point[ i ].dotProduct( axis );
mind = min( mind, dpTable[i] );
}

int n; // ilosc wierzcholkow
Vector lowest[]; // wspolrzedne wierzcholkow
for( int i=0; i < pointCount; i++ ) // znajdz wszystkie wierzcholki ktorych odleglosc od poczatku osi jest rowna `mind`
{
if( dpTable[i] == mind )
lowest[n++] = point[ i ];
}

Ale on wciaz nie dziala dobrze, moze ja juz jestem zmeczony i zrobilem jakis glupi blad w tym?
> Help < ;)
« Ostatnia zmiana: Lipiec 06, 2007, 17:25:11 wysłana przez Moriturius »

RageX

  • Gość
# Lipiec 06, 2007, 17:39:22
Proponuje kupic ksiazke "podstawy programowania" czy cos w tym stylu :)
A tak na serio to trzymaj dwie listy posortowane wedlug osi x,y wtedy bedziesz mial zlozonosc znalezienia punktu O(1), i jedynie zlozonosc dodania nowego punktu O(log(n))

RageX

  • Gość
# Lipiec 06, 2007, 17:49:48
Hmm, może źle dot product liczysz (do rzutowania jeden z odcinków musi miec długość równą jednostce - przypominam tylko).

W gruncie rzeczy (jesli dobrze rozumiem) po etapie sprawdzenia czy się zawiera.... chcesz wyliczyć odległość od najbliższego boku(znaczy się jak głęboko się zawiera w tym prostokącie).

Założenie: Masz dotProducty (wynik rzutowania na odcinek)...

Skalujesz znormalizowany kierunek danego odcinka przez wynik rzutowania... to ci zwraca te najbliższe punkty na bokach.

Liczysz odległości od twojego punktu do tamtych punktów... szukasz najkrótszego.

Jest to obliczeniożerne... znaczy się pogłówkuj jak to uprościć(np. liczenie odległości między odcinkami jest trochę "drogie").

Offline Moriturius

  • Użytkownik

# Lipiec 06, 2007, 18:08:29
A tak na serio to trzymaj dwie listy posortowane wedlug osi x,y wtedy bedziesz mial zlozonosc znalezienia punktu O(1), i jedynie zlozonosc dodania nowego punktu O(log(n))
Ale ja chce mieć to dla dowolnej osi, więc ten pomysł odpada ;]

Cytat: RageX
do rzutowania jeden z odcinków musi miec długość równą jednostce
Mało tego, musi to być ten wektor na który rzutujesz! ;) Ale to tylko w przypadku kiedy chcesz wyliczyc dokladne wspolrzedne. Dot product zwraca Ci długość tego wektora zrzutowanego, wiec jesli chcesz miec zrzutowane wspolrzedne to jesli wektor osi jest jednostkowym to wystarczy przemnozyc wspolrzedne i juz ;) Jesli interesuje mnie tylko dlugosc zrzutowanego wektora to wektor osi nie musi byc jednostkowy.

Ale mi chodzi już tylko o algorytm do znajdowania punktów leżących najniżej dla podanej osi
« Ostatnia zmiana: Lipiec 06, 2007, 18:10:59 wysłana przez Moriturius »

Offline Spider100

  • Moderator
    • Strona domowa

# Lipiec 07, 2007, 00:03:40
Witam!

Heh ... fajnie wszystko tylko, że jeśli to ma być wykrywanie kolizji do fizyki to i tak nic z tych pomysłów nie będzie :D

Powód prosty, nie wystarczy wykryć jednego punktu najbliższego, bo fizyka będzie niestabilna, więc potrzebne dwa punkty podparcia i robi się to przez przycinanie ścian albo stosując pewne uproszczenia założenia dotyczące geometrii, ale ja nie o tym chciałem pisać, bo problem jest inny.

Jak wykryć punkty?

Mamy dwa obiekty składające się z punktów wiec rzutujemy kolejno wierzchołki jednego na oś separacji później drugiego drugiego.

Wyznaczamy dla tych rzutów osobnych obiektów maksymalne i minimalne wychylenie oraz bierzemy informacje o wierzchołkach, które właśnie miały ostatnio wpływ na maksimum i minimum.
Mając rzuty na osi separacji możemy porównać je dokładnie tak jak boundingboxy tyle ze w 1d. Wiemy czy wykryto kolizje, jeśli tak to punktami odpowiedzialnymi są właśnie te, które wpłynęły na wygląd rzutów.

Koniec
Życzę powodzenia!
Spider ^*^

Offline Moriturius

  • Użytkownik

# Lipiec 07, 2007, 00:22:22
Heh ... fajnie wszystko tylko, że jeśli to ma być wykrywanie kolizji do fizyki to i tak nic z tych pomysłów nie będzie :D

Nie potrzebuje calej fizyki, narazie tylko kolizje i informacje o kolizjii. Potem moze pomysle o reszcie :)
BTW: nadal nie wiem jak wyznaczyc punkty najnizsze wzdluz dowolnej osi. Chyba jutro nad tym popracuje. Tam musi byc cos wybitnie prostego.

Koniec
Życzę powodzenia!
Spider ^*^

Dzieki. Przyda sie :)