Jump to content
  • Advertisement
Sign in to follow this  
newtomaths

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
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?

Share this post


Link to post
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 this post


Link to post
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.




Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!