Box2D Forums

Hello,

For folks interested in narrow phase 2D collision detection methods, I've created an implementation of the Minkowski Portal Refinement (MPR) Algorithm, written in the D programming language. It's Inspired by the work of Gary Snethen (Xeno) and XenoCollide, and featured in Game Programming Gems 7.

You can find the project here: http://code.google.com/p/mpr2d/

I've also incorporated MPR2D into the Blaze Physics engine. I have it working for all polygon and sphere collisions. You can find the demo here: http://svn.dsource.org/projects/blaze/downloads/Blaze-Demos.zip

And the project here:
http://www.dsource.org/projects/blaze

Hopefully other people may find this material helpful. So far, these have been very fun projects to work on!

Mason

Maybe I have misunderstood how it works (though I did read the code and http://xenocollide.snethen.com/mpr2d.html), but it seems to me that, although this MPR code correctly determines whether two shapes are overlapping, all the auxilliary data that it returns is useless (the normal, and the contact points on the two shapes).

Attached is a swf showing a particularly pathological case. You may need to zoom to see the detail.

The algorithm allows you to track the closest features of the two convex objects involved, and returns the contact normal and penetration depth. You can also calculate the closest point of separation if needed.

I'm not sure what you mean by "useless." Have you take a look at the demo? I'm using MPR and it's quite stable and fast!

Demo: http://svn.dsource.org/projects/blaze/downloads/Blaze-Demos.zip

Later,
Mason

Oh I see: It's not meant to be 100% accurate. That should probably be made clearer.

EDIT: Whoops, missed your second post.

I looked at your mpr demo, and if the shapes are badly overlapping, then you can see that the contact points are outside the original shapes. Some research shows me that MPR is not intended to return the correct result every time (as in, the minimum separation), but just be usually right, in the circumstances that matter (obviously, deep penetration isn't a problem case for solid objects). Hence why your demo works fine, and with speed. But you'll still need to ensure people place the centers of their objects sensibly to avoid the problem I raised.

Hi, Boris!

I appreciate the feedback.



As far as penetration depth is concerned, MPR is as accurate as any other simplex based algorithm, including EPA. They simply use different strategies to achieve the same end result: finding the minimum distance from the CSO origin to the Minkowski sum/hull. This is a very good approximation of the penetration depth. I've actually done a side by side comparison with SAT in Blaze, and the difference is negligible in regard real time game applications. For believable results, I would say that consistency is much more important than 100% accuracy.



Not sure what you mean... Considering I perform a point in polygon test on the candidate verticies, the contact points should never be outside the original shapes. If you see objects overlapping, I would propose this is more a function of the impulse solver rather than the collision detection method. With any iterative based constraint solver you will never be 100% accurate. The idea is to give plausible, realistic results for game applications. It may also be good to note that I'm not putting any of my objects to sleep... This is on the todo list.

Peace,
Mason

This is not quite how my understanding of it works. The min distance from the origin to the Minkowski sum is exactly the penetration distance. However, MPR merely approximates this value, finding a local minimum rather than the global minimum. EPA, by contrast, does find the global minimum. See the reference, that I gave before, as evidence. (I cannot see the difference between MPR and XenoCollide, perhaps there is one I'm missing that will resolve all our differences?).


This, I am not disputing. I am also not arguing that MPR is a bad algorithm; it is fast and works in all the important circumstances. Also I now appreciate that similar algorithms suffer the same problems.


Attached is a screenshot showing what I mean. The circles contact point is clearly not on the surface of the circle. Granted, if the objects were solid like in your other demo, then this problem would never occur, but my earlier swf shows that there are more plausible failure scenarios. Notice how the yellow dot is not inside the yellow triangle, which is the basic source of the problem.

Hi, Boris!



Ah, thanks for the screenshot! A picture speaks a thousand words.

I'll have to investigate a little further. Right now I'm more inclined to believe it may be a bug in my code, as the yellow dot is supposed to be calculated from the segment of the yellow triangle that lies on the Minkowski sum, i.e. the final portal. In any case, if you're objects are penetrating that much in an actual simulation I think you may have bigger problems to worry about.

I've implemented both EPA and MPR, and in my experience they both return the same result, as least in the 2D case. I can't speak for 3D, as that's definitely beyond my level. I barely slid by multivariable calculus in college; three dimensions only serves to give me a headache.

Anyway, both algorithms seek the closest point on the Minkowski sum to the origin. From my practical experience I don't quite follow how there is a difference. Maybe you could explain it to me in your own words?

Thanks,
Mason

I appreciate you pointing this bug out. It'b fixed, and changes have been posted.

Ok, well obviously part of my misunderstanding came from the fact I was using your code to understand how the thing worked. Hence, some of my complaints at the algorithm, are really complaints at that bug.

But your fixed screen still shot illustrates that MPR does not pick the closest point on the hull. The yellow dot could be closer to the origin if it slid down a bit, basically to where the yellow dot was in the original screenshot. (only actually on the hull, clearly).

Again, here's the swf (adjusted for the bug) that shows that there are problem cases other than deep penetration. I cannot show you an example of it from the demos you put, as they call contain regular shapes.

That's why I very much appreciate the feedback! The more holes you try to poke through my implementation, the more incentive it gives me to make it better.



Good point, although I'm more inclined to believe it's a flaw in my implementation rather than the algorithm itself. It seems like I'm only having these robustness issues with circles. Have you noticed the same behavior with polygons? I'll have to go back and review a few things.



In your demo you choose the worst possible center point. The centerpoint is the geometric center, and not the center of mass. I use AABB boxes in my broad phase Sweep and Prune, so I choose the the AABB center, which seems to work well.

Again, if you have situations where your objects are completley overlapping, I think there are bigger issues to contend with in the simulation. CCD would prevent this from happening in the first place. In my Blaze demos, the algorithm works quite well, as objects are not allowed to penetrate very far by virtue of the applying sequential impulses.

Regards,
Mason