An algorithm idea for contact point generation

[goruka]

I was struggling with generating the contact points between convex polyhedra. I looked at the way Bullet works, with the margins but the approach seens really complex to me. So I came up with something, but i'm not sure how well it would work...

The idea is, after you find the separation axis and normal, depending wether your separation is A->B or B->A, say you want to separate B from A..

Basic Form:

1) Start by finding the support vertex for B, any is okay, no matter if there is a quad, tri, edge, etc as support
2) With that vertex, and the separation normal, create a very, very large square polygon of 4 points, (much larger than any object can be), which is perpendicular to the contact normal
3) Now, go and clip the large polygon by all planes of A and B (except those parallel or almost parallel to the polygon). Clipping a polygon by a set of planes is a very quick operation.
5) Points of resulting polygon should be the contact points.

Optimization:

(this should help a lot for large polygons)

1) Find the supports for B and A, but also retrieve the information of planes asociated with that support, which can be somehow cached if you are storing points/planes , or compued if storing polygons.
2) Create the large polygon
3) Clip it by the cached planes.

What do you think? I've seen similar approaches which create planes directly from the supports, and then make one support clip the other, but that needs the collision to retrieve a _lot_ more information about the supports, such as if they are edges, tris, etc. By clipping an existing large polygon, the implementation should be a lot easier I think..

Well Cheers!

[Erwin Coumans]

One shot contact set generation using clipping works fine, but it only handles polyhedra. One example of such clipping in combination with Bullet can be found in Jan Benders IBDS library (see attached file for the actual clipping implementation).

The reason why Bullet doesn't perform polyhedral contact clipping in general, is because Bullet is designed to handle non-polyhedral (non-tesselated) shapes like implicit cylinders, cones and so on. We can still add such clipping method as special case. Other methods include pertubing/rotating the objects around the separating vector to collect multiple points from scratch, as discussed before on this forum (don't have a link handy).

Thanks,
Erwin