Minkowski Portal Refinement collision detection algorithm

Question

Preface: While I was learning the basics of collision detection, I read in various places that the SAT and GJK algorithms don't natively return contact points. So I decided to research the MPR algorithm. I've found very little information about it online.

My questions are the following:

1. What are the steps it takes?
2. Does MPR detect collisions continuously? If not, is it feasible to upgrade it?
3. Does it return contact points, or a simple true/false on collision? How does it calculate them?

(I'm targeting 2D, but it would be nice to know the differences in 3D.)

Answer 1

If you decided to research the MPR algorithm, I'd advice you to deal with GJK first. However I'm not sure, that the MPR is what you are looking for. The main idea of these two algorithms is very close, more over MPR does not provide information about contact point either. It should be mentioned that in contrast with GJK, MPR does not give the shortest distance between separated shapes

I'd never worked with MPR, but it is said, that in comparison with GJK, MPR is simpler and more numerically robust. Once you understand the GJK, this article will be enough to understand MPR.

I'm not sure, but I think that it is possible to make MPR incremental. In case of GJK, for example, you can cache the simplex from the last iteration and use it in next step, thus it would take less iterations. Perhaps, it may be possible to cache a portal.

To get the set of contact point, you have to use other algorithms. SAT can be extended to get the contact set.

You should take into account the fact, that the number of real intersections would be much less than the number of intersection tests. Thus it is likely that the pair of GJK algorithm and something simple to process intersecting polygons would be rather effective. If you have a pair of intersecting polygons, i.e. you can just do an edge to edge clip of each polygon against the other.