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]
Quick GJK Question
Author
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:
(V dot -P) > (P dot -P)?
or ((V - P) dot -P) > 0?
probably needs an epsilon value
((V - P) dot -P) > -Epsilon.
or ((V - P) dot -P) > 0?
probably needs an epsilon value
((V - P) dot -P) > -Epsilon.
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).
Author
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.
Well, it keeps either locking or returning early, so I'll start examining the suport mapping code with more detail, thank you both.
If you still have problems, could be as simple as a question of signs or wrong sign on the threshold.
Author
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:
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:
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.
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.
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]).
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]).
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
