Game Physics: Collision Detection – CSO & Support Function

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 A and B be two shapes (2D or 3D), the Minkowski Sum of A and B, denoted A \oplus B, is a shape resulted from “sweeping” A all across the region occupied by B, or sweeping B across A (the result is the same). Another way of saying this is that the Minkowski Sum of A and B is a shape that is a collection of points, where each point is the result of a point from A plus a point from B.

    \[ A \oplus B = \{ P_A + P_B \, | \, P_A \in A, P_B \in B \} \]

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

Minkowski Sum Circle Rect

If we reflect B about the origin, we get:

    \[ -B = \{ -P_B \, | \, P_B \in B \} \]

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

    \[ A \ominus B = \{ P_A - P_B \, | \, P_A \in A, P_B \in B \} \]

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.

    \[ Support(\overrightarrow{v}, A) = P \in A, \,\, (P \cdot\overrightarrow{v}) \ge (Q \cdot\overrightarrow{v}), \,\, \forall Q \in A \]

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

    \[ Support(\overrightarrow{v}, -B) = -Support(- \overrightarrow{v}, B) \]

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

    \[ Support(\overrightarrow{v}, A \oplus B) = Support(\overrightarrow{v}, A) + Support(\overrightarrow{v}, B) \]

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

    \[ Support(\overrightarrow{v}, A \ominus B) = Support(\overrightarrow{v}, A) - Support(- \overrightarrow{v}, B) \]

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.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Gamedev, Physics. Bookmark the permalink.

4 Responses to Game Physics: Collision Detection – CSO & Support Function

  1. karun says:

    Hi

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

  2. G.Z, Chen says:

    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.

    • Allen Chou says:

      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.

Leave a Reply