2D Expanding Polytope Algorithm

Started by
3 comments, last by oliii 15 years, 3 months ago
Is there anyone kind enough to give me a plain explanation of EPA in 2D and how it works? GJK itself (after a bit) made intuitive sense and was easy to implement, but I can't seem to grasp how this leads to full intersection data in its EPA extension. Also, can EPA offer 2 points in the case where 2 polygons are coincident at parallel edges? If not, how would the contact set be determined? thanks!
Advertisement
Not JUST bumping... I'm interested in why I didn't get any replies, I thought that surely someone has dealt with this before.

Could someone recommend a better forum or a better way of phrasing my question perhaps? Or a resource?
I'll give it a go.

for each vertex of the EPA that you add, you need to keep track of the two points on each convex objects that made up that point on the EPA, so you can work backward.

i.e. each point on the EPA is something like :

p_epa = (pointOnConvexA - pointOnConvexB);

Now, you need to find the point on the epa that is the closet to the origin. Most likely, that point would be on an edge feature, that is, a linear interpolation of two vertices of the EPA.

so p_closest = p_epa0 + t * (p_epa1 - p_epa0);

therefore, the two points of contact on each polygon would also be a linear interpolation of the two point features on each convex object.

pa_closest = p_epa0.pointOnConvexA + t * (p_epa1.pointOnConvexA - p_epa0.pointOnConvexA);

pb_closest = p_epa0.pointOnConvexB + t * (p_epa1.pointOnConvexB - p_epa0.pointOnConvexB);

if you catch my drift...

EDIT : Basically, it's the same thing you would do to calculate the closest point and distance between two disjoint convex objects, using the classic GJK.

Everything is better with Metal.

brilliant! that makes perfect sense, thank you! i'll give it a shot.
Hope that works.

here is another method. The closest point on the EPA basically gives you the normal of collision.

So, you can use that normal of collision to find the two supporting features (a face, a vertex, an edge) on both objects.

for object A, you will get either a support vertex, or a supporting edge.
for object B, you will get either a support vertex, or a supporting edge.

give the combinations (vertex vs vertex, edge vs edge, vertex vs edge, edge vs vertex), you can compute the contact points from the support points.

that's what I use here. I use the normal of collision to find the supporting vertices on the two objects, then I convert those support vertices into pairs of contacts.




Everything is better with Metal.

This topic is closed to new replies.

Advertisement