Possible EPA Algorithm Issues

[kovertopz]

I've ported your physics library to Java and I've discovered what I think is a bug. I've double checked my code a few times on a few different occasions and didn't discover any errors. What I have discovered is that the EPA algorithm doesn't seem to handle all the cases correctly though I lack understanding to fix it myself. The error is also present when I build your library from source but for the case of cylinders it doesn't visually show any problems. It is only the case of a cone in your library do I see the same glitches. The other shapes such as boxes, capsules, spheres seem to never hit EPA and don't suffer from the issue.

I've narrowed it down to case 3 of the EPA algorithm were we have a triangle from the simplex and we are going to be adding to more points to create a hexahedron. When that case occurs for cylinders or cones I always end up with a very large penetration depth (1.0-2.5) and the collision object bounces very noticeably. When we get out of the switch statement it seems that "!triangle->computeSilhouette" (line 380) eventually is false and that is how we break out of the loop. There are new face candidates being added too (line 388) and the amount differs. It seems like the other cases that start with 4 vertices work well break out above during computing the error (line 369). This appears to happen in all of the cases I've seen and I've done it quite a number of times. Hopefully knowing the path of the code through the failure case is helpful.

If I comment out case 3 from my code completely the jitter is gone and everything appears to be well. There are still a few cases where previously stable objects are unstable (seen boxes jitter, and cones sitting on their base, though rare) because that case no longer exists (I assume). Commenting out the code fixes much more of the problem than it causes.

I'm not sure what it is about the face candidates from case 3 that causes the issues. I can also keep all code in my port except for adding the 6 faces (lines 310-315) before it exits from the switch statement and it will be just as stable as well.

To reproduce this issue you must enlarge the floor to at least 50x50.

In my code I set a flag when case 3 occurs and printed out the normal and penetration depth. I've used my own demo Collision Test to rotate the cylinder laying horizontal and move it across the floor

Normal: (x= 6.2596635E-5, y= -1.0, z= -2.7572327E-5) Penetration depth: 2.5595193
Normal: (x= 1.0021483E-5, y= -0.9990377, z= 0.043859735) Penetration depth: 1.332282
Normal: (x= 3.6370513E-4, y= -0.9999998, z= -3.652762E-4) Penetration depth: 2.4280725
Normal: (x= 0.06166201, y= -0.99787545, z= -0.021030152) Penetration depth: 1.5822806
Normal: (x= -0.025286067, y= -0.9986612, z= 0.045127083) Penetration depth: 1.1724211
Used memory: 8% 78MB of 910MB
Normal: (x= -6.6948305E-5, y= -1.0, z= 1.19019205E-5) Penetration depth: 2.5640886
Normal: (x= -2.457223E-5, y= -0.99926066, z= -0.03844618) Penetration depth: 1.6300646
Normal: (x= 0.011597331, y= -0.99966383, z= 0.023188038) Penetration depth: 0.5759545
Normal: (x= 0.017189197, y= -0.9987077, z= 0.047828164) Penetration depth: 0.94106925
Normal: (x= -0.03228135, y= -0.99944663, z= 0.008018183) Penetration depth: 1.1154096
Normal: (x= 2.4790124E-6, y= -1.0, z= 3.3053498E-6) Penetration depth: 2.3081958
Used memory: 8% 81MB of 910MB
Normal: (x= -8.2760596E-7, y= -1.0, z= -5.7932416E-6) Penetration depth: 2.304658

In case you need to see my code it is available at: https://github.com/kovertopz/jReactPhysics3D

[DDoS]

I can confirm this bug, it's also a problem in our port (flow/React).

[DanielChappuis]

I have made some modifications in the EPA Algorithm in commit : 54d8b85

According to my tests, the robustness of case 3 of the EPA algorithm has been improved. Those changes will be available very soon in the next release of the library.

Maybe you can test those modifications on your side and check if it is better now ?

[DanielChappuis]

The modification to fix this issue is now part of the last release of the library (version 0.5.0).