Critical NewtonCollisionIntersectionTest bug

[Cannos]

I'm using NewtonCollisionIntersectionTest to test if 2 chamfer cylinders overlap. When I do have a case of overlap, I'm getting inconsistent or wrong results from NewtonCollisionIntersectionTest. Here's sample code:

Code: Select all

dMatrix offsetMatrix (dGetIdentityMatrix());
offsetMatrix.m_front = dVector(0.0f, 1.0f, 0.0f, 0.0f);
offsetMatrix.m_up = dVector(-1.0f, 0.0f, 0.0f, 0.0f);
offsetMatrix.m_right = dVector(0.0f, 0.0f, 1.0f, 0.0f);
offsetMatrix.m_posit = dVector(0.0f, 0.1f, 0.0f, 1.0f);
dVector cylSize(0.8f, 0.2f, 0.0f, 0.0f);

NewtonCollision* const chamferCylinderCollision = CreateConvexCollision(world, offsetMatrix, cylSize, _CHAMFER_CYLINDER_PRIMITIVE, 0);
NewtonCollision* const chamferCylinderCollision2 = CreateConvexCollision(world, offsetMatrix, cylSize, _CHAMFER_CYLINDER_PRIMITIVE, 0);

dMatrix mtxC(0.0f, 3.141592f * -0.5f, 0.0f, dVector(9.40291786f, 2.99999571f, -4.01828432f));
dMatrix mtxD(0.0f, 3.141592f * -0.5f, 0.0f, dVector(9.25f, 3.00000072, -4.375f));
int result = NewtonCollisionIntersectionTest(world, chamferCylinderCollision, &mtxC[0][0], chamferCylinderCollision2, &mtxD[0][0], 0);



Running the above code results in an assert in dgContactSolver::CalculateIntersectingPlane(). I don't quite understand the code, but I'm guessing that it can't find some separating planes. That makes sense because the shapes are overlapping, but I'm not sure about the reason for the assert.

Once that call fails, dgContactSolver::CalculateClosestPoints() won't calculate m_closestPoint0 and m_closestPoint1 since there are no simplexPoints. Again, I think that makes sense. But then, dgContactSolver::CalculateConvexToConvexContacts() tries to calculate a penetration amount from m_closestPoint0 and m_closestPoint0. But these haven't been set to anything. They're just at their initial values. In an older version of code I'm using, it appears that these values aren't initialized, so I'm getting random results. In the current code, they appear to be initialized, but I don't see where that is happening.

Does any of that make sense? Are there some bug fixes I should integrate? Is there a better alternative way for me to check for overlap of bodies besides NewtonCollisionIntersectionTest? Thanks.

[Julio Jerez]

I think it should work at all time, overlapping of not overlapping, has you sync to later commit?
and in what demo do I paste that repro?

[Cannos]

I just pasted this at the beginning of BasicRestitution.

It has been about a month since I got the latest code. It asserts in this version and an older version I'm using. In the newer version it appears to give correct results because the following line in dgContactSolver::CalculateConvexToConvexContacts() has m_closestPoint0 and _closestPoint1 initialized to the same value, so the penetration == -DG_PENETRATION_TOL;

Code: Select all

      dgFloat32 penetration = m_normal.DotProduct4(m_closestPoint1 - m_closestPoint0).GetScalar() - m_proxy->m_skinThickness - DG_PENETRATION_TOL;


In an older version of code, m_closestPoint0 and m_closestPoint1 don't appear to be initialized, so I get random results.

[Cannos]

If the CalculateClosestPoints(); call right before the penetration calculation wasn't asserting and failing to produce closest points, this wouldn't be an issue. But I think in cases where closest points can't be calculated, it probably shouldn't be calculating a penetration amount based on unknown m_closestPoint0 and m_closestPoint1. At least this is my understanding.

[Julio Jerez]

Oh I see what is happening, the two shape are almost overlapping so the code cannot find a point that to start the penetration, so it support to return collusion failure.

The reason is that in deep penetration like that you can get contact point but there is not clear definition of the minimum translation distance the will resolve teh penetration.

The way teh algorithm happen is base of a theorem by Minkowski that say that the Minkowski difference of tow convex shapes is another convex shape.
so what the code does is that it build a partial directed convex hold of the two shapes and following the distance that is closed to the surface of the Mink difference.
however if the case of two equal shape both having an orientation that such that all points of the surface are at equal distance to the center, then there is not unique distance solution.

I decided to reunr -1 and put an assert there, becaus etshi si so rare that I have nevery seen it happing unless I delivetly place the shapes in place like you are doing.

I will remove the assert and wh you cna do is that you can't check is the function return -1. if teh funtion return -1 and di a small pertuvation of any of the matric and try again, any small change will produce the a good result.

Return a contact is a huge mistake because there the is no way to knwo whi is the shortet diorection to resule the penetration.

In general in the game if tshi ever happend what happen si that the moemetum of the body make that next time they get a good contact. but lie I said I have only seen thsi is specific demos that are set up to test that.

does that answer yor question?

[Cannos]

I understand why there wouldn't be a good direction to resolve the penetration, but I still need a reliable way to check if they are overlapping. I'm not exactly sure what you're suggesting.

I don't need to know how to de-penetrate, just if they are intersecting.

I have a lot of cases where this is happening, so it isn't rare. Though in all the cases I've seen so far, the orientations are similar. In my game, I allow shapes to pass through each other in certain cases, and I just need to know if they are currently overlapping.

Given this callstack:
CalculateConvexToConvexContacts()
CalculateClosestPoints()
CalculateIntersectingPlanes()

If CalculateIntersectingPlanes() returns -1, CalculateClosestPoints() won't calculate m_closestPoint0 and m_closestPoint1. But CalculateConvexToConvexContacts() is still calculating an incorrect penetration based on uninitialized closest points. I think CalculateConvexToConvexContacts() needs to not calculate a penetration value if CalculateClosestPoints returns false. See the code below - in the intersectionTestOnly case it doesn't check the return value of CalculateClosestPoints, but the other case does:

Code: Select all

dgInt32 dgContactSolver::CalculateConvexToConvexContacts ()
{
   dgInt32 count = 0;
   if (m_proxy->m_intersectionTestOnly) {
      CalculateClosestPoints();
      dgFloat32 penetration = m_normal.DotProduct4(m_closestPoint1 - m_closestPoint0).GetScalar() - m_proxy->m_skinThickness - DG_PENETRATION_TOL;
      dgInt32 retVal = (penetration <= dgFloat32(0.0f)) ? -1 : 0;
      m_proxy->m_contactJoint->m_contactActive = retVal;
      return retVal;
   } else {
      bool colliding = CalculateClosestPoints();
      if (colliding) {
         dgFloat32 penetration = m_normal.DotProduct4(m_closestPoint1 - m_closestPoint0).GetScalar() - m_proxy->m_skinThickness - DG_PENETRATION_TOL;
...



But if CalculateConvexToConvexContacts() doesn't have points to calculate a penetration from, is it safe to assume the bodies are overlapping? Are there non-overlapping cases where closest points cannot be calculated?

I think I'll still need to change something at the lower levels here, because at a high level NewtonCollisionIntersectionTest() is returning 0 in these cases, even if it's valid for CalculatingIntersectionPlanes() to return -1.

[Cannos]

In case the above was confusing, I'm wondering if something like this change would be correct?

Code: Select all

dgInt32 dgContactSolver::CalculateConvexToConvexContacts ()
{
    dgInt32 count = 0;
    if (m_proxy->m_intersectionTestOnly)
    {
        bool validPoints = CalculateClosestPoints();
        // NOTE : Only calculate penetration if we have valid closest points
        if (validPoints)
        {
            dgFloat32 penetration = m_normal.DotProduct4(m_closestPoint1 - m_closestPoint0).GetScalar() - m_proxy->m_skinThickness - DG_PENETRATION_TOL;
            dgInt32 retVal = (penetration <= dgFloat32(0.0f)) ? -1 : 0;
            m_proxy->m_contactJoint->m_contactActive = retVal;
            return retVal;
        }
        else
        {
            // NOTE: Is it safe to assume that when CalculateClosestPoints() fails, that there is penetration?  IntersectionTest returns true if contact count == -1, so return -1 here
            return -1;
        }
    }
    ...


[Cannos]

It may also be worth noting that if I change either of the 2 chamfer cylinders to a regular cylinder, it appears to work correctly.

[Julio Jerez]

Oh so you do have shapes that overlap in deep penetration.
The code will fail if the return value of -1 is ignored and it proceed to build a convex cap. This is because the simplex will have either zero volume, zero length, of will be zero area.

This akin to say you have tow point and you need to know the d point and a direction, you can do
P is p0 and n = the normal p1 -p0
The problem is that normalization can't calculate normal of zero length.
Similarlly, the function that calculate. The the mining penetration will fail on a shape that does not have minimum penetration.

I can fix it was silly if I add a part the calculate a penetration instead of a mini penetration
And this will only do it when the assert triggers.

The code is very simple, but is more that just a tweak.

So I will added this weekend.

Basically is a code that build the hull cap along any two supporting point.

Finally yes it will not happens with shapes that do not have perfect symmetry, shapes like capsules spheres and campheres cylinder happens to be shapes which the link sum is also a sheep with perfect symmetry which may have and orientiontion that there is not a unique minimum tralnstion distance.

I think I can fix it tomorrow, try not to do any work around, because that algorithm is one of those think the is not intuitive, it need to know the math behind otherwise any intuitive chance does something you did not think it would do.

[Julio Jerez]

hold on, there may be a problem on the support function

Code: Select all

dgVector dgCollisionChamferCylinder::SupportVertex (const dgVector& dir, dgInt32* const vertexIndex) const
{
   dgAssert (dgAbs(dir.DotProduct3(dir) - dgFloat32 (1.0f)) < dgFloat32 (1.0e-3f));

   dgFloat32 x = dir.GetScalar();
   if (dgAbs (x) > dgFloat32 (0.9999f)) {
      return dgVector ((x > dgFloat32 (0.0f)) ? m_height : - m_height, dgFloat32 (0.0f), dgFloat32 (0.0f), dgFloat32 (0.0f));
   }

   dgVector sideDir (m_yzMask & dir);
   //sideDir = sideDir * sideDir.InvMagSqrt();
   sideDir = sideDir.Normalize();
   return sideDir.Scale4(m_radius) + dir.Scale4 (m_height);
}

[Julio Jerez]

ok it is fixed.
It turned out that only three shape can generate that bug: sphere, camphered cylinders and capsule
all witch are variant of a sphere.
this is because they shape has perfect symmetry points:
for a sphere: the origin at equal to all point on the surface
for a capsule: a point on ether end is a equal distance to the point on teh surface on either end.
for a chamfered cylinder: a points of the circle the define the distance and at equal distance

so when the origin and orientation of these shape are such that the teh symmetry lose one tow or all three degree of freedom teh the algorithm can not calculate a unique distance.

The solution is what I said first detent these shapes and if the alignment meet any of these condition, translate one along the lost dedree of fredon so that the algorithm can form an non regular convex hull.

teh simplex example to undertant is teh sphere:
if you place tow sphere at teh same origin, teh the convex hull of the mick is another sphere. so there is not clear direction, similarlly of to take tow capsule and you slide one along teh x axis the the convex hull o fteh MInk is anothe capule, again no clean solution.

for the champhered cylinder if you slide one alone the plane teh the mink is another a streacth champherd cylydner again to clean direction in three d. There is a solution in two D whi is a direction on the plane by newton is no cocern with 2d problems.

anyway it is fixed now at funtion ..\sdk\dgPhysics\dgNarrowPhaseCollision.cpp
line 1469 if you no not want to get the later, which is in a state of changes now.

[Cannos]

Thanks Julio, that fixes some of the cases but not all of them. If the bodies don't have the exact same orientation, the new fix doesn't get triggered.

For instance, the new fix won't happen in the test case, if I change this:

dMatrix mtxD(0.0f, 3.141592f * -0.5f, 0.0f, dVector(9.25f, 3.00000072, -4.375f));

to this:

dMatrix mtxD(0.0f, 0.0f, 0.0f, dVector(9.25f, 3.00000072, -4.375f));


This tolerance check is failing with the above test:

Code: Select all

dgMatrix diff(instance0.GetGlobalMatrix() * instance1.GetGlobalMatrix().Inverse());
if ((dgAbs(diff[0][0]) > dgFloat32(0.9999f)) && (dgAbs(diff[1][1]) > dgFloat32(0.9999f)) && (dgAbs(diff[2][2]) > dgFloat32(0.9999f))) {...}


Not sure, but perhaps those comparisons should be || instead of &&?

[Julio Jerez]

Oh yes checking for identity is not enough, each shape has to have its own check
for example in that case any yaw rotation meet the same this, change line 1477 to this, an tell me if it fix it for chamfered cylinder then I fox for all other shapes

from:

Code: Select all

//if ((dgAbs(diff[0][0]) > dgFloat32(0.9999f)) && (dgAbs(diff[1][1]) > dgFloat32(0.9999f)) && (dgAbs(diff[2][2]) > dgFloat32(0.9999f))) {


to:

Code: Select all

if (dgAbs(diff[1][1]) > dgFloat32(0.9999f)) {

[Cannos]

No, that doesn't fix it, but this does:

Code: Select all

if (dgAbs(diff[0][0]) > dgFloat32(0.9999f)) {

In this case diff is this:
m_front {1.00000000, 0.000000000, 0.000000000, 0.000000000}
m_up {0.000000000, 3.13916473e-007, -1.00000000, 0.000000000}
m_right {0.000000000, 1.00000000, 3.13916473e-007, 0.000000000}
m_posit {-5.00679016e-006, -0.152917862, 0.356715679, 1.00000000}

This test case has a 90 degree rotation in the offset matrix of the NewtonCollision. Not sure if that makes a difference.

[Julio Jerez]

sync and try again, pease, I did it for sphere and chamfered, I do the capsule later.

edit:
please sync again, I fixit and tested it and it worked.