Single Vs Multiple Contacts on a mesh

[Ally]

Hi,

I’m trying to get my head around the differences between Bullet and SOLID, specifically in the way they handle convex-mesh or mesh-mesh collision.

If I perform a sphere-mesh collision in Bullet I can get back every contacted triangle with a contact normal which is unique to that triangle-sphere collision and ignores the way the triangles are connected. In other words, I can get some quite bizarre contact normals due to a sphere-edge collision even though that edge is actually connected to another triangle and thus the true surface contact normal should really be some combination of the triangle face normals rather than the edges.

SOLID on the other hand only ever returns a single point of contact, but that single contact always appears to be relevant to the true surface rather than picking one specific sphere-triangle collision.

The effect is most pronounced on a vertex, with Bullet I may get a number of contact normals pointing in different directions but in SOLID I get one which doesn’t necessarily relate to any particular triangle.

So my question is how does SOLID do it? Is this something to do with GJK Vs EPA?

Any suggestions, explanations, links greatly appreciated!

[dneckels]

From the source code it looks like Bullet returns the normal as the normalized vector between the two closest points.

For face to vertex, this would be correct, since the line between closest point on the face and vertex must be normal to the face (else it wouldn't be the closest point). Of course, the normal won't relate in any way to the (averaged) normal at the vertex.
For the other non degenerate case, edge to edge, I believe this gives the correct result as well: the line between closest points must be orthogonal to both edges, otherwise it would be possible to find a closer pair. Since the cross product of the edges is normal to both edges, it must be that the normal returned by bullet is the same as the cross product result.

I don't know anything about SOLID (and not that much about bullet, either)...

[Ally]

Thanks for the reply, not quite sure I understand “the two closest points”. The witness points between object and each triangle individually? The closest between two adjacent triangles, what happens if you have more than two triangles?

Please bear with me and I’ll try to explain my confusion more clearly…

Say, we have a flat surface made up of a triangle fan with a vertex in the centre and a sphere moving around. Now the sphere collides with the surface so that the vertex is within the sphere but not centred.

If we perform a triangle-sphere check on each pair then some of the closest points will be within a triangle and the collision normal/pen depth will be the triangle face normal. However, some of the sphere-triangle closest points will be on an edge or vertex and the collision normal/pen depth will be (correctly for that pair) not the face normal even though the surface is flat.

So now we have a number of penetration vectors, some pointing up, others in slightly different directions, what do we do? In this case admittedly we could choose the deepest one but if the sphere was a cube, the deepest contact might push the cube sideways instead of up, likewise if the surface wasn’t flat.

So what now, we can’t average the normals, that wouldn’t result in an up vector, just one, fairly up. This seems like it must be either a very common problem or a massive oversight on my part as if I make a simulation where a box slides along a flat triangulated surface, which seems pretty basic, the box will occasionally get “caught” as now and again it transitions a triangle join and I get an edge contact pushing the box away.

On the other hand SOLID will return just one contact which ‘seems’ to always be correct but getting a box to sit flat on a surface with only one point of contact is a bit tricky.

So that’s my problem, I want the best of both worlds. I want all the points of contact to do my physics with, but I need those contacts to be correct relative to the surface. At the moment I store an edge connection graph and have some logic which merges contacts points together if they are within a tolerance and depending on whether the edge/vertex join is convex or concave pick a new normal. But this is a dirty, dirty hack and can’t be the right way to go about it.

Help!

[dneckels]

I see; it sounds like your question is more about how contact manifold points and their normals are maintained. My response was in regards to the frame per frame closest point (which become the contacts). I'm not sure how Bullet maintains the normals as the objects slide. have to defer to the knowledgable

[Ally]

Thanks for trying,

anyone else want to step up to bat?

[Ally]

Anyone… no?

Okay, my own investigation has got me so far, perhaps someone can answer this simpler question which hopfully requires less detailed an explanation.

Is it true to say that:
1) All fast penetration depth algorithms are based on convex objects and do not generalise to concave polyhedral surfaces?
2) Collision detection of concave polyhedral surfaces is EITHER based on polygon soups and polygon adjacency information is ignored OR based on some from of convex decomposition, surface patches, BSP etc. ?
Yes/No would be helpful, references yet more helpful, explanations even more so.

Cheers,
Ally

[ngbinh]

First of all, I can tell you that you need multiple contacts most of the time for stable simulation.

For non-convex ( the term non-convex is more general than concave) collision detection, most methods treat the non-convex shape as multiple convex parts ( from convex decomposition) . As far as I know, only UNC group (Prof Dinesh Manocha, Ming Lin) has an algorithm that deal with non-convex shape directly. I dont remember the name offhand but google may help.

[Erwin Coumans]

Bullet and SOLID compute the closest points, distance and penetration depth in a similar way using GJK and EPA, although Bullet fixes some issues that SOLID suffers from.
The main difference is that Bullet maintains multiple contact points, for better stability. But this seems to be not the real problem here:

You are suffering from the issue of hitting internal triangle edges: http://code.google.com/p/bullet/issues/detail?id=27

There are 2 things to remove or reduce the problem:

1) For the convexObject sliding along the triangle mesh call convexObject->setContactProcessingThreshold(0.);
Explanation: The Bullet constraint solver adds contacts ahead of time, not just for penetrations (negative distance) but also for small positive distances (using that threshold). This improves stability, but it increases the 'internal triangle edges' problem. So set the threshold to zero to reduce this effect.

2) Non-convex triangle meshes in Bullet are treated as a collection of triangles. You can use a contact callback to adjust the contact normal.
Please check the above issue, there is a callback code that shows how to modify the collision normal as the triangle normal.

If you are still suffering problems after applying both fixes, please get back, either in this forum or on that issue. There are a few more improvements that can be made, if you have connectivity information.
Thanks,
Erwin

[Ally]

Thanks both, really useful.

My main concern was that there is a better/faster way to do what I’m doing but it looks as if that’s not the case, simply at least.

Just in case it’s useful to someone else, I’ll give some detail as to how I solve my problem as it seems to be an unusual case, it’s not brilliant but it works.

It’s not actually a normal physics engine I’m playing with, it’s a haptic rendering engine for which I’ve used Bullet successfully for a few years but have always limited the simulation to well behaved convex decompositions of surfaces and purely convex haptic cursors.
Recently I moved to triangle meshes for deformable surfaces and found the problem above. First I tried, as the post Erwin gave suggests, just setting contact normals to face normals, but that’s unfortunately no good for haptics as you get very obvious discontinuities when you suddenly change from one face to another which aren’t flat.
My work around is helped by the fact that I’m only interested in convex cursor Vs triangle mesh. When I intercept the contact manifold, I check the face normals and contact point to see what I’ve hit. If the contact is on a vertex or edge and that vert/edge is non-convex I assume it is not possible/very unlikely I’ve actually hit a join as it shouldn’t be possible for a rounded edge to hit a non-convex join (though an acute edge/vert could, this is something I still need to sort out). So in this case it is valid to set the contact normal to the face and recomputed the penetration depth for this contact.
On the other hand, if the join is convex it is not valid to just set to the face normal so I store this contact and carry on checking all the other contacts. At the end I group any duplicate contacts, usually a pair of edge contacts or a number sharing the same vertex and group them together. Then I take all the triangles that are attached to a convex join, make a temporary shape out of them and do a convex-convex test to get a single valid normal and pen depth, a sort of convex decomposition on the fly. Then I send all my contacts off to the rendering engine to do its thing.

I’d be very interested if anyone has any useful insights.

Thanks again for your replies,
Ally