cute_c2: PolytoPoly collision fail due to float precision error in c2GJK

[SSBMTonberry]

Hello, and thank you for an awesome collisin library. I got some failing tests using the PolytoPoly functions, where the collision test fails due to a floating point precision error. I've solved this in my local environment, but I can also do a pull request on my solution if you accept. I'd like to present the problem first nonetheless. You might want to solve this in another way.

This is a visualisation of my tests:

For code reference, the colors of these polys refer to the following variables: black - c2Poly1 red - c2Poly2 blue - c2Poly3 yellow - c2Poly4 green - c2Poly5 pink - c2Poly6

These are defined in code as:

c2Poly c2Poly1 {4, {{40, 30}, {50, 40}, {40, 50}, {30, 40}}};
c2Poly c2Poly2 {4, {{40, 48}, {50, 58}, {40, 68}, {30, 58}}};
c2Poly c2Poly3 {4, {{58, 30}, {68, 40}, {58, 50}, {48, 40}}};
c2Poly c2Poly4 {4, {{40, 12}, {50, 22}, {40, 32}, {30, 22}}};
c2Poly c2Poly5 {4, {{22, 30}, {32, 40}, {22, 50}, {12, 40}}};
c2Poly c2Poly6 {4, {{40, 51}, {50, 61}, {40, 71}, {30, 61}}};
c2MakePoly(&c2Poly1);
c2MakePoly(&c2Poly2);
c2MakePoly(&c2Poly3);
c2MakePoly(&c2Poly4);
c2MakePoly(&c2Poly5);
c2MakePoly(&c2Poly6);

Or more visually:

The following collision I expect to be true fails: p1 to p2. p1 to p3.

After some investigation I found that they fail due to a diff caused by float precision. The error happens here (in my version of cute_c2, this starts on line 1022)

c2v a, b;
c2Witness(&s, &a, &b);
float dist = c2Len(c2Sub(a, b));

Specifically it happens after c2Witness, where the variables a and b ends up having (for the p1 to p2 test): a: {41,49}, b: {41, 48.9999962} This causes dist to have a value larger than 0, which will make the following logic believe a collision has not happened.

Likewise, for p1 to p3 there is a diff between values 50 and 49.9999962.

Test ends up this result:

Note: p1 to p6 is expected not to collide, so it's all good.

My simple solution to the problem was to do this:

c2v a, b;
c2Witness(&s, &a, &b);
float dist = c2Len(c2Sub(a, b));

//RBP: If the dist is very small, it should probably be 0.
if(c2Abs(dist) < 0.0002f)
    dist = 0;

I then get result as expected:

If you are okay with my solution, I can get the latest version of tiny_c2 and do a pull request. Alternatively, if you want to solve it yourself or want it to be solved another way that's okay too. Just thought I should inform about this :slightly_smiling_face:

On a different note: The PolytoPolyManifold functions seems to pass my tests, so no similar error found there. Though, it uses a completely different function, so that was expected.

[RandyGaul]

Thank you so much for the well written writeup and your investigation! This is a known limitation of the GJK algorithm. Once shapes are really close to each other it becomes ambiguous as to whether or not they are touching. Adding your if statement will actually degrade the precision of the overall algorithm, despite it achieving the expected output for your tests.

The best thing to do would be to use a different algorithm to achieve higher precision. Like you figured out, the manifold functions will work well in this case.

If you'd like to make a pull request I would suggest the best option here would be to note in the documentation at the top of the file about precision differences. The manifold functions generally take special care to maintain high numeric stability, while the boolean functions generally favor speed instead. So if high precision is wanted, go with the manifold function even if you don't need the manifold data.

[SSBMTonberry]

Thank you for a quick answer! I'll just leave it as it is and eventually use the manifold version instead :slightly_smiling_face: