As suggested by Dirk, I'm creating this topic to discuss some of the questions I had after reading through his presentation (http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf).

I actually only have one question atm. I haven't seen any mention of caching contacts between frames. If you generate the whole manifold on each frame, how do you find the corresponding contacts from the previous frame? Especially if some contact points are the result of a clipping operation, they might change over time even when converted to local space.

I have a contact for each pair of overlapping shape proxies. The contacts are persistent over frames. When I update the broadphase and detect an overlapping pair I first check if I already created a contact for that pair. Each shape has a list of associated contacts. So I simply search the shorter list. Alternatively you could have a simple hashtable.

Next I create the new manifold. If the new manifold was created from the same features as the old one I match the new points with the old points using the clipping Ids. I don't use any heuristic based on distance or local contact points.

In order for this to work you need relatively stable features. You need to favor one face over the other and face contacts over edge contacts. You can find an example here (b2CollidePolygons): https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2CollidePolygon.cpp

I suggest using combined relative and absolute tolerances and incorporate the edge separation as well:

http://realtimecollisiondetection.net/pubs/Tolerances/

You can find an example of the contact matching here:

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Dynamics/Contacts/b2Contact.cpp

There is also some example lib called Box2D Lite which is even easier to follow. It is part of one of Erin's presentations here (I think in GDC 2006):

http://box2d.org/downloads/

As a side note:

The pair management depends a bit on your broadphase. SAP has natural begin, persist, and end overlap events. When using a dynamic tree things are a bit different. These are really just implementation details. You just need a way to find existing contacts between pairs. Then simply match the new manifold points with the old ones.

We did discuss the contact ID creation at the end of this thread:

http://www.gamedev.net/topic/667499-3d-sat-problem/

HTH,

-Dirk

Oh, and maybe for terminology. There is one contact for each pair of overlapping shape proxies. A contact can have several manifolds. In practice I have a convex contact (sphere, capsule, and hull) which has exactly one maniold and a mesh contact which has up to three. Mesh contacts are bit more involved, so maybe let's keep that for another discussion.

Note that some engines insert bodies/compounds into the broadphase. In that case you would need a mid-phase to dispatch down to the pair level.

If you're using clipping you want to assign some unique values (perhaps based off of topology indices) to each possible clip point. Just make sure that there's a unique ID for each point created as an intersection of features from each shape.

I used Sutherland Hodgman clipping, and for some reason it was really difficult for me to come up with code that would create appropriate IDs. In Box2D Lite (link above in Dirk's first post) there's an example that can be extended to 3D pretty easily. I ended up drawing a lot of pictures/staring at Erin's code until the trick finally appeared to me. Hopefully others won't find it as difficult to figure out as I did.

Yes, I use the feature indices (e.g. plane or edge index) to build ids. I use the half-edge data structure for my hull so this come really naturally. It is really simple and you can use anything that is consistent and creates unique ids. The link I send above discusses essentially the feature pairs for Box2D and Irlan made a nice sketch to illustrate the idea.

The choice has to do with the penetration correction. I found for spheres and capsules that choosing the middle of the surface points gives the most stable contact points. For the hulls you move the contact points onto the reference face for culling, so I kept them there. I think it doesn't make much difference in practice. I try to choose the contact points as coherent as possible and this is what I ended up with over the years - empirically!

The art with contact points is really to find the same points again. E.g. for box vs box you could find up to 8 points. During reduction there are several combinations of four points that would be physically stable, but once you have chosen one you ideally want to find the same combination in the next frame again. You don't want the points to move around too much, because the solver would need to balance different torques every frame (hope that makes sense!) which would give it a hard time to converge considering the small number of iteration we usually use. We need to help as much as we can

Thinking about it, putting the contact points always onto the surface of one shape might be a good choice for games as well. E.g. the normal points from A to B and the contact points are always on the surface of A is consistent and should help gameplay programmers.

The contact stuff has been solved long time ago and I didn't really think about it recently. I agree a more consistent choice might be better!

No, assuming you want to solve such that p1 and p2 become identical, that should work as well.