Stuck at world.step

[William]

Any more info on this? Still curious if there's a problem with GJK or if you encountered the problem with SAT (just later)?

William

[maheshkurmi]

The very similar problem consumed almost half of my day.
Finally I got the source for the problem (the stuck in loop) in org.dyn4j.collision.narrowphase.Gjk class in this function

Code: Select all

protected boolean detect(MinkowskiSum ms, List<Vector2> simplex, Vector2 d) {
      // check for a zero direction vector
      if (d.isZero()) d.set(1.0, 0.0);
      // add the first point
      simplex.add(ms.getSupportPoint(d));
      // is the support point past the origin along d?
      if (simplex.get(0).dot(d) <= 0.0) {
         return false;
      }
      // negate the search direction
      d.negate();
      int j=0;
      // start the loop
      while (true) {
         j++;
         if(j>2000){
            System.out.println("stuck in loop in collision.narrowphase.Gjk 264 line");
         }
         // always add another point to the simplex at the beginning of the loop
         simplex.add(ms.getSupportPoint(d));
         // make sure that the last point we added was past the origin
         if (simplex.get(simplex.size() - 1).dot(d) <= 0.0) {
            // a is not past the origin so therefore the shapes do not intersect
            // here we treat the origin on the line as no intersection
            // immediately return with null indicating no penetration
            return false;
         } else {
            // if it is past the origin, then test whether the simplex contains the origin
            if (this.checkSimplex(simplex, d)) {
               // if the simplex contains the origin then we know that there is an intersection.
               // if we broke out of the loop then we know there was an intersection
               return true;
            }
            // if the simplex does not contain the origin then we need to loop using the new
            // search direction and simplex
         }
      }
   }

to get rid of the problem I replaced

Code: Select all

if (simplex.get(simplex.size() - 1).dot(d) <= 0.0)

with

Code: Select all

if (simplex.get(simplex.size() - 1).dot(d) <= DEFAULT_DISTANCE_EPSILON)

Let me know if it solves the problem, but I think William should have better solution.

[William]

Thanks for finding this. Do you have a test case that I could use to reproduce?

I just need the shapes and their transforms to setup a test.

William

[maheshkurmi]

It is very difficult to reproduce it on demand since the culprit for the bug is floating point precision.
what i got in debug>>

Code: Select all

simplex.get(simplex.size() - 1).dot(d)

returns double value of order 10e-16 while we are comparing it with 0.0, thats why it gets stuck.

BTW the test case (stucks in approx 1 out of 20-30 trials) had just one disc and one large infinite mass rectangle.

[William]

I understand the cause, but I'm looking for a reproduction case so I can test my fix and add a JUnit test for it. If you happen to see this again in debug mode, see if you can .toString() the shapes and transforms. I still haven't been able to produce this problem myself.

Either way, the GJK code should exit after maxIterations anyway - while(true) is always dangerous when the exit condition is based on floating point.

Thanks,
William

[William]

This should be fixed in the 3.3.0 version.

Thanks,
William