Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


Problem computing GJK support points


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 chandlerp   Members   -  Reputation: 105

Like
0Likes
Like

Posted 04 November 2012 - 03:44 PM

I'm trying to implement the GJK algorithm but am having difficulty calculating the support points. For my test case I am using equally size boxes stacked on top of each other, with box 2 at the origin and box 1 translated 10 units on the Y axis.

 ____
| 1  |
|____|
| 2  |
|____|

I start with a search direction of ( 0, 1 ) which finds the support points:
Box 1 - ( 5, 15 )
Box 2 - ( 5, -5 )

This yields the GJK support point of ( 5, 15 ) - ( 5, -5 ) == ( 0, 20 ). The Y term is correct but the X term is obviously wrong; the correct point on the Minkowski difference is ( 20, 20 ). This is found if Box 2's vertex at ( -5, -5 ) is used, but because both ( 5, -5 ) and ( -5, -5 ) meet the max( -DtBj ) requirement it depends which vertex was added to the hull first.

Question is how to guarantee the correct vertex is found to calculate the difference? Bonus points for a solution which works in 3 dimensions as that is the world the algorithm lives in.

Edited by chandlerp, 04 November 2012 - 03:45 PM.


Sponsor:

#2 greggles   Members   -  Reputation: 347

Like
2Likes
Like

Posted 04 November 2012 - 08:59 PM

Maybe I'm missing something, but what is wrong with (0, 20)? Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.

#3 chandlerp   Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 November 2012 - 09:05 AM

Maybe I'm missing something, but what is wrong with (0, 20)? Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.


Ah, yep. I think I've been staring at code and formulas too long. Thank you!

#4 BobXIV   Members   -  Reputation: 318

Like
0Likes
Like

Posted 08 November 2012 - 08:45 AM

Maybe I'm missing something, but what is wrong with (0, 20)? Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.

Greggles maybe I'm misunderstanding you, what you say is correct but the vertex (0,20) or any support point is indeed one of the vertices... if you mean the vertices of the Minkowski difference.

#5 greggles   Members   -  Reputation: 347

Like
0Likes
Like

Posted 08 November 2012 - 07:34 PM


Maybe I'm missing something, but what is wrong with (0, 20)? Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.

Greggles maybe I'm misunderstanding you, what you say is correct but the vertex (0,20) or any support point is indeed one of the vertices... if you mean the vertices of the Minkowski difference.

I think you may have misunderstood me. Let me clarify the calculations:

The original shapes are define by vertices
(-5, 5), (5, 5), (5, 15), (-5, 15)
and
(-5, -5), (5, -5), (5, 5), (-5, 5)

We know (intuitively, but this can be determined algorithmically with more calculation) that the resultant diffence will be a square, so finding the four vertices of the difference:
(-5, 5) - (5, 5) = (-10, 0)
(5, 5) - (-5, 5) = (10, 0)
(5, 15) - (-5, -5) = (10, 20)
(-5, 15) - (5, -5) = (-10, 20)
So there is an edge from (10, 20) to (-10, 20).

(0, 20) lies in the middle of this edge instead of one of its endpoints; thus it is not a vertex.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS