Minkowski — Let's Get Physical!
This is the first part of a series of blog posts where I'll be going through game physics related tech.
NOTE The blog post is interactible, best experienced with mouse.
After several attempts of using physics engines, none of the off-the-shelf solutions have tickled my fancy. In fact, some have been so bad I had to write more code to overcome the issues than the amount of code that's required for writing the physics simulation from scratch. As such, ever since our first game, we have done our own physics code.
Meet Minkowski
Minkowski addition and subtraction define arithmetics over sets of points. In principle it's very simple; the Minkowski addition of two sets is the set of all points in the first set being added to each point in the second set. For subtraction you subtract each point from first set with each point of the other.
It's fairly easy to get an intuitive sense of how the resulting shape should look like after a Minkowski addition. Consider having a brush that's the shape of one set, to do the addition you "paint" with that brush on each point on the other shape. In practice though, you only need to paint the contour as any internal point is already painted. This is sometimes also called dilation.
A:
B:
Minkowski addition of above shapes.
"But how does this help with physics simulation?" you might ask. If two bodies overlap, then there is at least one point a in set A and one point b in set B such that a = b, or more interestingly a - b = 0. This is why Minkowski based collision detection algorithms (such as GJK and MPR) try to determine if the set A - B contains the origin. If it does, then the bodies are overlapping and a collision needs to be resolved.
A:
B:
Use mouse to move around the shapes to see the Minkowski subtraction in action.
Support function direction:
Observe that origin is inside the shape only when A and B overlap.
The example shapes only contain convex sets. This is very important, as a convex set subtracted by another convex set is also a convex set. For games this is not a problem as the shapes are authored by the developer and complex shapes can be subdivided into multiple convex shapes.
Support Functions
Most often the convex sets are defined by a so-called support function. This function returns a point on the shape that is furthest along a given direction. In other words, it takes a direction as input, and returns a point on the shape that has the largest dot product with the direction. Sometimes there are several such points, in which case any of those points are valid results.
As an example support function, circles are defined by the support function circle.center + circle.radius * normalized(direction).
For collision detection, we're interested not in the support function of A supA(dir) and B supB(dir); but the support function of A - B sup(A-B)(dir). Thankfully, finding such a support function is trivial: it's sup(A-B)(dir) = supA(dir) - supB(-dir). Intuitively this makes sense. If we start at the point on A furthest along the direction dir and ask, which is the point subtracted from B that brings us furthest along the direction? That is the point on B that is furthest along the opposite direction.
Don't take my word for it, go have a look for yourself!
By defining shapes by their support functions, and the support function of the Minkowski subtraction, we have the required building blocks to create collision detectors that are not specific to the shapes themselves. The problem transforms from "Does shape X and shape Y overlap?" to "Can we determine if origin is inside a convex shape using its support function?".
In the next blog post I will go over one approach on how to determine if origin is, or isn't, inside such a shape. Stay tuned!
P.S. If you don't want to randomly refresh this page until the next blog post arrives, you can join our mailing list and get notified by email instead.
- Jens the Programmer, March & April 2025