GJK/EPA

Implementation of GJK (Gilbert–Johnson–Keerthi) and EPA (Expanding Polytope Algorithm) algorithm's in 2D

Note: A lot of the functions are not optimized. I'll try to mark them at some point, but in general be aware that this is not an optimal implementation, just an implementation.

Note 2: Have not added support for concave shapes, although you can draw them.

Controls:

• Q - switches between drawing and selecting mode. When drawing, a little red dot will follow the cursor
• Drawing Mode:
  • Left Click - place vertex
  • Space - links the vertices in the order they were placed. Note: There is no testing for non-simple polygons yet, so KISS
• Selecting Mode:
  • Left Click and Drag - move a shape around
  • Hold Left Click + Delete/Backspace - delete shape
  • Ctrl + Left Click - marks a shape. If 2 shapes are selected B replaces A and the new shape becomes B
  • Space - Calculates if intersecting

Build Requirements:

SFML 2.4.2 for rendering

References:

• GJK
  • Casey Muratori, "Implementing GJK" - molleyrocket.com
  • Allen Chou, "Game Physics: Collision Detection – GJK" - allenchou.net
• EPA
  • EPA (Expanding Polytope Algorithm) - http://www.dyn4j.org/
  • Allen Chou, "Game Physics: Contact Generation – EPA" - allenchou.net

See Also:

• Minkowski sum calculator
• Orbital physics engine