Multiple contacts with V-Clip
Author
Hi,
I am working on a rigid body simulator and I use V-Clip for collision detection. I am looking for some information/advice from someone who is familiar with this situation.
Unfortunetely I will not attempt to enforce nonpenetration and work with heavy backtracing. However, I use a simple binary time-of-impact search to find which features were closest between two bodies just before penetration was detected but then i continue integration forward from the penetration state and solve contacts/collision by iterating impulses. I always keep track of the latest closest features between two bodies so in case two bodies start a frame in penetration, and I cannot do any time-of-impact search, I simply chose the latest closest features as the contact-features.
The result of this is that by the end of the frame I have a, usually quite acurate, pair of closest features that I use to calculate two collision points and a collision normal. With this data I can succesfully resolve a collision but the problem starts with resting contacts states. The only possible pair of features returned are v-v, e-v, v-f and e-e. e-e and v-f being the most common and important.
Since I can never guarantee non-penetration I need some method to find multiple contact points or multiple close features in order to have bodies resting on each other, V-Clip only gets me one pair of close features. Does anyone have any experience with this? Is there any good extension of v-clip I can do to get multiple close feature or somehow convert to face-face and edge-face states?
I have done some testing succesfully converting a v-f state to e-f and f-f by check angles of the neibouring edges of he vertex to the face. Then from f-f and e-f state I can get accurate multiple contact points. However I dont know if this is a good option or what to do with the edge-edge case...
\\Theo
Author
I realize this question doesn’t really have an easy answer and that open documentation is quite limited with contact determination. However, I know some algorithms, like EPA, that you can extend GJK with in order to get a complete set of contact points after a GJK invocation. Isn’t there some similar algorithm that can be used when v-clip results in a penetrating state?
I have also heard of a technique using a smaller collision mesh which you use for the V-Clip invocations and then add a margin distance to it in order to be able to get good results from V-Clip even if the “real” objects are penetrating. But I haven’t been able to find any good information about this technique or how to generate the smaller mesh; does anyone have any info on this?
I have also heard of a technique using a smaller collision mesh which you use for the V-Clip invocations and then add a margin distance to it in order to be able to get good results from V-Clip even if the “real” objects are penetrating. But I haven’t been able to find any good information about this technique or how to generate the smaller mesh; does anyone have any info on this?
I would also be interested in more information in this area. I am just getting into my own real investigations in collision detection methods and starting to look into both gjk and v-clip. More information on the detection/determination of multiple contact points would certainly be helpful. As well as any more clear information on these techniques and others that may be beneficial to experiment with.
Author
Maybe the topic of this thread is a bit missleading.
I'm really looking for similar algorithms to EPA that are not based on Mikowski sums, but instaid can take advantage of feature based collision detection algorithms like VClip. So its not really about getting multiple contacts (that can be achieved by saving a list of contacts between frames) but more about calculation penetration depth vector. Or other alternatives of getting good contacts points when objekts are intersecting.
There must be some known algorithms or methods for this?
I'm really looking for similar algorithms to EPA that are not based on Mikowski sums, but instaid can take advantage of feature based collision detection algorithms like VClip. So its not really about getting multiple contacts (that can be achieved by saving a list of contacts between frames) but more about calculation penetration depth vector. Or other alternatives of getting good contacts points when objekts are intersecting.
There must be some known algorithms or methods for this?
Finding the contact manifold?
afaik, as long as you have the normal of collision, and you can get the supporting regions of the two objectys along that normal, you can do it feature-based :
1) find support points of both objects along the normal of collision.
2) each support point sets will define either :
. a face
. an edge
. a vertex
3) based on the combination of the two contacting surfaces (vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-face, face-face), you can find the contact pairs on the two surfaces.
edge-vertex, edge-edge, vertex-vertex are trivial cases. The most interesting cases are when you have a edge-face, or a face-face contact. Then a standard 3D clipping solution can work.
edge-face.
----------
for each edge of the clipping polygon, You take planes aligned with that edge and the polygon normal, and clip the contacting edge with those planes iteratively. What you'll be left with will be a smaller, 'clipped' edge.
face-face.
----------
You use one face as the clipping region, the other as the polygon to clip. For each edge of the clipper, you use the plane aligned with that edge and the normal of the clipper polygon, and clip the other polygon iteratively. What you will have remaining will be parts of the polygon inside the volume of the other polygon.
but, you need to know the normal of collision (the mtd, normalised) first.
I have some example somewhere.
afaik, as long as you have the normal of collision, and you can get the supporting regions of the two objectys along that normal, you can do it feature-based :
1) find support points of both objects along the normal of collision.
2) each support point sets will define either :
. a face
. an edge
. a vertex
3) based on the combination of the two contacting surfaces (vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-face, face-face), you can find the contact pairs on the two surfaces.
edge-vertex, edge-edge, vertex-vertex are trivial cases. The most interesting cases are when you have a edge-face, or a face-face contact. Then a standard 3D clipping solution can work.
edge-face.
----------
for each edge of the clipping polygon, You take planes aligned with that edge and the polygon normal, and clip the contacting edge with those planes iteratively. What you'll be left with will be a smaller, 'clipped' edge.
face-face.
----------
You use one face as the clipping region, the other as the polygon to clip. For each edge of the clipper, you use the plane aligned with that edge and the normal of the clipper polygon, and clip the other polygon iteratively. What you will have remaining will be parts of the polygon inside the volume of the other polygon.
but, you need to know the normal of collision (the mtd, normalised) first.
I have some example somewhere.
As for finding the MTD, you could use the SAT directly but it's rather brute force. Apart from the EPA (which I don't like either), you can have a look at the MPR (Minkowski Portal Refinement, there is an article in GPG7, but also discussions on the XenoCollide and Rocket Physics boards.
However the MPR is also an iterative solution similar to the EPA, but simpler.
However the MPR is also an iterative solution similar to the EPA, but simpler.
Author
Thanks for the reply!
Yes, the contact manifold is what i was looking for first. I think I implemented something similar to what you described... Although I dont actually get edge-face or face-face from vclip so I had the problem of trying to convert the other states to these (for example by checking the angle between a a face and the sorrounding edges of a vertex)
This MPR technique sounds very intriguing. I will try to read about it more in detail. However, from what I understand it is still based on the mikowski sum? So I guess it would be better to use GJK collision detection and take advantage of the resulting simplex?
Since I have already implemented V-Clip im courious if there is a technique to get the MTD by somehow taking advantage of the results from V-Clip? Or at least a technique that is independant so I can combine it with my V-Clip which I guess I then only use for collision detection...
Yes, the contact manifold is what i was looking for first. I think I implemented something similar to what you described... Although I dont actually get edge-face or face-face from vclip so I had the problem of trying to convert the other states to these (for example by checking the angle between a a face and the sorrounding edges of a vertex)
This MPR technique sounds very intriguing. I will try to read about it more in detail. However, from what I understand it is still based on the mikowski sum? So I guess it would be better to use GJK collision detection and take advantage of the resulting simplex?
Since I have already implemented V-Clip im courious if there is a technique to get the MTD by somehow taking advantage of the results from V-Clip? Or at least a technique that is independant so I can combine it with my V-Clip which I guess I then only use for collision detection...
Quote:
Yes, the contact manifold is what i was looking for first. I think I implemented something similar to what you described... Although I dont actually get edge-face or face-face from vclip so I had the problem of trying to convert the other states to these (for example by checking the angle between a a face and the sorrounding edges of a vertex).
It shouldn't be too complicated. Even just a list of vertices would work on its own. But if you have a list of faces, edges and vertices, then that can help you.
The problem seem to be that VClip does not return you face-face cases for resting contacts. What you can do, due to the convexity of the object, is to iterate through all the faces, and check to see if you have one that would align with the normal of collision (which you can compute from the different cases returned from VClip). Faces would be basically a list of convex polygons.
Face* foundSupportingFace(const Vector& direction){ for(int i = 0; i < numFaces; i ++) { float delta = face.m_normal.dotProduct(direction); static const float tolerance = cos(1.0f * pi() / 180.0f); // tolerance of one degree deviation. // angle between normal and direction in range [181, 179] degrees if(delta < -(1.0f - tolerance)) return &face; } return NULL;}So now you should have your face-face case to consider, and you can clip face features to get the manifold.
the MPR is like a simplified GJK. Here's the process in 2D. It seems much simpler. and also a lot simpler to get the mtd from it (you dont have to do a polytope expansion).
It seems more straight forward for solving swept tests as well (I kinda have an idea about that).
However, I haven't tried it yet. I'm in the process of writing a couple of examples to showcase the MPR (2D simple point-in polygon test, 2D poly-poly collision, 2D swept test, 3D test).
I'm not sure how solid it is, and if it suffers from some of the drawbacks of GJK.
oh yeah, this too.
http://www.cescg.org/CESCG-2000/PSovis/index.html
[Edited by - oliii on January 21, 2009 11:39:45 AM]
Author
Yes you're right. I think the function you presented is like a simpler, and perhaps better, than what I have done. It's a shame to loop through all faces though :/ I have tried something with only checking faces neibouring the resulting features... however then I need to calculate what these neighbours are (since e.g. a vertex only has edges as neighbours) and im not sure if its worth it. We have also the annoying situations with v-v and v-f which both could actually be e-f (and also f-f). Then there is a edge to "convert into" rather than a face.
I have come across the link you posted before, its good. Although it uses some TOI search to get contact data (or closest features just before collision) and I can not do that unforgunetly. Or I can only do it if the bodies were separated in the last frame. Since i do not enfore non-penetration bodies can be penetrating during several frame, therefore I need some MTD algorithm to get the collision normal and manifold. Rolling back to TOI seems too expensive.
When V-clip detects penetration it, mostly, results with a face and a edge that goes through it. I was trying to think of some algorithm that uses these results and somehow traverses though their neighbours to find the penetration depth vector (or MTD). But nothing like this seem to exist so my V-Clip is not really usefull.
I guess GJK/EPA or MPR is the way to go... Damn, i'll have to scrap my fine V-Clip implementation :(
Have you ever heard of these margin-methods? By having a smaller collision geometri (that could somehow be generated by pushing all faces inwards along the normal, for a certain marginal distance) and then when the real meshes are detected to be colliding I could run V-Clip again but instaid between the smaller meshes. Then I would get relevant data, at least some collision normal and distance which I maybe could could use on the real, big, meshes... I'm not really sure how this would work though or how to chose a margin distance. Something should get strange when the margin is too high. It would make it hard to have flat meshes...
I have come across the link you posted before, its good. Although it uses some TOI search to get contact data (or closest features just before collision) and I can not do that unforgunetly. Or I can only do it if the bodies were separated in the last frame. Since i do not enfore non-penetration bodies can be penetrating during several frame, therefore I need some MTD algorithm to get the collision normal and manifold. Rolling back to TOI seems too expensive.
When V-clip detects penetration it, mostly, results with a face and a edge that goes through it. I was trying to think of some algorithm that uses these results and somehow traverses though their neighbours to find the penetration depth vector (or MTD). But nothing like this seem to exist so my V-Clip is not really usefull.
I guess GJK/EPA or MPR is the way to go... Damn, i'll have to scrap my fine V-Clip implementation :(
Have you ever heard of these margin-methods? By having a smaller collision geometri (that could somehow be generated by pushing all faces inwards along the normal, for a certain marginal distance) and then when the real meshes are detected to be colliding I could run V-Clip again but instaid between the smaller meshes. Then I would get relevant data, at least some collision normal and distance which I maybe could could use on the real, big, meshes... I'm not really sure how this would work though or how to chose a margin distance. Something should get strange when the margin is too high. It would make it hard to have flat meshes...
in case of a shallow intersection, the vertex and face (or edge-edge) give you the MTD directly.
But yeah, VClip seem to be limited and cumbersome when computing contacts, especially when you have a deep intersection.
Also, using connected features to find colliding features is probably better than going through every feature of the object to detect resting edges and faces.
I have never heard of margin methods. But I've heard of offset collision meshes, in the context of doing BSP collision detection (like in Quake3). I don't think that's the same thing though.
So far so good with the MPR. I've got a simple 2D example going, for point-in-polygon test, and a slightly buggy polygon-polygon test, with added MTD calculations.
the MPR seems to be pretty simpleto get the MTD, one thing that bugged me with GJK. Basically, you just run the algorithm to its termination (when you detect the portal reaches the surface of the minkowski sum), and your MTD is just the distance of that plane to the origin.
But yeah, VClip seem to be limited and cumbersome when computing contacts, especially when you have a deep intersection.
Also, using connected features to find colliding features is probably better than going through every feature of the object to detect resting edges and faces.
I have never heard of margin methods. But I've heard of offset collision meshes, in the context of doing BSP collision detection (like in Quake3). I don't think that's the same thing though.
So far so good with the MPR. I've got a simple 2D example going, for point-in-polygon test, and a slightly buggy polygon-polygon test, with added MTD calculations.
the MPR seems to be pretty simpleto get the MTD, one thing that bugged me with GJK. Basically, you just run the algorithm to its termination (when you detect the portal reaches the surface of the minkowski sum), and your MTD is just the distance of that plane to the origin.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
