Jump to content
  • Advertisement
Sign in to follow this  
shaobohou

A very specific GJK question

This topic is 4871 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
Sign in to follow this  

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!