Box2D Forums

I put the center way off to one side in order to magnify the effect for the diagram. But I can also show you triangles where the centroid doesn't work, either (the red one is probably already an example). Or the paralellogram included in the last slide of the swf, where there is NO point where you could place the center which will avoid the problem shown for every possibly collision. (basically, I'm looking for circumstances where your bug fix makes a difference, i.e. when the origin, projected onto the edge corresponding to the 'portal' it is currently in, is not inside the edge. So the paralellogram ensures no matter where the center is, I can find an origin such that this is not the case).

However, the failure cases are still relatively minor, in the sense shapes that break it are usually fairly odd, and if we assume that two objects never penetrate more than x in a single frame, before they are moved away from each other, then you will only see mistakes when a collision occurs within x of a corner, and only rarely then, and even then it is only reporting the other normal associated to that vertex, with contact points also only off by x.

The variants of MPR used by XenoCollide and MPR2D don't return the minimum penetration depth, nor do they return the normal of minimum penetration.

These implementations of MPR rely on an interior point within each shape, usually near each shape's center.

Now, imagine that you pulled the overlapping shapes away from each other along the line connecting their center-points until the objects were just touching. This is the point of contact that the algorithm generates information about -- both contact normal and exact penetration depth (along the line between the interior points).

If you wanted to take the algorithm one step further, then once you found the contact normal, you could perform another search from the origin to the boundary of the CSO along the direction of the contact normal. This technique would provide a contact normal and penetration depth along this normal.

Neither of these variants produce the "minimum penetration depth". I created a variant of MPR that does, but I don't want to release it into the wild until I've proved it works in all cases.

Finding "minimum penetration depth" isn't necessary for stable (or correct) simulation. As the penetration is resolved, the origin moves towards the surface of the CSO and the MPR contact point and minimum depth contact point converge (i.e., they are the same for shallow penetration). When penetration is deep, the direction of minimum penetration is no more correct than the direction determined by MPR. In fact, a better direction would be the direction of relative velocity, which can be fed back into MPR to determine the penetration depth along the direction of relative velocity.

Generally speaking, MPR is very good at finding precise penetration depth in any direction -- but the published implementation does not find the minimum penetration depth, nor can it tell you the distance between two shapes that do not intersect.

---Xeno (Gary Snethen)
http://xenocollide.com

Thank you for clearing that up, Xeno. I'm sorry I kicked up so much fuss to force you to come over here.
Perhaps I should never have mentioned the deep penetration problems in the first place. I was aware that they were not really relevant to the stability of the simulation, but I wanted a screenshot from the demo program showing the problems.


This is a cool way to look at the method. It hadn't occured to me before.