Infinite loop possible in dgContactSolver::RayCast?

[JoshKlint]

In Newton 3, one of my users has discovered a pretty common situation that will cause an infinite loop to form in dgContactSolver::RayCast.

The user is performing a long ray cast on a scene, and an enemy with a collider collision shape is going into an infinite loop.

At line 1126, distance is equal to 3.1436167795842012e-09:

Code: Select all

         dgAssert (v.m_w == dgFloat32 (0.0f));
         const dgFloat64 distance = v.DotProduct(v).GetScalar();
         if (distance < dgFloat32 (1.0e-9f)) {
            index = -1;
            break;
         }

At line 1149, distance1 is equal to 0.000996447168, so the loop breaks and goes to 1181.

Code: Select all

const dgFloat32 distance1 = dir.DotProduct(wv).GetScalar();
if (distance1 < dgFloat64 (1.0e-3f)) {
   normal = dir;
   break;
}


Eventually, the logic hits this line:

Code: Select all

v = ReduceTriangle (index);
break;


And the loop starts again, forever, causing the program to freeze.

The function is confusing to me, and I do not know what I should be looking for.

[Julio Jerez]

if dist is 3.1436167795842012e-09
it is in fact very close to the tolerance.

but it seems there is round error, that prevent to getting closer.

In the pass that loop has a max number of iterations.
but the I made an improvement that use Cholesky to calculate the feature reduction, and I thought that it will not need that control.

That loop in general it iterates about 4 to 7 or 8 time, and in each iteration the distance should be monotonically smaller.
but if it the case that the line is almost collinear, like a line scraping the side of a shape, then numerical error can be larger than the monotonic descent and the algorithm may fail to terminate.
that will probably happen one in many million times, I have never seen it happens.

It is not a big problem; it just needs the max iteration limit, with a not hit.
(the line is parallel to one size of the shape, so that's a not hit)

Sync and try.

[JoshKlint]

If it is possible, my users will find it.

I also added some code that compares the current distance value to the last one, and exits if it doesnt change. Not sure if this is a good idea?

Code: Select all

   double lastvalue = NAN;
   do {
      dgInt32 iter = 0;
      dgInt32 cycling = 0;
      dgFloat64 minDist = dgFloat32(1.0e20f);

      do {
         dgAssert(v.m_w == dgFloat32(0.0f));
         const dgFloat64 distance = v.DotProduct(v).GetScalar();
         if (isnan(lastvalue) == false && lastvalue == distance) return param;
         lastvalue = param;


[Julio Jerez]

why are you doing that?
like I said, the ray is scraping a face that is almost collinear will the line.
That's a no hit, but numerical error prevents the algorithm from terminate.

that loop does not calculate the hit param, it finds the feature that the line hit.
(a point, and edge, a face or a volume)
the param is calculated when the loop terminates.
that test is not right.

just sync and it should work.

[JoshKlint]

Because I like to tinker. I synced your code, and then added my own fix that I don't understand.

I will remove it if it's bad.

[Julio Jerez]

It is bad, it is going to report incorrect hits.

just sync again, and it should just work.

[JoshKlint]

Thanks.

https://www.leadwerks.com/community/top ... in-update/