# 2D Expanding Polytope Algorithm

This topic is 3630 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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!

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
brilliant! that makes perfect sense, thank you! i'll give it a shot.

##### Share on other sites
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.

1. 1
2. 2
Rutin
20
3. 3
khawk
18
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633760
• Total Posts
3013723
×