I have been trying to learn a moving sphere to stationary triangle collision.
Other threads have suggested http://www.peroxide.dk/papers/collision/collision.pdf , however, even though I understand the algorithm I am still getting no collision when I should be.
I have a triangle being built clockwise with the following properties:
Vertex One: (4.0f, 0.0f, 4.0f)
Vertex Two: (4.0f, 0.0f, 0.0f)
Vertex Three: (0.0f, 0.0f, 0.0f)
Normal : (0, 1, 0)
I then have a sphere moving down onto it with the properties of:
Sphere Origin: (1.5, 1.5, 0)
Velocity : (0, -1, 0)
Radius: 1 (not taken into account here yet)
After a timestep of one second their should be collision in two places because the sphere will be at (1.5, 0.5, 0). There should be collision with the sphere going though the sphere and it is also colliding with the edge between Vertex Two and Vertex Three. Here is a picture of it
Front
Top
There should clearly be collision, however, I am not getting neither collision or not collision. I have done the math by hand to make sure there is no collision and there is none, I then followed those variables through the bugger and got the same result. It does get to an eventual Vertex Two to Vertex Three edge check, however, it does not report collision.
My question is, has anyone ever successfully implemented this algorithm before? If so, do you happen to see what my problem is? At first I tried to just code it using the algorithm, after having the same issue I literally rewrote their code basically line for line, using their same functions. The only issue I had was with their checkPointInTriangle as it seemed to always report collision, but I then implemented a check I read in Real Time Collision Detection and no longer got that issue. This leads me to believe maybe the author of this document made an error in it.
Here is my Vertex Two to Vertex Three check, it should report collision but it does not.
// p3 -> p1:
edge = p1-p3;
baseToVertex = p3 - base;
edgeSquaredLength = squaredLength(edge);
edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);
edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);
a = edgeSquaredLength*-velocitySquaredLength +
edgeDotVelocity*edgeDotVelocity;
b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity, &baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;
c = edgeSquaredLength*(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;
if (getLowestRoot(a,b,c, t, &newT)) {
float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/
edgeSquaredLength;
if (f >= 0.0 && f <= 1.0) {
t = newT;
foundCollison = true;
collisionPoint = p3 + f*edge;
}
}
Here is everything, in case it is interesting. I have checked for typo's countless times.
D3DXVECTOR3 triangleNormal = triangle->GetNormal();
D3DXVECTOR3 triangleOrigin = triangle->GetVertexOne();
D3DXVECTOR3 sphereVelocity = sphere->GetVelocity();
D3DXVECTOR3 p1 = triangle->GetVertexOne();
D3DXVECTOR3 p2 = triangle->GetVertexTwo();
D3DXVECTOR3 p3 = triangle->GetVertexThree();
D3DXVECTOR3 vBasePoint = sphere->GetOrigin();
// Get interval of plane intersection:
double t0, t1;
bool embeddedInPlane = false;
// Calculate the signed distance from sphere
// position to triangle plane
double signedDistToTrianglePlane;
{
double nDotOrigin = D3DXVec3Dot(&vBasePoint, &triangleNormal);
signedDistToTrianglePlane = nDotOrigin + -(triangleNormal.x*triangleOrigin.x +
triangleNormal.y*triangleOrigin.y + triangleNormal.z*triangleOrigin.z);
}
// cache this as we’re going to use it a few times below:
float normalDotVelocity = D3DXVec3Dot(&triangleNormal, &sphereVelocity);
// if sphere is travelling parrallel to the plane:
if (normalDotVelocity == 0.0f) {
if (fabs(signedDistToTrianglePlane) >= 1.0f) {
// Sphere is not embedded in plane.
// No collision possible:
crCollisionResult.enCollisionState = RESTING_CONTACT;
return crCollisionResult;
}
else {
// sphere is embedded in plane.
// It intersects in the whole range [0..1]
crCollisionResult.enCollisionState = HAS_COLLISION;
return crCollisionResult;
embeddedInPlane = true;
t0 = 0.0;
t1 = 1.0;
}
}
else {
// N dot D is not 0. Calculate intersection interval:
t0=(-1.0-signedDistToTrianglePlane)/normalDotVelocity;
t1=( 1.0-signedDistToTrianglePlane)/normalDotVelocity;
// Swap so t0 < t1
if (t0 > t1) {
double temp = t1;
t1 = t0;
t0 = temp;
}
// Check that at least one result is within range:
if (t0 > 1.0f || t1 < 0.0f) {
// Both t values are outside values [0,1]
// No collision possible:
crCollisionResult.enCollisionState = NO_COLLISION;
return crCollisionResult;
}
// Clamp to [0,1]
if (t0 < 0.0) t0 = 0.0;
if (t1 < 0.0) t1 = 0.0;
if (t0 > 1.0f) t0 = 1.0f;
if (t1 > 1.0f) t1 = 1.0f;
}
// OK, at this point we have two time values t0 and t1
// between which the swept sphere intersects with the
// triangle plane. If any collision is to occur it must
// happen within this interval.
D3DXVECTOR3 collisionPoint;
bool foundCollison = false;
float t = dElapsedTime;
// First we check for the easy case - collision inside
// the triangle. If this happens it must be at time t0
// as this is when the sphere rests on the front side
// of the triangle plane. Note, this can only happen if
// the sphere is not embedded in the triangle plane.
if (!embeddedInPlane)
{
D3DXVECTOR3 planeIntersectionPoint = (vBasePoint -
triangleNormal) + t0 * sphereVelocity;
if (checkPointInTriangle(planeIntersectionPoint, p1,p2,p3))
{
foundCollison = true;
t = t0;
collisionPoint = planeIntersectionPoint;
}
}
// if we haven’t found a collision already we’ll have to
// sweep sphere against points and edges of the triangle.
// Note: A collision inside the triangle (the check above)
// will always happen before a vertex or edge collision!
// This is why we can skip the swept test if the above
// gives a collision!
if (foundCollison == false) {
// some commonly used terms:
D3DXVECTOR3 velocity = sphereVelocity;
D3DXVECTOR3 base = vBasePoint;
float velocitySquaredLength = squaredLength(velocity);
float a,b,c; // Params for equation
float newT;
// For each vertex or edge a quadratic equation have to
// be solved. We parameterize this equation as
// a*t^2 + b*t + c = 0 and below we calculate the
// parameters a,b and c for each test.
// Check against points:
a = velocitySquaredLength;
// P1
D3DXVECTOR3 vBaseMinusP1 = base - p1;
b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP1));
c = squaredLength(p1-base) - 1.0;
if (getLowestRoot(a,b,c, t, &newT)) {
t = newT;
foundCollison = true;
collisionPoint = p1;
}
// P2
D3DXVECTOR3 vBaseMinusP2 = base - p2;
b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP2));
c = squaredLength(p2-base) - 1.0;
if (getLowestRoot(a,b,c, t, &newT)) {
t = newT;
foundCollison = true;
collisionPoint = p2;
}
// P3
D3DXVECTOR3 vBaseMinusP3 = base - p3;
b = 2.0*(D3DXVec3Dot(&velocity, &vBaseMinusP3));
c = squaredLength(p3-base) - 1.0;
if (getLowestRoot(a,b,c, t, &newT)) {
t = newT;
foundCollison = true;
collisionPoint = p3;
}
// Check agains edges:
// p1 -> p2:
D3DXVECTOR3 edge = p2-p1;
D3DXVECTOR3 baseToVertex = p1 - base;
float edgeSquaredLength = squaredLength(edge);
float edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);
float edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);
// Calculate parameters for equation
a = edgeSquaredLength*-velocitySquaredLength +
edgeDotVelocity*edgeDotVelocity;
b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity,
&baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;
c = edgeSquaredLength*
(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;
// Does the swept sphere collide against infinite edge?
if (getLowestRoot(a,b,c, t, &newT)) {
// Check if intersection is within line segment:
float f=(edgeDotVelocity*newT-
edgeDotBaseToVertex)/edgeSquaredLength;
if (f >= 0.0 && f <= 1.0) {
// intersection took place within segment.
t = newT;
foundCollison = true;
collisionPoint = p1 + f*edge;
}
}
// p2 -> p3:
edge = p3-p2;
baseToVertex = p2 - base;
edgeSquaredLength = squaredLength(edge);
edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);
edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);
a = edgeSquaredLength*-velocitySquaredLength +
edgeDotVelocity*edgeDotVelocity;
b = edgeSquaredLength*(2.0f*D3DXVec3Dot(&velocity,
&baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;
c = edgeSquaredLength*(1.0f-
squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;
if (getLowestRoot(a,b,c, t, &newT)) {
float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/
edgeSquaredLength;
if (f >= 0.0 && f <= 1.0) {
t = newT;
foundCollison = true;
collisionPoint = p2 + f*edge;
}
}
// p3 -> p1:
edge = p1-p3;
baseToVertex = p3 - base;
edgeSquaredLength = squaredLength(edge);
edgeDotVelocity = D3DXVec3Dot(&edge, &velocity);
edgeDotBaseToVertex = D3DXVec3Dot(&edge, &baseToVertex);
a = edgeSquaredLength*-velocitySquaredLength +
edgeDotVelocity*edgeDotVelocity;
b = edgeSquaredLength*(2.0*D3DXVec3Dot(&velocity,
&baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex;
c = edgeSquaredLength*
(1.0-squaredLength(baseToVertex))+edgeDotBaseToVertex*edgeDotBaseToVertex;
if (getLowestRoot(a,b,c, t, &newT)) {
float f=(edgeDotVelocity*newT-edgeDotBaseToVertex)/
edgeSquaredLength;
if (f >= 0.0 && f <= 1.0) {
t = newT;
foundCollison = true;
collisionPoint = p3 + f*edge;
}
}
}
This question was originally part of another topic, however, I moved it out to make it a more appropriate place. Hopefully someone else can learn something from this topic.
[Edited by - simotix on April 27, 2010 11:24:44 AM]