This post is part of my Game Physics Series.

Configuration Space Object (CSO), a.k.a. Minkowski Difference or Minkowski Configuration Object, is a very important concept for collision detection. In addition to CSO, support function is an equally important mathematical concept & tool. Many algorithms related to collision detection, including the Gilbert-Johnson-Keerthi (GJK) algorithm, Expanding Polytop Algorithm (EPA), and Minkowski Portal Refinement (MPR) algorithm, heavily depend on the concept of CSO and the use of support functions.

### Configuration Space Object

As complicated as its name sounds, it is actually a very simple concept. Let’s first look at a mathematical operation called the Minkowski Sum.

Let and be two shapes (2D or 3D), the Minkowski Sum of and , denoted , is a shape resulted from “sweeping” all across the region occupied by , or sweeping across (the result is the same). Another way of saying this is that the Minkowski Sum of and is a shape that is a collection of points, where each point is the result of a point from plus a point from .

Let’s look at something more visual. The Minkowski Sum of a circle and a rectangle is a rounded rectangle.

If we reflect about the origin, we get:

We call the Minkowski Sum of and the Configuration Space Object (CSO) of and , denoted . Geometrically, the CSO of and is a shape that is the collection of points, where each point is the result of a point from minus a point from .

One important property of CSO is that **if the CSO of two shapes contains the origin, the two shapes are colliding**. You can verify this from the figure above: the circle and rectangle are colliding, and thus their CSO contains the origin.

This property is actually very easy to prove. If two shapes are colliding, it means that there are common points that are in both shapes. Remember that the CSO of two shapes are a collection of “point differences” of points from both shapes. As we construct the CSO point-by-point, if we choose the common points that are in both shapes, then we would end up with a “zero” point, which is exactly the origin. Thus the origin is within the CSO if the two shapes are colliding.

All collision detection algorithms are essentially determining if the CSO of two shapes contains the origin.

Another important property of CSO is that if the CSO contains the origin, then the distance between the origin and the closest point on the CSO’s boundary to the origin is the __penetration depth__ of the two colliding shapes. And if the CSO does not contain the origin (thus the two shapes are not colliding), the distance between the origin and the closest point on the CSO’s boundary to the origin is the __closest distance__ between the two shapes.

### Support Function

In order to efficiently determine if the CSO of two shapes contain the origin, many collision detection algorithms make use of a mathematical tool called the support function, a.k.a support mapping. A support function takes a direction and shape as input and returns a point as output. The output point is the furthest point inside the shape along the given direction. Note that there can be multiple points that are valid support function outputs for a particular shape. For instance, the support function of an AABB, given the positive x-axis direction, can return any point on the AABB’s face in the positive x-axis direction.

For a reflected shape, the support function is as follows:

The support function for a Minkowski Sum of two shapes can be expressed as the sum of the support functions of individual shapes:

Thus, the support function of a CSO of two shapes is:

### Computing CSO Support Point with Space Conversion

Normally, the support functions for different collider geometry are implemented in model space. However, the support function output for a CSO and the direction passed to the function are both in world space. Here is how the space conversion works:

void CsoSupport ( const Collider &colliderA, const Collider &colliderB, const Vec3 &dir, Vec3 &support, Vec3 &supportA, Vec3 &supportB ) { const RigidBody *bodyA = colliderA->Body(); const RigidBody *bodyB = colliderB->Body(); // convert search direction to model space const Vec3 localDirA = bodyA->GlobalToLocalVec(dir); const Vec3 localDirB = bodyB->GlobalToLocalVec(-dir); // compute support points in model space supportA = colliderA.Support(localDirA); supportB = colliderB.Support(localDirB); // convert support points to world space supportA = bodyA->LocalToGlobal(supportA); supportB = bodyB->LocalToGlobal(supportB); // compute CSO support point support = supportA - supportB; }

### End of CSOs & Support Functions

I have covered the necessary tools for us to move onto actual collision detection algorithms. In the next post, I will introduce to you one of the most popular collision detection algorithms, the Gilbert-Johnson-Keerthi (GJK) algorithm.

Hi

You say “origin”, but you do not explain what that origin is.

It’s the point (0, 0) in 2D, or (0, 0, 0) in 3D.

Hi, I have one question about Minkowski Difference. I try some case for proving the property that if the CSO of two shapes contains the origin, the two shapes are colliding. It’s true. But I have no idea about it. Can you give me some tips or website resources about it? Thank you.

I have added a short paragraph. It shows a brief proof of why the fact that the CSO of two shapes contains the origin implies collision. I hope this helps.