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 had a max number of iterations.
but then I made an improvement that use Cholesky to calculate the feature reduction, and I thought that it will not need that control.

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

It is not a big problem; it just needs the max iteration limit and terminate 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 tetrahedra 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/