Stuck at world.step

Posts that don't fit into other categories.
William
Site Admin
Posts: 378
Joined: Sat Feb 06, 2010 10:23 pm

Re: Stuck at world.step

Postby William » Sat Mar 10, 2018 10:15 am

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
Posts: 63
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Stuck at world.step

Postby maheshkurmi » Mon Mar 19, 2018 9:31 am

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
Site Admin
Posts: 378
Joined: Sat Feb 06, 2010 10:23 pm

Re: Stuck at world.step

Postby William » Mon Mar 19, 2018 8:09 pm

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
Posts: 63
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Stuck at world.step

Postby maheshkurmi » Tue Mar 20, 2018 1:36 am

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
Site Admin
Posts: 378
Joined: Sat Feb 06, 2010 10:23 pm

Re: Stuck at world.step

Postby William » Tue Mar 20, 2018 7:12 pm

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
Site Admin
Posts: 378
Joined: Sat Feb 06, 2010 10:23 pm

Re: Stuck at world.step

Postby William » Sat Apr 21, 2018 11:28 am

This should be fixed in the 3.3.0 version.

Thanks,
William


Return to “General Discussion”

Who is online

Users browsing this forum: No registered users and 1 guest