Physics Simulation Forum

 Page 2 of 2 [ 17 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Posted: Tue May 02, 2006 5:45 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
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.

Top

 Post subject: Posted: Tue May 02, 2006 5:06 pm

Joined: Mon Apr 24, 2006 4:55 pm
Posts: 42
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)

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 17 posts ] Go to page Previous  1, 2

Who is online

Users browsing this forum: Bing [Bot] and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities