Programowanie w języku Delphi » Artykuły

Gry 3D, Kolizja Sferyczna

To jest na razie zalążek artykułu, będzie więcej bo trzeba jeszcze napisać tzw. Collision RESPONSE, czyli zaprogramować sferę odbijającą się od świata 3D w poprawny sposób: (jeszcze nad tym myśle)

Swoją drogą może ktoś ma pomysły to niech je doda, jakby to miało być wykonane, ja mam kilka koncepcji ale nie chce mi sie ich implementować :0

Żeby cokolwiek z tego połapać trzeba znać absolutne podstawy rysowania świata 3D i operacji matematycznych?

Teraz co nam jest potrzebne do poprawnego obsłużenia tej kolizji (bez collision response)
Nasz świat powinien się składać z tablic wierzchołków tzn.
Jest główna tablica (ściany), która zawiera w sobie jeszcze tablicę wierzchołków sceny.

Teraz zacznijmy już omówienie algorytmu :0

Co mamy: mamy tablice z wierzchołkami, sferę (na razie o jednym promieniu bo to nie elipsoida) i o pewnym środku.


Przyjrzyjmy się przykładowi trójkąta do testu:

(*

FACE SPACE PARTITION  [NOT ONLY FOR TRIANGLES, TECHNIQUE WILL WORK ON CONVEX POLYGONS]

ex.

\  b |
 \    |
   \  |
     \|
      .       b
      |\
      |  \
  b  |    \
      | T   \
      |       \
      |_____\
      |          \
      |   b       \
      |             \





  • )

Na rysunku widać b i T, b - to obszar poza testowaną ścianą, T - to obszar w środku ściany


Najpierw tworzymy pętle for, która będzie przelatywała (przez wszystkie ściany w tablicy [nie wierzchołki])
Sprawdzamy czy ściana jest zwrócona przodem do środka testowanej sfery jak tak to idziemy dalej

Tworzymy wektor odwrócony od normalnej ściany (zmieniamy znak każdej współrzędnej [np. p(1,3,-32) to po odwróceniu będzie p(-1,-3,32)]) = odwracamy znak wektora normalnego ściany i mnożymy przez jakąs stałą większą niż 1000
Mnożymy ten wektor przez skalar najlepiej jakiś duży (bo powinniśmy mieć znormalizowaną normalną ściany tzn. Długości powinny być w zakresie od 0 do 1)

wektor.x := -100000*model.face_normal[face_index].x;
wektor.y := -100000*model.face_normal[face_index].y;
wektor.z := -100000*model.face_normal[face_index].z;



Rzucamy promień od środka sfery w kierunku testowanej ściany. Sprawdzamy czy promień przebija ścianę jak przebija znajdujemy się w obszarze T, jak nie to jesteśmy w obszarze b
Jak jesteśmy w T i znaleźliśmy kolizje to powinniśmy zakończyć test (po uprzednim sprawdzeniu czy odległość punktu kolizji promienia jest mniejsza lub równa promieniowi sfery) i zwrócić odpowiednie wartości kolizji, ale mój kod sprawdza wszystkie trójkąty i dodatkowo wybiera ten najbliższy... ale to powinno sie wykonywać w osobnej funkcji dlatego zwracamy i dajemy exit;

Teraz jak nie jesteśmy w obszarze T to jesteśmy na bank w obszarze b, teraz przechodzimy do sprawdzenia czy jesteśmy wystarczająco blisko ściany, że możemy wykonać kolizję:
Do tego będą nam potrzebne 3 tablice dynamiczne: Nadajemy im długość równą ilości wierzchołków testowanej ściany.
setlength(DYSTANS_WIERZCHOLKI,model.facelength[face_index]);// : array of single;
setlength(DYSTANS_BOKI,model.facelength[face_index]);
setlength(uber_point,model.facelength[face_index]);


Teraz nowa pętla w pętli: FOR przez wszystkie wierzchołki w tej ścianie
for i:=0 to high(model.arrays[face_index]) do  begin
DYSTANS_WIERZCHOLKI[i] := n3ddistance(model.arrays[face_index][i].vertex3f,punkt);// Obliczamy odległość każdego wierzchołka od sfery
 
//A ten kod niżej sprawdza, odległość sfery od każdego boku ściany każdy bok to: jeden wierzchołek i drugi wierzchołek :)
 
if i <> high(model.arrays[face_index]) then     begin
uber_point[i] := ClosestPointOnLine(model.arrays[face_index][i].vertex3f,model.arrays[face_index][i+1].vertex3f,punkt);
DYSTANS_BOKI[i] :=  n3ddistance(punkt,uber_point[i])  end else begin
 
uber_point[i] := ClosestPointOnLine(model.arrays[face_index][i].vertex3f,model.arrays[face_index][0].vertex3f,punkt);
DYSTANS_BOKI[i] :=  n3ddistance(punkt,uber_point[i]); end;
 
end;



następnie szuka się najbliższego dystansu od sfery: w zależności mamy do wyboru 2 przypadki:
Gdy wierzchołek jest najbliżej sfery, lub gdy bok jest najbliżej sfery (środka sfery pamiętajcie!; nie sfery)
Czyli tworzymy tablice array of single (float) i jedna ma długość ilości boków a druga długość ilości wierzchołków
Sprawdzamy każdy dystans funkcja n3ddistance :S dystans czyli odległość środka sfery od Boku lub wierzchołka.

i szukamy w tych dwóch tablicach najmniejszej wartości i zapisujemy numer indeksu, teraz trik albo zwracamy najbliższy punkt kolizji, albo mówimy funkcji czy odbija sie od boku lub wierzchołka do wyboru do koloru

Później po znalezieniu tego najbliższego dystansu (i trzeba jeszcze odpowiednio nauczyć grę, żeby wiedziała, czy chodzi o bok czy o wierzchołek i o który chodzi), sprawdzamy czy dystans, który mamy jest mniejszy lub równy promieniowi sfery jak jest to mamy kolizje, jak nie to nasza pierwsza pętla przechodzi do następnej ściany.

Na razie tylko tyle, wasze pytania i prośby o rozbudowę będą czytane tez już nie wiem co mam dodać to tego.

Oto nasza funkcja sprawdzająca:
function SPHERE_INTERSECT_POLYGON(
punkt : t3dpoint;sphere_radius: single; model : tglarrayselectionmodel;
var FACE_INTERSECTIONPOINT : t3dpoint; face_index: integer;
var vRESULT : t3dpoint): boolean;
var
wektor : t3dpoint;
i : integer;
face_arr :  boolean;
cnt:integer;
base_side : integer;
BASE_DISTANCE : single;
BASE_DVOLUME_INDEX : single;
k:integer;
DYSTANS_WIERZCHOLKI : array of single;
NAJBLIZSZY_WIERZCHOLEK : integer;   tnW : single;
NAJBLIZSZY_BOK : integer;                         tnb:single;
DYSTANS_BOKI        : array of single;
uber_point :array of t3dpoint;
BY_VERTEX : BOOLEAN; //jak true to wtedy odbijamy sie od wierzchołka nie od boku
ODLEGLOSC_VERTEX : single;
ODLEGLOSC_BOK : single;
ODLEGLOSC_VOLUME : single;
begin
k:=-1;
 
BASE_DISTANCE := 1000000000000;
cnt:= -1;
result := false;
face_arr:=false;
tnW := 1000000000000;
tnb := 1000000000000;
 
if classifyapointagainstaplane(punkt,model.FACE_NORMAL[face_index],model.face_distance[face_index]) = isBACK then  exit;
JESTEM_W_OBSZARZE_T := true;
 
 
wektor.x := -100000*model.face_normal[face_index].x;
wektor.y := -100000*model.face_normal[face_index].y;
wektor.z := -100000*model.face_normal[face_index].z;
 
if  IntersectedPolygon(model.colarrays[face_index],
[punkt,vectors_add(punkt,wektor)],model.facelength[face_index]) = true then begin
//face_dist := n3ddistance(punkt,temp_intersect_v);
FACE_INTERSECTIONPOINT  := temp_intersect_v;
vRESULT :=normalize(vectorAB(FACE_INTERSECTIONPOINT,punkt));
 
if n3ddistance(FACE_INTERSECTIONPOINT,punkt) <= sphere_radius then begin
result:=true;
end else result:=false;
end else result:=false;
 
 
 
if result = true then exit;
//jak mamy koolizje sfera - wierzcholek
//NAJPIERW POBIERAMY WSZYSTKIE ODLEGŁOŚCI OD TROJKĄTA CZY TAM FACE"A
setlength(DYSTANS_WIERZCHOLKI,model.facelength[face_index]);// : array of single;
setlength(DYSTANS_BOKI,model.facelength[face_index]);
setlength(uber_point,model.facelength[face_index]);
 
for i:=0 to high(model.arrays[face_index]) do  begin
DYSTANS_WIERZCHOLKI[i] := n3ddistance(model.arrays[face_index][i].vertex3f,punkt);// <= sphere_radius then   begin
 
if i <> high(model.arrays[face_index]) then     begin
uber_point[i] := ClosestPointOnLine(model.arrays[face_index][i].vertex3f,model.arrays[face_index][i+1].vertex3f,punkt);
DYSTANS_BOKI[i] :=  n3ddistance(punkt,uber_point[i])  end else begin
 
uber_point[i] := ClosestPointOnLine(model.arrays[face_index][i].vertex3f,model.arrays[face_index][0].vertex3f,punkt);
DYSTANS_BOKI[i] :=  n3ddistance(punkt,uber_point[i]); end;
 
end;
 
for i:=0 to high(model.arrays[face_index]) do   begin
 
 
if DYSTANS_WIERZCHOLKI[i] < tnw then begin
tnw := DYSTANS_WIERZCHOLKI[i];
NAJBLIZSZY_WIERZCHOLEK := i;
end;
 
 
if DYSTANS_BOKI[i] < tnb then begin
tnb := DYSTANS_BOKI[i];
NAJBLIZSZY_BOK := i;
end;
                              end;
ODLEGLOSC_VERTEX := n3ddistance(punkt,model.arrays[face_index][NAJBLIZSZY_WIERZCHOLEK].vertex3f);
ODLEGLOSC_BOK := n3ddistance(punkt,uber_point[NAJBLIZSZY_BOK]);
if  ODLEGLOSC_VERTEX <= sphere_radius then begin
result := true;  end;
 
if  ODLEGLOSC_BOK <= sphere_radius then begin
result := true;    end;
 
 
if odleglosc_vertex <= odleglosc_bok then
BY_VERTEX := true else BY_VERTEX := false;
 
 
 
 
 
if BY_VERTEX then begin                    
FACE_INTERSECTIONPOINT := model.arrays[face_index][NAJBLIZSZY_WIERZCHOLEK].vertex3f;
vRESULT :=normalize(vectorAB(FACE_INTERSECTIONPOINT,punkt));
//face_dist := n3ddistance(punkt,temp_intersect_v);
end else begin
FACE_INTERSECTIONPOINT   := uber_point[NAJBLIZSZY_BOK];
vRESULT :=normalize(vectorAB(FACE_INTERSECTIONPOINT,punkt));
end;
 
end;



A teraz reszta funkcji, bez których to by nie działało:
function n3ddistance(first_point, second_point : t3dpoint)      : single;overload;
begin
result := sqrt(sqr(first_point.x-second_point.x)+sqr(first_point.y-second_point.y)+sqr(first_point.z-second_point.z));
end;
 
 
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;
 
 
//FUNKCJA RZUCA PROMIEŃ podajemy vPoly czyli tablicę z wierzchołkami, vLine to dwa t3dpoint (początek i koniec promienia), VerticeCount to ilosc wierzcholkow = dlugosc tablicy vPoly
 
u siebei w kodzie mam tak ze zmienne w tej funklcji:
CLIP_INTERSECT_POS itemp_intersect_v; sa zmiennymi globalnymi bo w tej funkcji nie ma zwrocenia punktu przecięcia promienia z polygonem. A jak przypiszemy im (zmiennym) punkt przecięcia to bedziemy mogli go wykorzystac.
 
function IntersectedPolygon(vPoly : array of t3dpoint; vLine : array of t3dpoint; verticeCount : integer):boolean;
const
  MATCH_FACTOR : Extended = 0.9999999999;
var
  vNormal : t3dpoint;
  vIntersection : t3dpoint;
  originDistance : Extended;
  distance1 : Extended;
  distance2 : Extended;
  vVector1 : t3dpoint;
  vVector2 : t3dpoint;
  m_magnitude : Double;
  vPoint : t3dpoint;
  vLineDir : t3dpoint;
  Numerator : Extended;
  Denominator : Extended;
  dist : Extended;
  Angle,tempangle : Extended;
        vA, vB : t3dpoint;
  I : integer;
  dotProduct : Extended;
  vectorsMagnitude : Extended;
begin
CLIP_POS.x := vline[0].x;
CLIP_POS.y := vline[0].y;
CLIP_POS.z := vline[0].z;
        vNormal.X := 0;
  vNormal.Y := 0;
  vNormal.Z := 0;
 
        originDistance := 0;
  distance1 := 0;
  distance2 := 0;        
  vPoint.X := 0;
  vPoint.Y := 0;
  vPoint.Z := 0;
 
  vLineDir.X := 0;
  vLineDir.Y := 0;
  vLineDir.Z := 0;
 
        Numerator := 0.0;
  Denominator := 0.0;
  dist := 0.0;
  Angle := 0.0;
 
 
 
 
  vVector1.x := vPoly[2].x - vPoly[0].x;
        vVector1.y := vPoly[2].y - vPoly[0].y;
        vVector1.z := vPoly[2].z - vPoly[0].z;
 
  vVector2.x := vPoly[1].x - vPoly[0].x;
        vVector2.y := vPoly[1].y - vPoly[0].y;
        vVector2.z := vPoly[1].z - vPoly[0].z;
 
 
 
 
        vNormal.x := ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));
 
        vNormal.y := ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));
 
        vNormal.z := ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));
 
 
 
 
  m_magnitude := sqrt((vNormal.x * vNormal.x) +
                      (vNormal.y * vNormal.y) +
                      (vNormal.z * vNormal.z) );
 
 
 
        vNormal.x := vNormal.x/m_magnitude;
        vNormal.y := vNormal.y/m_magnitude;
        vNormal.z := vNormal.z/m_magnitude;
 
 
 
  originDistance := -1 * ((vNormal.x * vPoly[0].x) +
                          (vNormal.y * vPoly[0].y) +
                          (vNormal.z * vPoly[0].z));
 
 
        distance1 := ((vNormal.x * vLine[0].x)  +
                         (vNormal.y * vLine[0].y)  +
                                 (vNormal.z * vLine[0].z)) + originDistance;
 
        distance2 := ((vNormal.x * vLine[1].x)  +
                         (vNormal.y * vLine[1].y)  +
                                 (vNormal.z * vLine[1].z)) + originDistance;
 
        if(distance1 * distance2 >= 0) then
  begin
 
          result := false;
    exit;
  end;
 
 
 
  vLineDir.x := vLine[1].x - vLine[0].x;
        vLineDir.y := vLine[1].y - vLine[0].y;
        vLineDir.z := vLine[1].z - vLine[0].z;
 
  m_magnitude := sqrt((vLineDir.x * vLineDir.x) +
                      (vLineDir.y * vLineDir.y) +
                      (vLineDir.z * vLineDir.z) );
 
 
        vLineDir.x := vLineDir.x/m_magnitude;
        vLineDir.y := vLineDir.y/m_magnitude;
        vLineDir.z := vLineDir.z/m_magnitude;
 
 
 
        Numerator := -1 * (vNormal.x * vLine[0].x +
                                             vNormal.y * vLine[0].y +
                                             vNormal.z * vLine[0].z + originDistance);
 
 
 
 
        Denominator := ( (vNormal.x * vLineDir.x) + (vNormal.y * vLineDir.y) + (vNormal.z * vLineDir.z) );
 
        if( Denominator = 0.0) then
  begin
                vIntersection := vLine[0];
  end
  else
  begin
 
 
          dist := Numerator / Denominator;
 
 
 
          vPoint.x := (vLine[0].x + (vLineDir.x * dist));
          vPoint.y := (vLine[0].y + (vLineDir.y * dist));
          vPoint.z := (vLine[0].z + (vLineDir.z * dist));
 
          vIntersection := vPoint;                                                                // Return the intersection point
  end;
temp_intersect_v.x := vIntersection.x;
temp_intersect_v.y := vIntersection.y;
temp_intersect_v.z := vIntersection.z;
temp_intersect_v2 :=  vPoint;
CLIP_INTERSECT_POS := temp_intersect_v;
  for i := 0 to verticeCount-1 do
  begin
 
 
    vA.x := vPoly[i].x - vIntersection.x;
 
          vA.y := vPoly[i].y - vIntersection.y;
 
          vA.z := vPoly[i].z - vIntersection.z;
 
 
    vB.x := vPoly[(i + 1) mod verticeCount].x - vIntersection.x;
 
          vB.y := vPoly[(i + 1) mod verticeCount].y - vIntersection.y;
 
          vB.z := vPoly[(i + 1) mod verticeCount].z - vIntersection.z;
 
 
    dotProduct := ( (vA.x * vB.x) +
                    (vA.y * vB.y) +
                    (vA.z * vB.z) );
 
 
          vectorsMagnitude := sqrt(
                     extended(vA.x * vA.x) +
                     extended(vA.y * vA.y) +
                     extended(vA.z * vA.z)
                          )
                          *
                     sqrt(
                     extended(vB.x * vB.x) +
                     extended(vB.y * vB.y) +
                     extended(vB.z * vB.z)
                          );
 
         tempangle := arccos( dotProduct / vectorsMagnitude );
 
 
          if(isnan(tempangle)) then
    begin
                  tempangle := 0;
    end;
 
 
          Angle := Angle + tempangle;
  end;
 
        if(Angle >= (MATCH_FACTOR * (2.0 * PI)) ) then
  begin
                result := TRUE;
    exit;
  end;
 
 
 
 
        result := false;
end;
 




3 komentarze

Komorkowy_dzony 2007-07-12 11:51

Bo te rysunki to sam rozrysowywałem problem i to było wyłącznie dla mnie. Rysunek ma sie nijak do tekstu w arcie.

ROB4L 2007-07-12 01:18

Jakieś takie mało obrazowe te rysunki i ich tłumaczenie też trochę ciulowe :\