Lillefix

03-08-2009, 11:13 AM

I am now trying to write a collisiond etection routine as described here: http://www.peroxide.dk/papers/collision/collision.pdf

So far the collision works mostly as expected, there are however some times that my sphere will ignore the first collision point and continue to second collision point (where it lies behind the plane) before stopping. I believe this is a simpel logical error, but I am simple unable to find it. Notice, the problem is with my edge-checking, not the triangle-test which I am positive works 100%.

Below is my ray/cylinder function and my move function in which I utilise it.

I do understand that this is no easy question, but I certainly hope that you will give it a try.

/*

This function will return true if there are any solutions to the quadratic equation. If not, it will return false.

O = Ray origin

D = Ray direction

A = Edge start-point

B = Edge end-point

time = float to fill with a solution

*/

bool rayCylIntersect(Vector O, Vector D, Vector A, Vector B, float &time)

{

float r1, r2;

float a, b, c;

//Fills in a, b and c as shown in this paper: http://www.peroxide.dk/papers/collision/collision.pdf

Vector edge = B - A;

Vector baseToVertex = A - O;

float edgeSquaredLength = edge.dot(edge);

float edgeDotVelocity = edge.dot(D);

float edgeDotBaseToVertex = edge.dot(baseToVertex);

float velocitySquaredLength = D.dot(D);

a = edgeSquaredLength * -(velocitySquaredLength) + edgeDotVelocity * edgeDotVelocity;

b = edgeSquaredLength * 2 * D.dot(baseToVertex) - 2 * edgeDotVelocity * edgeDotBaseToVertex;

c = edgeSquaredLength * (1 - baseToVertex.dot(baseToVertex)) + edgeDotBaseToVertex * edgeDotBaseToVertex;

float determinant = (b * b) - (4 * a * c);

if (a == 0) //Cylinder is parallel to edge.

{

return false;

}

if (determinant < 0) //Cylinder does not intersect with the edge

{

return false;

}

else

{

float sqrtD = sqrt(determinant);

r1 = (-b - sqrtD) / (2 * a); //Solution 1

r2 = (-b + sqrtD) / (2 * a); //Solution 2

}

if (r2 < r1) //Make sure that r1 is smaller than r2

{

float temp = r2;

r2 = r1;

r1 = temp;

}

if (r1 >= 0) //Returning solution 1 if it is higher than or equal to 0

{

time = r1;

return true;

}

if (r2 >= 0) //Returning solution 2 if it is higher than or equal to 0

{

time = r2;

return true;

}

//None of the solutions are positive, returning false

return false;

}

void Sphere::Move()

{

float time = 1; //Sets initial time to 1. This equals no collisions.

for (int i = 0; i < planes.size(); i++) //Loops through every plane (triangles)

{

Vector p1 = planes[i].pos[0]; //For convenience

Vector p2 = planes[i].pos[1];

Vector p3 = planes[i].pos[2];

Vector norm = planes[i].norm;

if (!planes[i].isFrontFacingTo(mov)) //Ignore planes facing the wrong way as all objects

continue; //are thought to be closed

float signedDist = planes[i].signedDistanceTo(pos); //Distance from the spheres position to plane

float normDotVel = planes[i].norm.dot(mov); //The dot product of the plane's normal and the velocity

if (normDotVel == 0) //The sphere is travelling parallel to the plane

continue; //We can then ignore this plane

float t0 = (1 - signedDist) / normDotVel; //Solution 1

float t1 = (-1 - signedDist) / normDotVel; //Solution 2

float temptime = 1; //Temptime should now be equal to the value closest to zero yet positive.

if (t0 < temptime && t0 >= 0) //If none of the solution are larger than 0 and smaller than 1, temptime equals 1

temptime = t0;

if (t1 < temptime && t1 >= 0)

temptime = t1;

if (temptime < time) //If the sphere hits a plane before the current smallest colliision time

{

Vector colPoint = pos + (mov * temptime) - norm;

if (pointInTriangle(colPoint, p1, p2, p3)) //If the collision-point is in the actual triangle

{

time = temptime;

continue; //As all plane-collisions will happen first, we can now continue to the next plane

}

}

temptime = 1; //reset temptime

if (rayCylIntersect(pos, mov, p1, p2, temptime)) //Check against the first edge

{

float line = findPointOnVector(pos + mov * temptime, p1, p2); //Check that the collision-point is within the segment

if (temptime < time && line <= 1 && line >= 0) //If the collision will happen before current collision time

{ //And is within the segment

time = temptime; //The collision time equals temptime

}

}

//Check against edge 2

if (rayCylIntersect(pos, mov, p2, p3, temptime))

{

float line = findPointOnVector(pos + mov * temptime, p2, p3);

if (temptime < time && line <= 1 && line >= 0)

{

time = temptime;

}

}

//Check against edge 3

if (rayCylIntersect(pos, mov, p1, p3, temptime))

{

float line = findPointOnVector(pos + mov * temptime, p1, p3);

if (temptime < time && line <= 1 && line >= 0)

{

time = temptime;

}

}

}

pos = pos + (mov * time); //Move the sphere according to the collision time.

}

Explanation of my problem:

http://img523.imageshack.us/img523/392/sphere.th.jpg (http://img523.imageshack.us/my.php?image=sphere.jpg)

So far the collision works mostly as expected, there are however some times that my sphere will ignore the first collision point and continue to second collision point (where it lies behind the plane) before stopping. I believe this is a simpel logical error, but I am simple unable to find it. Notice, the problem is with my edge-checking, not the triangle-test which I am positive works 100%.

Below is my ray/cylinder function and my move function in which I utilise it.

I do understand that this is no easy question, but I certainly hope that you will give it a try.

/*

This function will return true if there are any solutions to the quadratic equation. If not, it will return false.

O = Ray origin

D = Ray direction

A = Edge start-point

B = Edge end-point

time = float to fill with a solution

*/

bool rayCylIntersect(Vector O, Vector D, Vector A, Vector B, float &time)

{

float r1, r2;

float a, b, c;

//Fills in a, b and c as shown in this paper: http://www.peroxide.dk/papers/collision/collision.pdf

Vector edge = B - A;

Vector baseToVertex = A - O;

float edgeSquaredLength = edge.dot(edge);

float edgeDotVelocity = edge.dot(D);

float edgeDotBaseToVertex = edge.dot(baseToVertex);

float velocitySquaredLength = D.dot(D);

a = edgeSquaredLength * -(velocitySquaredLength) + edgeDotVelocity * edgeDotVelocity;

b = edgeSquaredLength * 2 * D.dot(baseToVertex) - 2 * edgeDotVelocity * edgeDotBaseToVertex;

c = edgeSquaredLength * (1 - baseToVertex.dot(baseToVertex)) + edgeDotBaseToVertex * edgeDotBaseToVertex;

float determinant = (b * b) - (4 * a * c);

if (a == 0) //Cylinder is parallel to edge.

{

return false;

}

if (determinant < 0) //Cylinder does not intersect with the edge

{

return false;

}

else

{

float sqrtD = sqrt(determinant);

r1 = (-b - sqrtD) / (2 * a); //Solution 1

r2 = (-b + sqrtD) / (2 * a); //Solution 2

}

if (r2 < r1) //Make sure that r1 is smaller than r2

{

float temp = r2;

r2 = r1;

r1 = temp;

}

if (r1 >= 0) //Returning solution 1 if it is higher than or equal to 0

{

time = r1;

return true;

}

if (r2 >= 0) //Returning solution 2 if it is higher than or equal to 0

{

time = r2;

return true;

}

//None of the solutions are positive, returning false

return false;

}

void Sphere::Move()

{

float time = 1; //Sets initial time to 1. This equals no collisions.

for (int i = 0; i < planes.size(); i++) //Loops through every plane (triangles)

{

Vector p1 = planes[i].pos[0]; //For convenience

Vector p2 = planes[i].pos[1];

Vector p3 = planes[i].pos[2];

Vector norm = planes[i].norm;

if (!planes[i].isFrontFacingTo(mov)) //Ignore planes facing the wrong way as all objects

continue; //are thought to be closed

float signedDist = planes[i].signedDistanceTo(pos); //Distance from the spheres position to plane

float normDotVel = planes[i].norm.dot(mov); //The dot product of the plane's normal and the velocity

if (normDotVel == 0) //The sphere is travelling parallel to the plane

continue; //We can then ignore this plane

float t0 = (1 - signedDist) / normDotVel; //Solution 1

float t1 = (-1 - signedDist) / normDotVel; //Solution 2

float temptime = 1; //Temptime should now be equal to the value closest to zero yet positive.

if (t0 < temptime && t0 >= 0) //If none of the solution are larger than 0 and smaller than 1, temptime equals 1

temptime = t0;

if (t1 < temptime && t1 >= 0)

temptime = t1;

if (temptime < time) //If the sphere hits a plane before the current smallest colliision time

{

Vector colPoint = pos + (mov * temptime) - norm;

if (pointInTriangle(colPoint, p1, p2, p3)) //If the collision-point is in the actual triangle

{

time = temptime;

continue; //As all plane-collisions will happen first, we can now continue to the next plane

}

}

temptime = 1; //reset temptime

if (rayCylIntersect(pos, mov, p1, p2, temptime)) //Check against the first edge

{

float line = findPointOnVector(pos + mov * temptime, p1, p2); //Check that the collision-point is within the segment

if (temptime < time && line <= 1 && line >= 0) //If the collision will happen before current collision time

{ //And is within the segment

time = temptime; //The collision time equals temptime

}

}

//Check against edge 2

if (rayCylIntersect(pos, mov, p2, p3, temptime))

{

float line = findPointOnVector(pos + mov * temptime, p2, p3);

if (temptime < time && line <= 1 && line >= 0)

{

time = temptime;

}

}

//Check against edge 3

if (rayCylIntersect(pos, mov, p1, p3, temptime))

{

float line = findPointOnVector(pos + mov * temptime, p1, p3);

if (temptime < time && line <= 1 && line >= 0)

{

time = temptime;

}

}

}

pos = pos + (mov * time); //Move the sphere according to the collision time.

}

Explanation of my problem:

http://img523.imageshack.us/img523/392/sphere.th.jpg (http://img523.imageshack.us/my.php?image=sphere.jpg)