I have been toying arround a physics engine with SAT collision detection.

Now, the collision detection part, works pretty good, but I am having some issues generating the manifold, and choosing a reference face: parallel faces.

Right now, I am using SAT collision detection with support points, as described by Dirk Gregorius on his GDC talk; but for the next step, is usually choosing the axis of least penetrarion as the collision normal; I found that the selected face is not always the contact face, since a mesh may have parallel faces, that share that same normal.

Since the choosing of a incident face, as far as I can tell is not hindered by this, the simplest solution is to clip the indicent faces with the whole reference collider, but that seems a bit overkill for this situations; and I am a bit stumped by this.

Does anyone know a solution for this kind of problem?

Here is my implementation of the Face to Face collision detection:

inline bool test_face_face_collision(const sColliderMesh &mesh1,
                                     const sColliderMesh &mesh2,
                                     uint32_t *face_collision_index,
                                     float *collision_distance) {
     float largest_distance = -FLT_MAX;
     uint32_t face_index = 0;

     for(uint32_t i = 0; i < mesh1.face_count; i++) {
         sPlane face_plane = mesh1.get_plane_of_face(i);
         sVector3 support_mesh2 = mesh2.get_support(face_plane.normal.invert());

         float distance = face_plane.distance(support_mesh2);
         if (largest_distance < distance) {
             face_index = i;
             largest_distance = distance;
         }
      }

      *face_collision_index = face_index;
      *collision_distance = largest_distance;

      return (largest_distance <= 0.0f);
}

I'm assuming you are colliding convex hulls only. If so, there always exists a face that intersects the collider, so brute-forcing it will work. Calculate the depth of penetration against each of the faces (as prism) and choose the deepest.

It looks like that's what you're doing, except you seem to be doing a brute force check against the normal to filter triangles; some kind of BVH might make that a little more efficient. Or you could sort faces in clusters based on normal major direction, and cull which ones you test that way. Even just culling faces that have normals with the correct dot product sign compared to the separating axis, will cut the number of triangle/triangle tests you run down to (1*1)/(2*2) or 25% of what you currently do.

In my presentation I assume merged coplanar faces! Otherwise you create unstable manifolds. E.g. a simple box with triangle faces would jitter since the solver would go back and forth between two coplanar triangles faces and don't find a stable rest configuration.

Thank you so much for your response!

But I am afaid that that was not the problem that I was having, and is my fault for workind it, pretty bad (nevertheless, I will also include a step to merge complanar faces, since that issue flew over my head!).

What I meant was not only parallel normals, but also inverted, like on the two faces of a cube, the top and bottom sides has a normal on the same, but inverted direction. What I find on some cases, is that the collision detection is choosing the top face as the reference face, when the bottom face is the one that the collision is happening. On both axis the interpenetration is the same, so I was wondering if there is some method for solving these case.

Assume you have two boxes stacked on top of each other. The reference face can come from either the upper or the lower box. This is due to floating point imprecision and very small movements. This can flip every frame and note that not only the normal flips, but also the order of the shapes. E. Catto called this feature flip-flop in one of his presentations iirc. This is a different problem than coplanar faces and becomes mostly an issue for warm-starting when you want to create stable contact ID from feature clipping. You must be careful with edge separations (3D) in these cases though. E.g. a bunch of the edge cross products will also create similar separations as the face separations and you must favor face contact over edge contact until the edge separation is significantly better.

Here is an example how this is done in Box2D. You basically just use a fuzzy compare using some tolerance instead of comparing separations directly:

https://github.com/erincatto/box2d/blob/main/src/collision/b2_collide_polygon.cpp#L144

JsMarq96 said:
What I find on some cases, is that the collision detection is choosing the top face as the reference face, when the bottom face is the one that the collision is happening.

You will note that I suggest that you should use the face normal compared to the separation axis to cull faces early, so you don't have to test impossible triangles. That will also take care of the “opposing faces” problem.

If you define the separting axis as pointing from object A towards object B, then you should only include triangles whose face normal dot axis is positive from object A, and negative from object B.

Thank you all for your responses and sorry for the delayed answer!

I knew about feature flip-flop, but my implementation was naive about it, plus, fixed the issue inverting the axis depending on the choosing of the reference or incident mesh!

Now I need to work a bit on my edge-edge contact point extraction, and I think that it should be enought for a naive SAT implementation.