Jump to content
  • Advertisement
Sign in to follow this  
Kwizatz

Quick GJK Question

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
(V dot -P) > (P dot -P)?

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

probably needs an epsilon value

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

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
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 this post


Link to post
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 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*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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!