So I have a convex hull that has vertices. For collision resolution I need to get the contact points, however I do not know how to figure out all face “combinations” from a bunch of vec3s (for example for a cube it'd be 6 x 4 sets of points).

I know how to find a face from a normal, so I could run EPA, which gives me a contact normal, and from that I can derive the corresponding face. This, however (on top of being slow and kinda dumb) only gives me the collision face, not the adjascent faces, which I need to later use for clipping.

So the final question is: how do I define sets of points that each correspond to a face on a convex hull?

You pretty much need to use a convex hull algorithm to find the triangles again. EPA is basically just a convex hull algorithm in disguise (Quickhull).

If you know the hulls are intersecting (e.g. by using GJK), you can feed the GJK simplex tetrahedron into EPA, which then expands the simplex into a convex hull approximating the minkowski difference of the hulls, at least in the direction of the minkowski origin. EPA can output the closest triangle to the minkowski origin. Then, you can map this triangle (in minkowski difference space) to the triangles on each convex hull (I do this by the storing point on A and B along with A-B). These two triangles approximate the contact between the hulls.

Project the origin onto the minkowski triangle's plane, compute barycentric coordinates, then use barycentric coordinates to find the contact points on A and B (using the triangleA and triangleB vertices). The contact normal is the normal of the closest triangle.

This works well enough, assuming you need only 1 contact point per frame, and works without clipping or explicit knowledge of triangles (it even works on spheres, capsules, cylinders, etc. if you define an appropriate error threshold for EPA). Using a contact manifold cache, you can add 1 contact per frame to quickly build the manifold needed for stable stacking.

First of all, thanks for the answer.

I had the method you described implemented, however I didn't really understand how to get all contact points from this algorithm. I read you need to “pertube” the object every frame to get a new point, but I'm not sure how to do that in a way that'd get me a new (and correct) point every frame. That's why I switched to SAT.

Is running the collision resolution algorithm on that one point counts as perturbing? If not could you elaborate on how it works please? I've tried figuring this method out for a long time but never quite understood this part.

dorcsyful said:
Is running the collision resolution algorithm on that one point counts as perturbing? If not could you elaborate on how it works please?

Yes, the collision response+gravity should cause the object to be perturbed a little bit on each frame, such that the contact point changes.

You can build a contact manifold using this process whenever a new contact is found:

1. Transform new contact into current local space of each object.

2. If the new contact is within a tolerance distance from an existing contact, then the existing contact is updated with the new collision point/normal and nothing else is done.

3. If not, then add the new collision point to the manifold if the manifold is not too big (e.g. no more than 4 points).

4. If there are already the maximum number of points, then discard one of the manifold points and replace it with the new point. You should choose the discarded point in order to maximize the area of the polygon/triangle defined by the remaining points (this is important for stacking).

The main downside of doing it this way (iteratively building contact manifold) versus using SAT and clipping is that there are several frames until the object stabilizes. This is not that noticeable in most cases. Some people do both, using SAT+clipping to build a full manifold on the first frame of collision, then iteratively update the manifold after that.

Wow, that cleared up a lot of things for me. I think I'll be able to write it now, thank you.