# Quick GJK Question

This topic is 4951 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634090
• Total Posts
3015434
×