I’m currently implementing a game engine as a hobby project and I am now implementing GJK for the first time after learning about it at university over a decade ago. To wrap my head around it, I decided to implement it in 2D first and share it here.
The problem we want to solve is to detect whether two convex1 shapes are intersecting and, if they are, identify a contact point and a separation vector which we can use for resolving the collision. This problem is equivalent to checking whether the Minkowski Difference of the two shapes contains the origin point. The separation vector is equal to the vector from the origin to the closest point on the surface of the Minkowski difference, and the contact point can be found by reconstructing the points on the two shapes which generated that point on the surface of the Minkowski difference.
GJK handles collision detection by searching for a subset of the Minkowski Difference which contains the origin. More specifically, each subset it considers is a simplex consisting of 1-3 vertices which form a point, a line, or a triangle within the Minkowski Difference. In 3D, we would have 1-4 vertices and additionally consider tetrahedrons. The algorithm either terminates having found a separating axis signifying that there is no intersection, or by finding a simplex of 3 points that contain the origin.
However, that’s not everything we need. We still don’t know the contact point or the separation vector, all we have is some simplex inside the Minkowski difference. To find the separation vector, we have to use a second algorithm called the Expanding Polytope Algorithm. This algorithm iteratively expands GJK’s final simplex by searching outwards from the face which is closest to the origin until it reaches the surface of the Minkowski difference and can’t search any further.
Without further ado, here’s the demo:
You can stop or start the simulation by clicking, and can control the flow of time with left and right arrow keys.
The simulation has two shapes being tested for intersections. Below them is a visualisation of the outputs from GJK and EPA:
I don’t minify the code for my site, so you can simply view the source for this page to see the commented code.