Last updated Screenshot from XenoCollide, the first implementation of MPR
The Minkowski Portal Refinementcollision detectionalgorithm 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.
External links
Snethen, Gary (2008) "Complex Collision Made Simple", Game Programming Gems 7, 165–178
In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.
MPR may refer to:
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of pairs, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a function with finite domain. It supports 'lookup', 'remove', and 'insert' operations.
Collision detection is the computational problem of detecting the intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing fields, primarily in computer graphics, computer games, computer simulations, robotics and computational physics. Collision detection algorithms can be divided into operating on 2D and 3D objects.
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
In geometry, the Minkowski sum of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B:
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.
A physics engine is computer software that provides an approximate simulation of certain physical systems, such as rigid body dynamics, soft body dynamics, and fluid dynamics, of use in the domains of computer graphics, video games and film (CGI). Their main uses are in video games, in which case the simulations are in real-time. The term is sometimes used more generally to describe any software system for simulating physical phenomena, such as high-performance scientific simulation.
Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.
A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to aid agents in pathfinding through complicated spaces. This approach has been known since at least the mid-1980s in robotics, where it has been called a meadow map, and was popularized in video game AI in 2000.
The Blender Game Engine was a free and open-source 3D production suite used for making real-time interactive content. It was previously embedded within Blender, but support for it was dropped in 2019, with the release of Blender 2.8. The game engine was written from scratch in C++ as a mostly independent component, and includes support for features such as Python scripting and OpenAL 3D sound.
The C4 Engine is a proprietary computer game engine developed by Terathon Software that is used to create 3D games and other types of interactive virtual simulations for PlayStation 5, PlayStation 4, PlayStation 3, Windows, Mac OS X, Linux, and iOS.
Bullet is a physics engine which simulates collision detection as well as soft and rigid body dynamics. It has been used in video games and for visual effects in movies. Erwin Coumans, its main author, won a Scientific and Technical Academy Award for his work on Bullet. He worked for Sony Computer Entertainment US R&D from 2003 until 2010, for AMD until 2014, for Google until 2022 and he now works for Nvidia.
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
Box2D is a free open source 2-dimensional physics simulator engine written in C++ by Erin Catto and published under the MIT license. It has been used in Crayon Physics Deluxe, Limbo, Rolando, Incredibots, Angry Birds, Tiny Wings, Shovel Knight, Transformice, Happy Wheels, and many online Flash games, as well as iPhone, iPad and Android games using the Cocos2d or Moscrif game engine and Corona framework.
The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets, first published by Elmer G. Gilbert, Daniel W. Johnson, and S. Sathiya Keerthi in 1988. Unlike many other distance algorithms, it does not require that the geometry data be stored in any specific format, but instead relies solely on a support function to iteratively generate closer simplices to the correct answer using the configuration space obstacle (CSO) of two convex shapes, more commonly known as the Minkowski difference.
Stencyl is a video game development tool that allows users to create 2D video games for computers, mobile devices, and the web. The software is available for free, with select publishing options available for purchase. The software was originally called "StencylWorks" while in development and for the initial release but was later shortened to just "Stencyl".
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
