MPR — the Cake is a Lie
This is the second part of a series of blog posts where I'll be going through game physics related tech. The previous blog post can be found here.
NOTE The blog post is interactible, best experienced with mouse.
We have managed to define our convex shapes using support functions, now what?
Minkowski Portal Refinement (MPR)
As mentioned in the previous blog post, to determine if two shapes are overlapping, we only need to figure out if the origin is inside the Minkowski subtraction. In this blog post I will go through Minkowski Portal Refinement
If you're familiar with GJK which has been around since the 80's, then MPR can be seen as a different approach to a similar solution; find a simplex that encloses the origin.
It's Very Simple(x)
The visualization I'm showing in these blog posts are 2D, simply because it's easier to read (and frankly, easier to write as well 🤣) but nothing related to Minkowski, MPR nor GJK is specific to any dimension — you can do collision detection in 4D if you wanted to!
The term simplex is a geometrical shape that can be thought of as a generalization of a 2D triangle to different dimensions. A 3-dimensional simplex is a tetrahedron (a pyramid made up of triangles) and a 1-dimensional simplex is a line segment.
Let's start building the simplex, but where do we start?
MPR starts at the proverbial "center" or "deep inside" of a shape. Which point you actually start with doesn't matter that much in the form of correctness, but if you pick a point close to the edge you might end up with numerical instabilities. Here's an Encyclopedia of Triangle Centers if you're looking for inspiration, but any point inside the shape should do.
A:
B:
Use mouse to move around the shapes.
c and p are the first vertices of the simplex.
After we have determined our center c, we want our next vertex to be towards the origin. If we use the support function, giving the direction from our center to the origin, we end up with a point on the contour of our Minkowski subtraction. Let's call this point p.
We can determine if the origin is obviously not inside the shape. Remember that the support function gives you the point furthest along a direction? This point, with the support direction, splits the space in two. On one side is the entire shape (including our center point), and on the other side is something that obviously can't be inside the shape. If the origin is inside the latter area, then the origin cannot be inside the shape. If it's on the same side as our center point, then we have more work to do.
Segment p-q is called a portal.
With c and p, we continue by searching for our third triangle point to enclose the origin. But in which direction?
The line going through c and p divides the space in two halves. The third point is determined by taking the edge normal towards the origin, and passing that direction to the support function. This gives us the point q which is our third point of the triangle.
The line segment between p and q is called a portal, which we will refine in case the point is not already inside the triangle.
Origin is inside the triangle if behind portal.
Note that the ray from c towards origin is always between the edges c-p and c-q. In other words, the ray from our center towards origin must pass through the portal.
Given this knowledge, we can determine if the origin is inside the triangle by checking which side of the portal it is on. If it's towards our center, we know the origin is contained in the triangle and we have overlapping shapes. If it is not, then we need to refine the portal.
Refinement is done by subdividing the portal.
Refinement step shrinks the portal.
We're looking for a point on the contour that is outside the portal. Such a point produces a line segment to c that intersects the portal. This point can be produced by passing the portal normal to the support function. Let's call this point r.
This gives us two new line segments, q-r and p-r — one of which will be our new portal.
The line passing through c and r divides the space in two parts, one containing the origin and one of the portal end points — and the other containing our second portal end point. The new portal is r and the old end point that is on the same side as the origin.
The refinement step repeats until the origin has been determined to be inside the triangle, or until a point is added such that the origin is determined to be obviously outside (see first step).
How many iterations can you make the algorithm take?
Detecting collisions is one of the first steps in physics simulation. Resolving a collision requires a bit more from the detector though — determining penetration depth, which is for the next blog post!
If you're coming here from the distant future, see you in the next post! If not, you can always join our mailing list and we'll send a message when it goes live. Until next time!
- Jens the Programmer, April & May 2025