# Quick GJK Question

This topic is 4623 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
(V dot -P) > (P dot -P)?

or ((V - P) dot -P) > 0?

probably needs an epsilon value

((V - P) dot -P) > -Epsilon.

##### Share on other sites
Nope, tried all those, apparently they're always true (early out situation) [sad]

##### 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 on other sites
Hi Christer, Great book, though you should have added some actual code for GJK [smile].

Well, it keeps either locking or returning early, so I'll start examining the suport mapping code with more detail, thank you both.

##### Share on other sites
If you still have problems, could be as simple as a question of signs or wrong sign on the threshold.

##### 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*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 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 on other sites
Quote:
 Original post by oliiithat'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 oliiiOut = 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 oliiifor 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!

That was me.

##### 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.

##### Share on other sites
Quote:
 Original post by oliiiAnyway, 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 on other sites
You know what? is this correct? [smile]

    /*       5- Compute V as a supporting point in direction -P.    */    direction=-P;    direction.Normalize();    ellipsoid.GetSupportPoint(direction,A);    polyhedron.GetSupportPoint((direction*-1),B);    V=A-B;

##### 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 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).

Now, to dig deep in the code [smile]

##### 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 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.