Sign in to follow this  
oliii

new take on swept sphere collision detection

Recommended Posts

oliii    2196
OK, first off, I have this algorithm that returns the closest point on a triangle to another point. I use it for basic sphere-triangle overlap detection and response, like in this. that's all fine and dandy, but not really useful for swept tests. Or so I thought... Then it occured to me that all is required it to see from the swept sphere viewpoint, looking down the direction of movement. Doing that, you will get the closest point on the triangle to the ray, as barycentric coordinates. SO now you have the potentially colliding point, all you have to do is trace the ray from that point back towards the sphere and see if it intersects the sphere, and when. Drum rolls, cue to the swept sphere-triangle solution. In essence, It's very much like testing if a ray intersects a triangle. Simple and clean solution (if it works). OK, so on little problem. I need to transform the triangle as viewed along the ray direction, like doing a shadow projection if you will. Another is what happen when the projection is really really shallow. But the maths to calculate the projection matrix seem to escape me. Any thoughts?

Share this post


Link to post
Share on other sites
oliii    2196
no matter, I've got it, from a shadow matrix equation actually.



void Project(const Vector& P, const Vector& Dir, Vector& Q)
{
float dot = Dir * Dir;
const float threshold = 0.000001f;

if (dot < threshold)
{
Q = P;
return;
}

float e0 = -Dir.x * Dir.x + dot; float e1 = -Dir.x * Dir.y; float e2 = -Dir.x * Dir.z;
float e3 = -Dir.y * Dir.x; float e4 = -Dir.y * Dir.y + dot; float e5 = -Dir.y * Dir.z;
float e6 = -Dir.z * Dir.x; float e7 = -Dir.z * Dir.y; float e8 = -Dir.z * Dir.z + dot;

Q.x = e0 * P.x + e1 * P.y + e2 * P.z;
Q.y = e3 * P.x + e4 * P.y + e5 * P.z;
Q.z = e6 * P.x + e7 * P.y + e8 * P.z;
}



and BTW, the algo seems to work. Here is the full algo



void Project(const Vector& P, const Vector& Dir, Vector& Q)
{
float dot = Dir * Dir;
const float threshold = 0.000001f;

if (dot < threshold)
{
Q = P;
return;
}

float e0 = -Dir.x * Dir.x + dot; float e1 = -Dir.x * Dir.y; float e2 = -Dir.x * Dir.z;
float e3 = -Dir.y * Dir.x; float e4 = -Dir.y * Dir.y + dot; float e5 = -Dir.y * Dir.z;
float e6 = -Dir.z * Dir.x; float e7 = -Dir.z * Dir.y; float e8 = -Dir.z * Dir.z + dot;

Q.x = e0 * P.x + e1 * P.y + e2 * P.z;
Q.y = e3 * P.x + e4 * P.y + e5 * P.z;
Q.z = e6 * P.x + e7 * P.y + e8 * P.z;
}

bool CSphere::Collide(const class CTriangle& xTriangle)
{
float u, v;

Vector Dir = m_xPos - m_xPrevPos;

float dist = Dir.Normalise();

if (dist > 0.00001f)
{
CTriangle Tri;
Project(xTriangle.V[0], Dir, Tri.V[0]);
Project(xTriangle.V[1], Dir, Tri.V[1]);
Project(xTriangle.V[2], Dir, Tri.V[2]);
Tri.Distance(m_xPrevPos, &u, &v);
}
else
{
xTriangle.Distance(m_xPrevPos, &u, &v);
}

Vector Pcoll;
xTriangle.CalculatePoint(Pcoll, u, v);

//Do the reverse-intersection;
float t = RayIntersection(Pcoll, -Dir);

if (t < 0 || t > dist)
{
return false;
}

m_xPos = m_xPrevPos + Dir * t;

//-----------------------------------------------
// then move the sphere away from the point.
//-----------------------------------------------
PushAwayFrom(Pcoll);

return true;
}

float CSphere::RayIntersection(const Vector& P, const Vector& D)
{
Vector L = P - m_xPrevPos;

// (Q - C)^2 = r2
// Q = P + D * t;
// ((P - C) + D.t)^2 = r2
// D.D.t2 + 2.((P-C).D).t + (P-C).(P-C) - r2 = 0
//
// => a.t2 + b.t + c = 0
//
// a = D.D
// b = 2.(P-C).D
// c = (P-C).(P-C) - r2;
//
// d = b.b - 4.a.c
// t0 = -b-sqrt(d) / 2a
// t1 = -b+sqrt(d) / 2a

float a = (D * D);
float b = 2.0f * (D * L);
float c = (L * L) - (m_fRad * m_fRad);

if (a < 0.0000001f)
{
return (c < 0.0f)? 0.0f : -1.0f;
}

if (c < 0.0f)
{
// interior
return 0.0f;
}

float d = b * b - 4.0f * a * c;

// miss
if (d < 0.0f)
{
return -1.0f;
}
d = (float) sqrt(d);

float t0 = (-b - d) / (2.0f * a);
float t1 = (-b + d) / (2.0f * a);

if (t0 > t1)
{
float temp = t0;
t0 = t1;
t1 = temp;
}

// too short
if (t1 < 0.0f)
{
return -1.0f;
}

// interior
if (t0 < 0.0f)
{
return 0.0f;
}

return t0;
}



Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
In essence, It's very much like testing if a ray intersects a triangle. Simple and clean solution (if it works).


It's not new. It works. Sort of.

Specifically, this is the method that Paul Nettle gave in his "ellipsoids" collision detection white paper. (I also describe it in my book, Section 5.5.6, if you have it.)

In a nutshell, you intersect an offsetted ray with the plane of the triangle, to find the point P of intersection at which the sphere first touches the plane (when moving towards it). Then you find the closest point Q on the triangle to this point P. From Q you fire a ray back at the sphere, which will give you the time of collision, if any.


Quote:
But the maths to calculate the projection matrix seem to escape me. Any thoughts?


No projection matrix necessary. Just offset the ray appropriately and do a ray/plane intersection calculation.


The reason I said it works "sort of", is that this method fails when the sphere is moving parallel to the plane of the triangle. (Because there is no intersection point with the plane in that case.) In some cases you can ignore such situations, in which case the method works fine. In other cases, you cannot ignore the problem, and the method must be enhanced with lots of additional code to handle this special case. For the latter cases, I'm suggesting shooting a ray against the Minkowski sum of the triangle and the sphere, which has no special cases.

Share this post


Link to post
Share on other sites
oliii    2196
yeah, I've re-read Nettle's paper, it's what I'm doing, "sort of". I don't like that special case either... back to the drawing board...

Share this post


Link to post
Share on other sites
gunning    749
Did you read the updated paper?

I just got it working yesterday and it is very stable. I never liked his collision response though because his sliding seems like a hack. A more accurate way would be to perform typical reflection of the sphere against the triangle keeping in mind both the surface friction and the coefficient of restitution. Then, sliding would happen automatically when the coefficient of restitution was 0 and would bounce appropriately when the coef isn't 0.

I'll upload the source this afternoon to my website.

Edit: The "updated" paper doesn't seem to be written by Nettle. Interesting.

[Edited by - skittleo on March 28, 2005 12:18:57 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this