Minkowski Portal Refinement

The Minkowski Portal Refinement collision detection algorithm is a technique for determining whether two convex shapes overlap.

Screenshot from XenoCollide, the first implementation of MPR

The algorithm was created by Gary Snethen in 2006 and was first published in Game Programming Gems 7. The algorithm was used in Tomb Raider: Underworld and other games created by Crystal Dynamics and its sister studios within Eidos Interactive.

MPR, like its cousin GJK, relies on shapes that are defined using support mappings. This allows the algorithm to support a limitless variety of shapes that are problematic for other algorithms. Support mappings require only a single mathematical function to represent a point, line segment, disc, cylinder, cone, ellipsoid, football, bullet, frustum or most any other common convex shape. Once a set of basic primitives have been created, they can easily be combined with one another using operations such as sweep, shrink-wrap and affine transformation.

Unlike GJK, MPR does not provide the shortest distance between separated shapes. However, according to its author, MPR is simpler, more numerically robust and handles translational sweeping with very little modification. This makes it well-suited for games and other real-time applications.

External links

• Snethen, Gary (2008) "Complex Collision Made Simple", Game Programming Gems 7, 165–178
• Snethen, Gary (2008) "XenoCollide Homepage"
• Open source implementation: libccd