OpenGL v Delphi4



Lepší detekce kolizí


Příklad a zdroják ke stažení (310k)


Detekci kolizí, kterou jsem řešil v jednom předešlém tutorialu není moc dokonalá. Proto jsem se rozhodl najít lepší řešení. Na stránkách ' GAMETUTORIALS ' jsem našel příklad ' Poligon collision '. Je psaný v C++, tak jsem se ho pokusil přepsat do Delphi. No a po troše námahy se to podařilo.

Příkládek je tvořen z jednoduchého trojúhelníku a čáry. Pokud čára protíná trojúhelník, tak je čára červená, jinak je žlutá. Pro detekci čáry s trojúhelníkem se používá docela šílenej algoritmus. Proto jsem napsal všechny výpočty do oddělené unity K3dMath.pas. Nechal jsem u toho anglický pokec, takže je to docela přehledný.

No a teď se pokusim vysvětlit, co všechno se musí vypočítat aby kolize fungovala. Před vykreslením trojúhelníka volám proceduru ' CalcCollision(i) '.


procedure DrawTriangle;
var
  i: integer;
begin
  for i := 1 to 1 do begin
  CalcCollision(i);          //volej tuto proceduru pro detekci kolize
  glPushMatrix;
  glDisable(GL_LIGHTING);
  glColor3f(1, 1, 1);
  glBindTexture(GL_TEXTURE_2D, TextureBin[i]);
  glEnable(GL_TEXTURE_2D);
  glBegin(GL_TRIANGLES);
    glTexCoord2f(Coord1[i].x,Coord1[i].y);
    glNormal3f(Normal1[i].x,Normal1[i].y,Normal1[i].z);
    glVertex3f(Point1[i].x,Point1[i].y,Point1[i].z);
    glTexCoord2f(Coord2[i].x,Coord2[i].y);
    glVertex3f(Point2[i].x,Point2[i].y,Point2[i].z);
    glTexCoord2f(Coord3[i].x,Coord3[i].y);
    glVertex3f(Point3[i].x,Point3[i].y,Point3[i].z);
  glEnd;
  glPopMatrix;
  end;
end;

Proměnná 'i' je tam proto, abych v budoucnu mohl zobrazit více trojúhelníků a rovnou aby se počítala kolize pro každý trojúhelník zvlášť.

V proceduře ' CalcCollisio() ' volám funkci ' IntersectedPolygon(Point1[val], Point2[val], Point3[val] , Line1, Line2); ', kde ' Point1 ' až ' Poin3 ' jsou body trojúhelníka, ' Line1 ' a ' Line2 ' jsou body čáry.


procedure CalcCollision(val: TGLInt);
begin
  bCollided[val] := IntersectedPolygon(Point1[val], Point2[val], Point3[val] , Line1, Line2);

 // Below we draw the line that the polygon will be colliding with. (RED is collision)
 glPushMatrix;
 glDisable(GL_TEXTURE_2D);
 if  bCollided[1]  then begin           // If we collided, change the color of the line to illustrate this.
   glColor3f(1, 0, 0);                        // Make the line RED if we collided with the triangle's plane
 end else begin
   glColor3f(1, 1, 0);                  // Make the line YELLOW if we didn't collide
 end;

 glBegin(GL_LINES);                                        // This is our BEGIN to draw Line
   glVertex3f(Line1.x, Line1.y, Line1.z);
   glVertex3f(Line2.x, Line2.y, Line2.z);
 glEnd;
 glPopMatrix;
end;

Teď se mrknem, co dělá funkce ' IntersectedPolygon(Point1[val], Point2[val], Point3[val] , Line1, Line2); '

function IntersectedPolygon(Poly1, Poly2, Poly3, Line1, Line2: TPoint3D): boolean;
var
  vNormal: TPoint3D;
  OriginDistance: TGLFloat;
  vIntersection: TPoint3D;
begin
  // First we check to see if our line intersected the plane.  If this isn't true
  // there is no need to go on, so return false immediately.
  // We pass in address of vNormal and originDistance so we only calculate it once



  // Reference
  if (IntersectedPlane(Poly1, Poly2, Poly3, Line1, Line2)) then begin
    Result := false;
  end else begin
    // Now that we have our normal and distance passed back from IntersectedPlane(),
    // we can use it to calculate the intersection point.  The intersection point
    // is the point that actually is ON the plane.  It is between the line.  We need
    // this point test next, if we are inside the polygon.  To get the I-Point, we
    // give our function the normal of the plan, the points of the line, and the originDistance.

    vNormal := CalcCollVector(Poly1,Poly2,Poly3);

    //////////////////////////
    // Let's find the distance our plane is from the origin.  We can find this value
    // from the normal to the plane (polygon) and any point that lies on that plane (Any vertice)

    OriginDistance := PlaneDistance(vNormal, Poly1);
    vIntersection := IntersectionPoint(vNormal, Line1, Line2, originDistance);

    // Now that we have the intersection point, we need to test if it's inside the polygon.
    // To do this, we pass in :
    // (our intersection point, the polygon, and the number of vertices our polygon has)

    if (InsidePolygon(vIntersection, Poly1, Poly2, Poly3)) then begin
      Result := true;   // We collided!          Return success
    end else begin  // If we get here, we must have NOT collided
      Result := false;  // There was no collision, so return false
    end; //end if (InsidePolygon(vIntersection, Poly1, Poly2, Poly3))
  end;  //end if (IntersectedPlane(Poly1, Poly2, Poly3, Line1, Line2))
end;

Funkce ' IntersectedPlane(Poly1, Poly2, Poly3, Line1, Line2)' počítá, jestli se čára nachází mimo trojúhelník, nebo jestli ho protíná. Pokud je mimo trojúhelník vyplivne hodnotu ' False ' a výpočet končí.

Pokud čára trojúhelník protíná, výpočet pokračuje dále. Vypočítá se normálový vektor trojúhelníka ' vNormal := CalcCollVector(Poly1,Poly2,Poly3); 'a potom počáteční vzdálenost kolizního bodu, který se vypočítá pomocí normálového vektoru a jednoho z bodů trojúhelníka ' OriginDistance := PlaneDistance(vNormal, Poly1); '. Hodnota ' OriginDistance ' se pak dosadí do funkce ' IntersectionPoint(vNormal, Line1, Line2, originDistance); ', která počítá přesný bod střetu čáry s trojúhelníkem. Nakonec funkce ' InsidePolygon(vIntersection, Poly1, Poly2, Poly3) ' vyhodnotí, jestli je vypočítaný bod opravdu uvnitř trojúhelníka. Pokud ano vyplivne hodnotu ' True ' a kolize se koná.

Teď se pokusim ponořit hlouběji do výpočtů.

Funkce ' IntersectedPlane(Poly1, Poly2, Poly3, Line1, Line2)' počítá, jestli se čára nachází mimo trojúhelník, nebo jestli ho protíná. Vypadá takto.


function IntersectedPlane(Poly1, Poly2, Poly3, Line1, Line2: TPoint3D): Boolean;
var
  distance1, distance2: TGLFloat;   // The distances from the 2 points of the line from the plane
  distance: TGLFLoat;
  vNormal: TPoint3D;
  OriginDistance: TGLFloat;
begin
  // We need to get the normal of our plane to go any further
  vNormal := CalcCollVector(Poly1,Poly2,Poly3);

  //////////////////////////
  // Let's find the distance our plane is from the origin.  We can find this value
  // from the normal to the plane (polygon) and any point that lies on that plane (Any vertice)
  OriginDistance := PlaneDistance(vNormal, Poly1);

  ///////////
  // Get the distance from point1 from the plane using: Ax + By + Cz + D = (The distance from the plane)
  distance1 := ((vNormal.x * Line1.x)  +                                      // Ax +
                         (vNormal.y * Line1.y)  +                             // By +
                                 (vNormal.z * Line1.z)) + originDistance;     // Cz + D

  // Get the distance from point2 from the plane using Ax + By + Cz + D = (The distance from the plane)

  distance2 := ((vNormal.x * Line2.x)  +                                      // Ax +
                         (vNormal.y * Line2.y)  +                             // By +
                                 (vNormal.z * Line2.z)) + originDistance;     // Cz + D

  // Now that we have 2 distances from the plane, if we times them together we either
  // get a positive or negative number.  If it's a negative number, that means we collided!
  // This is because the 2 points must be on either side of the plane (IE. -1 * 1 = -1).
  distance := distance1 * distance2;

  if (distance) <= 0 then    // Check to see if both point's distances are both negative or both positive
    Result := false             // Return false if each point has the same sign.  -1 and 1 would mean each point is on either side of the plane.  -1 -2 or 3 4 wouldn't...
  else
    Result := true;          // The line intersected the plane, Return TRUE
end;


Opět se počítá normálový vektor trojúhelníka ' vNormal := CalcCollVector(Poly1,Poly2,Poly3); ' a počáteční vzdálenost kolizního bodu ' OriginDistance := PlaneDistance(vNormal, Poly1); '. Podle vzorce ' Ax + By + Cz + D = (vzdálenost od trojúhelníka) ' vypočítáme vzdálenost prvního a druhého bodu čáry od trojúhelníka
distance1 := ((vNormal.x * Line1.x)  +                                      // Ax +
                         (vNormal.y * Line1.y)  +                           // By +
                                 (vNormal.z * Line1.z)) + originDistance;   // Cz + D

  
distance2 := ((vNormal.x * Line2.x)  +                                      // Ax +
                         (vNormal.y * Line2.y)  +                           // By +
                                 (vNormal.z * Line2.z)) + originDistance;   // Cz + D
Výsledné hodnoty vynásobíme ' distance := distance1 * distance2; ' a pokud je výsledek menší nebo roven nule, tak funkce vyplivne ' False ', pokud je větší než nula, vyplivne ' True ', což znamená, že čára trojúhelník protíná.

Výpočet normálového vektoru vypadá takto:


function CalcCollVector(Vect1,Vect2,Vect3:TPoint3D): TPoint3D;
var longi,vx1,vy1,vz1,vx2,vy2,vz2:TGLFloat;
    VectRes:TPoint3D;
begin
  vx1:=Vect1.x-Vect2.x;vy1:=Vect1.y-Vect2.y;vz1:=Vect1.z-Vect2.z;
  vx2:=Vect2.x-Vect3.x;vy2:=Vect2.y-Vect3.y;vz2:=Vect2.z-Vect3.z;
  with VectRes do begin
     x:=vy1*vz2 - vz1*vy2;
     y:=vz1*vx2 - vx1*vz2;
     z:=vx1*vy2 - vy1*vx2;
     //Optimalization vector
     longi:=sqrt(sqr (x) + sqr(y) + sqr(z));
     if longi>0 then  //avoid zero division error
     x:=x/longi;y:=y/longi;z:=z/longi;
  end;
  Result := VectRes;
end;                       

Počáteční vzdálenost kolizního bodu takto:

function PlaneDistance(Normal, Point: TPoint3D): TGLFloat;
var
  distance: TGLFLoat;  // This variable holds the distance from the plane tot he origin
begin
  distance := - ((Normal.x * Point.x) + (Normal.y * Point.y) + (Normal.z * Point.z));
  // Basically, the negated dot product of the normal of the plane and the point. (More about the dot product in another tutorial)
  Result := distance;
end;         

Přesný bod střetu čáry s trojúhelníkem takto:

function IntersectionPoint(vNormal, Line1, Line2: TPoint3D; distance: TGLFLoat): TPoint3D;
var
  vPoint, vLineDir: TPoint3D;   // Variables to hold the point and the line's direction
  Numerator, Denominator, dist: TGLFloat;
begin
  //pocita bod, na trouhelniku, ktery protina cara
  // Here comes the confusing part.  We need to find the 3D point that is actually
  // on the plane.  Here are some steps to do that:

  // 1)  First we need to get the vector of our line, Then normalize it so it's a length of 1
  vLineDir := CalcCollVector2(Line2,Line1);  // Get the Vector of the line



  // 2) Use the plane equation (distance = Ax + By + Cz + D) to find the distance from one of our points to the plane.
  //    Here I just chose a arbitrary point as the point to find that distance.  You notice we negate that
  //    distance.  We negate the distance because we want to eventually go BACKWARDS from our point to the plane.
  //    By doing this is will basically bring us back to the plane to find our intersection point.
  Numerator := - (vNormal.x * Line1.x +         // Use the plane equation with the normal and the line
                  vNormal.y * Line1.y +
                  vNormal.z * Line1.z + distance);



  // 3) If we take the dot product between our line vector and the normal of the polygon,
  //    this will give us the cosine of the angle between the 2 (since they are both normalized - length 1).
  //    We will then divide our Numerator by this value to find the offset towards the plane from our arbitrary point.
  Denominator := Dot(vNormal, vLineDir);  // Get the dot product of the line's vector and the normal of the plane



  // Since we are using division, we need to make sure we don't get a divide by zero error
  // If we do get a 0, that means that there are INFINATE points because the the line is
  // on the plane (the normal is perpendicular to the line - (Normal.Vector = 0)).
  // In this case, we should just return any point on the line.

  if( Denominator = 0) then begin  // Check so we don't divide by zero
    Result := Line1;
  end else begin  // Return an arbitrary point on the line

  // We divide the (distance from the point to the plane) by (the dot product)
  // to get the distance (dist) that we need to move from our arbitrary point.  We need
  // to then times this distance (dist) by our line's vector (direction).  When you times
  // a scalar (single number) by a vector you move along that vector.  That is what we are
  // doing.  We are moving from our arbitrary point we chose from the line BACK to the plane
  // along the lines vector.  It seems logical to just get the numerator, which is the distance
  // from the point to the line, and then just move back that much along the line's vector.
  // Well, the distance from the plane means the SHORTEST distance.  What about in the case that
  // the line is almost parallel with the polygon, but doesn't actually intersect it until half
  // way down the line's length.  The distance from the plane is short, but the distance from
  // the actual intersection point is pretty long.  If we divide the distance by the dot product
  // of our line vector and the normal of the plane, we get the correct length.  Cool huh?

  dist := Numerator / Denominator;  // Divide to get the multiplying (percentage) factor



  // Now, like we said above, we times the dist by the vector, then add our arbitrary point.
  // This essentially moves the point along the vector to a certain distance.  This now gives
  // us the intersection point.  Yay!

  vPoint.x := (Line1.x + (vLineDir.x * dist));
  vPoint.y := (Line1.y + (vLineDir.y * dist));
  vPoint.z := (Line1.z + (vLineDir.z * dist));



  Result := vPoint;  // Return the intersection point
  end;
end;

Nejdříve se počítá normálový vektor čáry ' vLineDir := CalcCollVector2(Line2,Line1); '
function CalcCollVector2(Vect1,Vect2:TPoint3D): TPoint3D;
var longi,vx1,vy1,vz1{,vx2,vy2,vz2}:TGLFloat;
    VectRes:TPoint3D;
begin
  vx1:=Vect1.x-Vect2.x; vy1:=Vect1.y-Vect2.y; vz1:=Vect1.z-Vect2.z;
  with VectRes do begin
     x:=vx1;
     y:=vy1;
     z:=vz1;
     //Optimalization vector
     longi:=sqrt(sqr (x) + sqr(y) + sqr(z));
     if longi>0 then  //avoid zero division error
     x:=x/longi;y:=y/longi;z:=z/longi;
  end;
  Result := VectRes;
end;
Potom podle rovnice ' vzdálenost = Ax + By + Cz + D ' vypočítáme vzdálenost jednoho bodu čáry od trojúhelníka
Numerator := - (vNormal.x * Line1.x +         // Use the plane equation with the normal and the line
                vNormal.y * Line1.y +
                vNormal.z * Line1.z + distance);
Pak provedeme součin normálového vektoru trojúhelníka a normálového vektoru čáry ' Denominator := Dot(vNormal, vLineDir); '
function Dot(vVector1, vVector2: TPoint3D): TGLFloat;
begin
  Result := ( (vVector1.x * vVector2.x) + (vVector1.y * vVector2.y) + (vVector1.z * vVector2.z) );
end;
Pokud je výsledek roven nule vrátí funkce hodnoty jednoho bodu čáry 'Line1'.

Jinak se vzdálenost dělí normálovým součinem ' dist := Numerator / Denominator; ' a vypočítaj se hodnoty bodu střetu čáry s trojúhelníkem.

vPoint.x := (Line1.x + (vLineDir.x * dist));
vPoint.y := (Line1.y + (vLineDir.y * dist));
vPoint.z := (Line1.z + (vLineDir.z * dist));

Poslední funkce ' InsidePolygon(vIntersection, Poly1, Poly2, Poly3) ' vyhodnotí, jestli je vypočítaný bod opravdu uvnitř trojúhelníka. Vypadá takto:


function InsidePolygon(vIntersection,Poly1, Poly2, Poly3: TPoint3D): boolean;
var
  Angle, Angle1, Angle2, Angle3: TGLFloat;  // Initialize the angle
  vA, vB: TPoint3D;   // Create temp vectors
begin

  // Just because we intersected the plane, doesn't mean we were anywhere near the polygon.
  // This functions checks our intersection point to make sure it is inside of the polygon.
  // This is another tough function to grasp at first, but let me try and explain.
  // It's a brilliant method really, what it does is create triangles within the polygon
  // from the intersection point.  It then adds up the inner angle of each of those triangles.
  // If the angles together add up to 360 degrees (or 2 * PI in radians) then we are inside!
  // If the angle is under that value, we must be outside of polygon.  To further
  // understand why this works, take a pencil and draw a perfect triangle.  Draw a dot in
  // the middle of the triangle.  Now, from that dot, draw a line to each of the vertices.
  // Now, we have 3 triangles within that triangle right?  Now, we know that if we add up
  // all of the angles in a triangle we get 360 right?  Well, that is kinda what we are doing,
  // but the inverse of that.  Say your triangle is an isosceles triangle, so add up the angles
  // and you will get 360 degree angles.  90 + 90 + 90 is 360.

  ////Angle1
  vA := CalcCollVector2(Poly1,vIntersection);          // Subtract the intersection point from the current vertex
  vB := CalcCollVector2(Poly2, vIntersection);  // Subtract the point from the next vertex
  Angle1 := AngleBetweenVectors(vA, vB);        // Find the angle between the 2 vectors and add them all up as we go along


  ////Angle2
  vA := CalcCollVector2(Poly2,vIntersection);
  vB := CalcCollVector2(Poly3, vIntersection);
  Angle2 := AngleBetweenVectors(vA, vB);

  ////Angle3
  vA := CalcCollVector2(Poly3,vIntersection);
  vB := CalcCollVector2(Poly1, vIntersection);
  Angle3 := AngleBetweenVectors(vA, vB);


  // Now that we have the total angles added up, we need to check if they add up to 360 degrees.
  // Since we are using the dot product, we are working in radians, so we check if the angles
  // equals 2*PI.  We defined PI in 3DMath.h.  You will notice that we use a MATCH_FACTOR
  // in conjunction with our desired degree.  This is because of the inaccuracy when working
  // with floating point numbers.  It usually won't always be perfectly 2 * PI, so we need
  // to use a little twiddling.  I use .9999, but you can change this to fit your own desired accuracy.

  Angle := Angle1 + Angle2 + Angle3;
             
  if(Angle >= 360) then        // If the angle is greater than 2 PI, (360 degrees)
    Result := TRUE        // The point is inside of the polygon
  else
    Result := FALSE;        // If you get here, it obviously wasn't inside the polygon, so Return FALSE
end;

Nejdříve se vypočítají úhly které svírájí přímky mezi body trojúhelníka a bodem střetu čáry s trojúhelníkem.

////Angle1
vA := CalcCollVector2(Poly1,vIntersection);          // Subtract the intersection point from the current vertex
vB := CalcCollVector2(Poly2, vIntersection);  // Subtract the point from the next vertex
Angle1 := AngleBetweenVectors(vA, vB);        // Find the angle between the 2 vectors and add them all up as we go along


////Angle2
vA := CalcCollVector2(Poly2,vIntersection);
vB := CalcCollVector2(Poly3, vIntersection);
Angle2 := AngleBetweenVectors(vA, vB);

////Angle3
vA := CalcCollVector2(Poly3,vIntersection);
vB := CalcCollVector2(Poly1, vIntersection);
Angle3 := AngleBetweenVectors(vA, vB);
Pak se všechny tři úhly sečtou. Pokud výsledný úhel je větší než 360, tak je bod opravdu v trojúhelníku a kolize se aktivuje. Pokud je výsledný úhel menší, bod je mimo trojúhelník a kolize je neaktivní.

Funkce ' AngleBetweenVectors(vA, vB); ' vypadá takto:


function AngleBetweenVectors(Vector1,Vector2: TPoint3D): TGLFloat;
var
  dotProduct: TGLFloat;
  vectorsMagnitude: TGLFloat;
  Angle: TGLFloat;
begin

  // Remember, above we said that the Dot Product of returns the cosine of the angle
  // between 2 vectors?  Well, that is assuming they are unit vectors (normalize vectors).
  // So, if we don't have a unit vector, then instead of just saying  arcCos(DotProduct(A, B))
  // We need to divide the dot product by the magnitude of the 2 vectors multiplied by each other.
  // Here is the equation:   arc cosine of (V . W / || V || * || W || )
  // the || V || means the magnitude of V.  This then cancels out the magnitudes dot product magnitudes.
  // But basically, if you have normalize vectors already, you can forget about the magnitude part.

  // Get the dot product of the vectors
  dotProduct := Dot(Vector1, Vector2);

  // Get the product of both of the vectors magnitudes
  vectorsMagnitude := Magnitude(Vector1) * Magnitude(Vector2);

  // Return the arc cosine of the (dotProduct / vectorsMagnitude) which is the angle in RADIANS.
  // (IE.   PI/2 radians = 90 degrees      PI radians = 180 degrees    2*PI radians = 360 degrees)
  // To convert radians to degress use this equation:   radians * (PI / 180)
  // TO convert degrees to radians use this equation:   degrees * (180 / PI)
  Angle :=   ArcCos(dotProduct / vectorsMagnitude);
  Result :=  RadToGrad(Angle);  //convert radians to degrees
end;

Provedu součin obou vektorů ' dotProduct := Dot(Vector1, Vector2); '
function Dot(vVector1, vVector2: TPoint3D): TGLFloat;
begin
  Result := ( (vVector1.x * vVector2.x) + (vVector1.y * vVector2.y) + (vVector1.z * vVector2.z) );
end;
Potom vektory optimalizujem a vynásobíme ' vectorsMagnitude := Magnitude(Vector1) * Magnitude(Vector2); '
function Magnitude(vNormal: TPoint3D): TGLFloat;
begin
  // This will give us the magnitude or "Norm" as some say, of our normal.
  // Here is the equation:  magnitude = sqrt(V.x^2 + V.y^2 + V.z^2)  Where V is the vector

  Result := sqrt( (vNormal.x * vNormal.x) + (vNormal.y * vNormal.y) + (vNormal.z * vNormal.z) );
end;
Pak už jen vypočteme úhel a převedeme z radiánů na stupně
Angle :=   ArcCos(dotProduct / vectorsMagnitude);
Result :=  RadToGrad(Angle);  //convert radians to degrees

Tak a to je konec.... Přeji příjemné programování.
Honza (Kwan)

Celé zdrojáky jsou tady
BColl_f.pas
K3dMath_f.pas


Emboss Bumpmapping Kolize koule a kamery se stěnama místnosti

Home