Page 2 of 2

Posted: Tue May 02, 2006 5:45 am
by Erwin Coumans
melax wrote:In particular when taking the cross product with an edge on the other side there would be two possible options, and you end up just hardcoding one of the choices.
I just wanted to find the triangle with the largest area. So for triangle ABC, it would be 0.5 * |AB x BC|. Because I'm only interested in relative area, I don't take the square root and 0.5.

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?

A couple of other idea were brought up: Only add a new point if it makes the area bigger. This results in more stable simulation, especially for certain constraint solvers. GJK typically gives points anywhere on the surface.

Another consideration is to only throw away one point per frame. This adds symmetry of adding only one point per frame. It makes simulation also more stable. I haven't had the chance to add this contribution. Although not perfect, I'm happy with the results, and other areas need more urgent attention.

Posted: Tue May 02, 2006 5:06 pm
by melax
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)