GJK raytest fails, revert to old 'subsimplex' convex cast and fix it

[erwincoumans]

Bullet 2.x btCollisionWorld::rayTest is using the gjk convex caster, instead of subsimplex convex caster. There is some issues we need to fix.

See also http://bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=9&t=9723&p=32797#p32797

[erwincoumans]

By the way, you can revert to the old behavior using the following setting:
resultCallback.m_flags |= btTriangleRaycastCallback::kF_UseSubSimplexConvexCastRaytest;

[sherm1]

Hi, @erwincoumans! We are enthusiastic Bullet users for collisions in Drake. I'm working with @amcastro-tri (Alejandro Castro) who finally solved a long-standing problem for us that we think is due to the bug discussed in this issue. The fix was small, but the pain was large because it took several people and 3 months (off and on) to identify the problem (of course we thought it was our bug). Alejandro will follow up with more info. Best regards, Sherm

[amcastro-tri]

Erwin, this is the issue in Drake that @sherm1 is referring to. Essentially we are using ray casting for a simple lidar model. The test in that issue is simply a 2D lidar placed in front of a box. Some strange returns were observed when they ray was hitting the box close to being perpendicular to it (the zero angle in the plots).
I found out that Bullet resolves the ray collisions with the call to btSubsimplexConvexCast::calcTimeOfImpact. In that method there is a hardcoded tolerance to be epsilon = 0.0001) and for some hits the iteration barely converges within that tolerance (for us it translated into a 1 cm error) in 8 iterations. Details are offered in Drake's PR 2354.
The solution I found to work just two days ago was to change the default algorithm (the sub simplex convex cast) with a GJK convex cast. This is done by setting the option btTriangleRaycastCallback::kF_UseGjkConvexCastRaytest for the ClosestRayResultCallback.

We have the following questions:

1. Are these algorithms (GJK and sub sumplex) applicable to concave shapes as well? (their names led us to think that they might only work with convex shapes).
2. Is there a particular advantage (computational cost, robustness) that any of these two algorithms might have?
3. Would it be possible to expose this epsilon for the user through the API? Ideally I would like to set it to a relative (no units) tolerance. For instance, 1% of some reference length of the object (like the minimum edge length of the object's OBB).

I am working on a very simple demo in my Bullet's fork with just this test (ray vs. one box) in case you are interested in seeing it. I'll post the link soon.

[amcastro-tri]

@erwincoumans: in my fork of Bullet I added another example to the Example Browser. Is in Explorer->Raycast->RayCastBug.

If you run it you'll see just a 1x2x1 box with its center at [0.5; 0.0; 0.0]. A ray is cast from [0.0; 0.0; 0.0] at a very small angle from the x-axis (just 0.04 radians, almost normal to the box).

The example prints to screen the hit point computed with both kF_UseSubSimplexConvexCastRaytest and kF_UseGjkConvexCastRaytest. What you'll see on the screen is:

***********************************************************************
** Computation performed with "kF_UseSubSimplexConvexCastRaytest":   **
   Box hit at: -0.00912261 0.0396562 0 

***********************************************************************
** Computation performed with "kF_UseGjkConvexCastRaytest":          **
   Box hit at: -5.96046e-08 0.0400213 0

The correct solution would have x=0, where the front side of the box is located. However you can see that when using kF_UseSubSimplexConvexCastRaytest the error is quite large, 0.0091.

[erwincoumans]

Thanks a lot for reaching out and thanks for tracking down the issue and creating a repro case.

Yes, the subsimplex convex cast is more sensitive to various issues, and it is better to disable it by default.

1. Are these algorithms (GJK and sub sumplex) applicable to concave shapes as well?

Yes, they can be extended to concave shapes, by using an acceleration structure, and doing a pairwise test for all potential candidates and taking the minimum. So although the elementary test only applies on convex shapes, the children in a concave shape are convex (convex triangles in a concave triangle mesh, or convex child shapes in a compound shape).

1. Is there a particular advantage (computational cost, robustness) that any of these two algorithms might have?

The subsimplex convex cast has theoretically a better performance, by merging two iteration loops into a single loop. See also http://bulletphysics.com/ftp/pub/test/files/physics/papers/jgt04raycast.pdf for details on these algorithms.

1. Would it be possible to expose this epsilon for the user through the API?
   Yes, good idea. Both exposing the tolerance(s) and choice of algorithm should be exposed.

In addition, we should create some unit test using gtest, see Bullet/tests/... , those unit tests are executed as part of each pull request etc.

[amcastro-tri]

Thank you for your answer @erwincoumans! Good to know we are using the correct algorithm now.
Three new questions:

1. When should we opt instead for the sub-simplex algorithm? when we are not worried about accuracy and just want faster results? (though it seems accuracy could be controlled if epsilon was available to the user)
2. At the very beginning of this issue the decision was to make sub-simplex the default since at that time there was a problem with Gjk. Was this problem resolved? if not, when should we expect it and how would it manifest?
3. Is making tolerances available to the user a change to be expected in future releases? that'd be a great addition!

[erwincoumans]

1+3) Yes, I'll expose the tolerance for the next release. Sub-simplex cast should be faster that gjk+conservative advancement. Note that there are some improvements that we could make, both for sub-simplex ray cast and convex cast. Erin Catto describes this in one of his GDC 2013 Physics Tutorial presentation 'Continuous Collision', see http://box2d.org/downloads

2. Yes, that particular original issue related to GJK ray cast was resolved. Nevertheless, we need to start working on unit tests for all functionality, including GJK, and that may expose other issues.

[erwincoumans]

It has been a while. We use BT_USE_DOUBLE_PRECISION by default now, in PyBullet, Bullet for Robotics.
Also, we use the GJK convex cast instead of the subsimplex convex cast. Nevertheless, I just exposed the tolerance/max iteration count, to close this issue. Although, I guess you are now using FCL :-)
Thanks and happy holidays,
Erwin
d477d18

[sherm1]

Thanks for the Xmas present, Erwin! I hope you enjoy some time off. Best regards, Sherm

[amcastro-tri]

This is great news, thank @erwincoumans. And happy holidays!