Hello!
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:
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!
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!
Watched to about to before the 3D discussion starts. I've implemented GJK for 2D before (following Caseys video and other example code I could find) but never found a good way to resolve collisions. Haven't done 3D collision before so don't know how much the latter part of the video will help me but will certainly check it out when I'm working on that sort of thing again.
So not much feedback from me right now unfortunately, just wanted to thank you for making the effort. Good visuals are certainly a lot easier to understand and the more the better in my opinion.
So not much feedback from me right now unfortunately, just wanted to thank you for making the effort. Good visuals are certainly a lot easier to understand and the more the better in my opinion.
After watching this video to get started and reading this article for additional information, I just implemented EPA in 2d.
I have one remark about the video (about the 2d part): I don't think it's possible to get a concave polytope because GJK should always return a simplex where the points are on the perimeter of the Minkowsky difference. And when EPA adds a new point, it uses the GJK support function that also returns a point on the perimeter.
The problems I ran into when implementing EPA (in 2d) where different:
- GJK can return a simplex where one of the points is the origin. But you can early out of this case because it means that the shapes are just touching, there is no overlap to "correct".
- (I guess) Floating point precision error in 2 places:
1. When I use the support function to search for a new point in the direction on the closest edge from the origin.
If there is no farthest point, the support function will return one of the two points from the closest edge, that we dot with the normal of the edge to know the distance of the origin to the edge (we do that in all case, but the problem is only if there is no new point). Depending on which point was returned, the distance might not exactly equal the minimum distance computed before and so we can failed to finish the loop and add a point that was already in the polytope. To solve that you can either have a tolerance value (0.00001f was not enough in my case) or compare with both points of the edge and pass if one of them has the right distance (in my case distance - minDistance always return 0.0f).
2. When searching for the closest edge and the origin is on one of the simplex edges.
I have an assert in the code to make sure the distanceFromOriginToEdge is >= 0. But when the origin is on one of the edge, it sometimes is less then zero (a very small number). In practice it should not matter as long as the normal direction is toward the outside of the polytope.
I have 3 question, not directly related to EPA or GJK, about floating point numbers:
1. Can I assume, given similar floating point inputs that a set of operations will always give me the same result on the same computer ?
2. Is there a way to compute the error range of floating point computations ? For example if I know that I have 3 multiplies, 4 adds and 1 divide that should add up to an expected value, can I know "how far" from that value I might end up ? And I suppose it depends on if those are small numbers (0.000001f) or big numbers (100000.0f) or a combination of both.
3. Is it interesting to use doubles instead of floats for computations if the inputs are floats casted to doubles ?
I have one remark about the video (about the 2d part): I don't think it's possible to get a concave polytope because GJK should always return a simplex where the points are on the perimeter of the Minkowsky difference. And when EPA adds a new point, it uses the GJK support function that also returns a point on the perimeter.
The problems I ran into when implementing EPA (in 2d) where different:
- GJK can return a simplex where one of the points is the origin. But you can early out of this case because it means that the shapes are just touching, there is no overlap to "correct".
- (I guess) Floating point precision error in 2 places:
1. When I use the support function to search for a new point in the direction on the closest edge from the origin.
If there is no farthest point, the support function will return one of the two points from the closest edge, that we dot with the normal of the edge to know the distance of the origin to the edge (we do that in all case, but the problem is only if there is no new point). Depending on which point was returned, the distance might not exactly equal the minimum distance computed before and so we can failed to finish the loop and add a point that was already in the polytope. To solve that you can either have a tolerance value (0.00001f was not enough in my case) or compare with both points of the edge and pass if one of them has the right distance (in my case distance - minDistance always return 0.0f).
2. When searching for the closest edge and the origin is on one of the simplex edges.
I have an assert in the code to make sure the distanceFromOriginToEdge is >= 0. But when the origin is on one of the edge, it sometimes is less then zero (a very small number). In practice it should not matter as long as the normal direction is toward the outside of the polytope.
I have 3 question, not directly related to EPA or GJK, about floating point numbers:
1. Can I assume, given similar floating point inputs that a set of operations will always give me the same result on the same computer ?
2. Is there a way to compute the error range of floating point computations ? For example if I know that I have 3 multiplies, 4 adds and 1 divide that should add up to an expected value, can I know "how far" from that value I might end up ? And I suppose it depends on if those are small numbers (0.000001f) or big numbers (100000.0f) or a combination of both.
3. Is it interesting to use doubles instead of floats for computations if the inputs are floats casted to doubles ?
Edited by Simon Anciaux
on
mrmixer
I have 3 question, not directly related to EPA or GJK, about floating point numbers:
1. Can I assume, given similar floating point inputs that a set of operations will always give me the same result on the same computer ?
2. Is there a way to compute the error range of floating point computations ? For example if I know that I have 3 multiplies, 4 adds and 1 divide that should add up to an expected value, can I know "how far" from that value I might end up ? And I suppose it depends on if those are small numbers (0.000001f) or big numbers (100000.0f) or a combination of both.
3. Is it interesting to use doubles instead of floats for computations if the inputs are floats casted to doubles ?
keyword: https://en.wikipedia.org/wiki/Numerical_stability
Thanks.
I read several articles about floating point precision and I have a (kind of) better idea of what to expect. Here are links to some of those site/articles:
Comparing Floating Point Numbers, 2012 Edition
The Floating-Point Guide
Floating point on wikipedia
What Every Computer Scientist Sho...w About Floating-Point Arithmetic
And to come back to EPA, in my first case of floating point problem, I found a case where the solution (testing both points of the segment) doesn't work: If the minkowsky sum has several co-linear points on the nearest edge. So I changed to having an error margin.
I read several articles about floating point precision and I have a (kind of) better idea of what to expect. Here are links to some of those site/articles:
Comparing Floating Point Numbers, 2012 Edition
The Floating-Point Guide
Floating point on wikipedia
What Every Computer Scientist Sho...w About Floating-Point Arithmetic
And to come back to EPA, in my first case of floating point problem, I found a case where the solution (testing both points of the segment) doesn't work: If the minkowsky sum has several co-linear points on the nearest edge. So I changed to having an error margin.
You are my best friend right now! :D <3 Thanks for the video, exactly what I need right now to move forward.
Your video helped me a lot, also the reference http://www.dyn4j.org/2010/05/epa-expanding-polytope-algorithm/ and Casey's great GJK video.
I had a go at implementing GJK and EPA in 2d and made it into a header file in the style of Sean Barret's library. https://github.com/Olster1/easy_headers/blob/master/easy_gjk.h
Maybe more for educational use. Still needs more work to be done to make it more robust and handle more shapes (and there might still be bugs in there). I was surprised how well it works :) Thanks everyone for the great references!
I had a go at implementing GJK and EPA in 2d and made it into a header file in the style of Sean Barret's library. https://github.com/Olster1/easy_headers/blob/master/easy_gjk.h
Maybe more for educational use. Still needs more work to be done to make it more robust and handle more shapes (and there might still be bugs in there). I was surprised how well it works :) Thanks everyone for the great references!
Edited by Oliver Marsh
on