Expanding Polytope Algorithm

[xaein]

I'm doing my best to implement the EPA, but I'm not getting correct results. I was hoping that someone here could verify that what I'm doing is logically sound.

The goal is to expand the polytope, so that, with a degree of certainty, you can find the face from the minkowski sum which is nearest the origin. This is done by finding the face of a GJK termination simplex, which is nearest the origin, and then searching the minkowski sum in the direction of that face for the farthest point, and expand the polytope to contain that point. This is done until you find a repeat face -- which represents that the fact that the polytope tried to expand on that face, and since it couldn't it must be the nearest face to the origin.

Vector4 PhyUtils::EPA(ConvexHull* simpl, const ConvexHull& a, const ConvexHull& b)
{
// Algorithm Summary: Find penetration depth. Find the face which is nearest the origin. Expand the polytope to
// contain that point, and repeat until finding get a repeat edge.
//
// Let F be the nearest feature to the origin
// G = -1
// while prevNearestFeature != nearestFeature
// Expand the polytope on F
// G = F
// F = the nearest feature to the origin, D = distance to point on feature

Vector4 D;
int F = simpl->GetFeatureNearestOrigin(&D);
int G = -1;
while(F != G)
{
ExpandPolytope(simpl, F, a, b);
G = F;
F = simpl->GetFeatureNearestOrigin(&D);
}

return D;
}

If this does sound "correct", then I suppose I can move on to try and debug what I'm doing wrong, rather than wonder if I'm misunderstanding something significant.

Thanks,
David

[Erwin Coumans]

What kind of problems are you facing?

Can you compare your steps with the one in this topic?
http://www.bulletphysics.com/Bullet/php ... f=4&t=2931

Are you making sure to keep the expanding polytope convex?
Thanks,
Erwin

[gino]

In principle, your approach could work for a pair of convex polytopes. However, since the boundary of the configuration space obstacle (Minkowski difference) of the polytopes may contain quadrilaterals it could very well happen that EPA cycles between two (or more) faces. Progressive growth of the expanding polytope is possible as long as new support points are generated, so once a support point is generated that is already in your current polytope you may terminate returning the minimum penetration depth.

Note that this approach only works for polytopes. If you also have quadric shapes in your primitive set then you have to rely on the original termination condition.

Gino