Minkowski Portal Refinement
Encyclopedia
The Minkowski Portal Refinement collision detection
algorithm
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
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.
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Crystal Dynamics is an American video game developer based in the San Francisco Bay Area and founded in 1992 by Judy Lang, Madaline Canepa and Dave Morris...
and its sister studios within Eidos Interactive
Eidos Interactive
Eidos Interactive Ltd. is a British video game publisher and is a label of Square Enix Europe. As an independent company Eidos plc was headquartered in the Wimbledon Bridge House in Wimbledon, London Borough of Merton....
.
MPR, like its cousin GJK, relies on shapes that are defined using support mappings
Support (mathematics)
In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set . This concept is used very widely in mathematical analysis...
. 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
Affine transformation
In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
.
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