search

MattiaMontanari / openGJK

Fast and reliable implementation of the Gilbert-Johnson-Keerthi (GJK) algorithm for C, C#, Go, Matlab and Python
https://www.mattiamontanari.com/opengjk/
GNU General Public License v3.0
135 stars 37 forks source link

bug in ADAPTIVEFP branch #16

Closed adrianstephens closed 1 year ago

adrianstephens commented 3 years ago

openGJK.c, line 294, you're calling orient2d with the same parameters for B[0] and B[1] (presume it's supposed to be orient2d(pp, sb, sc)?)

Secondly, a question: in S1D is the dimension-reducing stuff necessary? After you have dotProduct(b, t) / dotProduct(t,t) can you not just clamp that to [0,1] as the lambda?

MattiaMontanari commented 3 years ago

Yes, that's likely a bug, but:

  1. I believe B[0] isn't right, although barely used because it represents the case when the latest vertex a is discarded - and that's never the case for GJK, but may be useful to develop for EPA.
  2. I doubt you actually need to ADAPTIVEFP.

I'm not sure if I understand your question, what do you mean by "clamp that to [0,1] as the lambda"? Anyway, unless you can guarantee that all your simplices are not "degenerate", then you need the reduction stuff. The SV method is recursive, but specifically for a 1-simplex (line segment) the call to S1D leads to either of these cases: (i) The origin is between A and B or (ii) The origin is beyond A. Again, the origin cannot be found beyond B in GJK, but may be useful to develop for EPA.

adrianstephens commented 3 years ago

Thanks for the reply - I don't need the ADAPTIVEFP, but I was looking at that branch because it was easier to understand than the for -loop in the non-adaptive case!

As for the S1D stuff, consider the test of point b. if x is dotProduct(b, t) / dotProduct(t, t) then det_pb = (x (ai - bi) + bi) - bi = x (ai - bi) so the sign test with ti (= bi-ai) is comparing the signs of x * (ai - bi) and -(ai - bi)

In other words, ai and bi make no difference, degenerate or not, to the sign check and you can just test for x < 0. And in the case of the origin being between A and B, x actually is the first lambda value.

Not sure if I've explained this properly or if I'm missing something?

Adrian

MattiaMontanari commented 3 years ago

You are right, there are a few unnecessary operations there: -bi, -1*. I believe the method would be equivalent but better coded - and better coding help presenting the method as well.

We have been working on a new, totally undocumented, method and for S1D things may work out like you said: first a dot product identifies the support of the point of minimum norm, then a second step computes the shortest vector.

MattiaMontanari commented 3 years ago

I won't do any work to fix the potential bug reported here, but I'll close this once I merge the dev branch into master as the new algorithm doesn't show this.