Jump to content
  • Advertisement
Sign in to follow this  
Kazade

How do I find collision intersection point(s) using EPA?

This topic is 1192 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

I've implemented 2D collision detection using the GJK and EPA algorithms which provides the intersection normal and penetration depth, but to implement decent collision response I need to find the intersection point.

I've been searching for the answer for a while now but I can't find anything. Could someone explain how to find the intersection point?

Share this post


Link to post
Share on other sites
Advertisement

I haven't implemented the algorithm myself, but Gino Van den Bergen does write about the answer to your question in his book "Collision Detection in Interactive 3D Environments", iirc. Also, iirc, EPA will always only return a single point of intersection -- not multiple points.

 

My hunch would be that if you can grab the penetration depth through your implementation, then the best point of contact to represent the collision would be the deepest point. You should be able to just pull that right out of your EPA data once the algorithm terminates. If not then you can possibly just query a support point along the intersection normal.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites

IMHO EPA has too many numerical instability for closing contacts. Also, you'll need a contact caching mechanism later (which doesn't have the same quality as an single-shot contact generation method such SAT + Sutherland-Hodgman according to my research). 

 

Here you can find an old naive GJK-SAT implementation I wrote. No collision skins added. 

 

To get the closest points, I've followed this EPA approach. Assumming you have a tetahedron that encloses the origin of the MD at the end, you expand the polytope removing and adding vertex as described in the link. The data structure he uses is not the best one (he's not using structures such the half-edge), and the insert/removing operations on the polytope may be slow most of the time (cylinders, spheres, curved objects).

Edited by Irlan

Share this post


Link to post
Share on other sites

 

 

The data structure he uses is not the best one (such the half-edge)

What is bad about the half-edge data structure and what data structure do you recommend instead?

Share this post


Link to post
Share on other sites

 

 

 

The data structure he uses is not the best one (such the half-edge)

What is bad about the half-edge data structure and what data structure do you recommend instead?

 

 

Oh! I was suppose to mean "he's not using structures such the half-edge" (tried to connect the "best-one-such")). 

 

Edited.

Edited by Irlan

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!