|
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)
|
Home
