Minkowski Portal Refinement (MPR) for 2D

[pcm2008]

Maybe I can help. What is the actual problem you're seeing?

I'm having trouble interpreting the image you provided. Can you explain how the image demonstrates the problem?

Hi,
First of all I would like to say that is not the author of this applet; I've found it on this forum. So I don't know how MPR is implemented in this applet, but I've tried to follow the steps from your webpage and it seems like the penetration dir is slightly inaccurate for this case.
The red and green polygons are the colliding objects and the blue polygon is their Minkowski difference (MD). The red and green large points are the closest features in the polygones returned by the algorithm, coresponding to the yellow point on the MD.
You can see that the distance from the origin to the yellow point on the MD is not the shortest (I've marked it with a red line). The shortest distance from the origin to the MD (that is the penetration dir) is marked with a green line. I've marked the brown point as the correct point, both on the MD and the two polytopes drawing.
I'll try to make more captures from the algorithm steps for better understanding.

[Xeno]

Thanks! I understand the problem now.

For the purpose of this discussion, let me define two distinct terms:
Penetration depth: The distance two bodies must be separated along a given vector until they are no longer penetrating.
Minimum penetration depth: The smallest penetration depth needed to separate two bodies.

The MPR2D algorithm that is described on my site (http://xenocollide.snethen.com/mpr2d.html) does not attempt to find the penetration depth. It only detects overlap.

Given that, let's discuss how to detect the contact normal and penetration depth along that normal using MPR on two shapes, A and B.

The easiest approach is to first determine that the origin is within A-B (the Minkowski difference). You can do this in 2D using the MPR2D algorithm on my website or the 3D equivalent in Game Programming Gems 7 ("XenoCollide: Complex Collision Made Simple").

Once you've identified that the origin is within A-B, you know there's a collision. You can then continue casting the origin ray to the boundary of A-B. Once you hit the surface, the normal of the portal is your contact normal.

You now need to find the penetration depth along this contact normal. To do that, run MPR again, using the contact normal as the direction of your origin ray. (You can do this by using "origin - contactNormal" as your interior point.) The distance between the origin and the surface of A-B along the direction of the contact normal is the penetration depth.

A note about minimum penetration depth: The MPR penetration depth I described above converges to the minimum penetration depth as the penetration is resolved. In the case you presented in your post, the objects are very deeply penetrated. There's no reason to believe that the direction of minimum penetration is the best choice (or even a good choice) when penetration is that deep.

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

[pcm2008]

Thanks Xeno for your reply.

The easiest approach is to first determine that the origin is within A-B (the Minkowski difference). You can do this in 2D using the MPR2D algorithm on my website or the 3D equivalent in Game Programming Gems 7 ("XenoCollide: Complex Collision Made Simple").

I've noticed indeed that is very simple to detect the overlap for 2 shapes using MPR, even for 3D case.

You now need to find the penetration depth along this contact normal. To do that, run MPR again, using the contact normal as the direction of your origin ray.

I think I understood your aproach. I'll try to use it.

There's no reason to believe that the direction of minimum penetration is the best choice (or even a good choice) when penetration is that deep.

I know that for this case the minimum penetration might not be the best separation at all. In fact that's why I'm trying to use some sort of caching aproach to obtain some temporal coherence, like I've wrote to you in a private message. It's pretty ok, but are there other better methods to use (managing the cache is sometimes tricky)?