Sign in to follow this  
Kwizatz

Quick GJK Question

Recommended Posts

Ok, thanks to the Real Time Collision Detection book and the papers explaining GJK by Christer Ericson, I got my Implementation of GJK going, however I have a problem with the exit condition in the case that the 2 polytopes are not colliding. On these notes, page 6, where the algorithm is detailed step by step, the 6th step reads:
Quote:
If V is no more extremal in direction -P than P itself, stop and return A and B as not intersecting. The Length of the vector from the origin to P is the separation distance of A and B.
The question is, how do I find out whether "V is no more extremal in direction -P than P"? I tried just comparing the lenghts of the 2 points, but that resulted in an early out, if I dont check at all, my test case locks into the loop as soon as the 2 polytopes stop colliding, so I think that besides this issue, I got the implementation right [smile]

Share this post


Link to post
Share on other sites
Quote:
The question is, how do I find out whether "V is no more extremal in direction -P than P"?
What oliii posted is the correct interpretation, namely:

if (Dot(V - P, -P) <= 0.0f) {
/* Stop, return A and B as not intersecting */
}

You ultimately want to have some tolerance in this comparison (and not just compare to zero) but if the above isn't working for you, then you have some problem elsewhere (presumably in computing P, or possibly V).

Share this post


Link to post
Share on other sites
Well, I am suspecting my support mapping function, it seems to work just the way I want it with convex vs convex (actually 2 boxes) tests, here is the code:


void Polyhedron::GetSupportPoint(const CVector3& direction,CVector3& out) const
{
int c = 0;
size_t numVerts = points.size();
float h = points[0]*direction;
float d;
for (size_t i = 1; i < numVerts; ++i)
{
if ((d = points[i]*direction) > h) { c = i; h = d; }
}
out=points[c];
}






However, when doing ellipsoid vs convex tests, I get errors such as reporting the 2 objects colliding when they're obviously not, or locking in the loop, here is the code for the ellipsoid mapping function (I am not considering rotations yet so it is an Axis aligned ellipsoid), transform.mx is an OpenGL 4x4 matrix for the ellipsoid:


void Ellipsoid::GetSupportPoint(const CVector3& direction,CVector3& out) const
{
out.v[X]=transform.mx[12]+(radii.v[X] * direction.v[X]);
out.v[Y]=transform.mx[13]+(radii.v[Y] * direction.v[Y]);
out.v[Z]=transform.mx[14]+(radii.v[Z] * direction.v[Z]);
}






Edit: on the first snippet, the * operator performs the dot product operation between the 2 vectors.
More Edit: I asume direction to be normalized on the second function, and I pass a normalized -P value in the GJK function to both.

Share this post


Link to post
Share on other sites
that's wrong. I'm not sure of the exact suport mapping function for an ellipsoid, but in should be in Christer's book. Here is a try...

Out = Position + fabs(Dir * Direction[X]) * Radii.x * Direction[X] +
fabs(Dir * Direction[Y]) * Radii.y * Direction[Y] +
fabs(Dir * Direction[Z]) * Radii.z * Direction[Z];


for a box, I know it, it's relatively similar

Out = Position + sign(Dir * Direction[X]) * Radii.x * Direction[X] +
sign(Dir * Direction[Y]) * Radii.y * Direction[Y] +
sign(Dir * Direction[Z]) * Radii.z * Direction[Z];

Direction[] are vectors taken from the transform matrix (3 first elements of columns or rows, depend on your matrix stuff). For example, Direction[X] = Vector(trans.m[0], trans.m[1], trans.m[2]), or maybe Direction[Z] = Vector(trans.m[2], trans.m[6], trans.m[10]).

Position is the bottom row or column. for you, apparently, Position = Vector(trans.m[12], trans.m[13], trans.m[14]).



Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by oliii
that's wrong. I'm not sure of the exact suport mapping function for an ellipsoid, but in should be in Christer's book. Here is a try...


Surprisingly, the mapping function for ellipsoids is not there, on page 63 the support mapping for a sphere is given by Sc(d)=O+r*(d/||d||) or Sphere Origin plus radius times the normalized distance (or so I thought), which is from where I came up with my erronius function.

There is a note in page 402 that reads: "Although presented here as a methot operating on polyhedra only, the GJK algorithm can in fact be applied to arbitrary convex bodies. Because bodies are always sampled through their support mappings, all that is required to allow the GJK algorithm to work with general convex objects is to supply appropiate support mappings", but that's as far as it goes in that direction.

I am just saying here [smile], the book is in fact great, I added a lot of stuff to my math library, and the rest I fixed thanks to it.

Quote:
Original post by oliii
Out = Position + fabs(Dir * Direction[X]) * Radii.x * Direction[X] +
fabs(Dir * Direction[Y]) * Radii.y * Direction[Y] +
fabs(Dir * Direction[Z]) * Radii.z * Direction[Z];


Thanks, I will test that, I would rate you up, but I already gave you the highest ratting I can [smile]

Quote:
Original post by oliii
for a box, I know it, it's relatively similar


Actually, I said boxes because my test polyhedrons are boxes (you know, 8 verts, 6 faces) I took the function from FreeSOLID, this file to be exact, the very last function "Point Polyhedron::support", and like I said, this test does work.

Cheers!

Share this post


Link to post
Share on other sites
For a GJK implementation, it's all in solid, and Gino also wrote a book about it. It's got support mappings for polyhedras, boxes, cones and cylinders, but sadly, no ellipsoid :)

He also discuss a way to calculate the MTD in case of an intersection. There is little discussion on building a continuous GJK, but theer is a paper about it, and it's relatively straight forward.

GJK in my opinion is probably the best all round collision detection system. But then again, doing collisions on the three simplest and most used collision shapes (AABB, OOBBox, Sphere, triangle) isn't that bad to do.

anyway, enough rambling, hope I answered your questions [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
Anyway, enough rambling, hope I answered your questions [smile]


You sure did, but now I am trying the ellipsoid mapping function you gave me, I dont have a float * Vector operator, so I made some adjustments, here is the function I have now, is this the equivalent to yours? it makes sence (the mappings are on the ellipsoid surface), but I better make sure:


out = position +
directionX * (radii.v[X] * fabs(direction * directionX)) +
directionY * (radii.v[Y] * fabs(direction * directionY)) +
directionZ * (radii.v[Z] * fabs(direction * directionZ));



* between vectors mean dot right?

Now, it seems that the points are being all positioned on the positive quadrant of the ellipsoid because of the fabs call, this time it locks if I move the ellipsoid to a non colliding position on the negative Y direction and exits early if I move it on the positive Y direction, this makes sence since apparently the mapping for -1,0,0 and 1.0.0 directions return the same point.

Share this post


Link to post
Share on other sites
It's equivalent but you can implement an operator like I did (Vector = float * Vector).

and also the unary operator, so instead of

polyhedron.GetSupportPoint((direction*-1),B);

you'd do

polyhedron.GetSupportPoint(-direction,B);


class Vector
{
public:
Vector() {}
//....
//.....

float operator * (const Vector& V) const { return (x*V.x + y*V.y + z*V.z); } // my dot product

Vector operator * (float k) const { return Vector(x*k, y*k, z*k); } // uniform scaling

Vector operator - () const { return Vector(-x, -y, -z); }

friend Vector operator * (float k, const Vector& V) { return V * k; }

};





just for the sake of clarity [smile]

about the quadrant thing, that should not matter which direction the ellipsoid or the sep axis is facing. This is why an fabs() is used. As for signs, it depends entirely on your implementation. The support mapping I provide here is the positive support (the max bound), but sometimes people use the negative support (the min bound).

Sometimes I prefer negative, as it is more representative for a collision. Imagine a ball hitting a table. Collision is going up, but you want the bottom vertex as support, hence the negative mapping.

All signs depends. You'll have to simply debug it step by step and check which vertex is returned.

EDIT : I think you're right about the bad ellipsoid mapping. there is in facxt no need for abs(). try


out = position +
directionX * (radii.v[X] * (direction * directionX)) +
directionY * (radii.v[Y] * (direction * directionY)) +
directionZ * (radii.v[Z] * (direction * directionZ));





I got confused by the box mapping.

Share this post


Link to post
Share on other sites
Thanks, I did remove the fabs calls, now I am getting similar results as with my original function, but thanks to you, I don't have to worry about rotation later [smile].

There must be something on the simplex creation code or on the get closest point in Triangle/Polyhedron (or I am using them Wrong), here for example the green lines and points are supposed to be the simplex containing the origin, which is clearly NOT contained in the simplex, the blue sphere (actually an ellipsoid with all radii having the same length) means the GJK function returned that a collision took place, obvously, it did not.

The pink points at the sides of the sphere are support mapping points for positive and negative axis directions (just to test that the support mapping points are correct).

GJK Fails

Now, to dig deep in the code [smile]

Share this post


Link to post
Share on other sites
For simplicity, I'd try with only one shape (a box), that is away from the origin (set A or B to (0, 0, 0) and ignore the second convex shape), so you can see the support points being rendered on the shape one after the other on the surface of the convex shape.

It should be easier to debug and visualise. Then when this is working you can introduce the second shape.

That's just the way I'd debug it.

Share this post


Link to post
Share on other sites
I did what you sugested, everything worked in that convex shape vs Origin situation, so I printed to stdout the end simplex points from the box vs sphere test, seems like for some reason when the simplex is a tetrahedron and 2 of the points are too close to each other (for example a 0.000204 difference), the ClosestPointInTetrahedron function retuns the origin, and thus a wrong collision is detected.

Now I have to trace that function.

Just thought I should post an update [smile]

Oh and thanks for the operator functions, I was going to add the float * vector one but I didnt know how.

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