Physics Simulation Forum

 

All times are UTC




Post new topic Reply to topic  [ 17 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Tue Apr 04, 2006 3:00 am 
Offline

Joined: Wed Nov 30, 2005 11:07 am
Posts: 24
Location: China
Hello all

As we know GJK can handle the convex vs convex collision and return two cloest point,but how can GJK handle this situation:a box fall on the plane and the box bottom face is parallel with the plane. If i use GJK to handle this situation then GJk just return one point of box not four vertex which i wanna.Only one point is not useful to physics engine.

How to use GJK handle this collision?

Thanks


Top
 Profile  
 
 Post subject:
PostPosted: Tue Apr 04, 2006 3:30 am 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
GJK will give you one point at a time, and within a few frames, you gather new points. So maintain the old points, and gather new. I'm going to write up some whitepaper about this with more in depth explanation.

You can see the GJK contact points added and removed when you press 'w' and 'c' in this demo (boxes are using GJK collision detection). You can also drag objects with right mouse button.

http://www.continuousphysics.com/ftp/pu ... 2-demo.zip

You can see the C++ implementation details here:
http://www.continuousphysics.com/Bullet ... ource.html

Erwin


Last edited by Erwin Coumans on Thu Jun 29, 2006 11:56 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue Apr 04, 2006 6:52 am 
Offline

Joined: Thu Aug 18, 2005 6:27 pm
Posts: 34
It this one wrong? :?
http://www.mollyrocket.com/forums/viewt ... b87b50d844


Top
 Profile  
 
 Post subject:
PostPosted: Tue Apr 04, 2006 12:56 pm 
Offline

Joined: Tue Jan 17, 2006 6:27 pm
Posts: 8
Erwin, you've explained it before, not in great depth but ok...
Here's the link,
http://www.continuousphysics.com/Bullet ... .php?t=226

For the "at once" method, you can read this thread, see post from John Nagle:
http://groups.google.com/group/comp.gam ... 902ce3fd5d


I've already implemented what John explains in his post, so, if you have any problems, I can help. :)

Bye!


Top
 Profile  
 
 Post subject:
PostPosted: Tue Apr 11, 2006 3:01 am 
Offline

Joined: Wed Nov 30, 2005 11:07 am
Posts: 24
Location: China
Erwin Coumans wrote:
I'm going to write up some whitepaper about this with more in depth explanation.
Erwin

I look forward to your paper.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Apr 11, 2006 9:02 am 
Offline
Physics Researcher

Joined: Mon Jun 27, 2005 9:28 am
Posts: 23
Location: Helmond, Netherlands
Taking the closest features of the last-found simplices (sets of support points) for the two objects tested using GJK gives you a rough approximation of the contact manifold but you can do better, since (a) this simplex is usually not the complete manifold and (b) it is not necessarily a face of the boundary.

The following single-shot method for computing the contact manifold does a better job:

Given a contact normal N and a support mapping A, the contact area can be defined as the set of support points

lim conv{S_A(U) : angle between N and U < alpha}
alpha -> 0

Thus, the contact area is the convex hull of the set of support points found by slightly perturbing the contact normal. You can perturb the contact normal by adding a tiny vector orthogonal to the contact normal. These tiny vectors can lie on a circle or can be generated randomly. For instance, you could generate the vectors by hierarchically slicing the unit circle until for some iterations no new support points are found. The actual contact manifold is the intersection (after projection) of the two convex areas.
This method is somewhat cumbersome, so in many cases Erwin's solution of maintaining the last-found contact in a persistent manifold is often sufficient and a lot cheaper.

Finally, when doing convex vs complex mesh, it is better to use the face normals of the mesh rather than the penetration depth vector between the convex and each face in the mesh as contact normal. This is cheaper, since it does not require a penetration depth computation, and behaves better since objects will always slide along the surface of the mesh rather than bounce of the internal edges of the mesh.

I might someday put this stuff in a paper and add some illustration but for the time being this should get you going.


Gino

PS: Does this forum count as prior art?


Top
 Profile  
 
 Post subject:
PostPosted: Wed Apr 19, 2006 5:25 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
gino wrote:
Taking the closest features of the last-found simplices (sets of support points) for the two objects tested using GJK gives you a rough approximation of the contact manifold but you can do better, since (a) this simplex is usually not the complete manifold and (b) it is not necessarily a face of the boundary.

The following single-shot method for computing the contact manifold does a better job:

Given a contact normal N and a support mapping A, the contact area can be defined as the set of support points

lim conv{S_A(U) : angle between N and U < alpha}
alpha -> 0

Thus, the contact area is the convex hull of the set of support points found by slightly perturbing the contact normal. You can perturb the contact normal by adding a tiny vector orthogonal to the contact normal. These tiny vectors can lie on a circle or can be generated randomly. For instance, you could generate the vectors by hierarchically slicing the unit circle until for some iterations no new support points are found. The actual contact manifold is the intersection (after projection) of the two convex areas.
This method is somewhat cumbersome, so in many cases Erwin's solution of maintaining the last-found contact in a persistent manifold is often sufficient and a lot cheaper.
Gino


There is the contact generation, and contact persistency.

For contact generation, there are sampling methods and intersecting/clipping methods.

Essentially Gino's approach and mine are both sampling methods to generate the contact manifold. Gino just uses a higher sampling rate.
There have been various attempt in generating the 'pertubation' for sampling, using the physics simulation (as I do), or kinematic (as Gino proposes).

However, Gino seems to not take contact persistency into account.
Persistency can be useful in rigidbody dynamics, so the constraint solver can do 'warmstarting'. I've seen distance based methods, or feature based methods to identify persistent contact points.

There is a lot to write about this topic, I hope to get some time to write it up in a paper.

Erwin


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 4:05 am 
Offline

Joined: Fri Aug 12, 2005 3:47 pm
Posts: 117
Location: Newyork, USA
Erwin Coumans wrote:
gino wrote:
Taking the closest features of the last-found simplices (sets of support points) for the two objects tested using GJK gives you a rough approximation of the contact manifold but you can do better, since (a) this simplex is usually not the complete manifold and (b) it is not necessarily a face of the boundary.

The following single-shot method for computing the contact manifold does a better job:

Given a contact normal N and a support mapping A, the contact area can be defined as the set of support points

lim conv{S_A(U) : angle between N and U < alpha}
alpha -> 0

Thus, the contact area is the convex hull of the set of support points found by slightly perturbing the contact normal. You can perturb the contact normal by adding a tiny vector orthogonal to the contact normal. These tiny vectors can lie on a circle or can be generated randomly. For instance, you could generate the vectors by hierarchically slicing the unit circle until for some iterations no new support points are found. The actual contact manifold is the intersection (after projection) of the two convex areas.
This method is somewhat cumbersome, so in many cases Erwin's solution of maintaining the last-found contact in a persistent manifold is often sufficient and a lot cheaper.
Gino


There is the contact generation, and contact persistency.

For contact generation, there are sampling methods and intersecting/clipping methods.

Essentially Gino's approach and mine are both sampling methods to generate the contact manifold. Gino just uses a higher sampling rate.
There have been various attempt in generating the 'pertubation' for sampling, using the physics simulation (as I do), or kinematic (as Gino proposes).

However, Gino seems to not take contact persistency into account.
Persistency can be useful in rigidbody dynamics, so the constraint solver can do 'warmstarting'. I've seen distance based methods, or feature based methods to identify persistent contact points.

There is a lot to write about this topic, I hope to get some time to write it up in a paper.

Erwin


It will be helpful.
Basically you can't have stable simulation by using just infromation of closet feature. We need "close enough" features to prevent and correct penetrations.

Erwin, do you think I can get all pairs of features (pi,qi) where d|pi,qi| < epsilon? Well, that's not really what I need but it's might be an easy way.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 4:47 am 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
ngbinh wrote:
Basically you can't have stable simulation by using just infromation of closet feature. We need "close enough" features to prevent and correct penetrations.

Erwin, do you think I can get all pairs of features (pi,qi) where d|pi,qi| < epsilon? Well, that's not really what I need but it's might be an easy way.


The PersistentManifold approximates the contact set by sampling. Then it reduces the point set to 4 points, maximizing the area and keeping the deepest point. This is really good enough in practice, as you can experience by just running the latest Bullet demos. You can interact with the boxes using the mouse. It uses GJK and described sampling method.

Win32:
http://www.continuousphysics.com/ftp/pu ... dfc2849ad4
Linux:
http://www.continuousphysics.com/ftp/pu ... dfc2849ad4

The proof of the pudding is in the eating :)


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 5:09 am 
Offline

Joined: Fri Aug 12, 2005 3:47 pm
Posts: 117
Location: Newyork, USA
I've checked that already.Impressive!
But PersistentManifold report them when they are already in penetration, right? What I really after now are close enough pairs,i.e prevention not correction. You could see that only use penetration depth is similiar to "chasing your tail".


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 5:13 am 
Offline

Joined: Fri Aug 12, 2005 3:47 pm
Posts: 117
Location: Newyork, USA
And the nice thing about "prevention" method is that it doesn't harm your accuracy if you report redundant pairs(It does hurt performance though but not that much because the LCP solver will quickly find the solution for the constraint enforced by that pairs).


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 5:19 am 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
ngbinh wrote:
I've checked that already.Impressive!
But PersistentManifold report them when they are already in penetration, right?

That is not completely accurate.
PersistentManifold keeps points, even if they are non-penetrating, within an epsilon. For stable stacking this should be enough.

Quote:
What I really after now are close enough pairs,i.e prevention not correction. You could see that only use penetration depth is similiar to "chasing your tail".

As mentioned before, a good contact set is collected by the PersistentManifold, within the positive epsilon distance, not limited to penetrations. If anti-tunneling is what you are after, I would recommend to calculate/estimate the time of impact. But that is a different story.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 5:41 am 
Offline

Joined: Fri Aug 12, 2005 3:47 pm
Posts: 117
Location: Newyork, USA
Thanks.

I'm not particularly after anti-tunelling. Like what I said, our method trying to prevent penetrations not just resolve them. Let me explain more.
Our step:
+ Check for penetrations + penetration candidates
+ Put them in LCP, so the LCP will do:
1) Correct the penetrations
2) Make sure that those candidates won't penetrate ( not 100% because of the linearization of contact surface, with fully implicit geometry I think we could 100% prevent penetration)
+ Solve, update.....

So the key here is finding correct candidates and right now I'm using a naive heuristic: pairs that has distance < epsilon are chosen.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 20, 2006 2:57 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
Gino wrote:
Given a contact normal N and a support mapping A, the contact area can be defined as the set of support points

lim conv{S_A(U) : angle between N and U < alpha}
alpha -> 0

ngbinh wrote:
So the key here is finding correct candidates and right now I'm using a naive heuristic: pairs that has distance < epsilon are chosen.


Usually you don't want this whole set. Too many points are redundant, hurt performance and stability (for some solvers).

Anyhow, this set is build by the PersistentManifold. It keep on adding new points, and updating the old ones. Then there is a reduction step, which reduces the number of contacts to 4.

You can read a bit about reduction in this paper:
http://www.continuousphysics.com/ftp/pu ... draft9.doc

Or another posting with some details here:
https://mollyrocket.com/forums/viewtopi ... light=#760


Top
 Profile  
 
 Post subject:
PostPosted: Tue May 02, 2006 3:57 am 
Offline

Joined: Mon Apr 24, 2006 4:55 pm
Posts: 42
Erwin, Since your webpages, explanations and demo code show how trivially easy all this actually is, i just had to try myself. (only the contact manifold part for now)

minor minor observation and idea...

one thing I noticed in how you are deciding which point to replace:
http://www.continuousphysics.com/Bullet/BulletFull/PersistentManifold_8cpp-source.html

Obviously it works, but i'm not sure i get the jist of the details. 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 figure that the results could be sensitive to the choice of which edge we do the cross product with. Instead, I tried something that should be more "symmetrical" when searching for contact to replace. In the case when i've reached the maximum number of contacts and the next contact is at least epsilon away from any of the current ones we consider replacing. The pseudocode for that is:
Code:
for(j=0;j<count;j++)
{
  float3& vp = contact[j-1];  // next point in contact manifold
  float3& vn = contact[j+1];  // previous point
  float3& vc = contact[j ]; // current point we consider replacing
  float3& v  = impact;  // new point
  float3& n  = normal; 
  if(dot(n,cross(v-vp,vn-v))>dot(n,cross(vc-vp,vn-vc)))
  {
    replace old contact point vc with new impact v
    break;
  }
}

i.e. for each contact take the cross product of the previous and next edges. That's the actual area contribution added by that point. (technically you divide by 2 to get actual triangle area but i'm sure you get the idea.)
The points tend to always end up in a convex ccw order. Furthermore, the approach should let you scale up if you wanted to have more than just 4 contacts.


Anyways, just a suggestion. Perhaps i've over-analysed something that isn't all that important. Or, Perhaps you were already doing things in a particular way in your code for a reason and i simply didn't see what that was.

my 2c


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 17 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 0 guests


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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group