Minkowski difference

Before I start I should mention that technically the phrase "Minkowski difference" actually indicates a different operation than the one described here. However, its such a common misnomer that it really does no harm and is more descriptive of whats going on than either "Minkowski sum" or, to use robotics terminology, the "Translational Configuration Space Obstacle" (TSCO).

The Minkowski difference is a special case of the Minkowski Sum of two convex shapes. The Minkowski difference of two shapes is one shape "grown" by the shape of another. If you imagine two circles of equal radii (positioned at A and B), the Minkowski difference would be one circle of twice the radius, positioned A-B.

It's formed by taking every point on the surface of one object, finding the most opposite point of the other and subtracting them to form a third point which lies on the surface of the Minkowski difference. Its easiest to imagine this in the case of circles; for any direction D, there is a point most opposite it in the direction -D. If you do this for two circles of equal radius, you end up with a third circle of twice the radius, which is the Minkowski difference of the two shapes.

The key thing to note is that when A and B collide, C contains the origin of what is referred to as Configuration Space. Configuration space is the space that the Minkowski difference resides within - the set of vector differences of two objects. In these applets I have overlaid configuration space and world space so you can see both objects and the difference.

Notice that the penetration depth is simply the vector from the origin to a point projected onto the surface the Minkowski difference, show here as the green line.

Move the spheres by dragging their centres

You can use the Minkowski difference to simplify the dimension of a problem. A good example is for finding the distance between two line segments in 3d. The Minkowski difference of two line segments is a parallelogram, so then the problem is reduced to finding the distance between the parallelogram and the origin. Simply project the origin onto the plane of the parallelogram and clamp at its edges so that the projection lies within the polygon. Then the distance is that of the projected, clamped point to the origin.

If you wanted to collide a sphere with a triangle, the Minkowski difference is the triangle "inflated" to have spherical edges which are the radius of the sphere. The distance between the two is, as ever, the the distance from the Minkowski difference to the origin. This is no easier than simply finding the clamped distance from the sphere centre to the triangle. However if you then wanted to find the time of first contact of a moving sphere and a triangle the Minkowski difference comes into its own. Ray-casting against the Minkowski difference starting from the origin, going in the direction of the ray will give you time of first contact between the sphere and the triangle.

This works for any convex shapes which you can perform the Minkowski Difference operation on and Gino Van Den Bergen has recently written a paper on a way to modify GJK to compute these ray-casts against general convex shapes. I will talk about this more in the section on continuous collision detection.

Finding the distance from a capsule (line swept sphere) to a triangle is equivalent to finding the distance from the Minkowski difference (which looks like the triangle swept along the capsule's axis) to the origin. This comes down to finding the minimum of distances between faces (the normal of which having a positive dot product with the origin) and the origin.

When ever I'm faced with a new geometrical collision detection problem I always try to imagine it in terms of the Minkowski Difference and the solution nearly always follows. I find the alternative (separating axis test) is often difficult to visualise and therefore less intuitive to solve in practice, although often the two come down to identical maths.

The following is a fairly flexible example of n sided polygons undergoing the Minkowski difference operation. The two number boxes indicate the number of points in each polygon. Try entering 2 in one to get a line and then three in the other to get a triangle. Also try increasing the second until its 20 or so, where it approximates a circle to see the shape of the difference change.

Enter numbers and drag polygons (you can drag vertices to rotate objects)