Contact Manifold Generation: A question about GJK
Contact Manifold Generation: A question about GJK
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
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
 Site Admin
 Posts: 4073
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
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 ... 2demo.zip
You can see the C++ implementation details here:
http://www.continuousphysics.com/Bullet ... ource.html
Erwin
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 ... 2demo.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.
It this one wrong?
http://www.mollyrocket.com/forums/viewt ... b87b50d844
http://www.mollyrocket.com/forums/viewt ... b87b50d844
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!
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!

 Physics Researcher
 Posts: 23
 Joined: Mon Jun 27, 2005 9:28 am
 Location: Helmond, Netherlands
 Contact:
Taking the closest features of the lastfound 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 singleshot 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 lastfound 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?
The following singleshot 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 lastfound 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
 Site Admin
 Posts: 4073
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
There is the contact generation, and contact persistency.gino wrote:Taking the closest features of the lastfound 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 singleshot 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 lastfound contact in a persistent manifold is often sufficient and a lot cheaper.
Gino
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.Erwin Coumans wrote:There is the contact generation, and contact persistency.gino wrote:Taking the closest features of the lastfound 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 singleshot 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 lastfound contact in a persistent manifold is often sufficient and a lot cheaper.
Gino
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
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 dpi,qi < epsilon? Well, that's not really what I need but it's might be an easy way.
 Erwin Coumans
 Site Admin
 Posts: 4073
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
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.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 dpi,qi < epsilon? Well, that's not really what I need but it's might be an easy way.
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
 Erwin Coumans
 Site Admin
 Posts: 4073
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
That is not completely accurate.ngbinh wrote:I've checked that already.Impressive!
But PersistentManifold report them when they are already in penetration, right?
PersistentManifold keeps points, even if they are nonpenetrating, within an epsilon. For stable stacking this should be enough.
As mentioned before, a good contact set is collected by the PersistentManifold, within the positive epsilon distance, not limited to penetrations. If antitunneling is what you are after, I would recommend to calculate/estimate the time of impact. But that is a different story.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".
Thanks.
I'm not particularly after antitunelling. 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.
I'm not particularly after antitunelling. 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
 Site Admin
 Posts: 4073
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
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
Usually you don't want this whole set. Too many points are redundant, hurt performance and stability (for some solvers).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.
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
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:
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 overanalysed 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
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[j1]; // 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(vvp,vnv))>dot(n,cross(vcvp,vnvc)))
{
replace old contact point vc with new impact v
break;
}
}
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 overanalysed 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