Over the past week I have implemented the EPA algorithm. My implementation is based heavily on the description of the algorithm in Gino's book, so in a sense it's a by-the-book implementation. Here is a link to the source as well as the source for a tool I used to debug my implementation. My EPA algorithm can dump it's state after each step in the algorithm and the tool can graphically display the current convex simplex (see screen shot). I now use this as the default penetration depth solver in my engine with great results.
Because the open source physics/collision detection community appears to be converging on the ZLIB license, The link now contains a ZLIB licensed version of my EPA.
Well, I've been re-writing the code to understand it better. I doubt that case is hit very often. It would be nice to have a test suite that forced each of the initial simplex scenarios to occur.
Do you have any comparisons to share about your EPA vs Bullets or vs SOLID?
I think this is a valuable resource. You might consider wrapping it up in a self contained library. It is missing some structures, like the simplex.
I'm sure the Bullet EPA is good, but it is hard to read and understand.
Erin, I believe it does. But it's been many months since I've looked at it. Could you explain how the line segment case could cause CW triangles?
Erwin and I were discussing EPA this afternoon and he made an excellent point about robustness problems in my initial tetrahedron construction code: I pass in the simplex from the original GJK run. This simplex is built from support points that do not include the margin. This can lead to degeneracies when the origin is on the surface but not inside the simplex. The code in bullet rebuilds the simplex from scratch but uses support points that include the margin, then constructs the initial tetrahedron.
Or more simply,
Mine:
GJK(no-margin) -> EPA
Bullet:
GJK(no-margin) -> GJK(margin) -> EPA
Soon I'm going to get myself reacquainted with this code, fix the bugs and include it in Bullet. Then it should be easy to add testing between the two different EPA implementations.
What Erwin mentions is not so much a bug with your EPA, but just how one might feed in the initial simplex incorrectly.
When the simplex is a line segment, you form a dypyramid by finding 3 support points in directions perpendicular to the line segment (with 120 degrees between each direction). Then you determine which tetrahedron contains the origin and toss the other one away. Then you go on to build the tetrahedron triangles. But this process doesn't seem to consider which tetrahedron was retained. For example, if you drop y[0] by setting y[0]=y[4], then triangle y[0], y[1], y[2] is CW.
Edit: This is probably a false alarm. I think your code doesn't depend on the winding order.
Hmm, I'm a bit confused. Gino's book suggests that we should try to maintain consistent vertex ordering, but I don't know why it matters in the actual code. In particular, see Figure 4.17 on page 156.
Okay, we need consistent ordering so that the sillouette edge is built in a known order. The sillouette edge must be ordered so that we can link the new faces together correctly. This means that the initial simplex must be ordered by swapping vertices as necessary.
Yes, it doesn't matter if the winding is CW or CCW just that it is consistent. I think you are right about the line case producing a CW triangle when y[0] = y[4] not only for 0,1,2 triangle but also the 0,2,3 triangle. Do you see that as well?
Actually, after looking at Figure 4.18 (pg. 159) it appears to me that all triangles are wound CW in both cases of y[0] = y[4] and y[1] = y[4]. This should be fine.
Yeah, I can see that the simplex_size==2 case will produce CW triangles.
How about the cases 3 and 4?
Case 3 seems to be CCW because you are building the normal according to the cross(y1 - y0, y2 - y0) then finding a support y3 in the normal direction and then building a triangle y0-y1-y3. Shouldn't you reduce case 3 to a tetrahedron since the original simplex3 triangle might be on the border of the Minkowski sum?
Case 4 seems to depend on the provided simplex to be a certain winding. Is this handled by outside code? GJK doesn't guarantee any particular winding. Why is there a bad_vertex case? Shouldn't GJK provide a tetrahedron that surrounds the origin? Otherwise the GJK is broken.
How about closest_is_internal condition? This seems to be a requirement.
I looked at the EPA2 provided by Nathanael Presson. It seems to take greater care than the previous version about winding in the initial simplex. Do you guys plan to integrate btGjkEpa2 into Bullet soon?
For case 3 assuming CW winding, I think that the normal will be pointing in the opposite direction than it is in Figure 4.19 (pg. 161) and the resulting triangles will be wound CW.
You raise an interesting point about case 4, I don't think there is any guarantee that the verticies are arranged properly. It does appear to work though, I need to investigate more.
I never used closest_is_internal() because my construct_triangle function will return NULL if that is the case and I quit. I don't know if that is what SOLID does, but I it is working fine for me. I have a vague memory of deciding to do this to make constructing the cap for the silhouette edge easier.
