I recently used Casey's GJK video to learn and implement GJK for discrete collision detection. However, once GJK detects a collision, what do we do next? Often, we want to translate one of the objects so that there is no longer a collision. Well, one way that to calculate this translation vector that I saw commonly mentioned in various threads is called the Expanding Polytope Algorithm (EPA). It is extremely similar to GJK (in fact, I would argue that a cursory knowledge of GJK is necessary to understand EPA).
However, it took me longer to implement than I liked because there really weren't any good tutorials for it that I could find. They all lacked one of two things:
- Good visual examples (which is what made Casey's GJK video so understandable).
- Concrete explanation of how to extrapolate from the 2D version of EPA to the 3D version.
I added lots of debug visualization rendering to my test sandbox to help me understand what my implementation was doing, and where bugs were appearing. This visualization improved my understanding of both GJK and EPA dramatically -- a picture is worth a thousand words!
Anyways, since I hadn't been able to find a good EPA tutorial, and since I had a great visualization tool, I figured I would go ahead and make what I consider to be a good EPA tutorial myself, so I can share it with others. I'm not the most graceful speaker, but I think it turned out really well and I hope that it can be the go-to video explanation for the EPA algorithm in much the same way that Casey's video is for GJK.
It includes both an explanation of EPA, and a visualization of both GJK and EPA. So even if you already understand these algorithms, I think the visualizations at the end are worth a watch to help solidify your understanding with visual examples. The description includes timestamps to skip straight to the visualization.
Without further ado, here is the video:
If you have any questions or feedback after watching, please let me know!