GJK & EPA

Description:
For this assignment we had to implement a GJK and EPA algorithm to detect collisions between convex polygons.

GJK works by creating a simplex from Minkowski differences and checking within the created shape for the Origin.

EPA works to calculate penetration depth and the penetration vector of the colliding polygons.

Part A
Demonstrated here is the output running Steerlite using Polygon1

Part B
Demonstrated here is the output running Steerlite using Polygon2

Part C
Notice how part B erroneously detects a collision between polygons where none exist. This is because the GJK algorithm used in this project assumes all shapes input are convex, whereas in the case of the polygons tested in part B are most certainly not. To remedy this error, simply reorder the vertices in the xml file containing the polygons. SteerLite reads in the vertices in a way in which order matters, thus by reordering vertices we can make a set of points that output as a concave or complex polygon a convex or set of convex polygons. Below is the result of reordered vertices in the xml.

Notice that the output is the same in the terminal