The Minkowski Portal Refinement

collision detection Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

is a technique for determining whether two convex shapes overlap. 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 Crystal Dynamics, Inc. is an American video game developer based in San Mateo, California and part of Embracer Group. The studio developed the '' Gex'', ''Legacy of Kain'', and ''Tomb Raider'' series. Founded in 1992 by Madeline Canepa, Judy L ...

and its sister studios within

Eidos Interactive Square Enix Limited (formerly Domark Limited and Eidos Interactive Limited) is a British subsidiary of the Japanese video game company Square Enix, acting as their European publishing arm. The company formerly owned ''Tomb Raider'', which was in ...

. 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 In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generally, ...

. 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
Geometric algorithms Convex geometry {{geometry-stub