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.

A useful resource is this article:

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.

A useful resource is this article:

http://www.dyn4j.org/2010/05/epa-expanding-polytope-algorithm/

Technical Details

Since GJK and EPA tend to work better for convex shapes over other types of polygons, there can be abnormal behavior when ¬†certain test cases don’t conform to this assumption. This happened with the polygons2.xml, when we were given a concave shape as input. In order to remedy this, we rearranged the points in the xml file to form the convex hull of the original shape, and then proceeded to run GJK and EPA to check for collision detection.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s