collision object ordering and collision results

[SeanCurtis-TRI]

I have a scenario with two colliding objects. I find that if I add them to the collision world in one order I get a slightly different collision computation than if I add them in the reverse order. The location of the contact point varies on an order of approximately 1e-5.

Is this a known property? How dependent is accuracy on order of operations and, if it depends, is there a prescribed order that will reduce inaccuracies?

[erwincoumans]

Yes, the order of operations is one of several parts that can influence the outcome of the collision detection computation. This is a complex topic and it helps to first determine:

1. what are the two collision shape types involved
2. which algorithm is used to compute the closest (contact) points (GJK, EPA, SAT etc)
3. Is there any contact caching (persistent contact manifold) enabled (which it is by default)?
4. Are the closest points (penetration depth) location unique (sphere vs sphere) or not (two polyhedra with parallel touching faces)?

It helps to use the double precision version of Bullet if you care about collision quality, are you using double or single precision?

Once we have all the details of above, we likely can sort out the order-dependent results.

Ideally we just create a simple reproduction case in the Bullet Example Browser and go from there, it is pretty trivial to create it.

[SeanCurtis-TRI]

Two answer your questions:

what are the two collision shape types involved

A cylinder and a convex hull shape

which algorithm is used to compute the closest (contact) points (GJK, EPA, SAT etc)

This particular query is for colliding objects, so I assume EPA. (ultimately invoked by a call to btCollisionWorld::performDiscreteCollisionDetection).

Is there any contact caching (persistent contact manifold) enabled (which it is by default)?

Technically, yes, but the result I'm looking at is the very first invocation of the collision detection, so persistence shouldn't be an issue.

Are the closest points (penetration depth) location unique (sphere vs sphere) or not (two polyhedra with parallel touching faces)?

This is possible but highly unlikely. I haven't delved specifically into the exact scenario but the odds that the contact is on the cap of the cylinder that is perfectly aligned with the colliding face is so small, I assume not.

It helps to use the double precision version of Bullet if you care about collision quality, are you using double or single precision?

Yes, double.

I can look into creating a reproduction if we feel that's the best way forward.

[erwincoumans]

Are you using default collision margins? If not, this can introduce all kinds of issues.
I'm happy to work with you to improve the quality of collision queries in Bullet. For a start, we could create more tests to Bullet for various collision queries.

[SeanCurtis-TRI]

It's difficult for me to accurately assess if we're using "default" margins. We have different behavior based on the the type of shape.

• Sphere and Cylinder: no margins are addressed in anyways. Only the radius is set.
• We have a "capsule" shape which is a btConvexHull shape with two points and a margin equal to the desired radius.
• Boxes and dynamic meshes are converted into btConvexHull and a margin of at least 1e-9 is applied (possibly larger in some use cases.)
• Static meshes use btBvhTriangleMeshShape and likewise have a minimum margin of 1e-9.
• Point clouds - we abuse the btConvexHull to quasi-support point clouds by pushing the points into the btConvexHull and providing it the same minimal margin of 1e-9.

The query we're doing (where the answer depends on ordering) is using the geometry described above with the minimum margin value of 1e-9.

[erwincoumans]

The location of the contact point varies on an order of approximately 1e-5.

If you provide a reproduction case in a simple Bullet demo, I'll look if we can improve it.

Once you start setting the margin to tiny values (such as 1e-9) you are fighting the implementation. 1e-9 margins for various objects will disable robustness and reduce performance in GJK/EPA: it relies on some positive margin to avoid degenerate GJK simplex and to avoid EPA in shallow penetration cases. In many cases it is possible to use a larger margin and embed the margin inside the object:
btSphereShape and btCapsuleShape uses margin as radius
btBoxShape: the margin is already 'inside' the box, so the box is the right size, but slightly rounded corners.
btConvexHullShape: you can use some utility to create a smaller convex hull so that the shrunk convex hull + margin is the same size as the original btConvexHullShape.
If you apply above rules, then only the concave triangle meshes have tiny margins. Since we usually don't perform queries between two triangle meshes, each query will have sufficient margins.

[SeanCurtis-TRI]

I'll work up an example and get back to you.