Minkowski Difference & GJK Algorithm
I decided I wanted to challenge myself to detect intersects of complex shapes using methods that differ to Axis Aligned Bounding Boxes (AABB) or Spherical detection. Often we’re able to approximate shapes down to squares or circles in smaller projects, but in larger projects which require more realism there is often a need for more accurate collision detection (or intersection detection) and we must use a more robust method. The repository is publicly available for access on GitHub.
Minkowski Difference
Minkowski Difference is the core behind the theory of the solution I worked to implement. It works by taking every vertex belonging to Polygon A and subtracting every vertex in Polygon B. If the resulting shape contains the origin, then we can assume a collision has occurred and the two shapes intersect.
However, there is more complexity to consider. We must identify the convex hulls defined by the resulting vertices and discard the unnecessary vertices that do not contribute to the shape of the convex hull (meaning they are located inside the hull rather than on an edge). Once the convex hull has been constructed, we create triangles using every vertex belonging to the convex hull, and identify if the origin lies within any of these triangles. This is a bit of a brute force approach, and becomes quite inefficient on large and complex 3D models with lots of polygons, and unlikely to be a scalable solution.
Take a look on the left and you can see the algorithm at work. We take two separate shapes defined by figures A and B with an intersection. We subtract each vertex of one shape from the other, and find ourselves with a new resulting shape defined by figure C. Whilst there would be an awful lot of images to include to show every triangle that was checked, you can see Figure D draws the triangle vertices that contain the origin indicating a collision has occurred.
The project code for Minkowski Difference can be found here.
GJK Algorithm
Minkowski Difference has some shortcomings for collision detection within games. Modern 3D models can be incredibly complex with lots of polygons, and it would prove inefficient to do lots of these collision detection checks at runtime. This is where the GJK algorithm steps in. Instead of calculating the Minkowski Shape and brute forcing the triangles of the convex hull to check if any contain the origin, it calculates the most extreme points in each direction to identify the outermost points of the shape. It does this by first creating a Simplex, and then using a support function to gradually adjust the points of the simplex to represent the outermost points of the Minkowski difference. Each time we calculate a new line, we check if the origin could possibly lie behind the line – if not, we can escape early and no more calculations are required. This keeps all the benefits of Minkowski Difference collision detection without anywhere near as much of the computational cost.
Let’s take a look at the figures on the right to better understand the process. Take figures E and F as the shapes we want to check for intersection. By using the support function of the gjk algorithm, we identify the points in the most extreme directions in figures G and H. We know that it’s possible that the origin could lie on one side of each one of these simplexes (or in this case lines) meaning a potential intersection could be detected – if this was not the case we would have escaped early to avoid unnecessary calculations.
When we plot the support points together as in figure I, it becomes immediately clear that the origin is contained within the shape, and therefore a collision must have occurred.
The project code for the GJK algorithm can be found here.
