GJK/EPA Question

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
mikeshafer
Posts: 49
Joined: Fri Feb 24, 2012 10:45 am

GJK/EPA Question

Post by mikeshafer »

Hi there everyone,

So usually this is not a problem in my engine, but when one convex object's center penetrates another convex object (say a triangle), the collision normal I'm getting is on the wrong side of the object. I guess GJK/EPA doesn't care that I'm colliding a long capsule against a triangle. My question is this: is there any way to tweak GJK/EPA so that it recognizes the triangle's normal and gives you the far-side collision normal instead of the near one?

I got some ideas I'm going to try, but if someone has already solved this problem, help would be appreciated.

Thanks,
Mike
mikeshafer
Posts: 49
Joined: Fri Feb 24, 2012 10:45 am

Re: GJK/EPA Question

Post by mikeshafer »

Fixed. Here is the solution:

In the support mapping function, if it's EPA after you get the support vectors from the two convex objects and you get the Minkowski difference, flip the sign on the Minkowski difference if the direction of the search vector is in the direction of the triangle's normal (dot product is greater than zero).

Mike
mikeshafer
Posts: 49
Joined: Fri Feb 24, 2012 10:45 am

Re: GJK/EPA Question

Post by mikeshafer »

So that didn't turn out to be the solution. I don't want to mislead anyone, I'm still looking for a solution.
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: GJK/EPA Question

Post by RandyGaul »

Could you be a bit more explicit with the scenario? Perhaps some screenshots? There's a few too many ambiguities for me to be able to help.
mikeshafer
Posts: 49
Joined: Fri Feb 24, 2012 10:45 am

Re: GJK/EPA Question

Post by mikeshafer »

Ok so here is a picture:

Image

The top case works fine as the center of the capsule is not penetrating the triangle. The bottom case, I want the blue dotted line's distance, but I'm getting the red dotted line from the GJK/EPA algorithm. Obviously it's too much penetration for GJK, so it's handled in EPA.

In EPA, I have a function called u32 MEHEPACollision::FindClosestTriangle(MEHVector3 &outNorm, scalar &outDist). I modified this function to return the triangle most along the triangle normal. Note that this triangle normal I speak of differs from the "Triangle" in FindClosest"Triangle". FindClosestTriangle is working with the convex polytope to eventually get you the penetration distance. The triangle normal I speak of is the triangle in the original Capsule Vs. Triangle pair-wise collision. Remember GJK/EPA works on a pair of shapes and in this case it's a capsule and a triangle. But this method is giving me ghost collisions since in a building complex there are walls facing toward you and away from you and the ones facing away from you (say out in the hallway) trigger a severe penetration.

The reason I need it to detect such extreme penetrations is because it's for the camera and if the player turns the corner the camera will take on a severe penetration. I have it working so far but sadly, I'm only using GJK to test for intersection--I'm not using the collision normal or penetration distance the function is returning. It would be nice if we could somehow modify GJK/EPA to return the penetration distance when one of your two objects is one-sided. Let me know if you have any suggestions.

Mike
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: GJK/EPA Question

Post by RandyGaul »

Ah, usually I see this issue fixed with a height map. Adjacency information between triangles can be calculated during runtime and used to correct poor collision detection results.

In the case of modifying EPA, I'd say that's the wrong way to go about it. What you really need is more of a half-space intersection test, instead of running collision detection against two meshes. One way to do this would be to just treat your triangles as thick triangular prisms. From what I can see: no matter what you'll need to do some additional authoring of your collision detection; EPA is giving you "correct" results, but you're trying to do something that breaks EPA's assumptions.
mikeshafer
Posts: 49
Joined: Fri Feb 24, 2012 10:45 am

Re: GJK/EPA Question

Post by mikeshafer »

Randy,

Thanks for your thoughtful post. I think you're right but I'm too lazy to do anything when I got GJK working so well. In the end I stuck with my alignment modification to EPA--it seems to work fine. In fact the rag doll limbs that use to go through the floor don't go through the floor anymore. Until I see something teleport, I'm going to run it this way. Basically, when you're expanding your polytope, you choose planes that are most along the triangle normal. Looks good so far and for whatever reason, rag doll didn't break. I'm happy. Thanks again Randy.

Mike
janzdott
Posts: 2
Joined: Tue Nov 12, 2013 8:59 pm

Re: GJK/EPA Question

Post by janzdott »

Were you able to get the contact point from EPA? I have implemented EPA. It works great, and gets the penetration depth and normal, but I cannot figure out how to generate a contact point for the life of me :(
Post Reply