In Computer Animation (more generally in Computational Geometry), a problem of interest is to find out when two polygons represented on a computer intersect. To handle this (for the case of 2d polygons), we implemented the GJK and EPA algorithms.

GJK

The GJK algorithm makes use of the fact that if the Minkowski Difference of two polygons (represented by the set of their vertices) contains the origin, then the polygons must intersect. Since the Minkowski Difference is computationally inefficient to represent, GJK gets around this by constructing a simplex (in 2d, a triangle) inside of the hypothetical Minkowski Difference, and check if the origin lies in that point. If the origin doesn’t lie in that point, we use a support vector and two of the previous points to get a new simplex, and iterate until we find the origin. If we don’t find the origin (it’s not even in the Minkowski Difference, let alone the simplex), we stop.

http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/

EPA

EPA works the same way as GJK, except the question it answers is different. Whereas GJK creates the sequence of simplicies to find out whether or not there is a collision (i.e., return true or false), EPA returns the information associated with the simplex in which the origin was found: the depth and the support vector.