I'm doing GJK + EPA in 2D for collision detection + resolution.

For GJK, I was using the vector (1,0) as my first support direction. However, if the origin happens to fall exactly on the simplex line ( quite easily happens with circles placed on an axis-aligned plane), inside EPA, it doesn't know which direction to expand to. That is because the expansion is supposed to happen in the direction of origin. But because the origin is on the line, the vector towards origin has a length of 0. So although collision is detected in GJK, I don't get any contact normal + penetration depth from EPA.

I've 'solved' it by randomizing the initial support direction every time. It can still miss a few times in a second but the visual result looks fine.

Is there a standard way of handling this edge case that I don't know of? Or maybe this shouldn't be happening at all and I'm doing something wrong?

[Edit] Since I'm not getting any replies, I've added a picture trying to make the situation clearer. Figure B shows when the origin is not on the simplex line. So a third point can be found by expanding towards the direction of the origin.

However, in Figure A, the origin lies directly on the simplex line. So there is no 'direction' towards the origin to expand towards.

EPA example image

  • \$\begingroup\$ I'm nearly a month late, but back when I implemented EPA for my own engine, I believe that my research said that any direction would work perfectly fine. \$\endgroup\$ Aug 27 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.