EPA

[Erin Catto]

I never used closest_is_internal() because my construct_triangle function will return NULL if that is the case and I quit.

Are you sure? All I see is a determinant check, which is really just a degeneracy check.

I think you need the non-internal triangles because they may be traversed while building the sillouette. This may only come up with complex polytopes.

It seems very tricky to get the correct initial simplex, especially if you have a margin of zero. This can often lead to case 2 and 3 for aligned boxes.

So if we know the orientation of triangles, can't we simplify the origin in tetrahedron test?

I think you need to be more careful about case 2. It is possible that both origin in tetrahedron tests return false when the origin is close to the mid-plane. First we should test the mid-plane, then test the two halves accordingly.

Here's a question (maybe Gino and/or Erwin can chime in). EPA places a lot of importance on enclosing the origin. Can we modify EPA to find the minimum separating axis in both the overlapped and non-overlapped case? Perhaps we can use the signed distance of the origin from each triangle of the embedded polytope. By starting with a tetrahedron, we should be able to avoid local minima in both overlapped and non-overlapped cases. If this is true, we can just initialize EPA in a generic way. Just try to find a tetrahedron inside the CSO, starting from scratch or from some cached features from the previous EPA solution.

[Nathanael]

John,
It will be nice to have a tests suite for gjk/epa in Bullet, something where we can add tests easily, compare accuracy (or failure) again SAT for polytopes of different implementations (epagjk,epagjk2,Solid,and yours), i don't have time to do that right now, but having a rock solid epa for Bullet is worth the pain i think, and could benefit the community at large.
Performances / memory usage are not of primary concern at first, we know the complexity bounds of EPA, that can be addressed later, just keep in mind that you need to bound memory usage somehow, SPU's have limited resources.

Regards, Nat.

[Erwin Coumans]

More testing would be useful, even though I think Nathanael's btGjkEpa is very robust. There is some very basic comparison/test in Bullet/Demos/EPAPenDepthDemo.

But I haven't seen a robust open source 3D SAT test (with contact clipping) yet.... (Pierre?)
It would be nice to have a full working 3D SAT as comparison (and as alternative for polyhedra). There is starting point in Bullet/Extras/SATConvexCollision, but that has some approximation (not all edge-edge cases are performed), and it hasn't been integrated/updated to the latest Bullet source code. Because users seem to be satisfied with EPA, it hasn't been high priority to work on SAT/tests so far.

Are there other open source (preferably Zlib licensed) 3D SAT implementations with contact clipping out there?
Thanks,
Erwin

[Erin Catto]

More testing would be useful, even though I think Nathanael's btGjkEpa is very robust. There is some very basic comparison/test in Bullet/Demos/EPAPenDepthDemo.

How robust is it on polytopes without a margin? Have you tested degenerate configurations of intersecting boxes? I think this is where things start to can fall apart when trying to use EPA as a replacement for SAT. To test the EPA we only need to compare it with brute-force SAT. No optimizations are necessary.

One problem with EPAPenDepthDemo is that it requires a binary file format and provides no mechanism to create new shapes. Also, it runs with a margin so it cannot be checked against SAT numerically.

Here's how I would setup an exhaustive EPA test. All tests would run without margin so that numerical comparison with brute-force SAT is possible.

Test1:
Box-box test including all degenerate configurations. Ensure simplex-1,2,3 cases are hit. Test with 90 and 180 degree rotations. Compare numerical result with brute-force SAT. Run this for millions of configurations.

Test2:
Build random polytopes with 4-10 vertices. Test these in random configurations. Compare numerical result with brute-force SAT. Run this for millions of configurations.

[Nathanael]

How robust is it on polytopes without a margin? Have you tested degenerate configurations of intersecting boxes? I think this is where things start to can fall apart when trying to use EPA as a replacement for SAT. To test the EPA we only need to compare it with brute-force SAT. No optimizations are necessary.

Current EPA implementations work very well in the context it was developed for, (depth penetration, margin), but having empirical proofs that it work all the time, in all situations will be great, and i think thin ellipsoids should be included in the tests.
So brute-force SAT will do just fine for polytopes, but we need a ellipsoid-ellipsoid distance solver as well.

That said i have tested gjkepa/gjkepa2 in Bullet (CCDdemo) with zero margin with great success, so i don't think current implementation will 'fall apart', but its not the same than saying it will work all the time, a tests suite could give us that insurance and then Bullet EPA could become a reference implementation.

So anyone up to the task ?

Nat.

[Erwin Coumans]

How robust is it on polytopes without a margin?

The hybrid method in Bullet doesn't support zero margin, so that case should not happen in practice. As long as you use a margin, GJK+EPA should be robust.

In the past, Pierre pointed out a few issues with GJK that occured even when using a margin (with SOLID and Bullet), so it was not an EPA issue. Those issues should have been resolved for Bullet.

Here's how I would setup an exhaustive EPA test. All tests would run without margin so that numerical comparison with brute-force SAT is possible.

As I mentioned before, GJK+EPA without margin is not supported in Bullet. It would be a nice future improvement to start supporting zero-margin GJK+EPA. Could be a nice research project, but our development is steered by developer feedback/demand, and there other things have higher priorities.

Is it possible to design tests between GJK+EPA and 3D SAT that allow for a margin?