Penetration depth computation: reliable?

[Pierre]

Hi,

I have some troubles with Bullet's penetration depth computation. Here is a repro: http://www.codercorner.com/TestBullet.rar

There is a Readme file explaining the problem. Can you tell me what's going on?

- Pierre

[Erwin Coumans]

Hi,

I have some troubles with Bullet's penetration depth computation. Here is a repro: http://www.codercorner.com/TestBullet.rar

There is a Readme file explaining the problem. Can you tell me what's going on?

- Pierre

Bullet doesn't support zero collision margin. So please don't set the margin to exactly zero. The penetration depth/distance calculation should be reliable (in a rigid body simulation) if you leave the margin to a value above 0.04 units (4 centimeter if your units are meters).

Code: Select all

	convexA.setMargin(0.0f);

An assert should probably be in place, including a small value to prevent setting a zero margin. It will be added to the documentation. Bullet uses the hybrid solution, where shallow penetrations (less then the sum of the margins) are dealt with by GJK. Deep penetrations should infrequently happen (especially when using CCD for fast moving objects). The MinkowskiPenetrationDepthSolver is approximate, and is only supposed to be called for 'deep' penetrations. It samples in a fixed number of directions, which causes an error for large objects, so those are not supported by this method. About the optional classes in Bullet/Extra: EPA solver in Bullet is work in progress, and should get at least the same quality as SOLID. But it still requires the non-zero margins/hybrid method.

If you can reproduce this with non-zero collision margin (preferably at least 0.04 units) please let me know,
Hope this helps?
Erwin

[Pierre]

Bullet doesn't support zero collision margin.

Hmmmeeeerrrr...... I'm confused. What is the "setIgnoreMargin(bool)" function doing then?

So please don't set the margin to exactly zero. The penetration depth/distance calculation should be reliable (in a rigid body simulation) if you leave the margin to a value above 0.04 units (4 centimeter if your units are meters).

I think it still fails. If I set the margins to 0.04 and move the object along the X axis, the orange wireframe convex goes up and down in a very non-natural way. I think you should try to compile the repro and see for yourself, it's pretty obvious that something's wrong - I think.

Bullet uses the hybrid solution, where shallow penetrations (less then the sum of the margins) are dealt with by GJK. Deep penetrations should infrequently happen (especially when using CCD for fast moving objects).

Sorry but this is irrelevant. Bullet obviously works, when using all the components together. However, as the doc suggests, its modular design should allow users to take advantage of one component only. Right? In my case, I don't care about CCD, I don't care about deep penetrations, I just need a replacement for the "reference" penetration depth computation code included in the repro. As far as I can see, Bullet doesn't help for this. Its penetration depth computation can not be used alone, because it produces unreliable results. At least that's what it looks like, unless I don't use the library correctly.

The MinkowskiPenetrationDepthSolver is approximate, and is only supposed to be called for 'deep' penetrations.

Well, try the repro. Even with 0.04 margins and objects overlapping completely, it only reports a penetration once in a while...

- Pierre

[Erwin Coumans]

Bullet doesn't support zero collision margin.

Hmmmeeeerrrr...... I'm confused. What is the "setIgnoreMargin(bool)" function doing then?

It should not be there, I will remove it, it is a remainder from some refactoring.

Well, try the repro. Even with 0.04 margins and objects overlapping completely, it only reports a penetration once in a while...
- Pierre

The software in the Extras folder is unsupported, and not part of Bullet core code, mostly for comparison, utility and work in progress. SOLID penetration depth solver is just for comparison, similar for the ODE quickstep solver. The Extras/EPA contains a unfinished Expanding Polytope Algorithm. Bullet only supports the hybrid penetration depth, which means that GJK handles accurate shallow penetrations. The sampling btMinkowskiPenetrationDepthSolver is an approximation for deep penetrations, where accuracy is not needed.

I just need a replacement for the "reference" penetration depth computation code included in the repro. As far as I can see, Bullet doesn't help for this.

I'm curious about the actual error in Bullet's hybrid approach with sufficient margin and the btMinkowskiPenetrationDepthSolver? If your BulletTest shows some serious issue (which I haven't seen yet), I will attempt to fix it. I appreciate your interest for a more accuracte/reliable penetration depth solver. I will add your test in the Bullet/Demos folder, and check the hybrid solution. When you want accuracy for deep penetrations (deeper then the margin) then improving the Extras/EPA penetration depth solver is one way. This EPA is fairly low priority though.

Thanks a lot for the feedback,
Erwin

[Pierre]

The software in the Extras folder is unsupported, and not part of Bullet core code, mostly for comparison, utility and work in progress. SOLID penetration depth solver is just for comparison, similar for the ODE quickstep solver. The Extras/EPA contains a unfinished Expanding Polytope Algorithm. Bullet only supports the hybrid penetration depth, which means that GJK handles accurate shallow penetrations. The sampling btMinkowskiPenetrationDepthSolver is an approximation for deep penetrations, where accuracy is not needed.

So, if I understand correctly, there's actually no way in Bullet to compute a reliable penetration depth (shallow or not)?

I have a few questions regarding the margins/GJK method:

- does it mean the margins go inside the objects, i.e. you do GJK on shrunk objects?

- but then, does it work for flat objects, or objects whose size is smaller than the margin? Like a 2D quad?

- your "penetration depth" is a distance then, right? It is not really the same.... Your pseudo-penetration vector will have a continuous orientation, while a typical penetration vector has discontinuities. I see why it can be used with incremental, persistent contact manifolds, but there's no way I can use this as a replacement for a "proper" penetration depth.

I'm curious about the actual error in Bullet's hybrid approach with sufficient margin and the btMinkowskiPenetrationDepthSolver? If your BulletTest shows some serious issue (which I haven't seen yet), I will attempt to fix it.

I'm not sure. If I setup margins and move the convex along X, sometimes it reports an overlap, sometimes not. I feels wrong but it's unclear, as the repro doesn't visualize the shrunk objects (just the real ones). I'll play with this more next week.

- Pierre

[Erwin Coumans]

So, if I understand correctly, there's actually no way in Bullet to compute a reliable penetration depth (shallow or not)?

Shallow penetration should be very accurate when using Bullet's GJK, and the deep penetration is an approximation, which should be good enough in rigid body simulation for games/animation. I would not call this unreliable, this is just an approximation for deep penetrations. This puts limitations on extreme object sizes (don't make object thinner then the margin, don't make objects very large, otherwise the deep penetration depth approximation fails. Bullet's GJK works best on object size in the range of 15 centimeter up to 50 meter (if units are in meters).

I have a few questions regarding the margins/GJK method:
- does it mean the margins go inside the objects, i.e. you do GJK on shrunk objects?

It depends which shape. The entire radius of btSphereShape is margin. For btBoxShape, the margin is subtracted from the half extents, so the margin is 'internal'. For convex objects, cylinder, cone the margin is outside, so you have to compensate the graphics model. For convex hulls, I plan to shift the planes inwards, as your collegue Dennis from Meqon recommended me a few years ago, before they got acquired by Ageia.

- but then, does it work for flat objects, or objects whose size is smaller than the margin? Like a 2D quad?

Moving objects should never be smaller then the margin in any direction. Static concave collision shapes, like a 2D quad, can have zero margin if you like. Then during a collision with still have at least a total sum of 0.04 margins (this 0.04 is an example, but recommended minimum value).

- your "penetration depth" is a distance then, right? It is not really the same.... Your pseudo-penetration vector will have a continuous orientation, while a typical penetration vector has discontinuities. I see why it can be used with incremental, persistent contact manifolds, but there's no way I can use this as a replacement for a "proper" penetration depth.

I don't see the issue here, please explain why you cannot use this? The concept of hybrid penetration depth is reliable and widely used and many shipped games rely on this concept. It would be nice to improve the deep penetrations depth (improving the Extras/EPA implementation). If you spot some bug in the implementation (shallow and/or deep) I am happy to look into it and fix it.

Thanks again for the feedback, and please check the reply on Stackless traversal: http://continuousphysics.com/Bullet/php ... =2251#2251

Erwin

[Pierre]

Shallow penetration should be very accurate when using Bullet's GJK, and the deep penetration is an approximation, which should be good enough in rigid body simulation for games/animation. I would not call this unreliable, this is just an approximation for deep penetrations.

Look, I think you know what I mean. It is a very easy and very -clearly- defined problem:

- I have two overlapping convexes
- I want to compute the *exact* (= accurate) penetration depth between them (i.e. the same as what the reference code gives me, in my repro)

I am not asking for a shallow GJK solution (it is *not* accurate because the returned *distance* vector is *not* the same as the real penetration depth). I am not asking for an approximation either.

I am asking for the real answer. I thought Bullet would help thanks to its 2 different penetration depth solvers (Solid & EPA). Both appear to fail. Both *are* unreliable. That's all I'm saying. Could you agree with this, instead of trying to convert me to the hybrid approach ? I am not saying the hybrid approach doesn't work. It does.

I don't see the issue here, please explain why you cannot use this? The concept of hybrid penetration depth is reliable and widely used and many shipped games rely on this concept.

I know the concept works, we've been discussing this enough in the past.

The issue is that is it easy to replace a penetration depth module in an already existing engine. It is a lot more difficult to replace the whole contact generation machinery, introducing persistent manifolds, etc, etc.

As you know, since you saw the code, the current contact generation works in two passes:
1) compute the penetration distance
2) find two best contact polygons "closest" to this, and do some clipping

This works, but it's very fragile. In particular, 1) absolutely needs the exact penetration depth, else Bad Things happen. If I replace the current first part with Bullet's version (either Solid or the EPA contribution), things just explode. Hence, "unreliable".

I think we will be moving in the "hybrid" direction in the future, so I *know* it works, you don't need to convince me. All I'm trying to do, meanwhile, is to improve/optimize the current system. And for this, I need a real penetration depth - unless you also have a replacement for 2), something that would work with an approximate PD!

It would be nice to improve the deep penetrations depth (improving the Extras/EPA implementation). If you spot some bug in the implementation (shallow and/or deep) I am happy to look into it and fix it.

I'm afraid I will not have time to really look at the details...

Thanks for your answers anyway.

- Pierre

[Erwin Coumans]

Both Solid EPA and Bullet EPA appear to fail. Both *are* unreliable. That's all I'm saying. Could you agree with this, instead of trying to convert me to the hybrid approach ?

OK, the Bullet EPA contribution is unreliable, hence it is unused and moved away into the Extras folder. I want to make it more reliable, so we can both (consider to) use it.

Thanks,
Erwin

[Erwin Coumans]

Hi Pierre,

Thanks a lot for your penetration depth testbed.

I had a closer look at the problems today, and there were some funny issues, and more serious:
The default penetration depth solver in Bullet, Minkowski sampler, used a global structure called 'MyResult', and in your testbed you use the same. For some reason it used your struct. I made this local and renamed it, which fixed some issues.

Then, I looked into the actual issues, which are problematic termination conditions in my Hybrid GJK loop. Some degeneracies can be catched/determined inside the 'voronoi' simplex solver. With some extra logic, I could make the default 'sampling' penetration depth solver much more reliable. However, both my ported Solid 3.5 and Bullet EPA work in progress penetration depth solvers have issues, as I expected.

I will work on this as soon as I get some more time.
You can check the latest test in Bullet 2.26. Make sure to set

Code: Select all

m_catchDegeneracies

to true. The updated demo in Bullet/Demos/EPAPenDepthDemo works much better now for sampler version. There are projectfiles for it (and Extras/EPA, Extras/ExtraSolid35) called msvc/8/libEPA.vcproj, msvc/8/libExtraSolid35.vcproj and appEPAPenDepthDemo.vcproj. Just open up Bullet's solution file in msvc/8/wksbullet.sln and add those, make the EPA demo dependent on those EPA projectfiles and the other Bullet libraries (and openglsupport lib for text rendering).

Thanks a lot for your great testbed! I'll let you know what the issues are on EPA (Bullet's EPA that is).
Erwin

[Erwin Coumans]

Hi Pierre,

Bullet 2.32 should have some improvement in penetration depth calculation.
A new EPA contribution, and improvements in the sampling 'minkowski' pd method. Your test is included in Bullet/Demos/EPAPenDepthDemo
Hope this works better,

Thanks for your feedback,
Erwin