Erwin Coumans wrote:
Thanks for the suggestion. However, take a circle with more then 4 points. Wouldn't your algorithms only take triangles along the border into account, not the full area?
At each "greedy" incremental step the difference in total area by replacing one point
b with another
b' *is* the difference in sizes of the two 'border' triangles: the existing one
||(b-a)X(c-b)|| and the new candidate
||(b'-a)X(c-b')||. The rest of the area is likely to remain unchanged. I only say "
likely" since it is remotely possible that the new point, if far enough out, will also sweep additional area making s neighboring point
a or
c concave. That will no longer happen once all the points are in fact somewhere on the limits of the convex contact manifold.
Say the contact manifold is shaped like an ellipse with more than four points. Furthermore, when the faces of two bodies are parallel gjk can end up returning any contact point along the edge or in the interior. So over many frames the persistant manifold algorithm is gets a sequence of contacts that is like random points from within this area. You would want the algorithm to efficiently converge to the maximum-area rectangle inscribed within the ellipse. When those less-suitable contact candidates come along (that would reduce area) they are rejected and do not replace the optimal ones (due to the equations proposed).
I didn't explain one detail previously. Instead of doing dotting the cross product with itself to get the magnitude squared (dot(cp,cp)), I take the dot product with the normal of the contact patch. The normal doesn't have to be unit length since we only are doing this for comparison with another dot product and/or with zero. The advantage is you have a signed area. This way all the points end up in ccw order in the array which just makes life easier.
Referring back to your implementation...
if instead of just doing the cross product wrt just one edge on the other side of the contact patch, you could sum up the area (do cross products) for both of the other opposing edges (c,d) and (d,a). Later, if the code was then optimized so that identical terms are dropped from both sides of the comparison equation, then I suspect it would no longer depends on the far point
d and we would both end up with identical code.
Like I said, it was just a minor suggestion. Feel free to take it or ignore it.
On the other topics you mention...
Yes that likely is a good idea to drop points the same way you add them.
I wish I had more time to try more of these things. (i'm not the low-level engine guy)