Contact Manifold Generation: A question about GJK

[jiangwei]

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

[Erwin Coumans]

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

[Etherton]

It this one wrong?
http://www.mollyrocket.com/forums/viewt ... b87b50d844

[omicron]

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!

[jiangwei]

I'm going to write up some whitepaper about this with more in depth explanation.
Erwin

I look forward to your paper.

[gino]

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?

[Erwin Coumans]

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

[ngbinh]

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.

[Erwin Coumans]

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

[ngbinh]

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".

[ngbinh]

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).

[Erwin Coumans]

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.

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.

[ngbinh]

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.

[Erwin Coumans]

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

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

[melax]

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 ... ource.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: Select all

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