Home > Physics > Minkowski Portal Refinement

Minkowski Portal Refinement

The below demo shows off the Minkowski Portal Refinement algorithm. To give everyone a brief overview… lets start with the basics. Imagine I wanted to see if a convex polyhedra (lets call it A) contained a point or not. We could make an infinite half plane with every face, and see if the point is inside each half plane… but that could get ugly for convex shapes with large amounts of faces. Would you buy the argument that if another convex shape, B, is inside the original convex shape A, and the point is inside B, then it is necessarily inside A? Given that’s the case, what if we could find a smaller shape inside A that contains the point, instead of testing with every face? That’s a good portion of MPR.

The second mind trip comes primarily from computational geometry and Minkowski spaces, but I’ll see if I can’t sum it up. Imagine you had two shapes J and K, and somehow you subtracted every single point in J from every single point in K. One interesting thing that would come up is that if the shapes were colliding, then necessarily the zero vector would show up in the subtraction (because the two shapes would have at least one point in common, thus that point minus itself is zero!). Furthermore, we introduced a new operation called the Minkowski Difference, which is essentially the subtraction I described above, however, it turns out that we don’t actually need to subtract all the points from each other (this would be prohibitively expensive). Instead, what we can do is attempt to combine what we talked about above with the Minkowski Difference operation, and attempt to find the zero vector! This step is a little more complicated than I’m making it out to be, but that is the gist of the algorithm (actually what I covered is more like GJK, but MPR is a subset of GJK). From that point, when you find the origin, it turns out you can also find the penetration depth and contact normals.

For anyone that wants to see an implementation or code sample, here it is: MPR


Categories: Physics Tags:
  1. boineeincuddy
    June 8th, 2010 at 04:20 | #1

    great article, very informative

  1. No trackbacks yet.