• Advertisement
Sign in to follow this  

A very specific GJK question

This topic is 4781 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

This is for anyone who has knowledge about implementing the GJK algorithm. When computing for subsimplex of simplex "Wk U {wk}", should the simplex itself always be acceptable (i.e. should the calculation always show) as a suitable subsimplex of itself (at least in the case where there are no other suitable subsimplex). This is a problem for me as according a Gino Van Den Bergen paper, to look for subsimplex, only those subset X that contains wk need to be inspected. I added this optimisation into my implmentation and algo bombs out because it reaches a situation where non of the subsimplex it inspected is suitable (including the original simplex itself), so the lambda values cannot be calculated correctly (as it requires all delta value for subsimplex to be > 0.0). Previous version of my implementation inspects subsimplex X that does not contain wk and were able to find one suitable.

Share this post


Link to post
Share on other sites
Advertisement
I am also trying to figure out the intecasies of GJK and im comming up short. I come from a background of basic collision detection using ray tracing and simple bounding primatives.

I think I am on the fringe of cracking it but I am still getting very erronious results. I was wondering seen as we are both having problems if you would like to knock our heads together and try andf come up with some kind of solution?

Share this post


Link to post
Share on other sites
Wow, after all these time, somebody replied.

I have actually fixed the problem described in my post (an embarassing indexing error) and the implementation now behaves reasonably well.

I am willing help you with difficulties you may be having with implementing GJK, however keep in mind that I only know how it works but not all the whys.

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_work
Gino van den Bergen's book is probably a good place to look to thoroughly understand the why's, :).


It is on my amazon wishlist.

Share this post


Link to post
Share on other sites
I have his book but as I am not that oh fay with Mathematical symbols I find the book extrememly hard goin. I think I have got the idea of the technique but I need to confirm one major issue.

In what space is the collision detection performed because I have been using it in World Space and it is behaving badly and with a little bit of investigation I think the reason is that I am not performing it about the origin.

Could you help?

Share this post


Link to post
Share on other sites
The GJK algo, iterative bits works in configuration space (abstract stuff), where you construct the minkoski sum and traverse on its surface to find the closest point to origin in configuration space.

To do this you need to be able to find the support point of an object (I used convex hull) in any given direction. There is a forumla relating support mapping in object space to support mapping in world space.

I don't quite understand what you mean about not performing it about the origin, so please clarify.

Share this post


Link to post
Share on other sites
I think this is the area I am struggling to understand. I was not computing the mincowsky sum I dont think, I was under the impression that the support map was generated by using a Vector between the two closest points already calculated in the Support mapping formula. From what you have just said I dont think im doing it anywhere near correctly.

The main problem I was having with the mincowski sum was how it was calculated. I understand it is a resultant shape generated by the combination of the two objects but i am unsure how it should be calculated in real life. Once this is calculated I understnad we take a point at random from this mincowski sum simplex and use this vector in then generated the support map.

The next question is as there are two objects combined, lets say a cylinder and a sphere, the mincowski sum object will look somthing like a tic tac. Do I have to derive and support map equation for the new object or do I find the support map for each and then substitute one from the other?

Sorry to bombard you with questions but I really do want to understand this technique and feel I can do it, im just doing it via the scenic route :D

Thanx for you time

Share this post


Link to post
Share on other sites
support mapping maps a vector representing direction to a point on the surface of the object which has maximal displacement along the that direction, so
support function sA(D) will return a point on A that has maximal displacement along D. It is simple to find this in object space, to get it in world space there is that formula in all the GJK papers that given a transformation will get you the support point in world space.

to get the support function for the minkowski sum of two object (use world space one here), what you actually want is the support mapping for A + (-B), you get that using the support function of the two objects as follow:
sA-B(D) = sA(D) - sB(-D).

The iterative step basically finds progressively better D that minimises the distance between A and B, but you don't need to worry about this when you are writing the support function. Don't worry about the shape of the minkowskit sum, it is not that important if you are using convex objects

Share this post


Link to post
Share on other sites
Ok, I think it would be best if i explain what im doing so u can see where im missing the point cos i think im ok to the support map bit.

In my algorithm i start out by calculating my first support point by finding the vector between the two object centres (i thought this was ok as the two random points as they both lie inside it) and then using the Minus Vector (ala Gino Van Den Bergen paper) as the D value in your equation above.

sA-B(D) = sA(D) + sB(-D)

The point that is output is then put onto my Simplex list. A while loop is then entered, and as it is the first occasion, the w vector i just put onto the Simplex List is used as the new D vector to find the new Support map.

I then run the code below where the V vector is the D input vector and w is the support point. 0.1 is the tolerance I want to test to, is this a close enough distance?

gamma = D3DXVec3Dot(&V, &w) / VecMagnitude(&w);
mu = Max(mu,gamma);

if((VecMagnitude(&V) - mu) <= 0.1f)
{
close_enough = true;
}

If the objects are not close enough, I place the w vector onto my Simplex List and sort the list so the closest vector to the origin is at the front of the list.

I am very unsure about how to transform the support point into world space, do I transform the point by the sum of the two object world matrices ?

When the loop continues, because there is more than one point in the simplex, I calculate the vector V = V1 - V2 where V1 is the closest support point to the origin and V2 is the next closest. The loop then continues as above.

Lastly when we have found the point on the minkowski sum simplex which is the closest to the origin, how do u work out the two points which are closest on the objects which this point refers to?

Sorry for all the questions, thanks for your help :D

Share this post


Link to post
Share on other sites
In one of the Gino van den's paper, he has the algorithm has follow:

v = aribtrary point in A -B;
W = empty;
mu = 0;

close_enough = false;
while not close_enough and v /= 0 begin //test that v's magnitude is not near zero
{
w = sA-B(-v);
sigma = v * w / ||v||;
mu = max(mu, sigma);
close_enough = ||v|| - mu <= e; //e is tolerance, small postive number

if not close_enough then begin
{
v = vector_on_simplex_closest_to_origin(W \/ {w}); //\/ means set union
W = "smallest X which is subset of (W \/ {w]) such that v is contain in X
}
}

return ||v||

This is similar to the algorithm you described, this is missing the bit which initialises the simplex with at least one vertex, (he was only looking for distance, not closet pair of point). Check your algo with that.


As for the transformation, the support function you use should be in world space which relates to the object space support function via:
given T(x) = Bx + c, stA(D) = T(sA(Bt * D)), where T(x) is the transformation, B is the rotation matrix, c is translation vector, stA(D) is the support function in world space and Bt is the transpose of the rotation matrix.


The part which calculate the nearest point on the simplex to the origin should also return a set of delta values corresponding to the support vertices in the simplex (which in turn is calculated from the support point of A and B), if you store the necessary information to find out which vertex in A and B forms the support points, them the sum of delta values multiplied to the vertex's position should give you the closest point on that object.

I have not explained that part very well, but read this, it is very helpful:

http://www.win.tue.nl/~gino/solid/jgt98convex.pdf

Share this post


Link to post
Share on other sites
yes, using barycentric coordinates when you update the simplex with a newly found point on the surface of the Minkowski sum, you should end up with weights, and corresponding points on A and B. After the iterations are complete, you just re-apply the weights to the vertices of A and B and that shoudl give you back the support points on both objects.

for the transformations, it's just the usual local space to world space transforms.

Share this post


Link to post
Share on other sites
to get back to your original question, since I'm also wondering about GJK, If you found that the sub-simplex is your original simplex, it means that the {w} does not bring you closer to the origin, so effectively tou should be at the closest point by now. I think it's related to his further annexes about getting stuck in a loop for very large flat surfaces that are colinear.

Is Gino roaming these forums by any chance? :)

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
to get back to your original question, since I'm also wondering about GJK, If you found that the sub-simplex is your original simplex, it means that the {w} does not bring you closer to the origin, so effectively tou should be at the closest point by now. I think it's related to his further annexes about getting stuck in a loop for very large flat surfaces that are colinear.

Is Gino roaming these forums by any chance? :)


Don't think I have seen him around, but he did reply to me when I posted the question on comp.graphics.algorithms.

In the paper I linked, he suggested a way of preventing this sort looping behaviour and it works quite well, which is probably why my implementation worked even though it was actually indexing the wrong place at one point.

Share this post


Link to post
Share on other sites
Quote:
Original post by GameCat
GJK algorithm explained b Christer Ericsson. Sorry, don't have time to read through the tread properly, but the above link is a good read on GJK.


That link doesn't seem to work. I think you meant to link to my SIGGRAPH'04 GJK presentation here (both slides and notes):

http://realtimecollisiondetection.net/pubs/

I should point out that in my presentation I deliberately avoided Johnson's distance subalgorithm and instead used a geometric approach, which I find to be more intuitive (and which can be made to be equivalent, with appropriate twiddles to the math).


Christer Ericson
Sony Computer Entertainment, Santa Monica

Share this post


Link to post
Share on other sites
Thank you very much Christer for posting the link for your slides and notes. I have had a quick look at them and I think I have finally got the gist of the algorithm and how it actually works.

There was a point I was slightly hazy about. When you try to find the Voronoi region the point lies in, do you perform the region tests in 3D or do you project the triangle onto a projection plane and then perform the calculations in the 2D projection space?

Share this post


Link to post
Share on other sites
Still waiting for your book to arrive, Chirster [wink] Can't wait...

*grumble.... Amazon...*

Share this post


Link to post
Share on other sites
Quote:
Original post by PhilTheGreek
There was a point I was slightly hazy about. When you try to find the Voronoi region the point lies in, do you perform the region tests in 3D or do you project the triangle onto a projection plane and then perform the calculations in the 2D projection space?


You perform the tests directly in 3D.


Christer Ericson
Sony Computer Entertainment, Santa Monica

Share this post


Link to post
Share on other sites
Is the following code correct for calculating the support mapping for the minkowski sum. The imput parameter is the negated closest point from my simplex vector.

D3DXVECTOR3& CMinkowski::SupportMapping(D3DXVECTOR3 V)
{
D3DXVECTOR3 P1 = child1->SupportMapping(V);
D3DXVECTOR3 P2 = child2->SupportMapping(-V);

return (P1 - P2);
}

I am looking at different mappers and seeing different ways of calculating the support map for the minkowski sum. Can anyone help?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement