A few questions about current GJK implementation

[RobW]

First off, I would just like to say thank you to Erwin and all the other Bullet contributers for their fantastic work, I have learnt a lot exploring Bullet over the last few months, and I would like to think I could make some contibutions in the future.

Something is puzzling me a little at the moment, and I'm hoping someone can clarify the issue for me.

I'm unsure about the relationship betwen btGjkPairDetector and btGjkEpaSolver. It appears that btGjkPairDetector::getClosestPoints does an initial GJK test to determine whether two objects intersect, and then btGjkEpaSolver uses the EPA algorithm to calculate the penetration depth. However, btGjkEpaSolver also seems to repeat the initial GJK test to find a simplex enclosing the origin, not using the result from btGjkPairDetector. It appears that btGjkPairDetector::getClosestPoints includes more degeneracy handling so it is almost as if it is providing an initial, more robust, version of the test done again in btGjkEpaSolver. So is this something that needs a refactor to do reduce the duplication, or have I just completely missed the point?

In addition, it doesn't appear that the GJK separating axis/search vector is actually cached from one iteration of collision detection to the next. Is this a relatively simple task that would allow non penetration cases to be reject much quicker? It seems to me that there is some complication in doing this, specifically for collision detection with triangle meshes, as the triangle mesh is represented as a single collision shape but ideally you would want to cache a separating axis for each triangle (or perhaps just a few, with a lifespan), in contrast to most collision shapes which are not a collection of primitives.

Am I also right in thinking that only a single manifold is maintained for collision against a triangle mesh - is it not relatively easy then for a 4 point manifold to be insufficient, as an object can have several discontinuous contacts with a concave triangle mesh?

I'm still getting to grips with everything, but if I could better understand these issues it would help me focus on where I might be able to contribute

edit: meant concave, wrote convex.

[Erwin Coumans]

So is this something that needs a refactor to do reduce the duplication, or have I just completely missed the point?

You are right. btGjkEPA was a contribution to provide penetration depth computation. It is self-contained, so it includes its own GJK. We could refactor the btGjkEPA code to accept an initial simplex from the btGjkPairDetector indeed. Before refactoring it would be good to create some unit tests, to make sure this fix doesn't break things that weren't broken.

it doesn't appear that the GJK separating axis/search vector is actually cached from one iteration of collision detection to the next.

It used to be cached in the past, but I haven't seen a much performance difference (it can be trivially added in the convex-convex collision algorithm. But there is a better way, caching the separating axis between convex objects in general (not just when using GJK), and keeping track of a conservative distance. As long as the distance is positive, no narrowphase needs to be performed. If you are interested in this optimization we can discuss further.

Am I also right in thinking that only a single manifold is maintained for collision against a triangle mesh - is it not relatively easy then for a 4 point manifold to be insufficient, as an object can have several discontinuous contacts with a concave triangle mesh?

I think it is not easy to come up with a case where 4 points are insufficient. But if you can, I'm looking forward to a test case. 4 contact points appear to be enough for stable resting of a convex object on a concave triangle mesh. The contact caching strategy in Bullet automatically keeps the deepest point. If an important contact would be missing, it would be there the next frame.

Some contributions that would be highly appreciated:
- create some test case(s) that (try to) break the convex versus concave triangle mesh contact strategy.
- add separating axis performance optimization
- enabling the SAT (separating axis theorem) implementation, see Bullet/Extras/SATConvexCollision
- adding one-shot contact generation. There are some ideas recently discussed, as well as an implementation for convex polyhedra in Jan Bender's project using Bullet.

Thanks for offering help,
Erwin

[RobW]

Thanks Erwin,

I haven't seen a case where convex vs concave trimesh goes wrong, but I am experiencing quite a bit of jitter where a complex convex object is lying on a trimesh, the object is experiencing small angular velocity which is just large enough to prevent sleeping conditions being met. Intuitively, I thought it could be insufficient points in the contact manifold but have no proof - I'm actively investigating at the moment and will get to the bottom of it!

I guess it makes sense that caching separating axis will have little performance benefit, since for objects in motion it would only help in between the time their AABBs overlap and when they collide. Even if objects manage to rest 'nearly' in contact they will be deactivated by the sleeping condition.

I'm initially interested in removing the duplicate processing in GJK as I suspect a lot of processing time is spent here. Since the existing code is along these lines:

Code: Select all

if ( btGjkPairDetector GJK detects intersection )
{
  if ( btGjkEpaSolver GJK detects intersection )
  {
   do btGjkEpaSolver EPA 
  }
}

and because the direct use of btGjkEpaSolver is not enabled by default (btConvexConvexAlgorithm::processCollision), I would infer that btGjkEpaSolver's GJK could have problems in the non-penetration case, either false positives or failure to exit effectively? So I suppose what needs doing is analysis of the extra robustness of btGjkPairDetector and to replicate it in btGjkEpaSolver. Or, as you say, just pass the simplex from btGjkPairDetector to the EPA in btGjkEpaSolver, but that assumes tha tht btGjkEpaSolver's GJK isn't hiding any problems in btGjkPairDetector's GJK. I'll start looking into this tomorrow, and the first line of defence will be that our existing stuff doesn't break.

Did you have any particular unit tests in mind?

[Erwin Coumans]

I haven't seen a case where convex vs concave trimesh goes wrong, but I am experiencing quite a bit of jitter where a complex convex object is lying on a trimesh

Can you please provide a reproducing testcase for that convex-concave jitter?
I'm very interested to check out what is happening, it might have other reasons. For example, tiny objects (< 0.2 units) against huge objects (>10 units for any feature) etc. Note that it is best to leave the default collision margins as they are, and never set the collision margins to zero.

I guess it makes sense that caching separating axis will have little performance benefit, since for objects in motion it would only help in between the time their AABBs overlap and when they collide. Even if objects manage to rest 'nearly' in contact they will be deactivated by the sleeping condition.

It increases performance before objects fall asleep, which is nice to have. Apart from that, it is a common performance benchmark to test non-sleeping stacks

I'm initially interested in removing the duplicate processing in GJK as I suspect a lot of processing time is spent here.

The fallback into btGjkEPA is should not happen frequently. You can check how infrequent it happens, by checking the counter for 'deep penetrations' in the demos.
There is one thing I forgot to point out: collision margins play an important role in both non-overlapping GJK and the EPA fallback. btGjkEPA uses 'localGetSupportingVertex', whereas btGjkPairDetector uses localGetSupportingVertexWithoutMargin. I will make some illustrations to make this more clear.
You pseudo-code would be more accurate like this:

Code: Select all

if (btGjkPairDetector GJK _without_margin_ detects intersection (deep penetation > sum of margins) or degenerate case (false positives and negatives))
{
  if (btGjkEpaSolver GJK detects intersection _including_margin_)
  {
     do btGjkEpaSolver EPA including_margin
  }
}

Because of the difference of margins, just adding the simplex points of non-margin GJK into margin-EPA might have issues.

Best unit test would be to enable the SAT implementation, and randomly position objects and measure the difference.
Hope you can help with reproducing jitter case, SAT or other feedback,
Thanks,
Erwin

[RobW]

I have managed to recreate the jittering problem, I took 'appConcaveDemo', imported my specific convex object, and generally tweaked things like the size of the ground mesh until the problem I've been having started to appear.

However, in doing so I think I have found the problem

Basically, the mass and inertia tensor were being derived from the mesh itself with a predefined density, which was too low (the code to do this was adapted from ODE). The result was a very small inertia tensor and I think this was causing numerical issues, possibly when the inertia tensor was inverted. By fixing this, the jitter has been reduced greatly and the object sleeps very soon after coming to rest.

I can give you the test case as a single .cpp file to replace ConvexPhysicsDemo.cpp in appConcaveDemo, if you would like to see it, but it seems that numerical accuracy is the likely prognosis.

I have made various changes, extensions and optimisations to Bullet in the last couple of months and continue to do so but I'll explain in more details the things I've done at a slightly later date. There's nothing ground breaking, but there are one or two interesting things.

I'll be at GDC from Wednesday onwards, so sadly unable to attend the physics workshop on Tuesday...if I find the Bullet stand I'll say hello