I wasn't finding a separating axis at all . Here's the solution:

if ( !TestFaces(_psiShape0, _psiShape1) ) {
	return false;
}
if ( !TestFaces( _psiShape1, _psiShape0 ) ) {
	return false;
}
if ( !TestEdges( _psiShape0, _psiShape1 ) ) {
	return false;
}
return true;

You also want to check for parallel edges in the edge test. A random normal can generate a false separation or penetration.

E.g. you could use: |e1 x e2| = |e1| * |e2| * sin( alpha ) *and* sin( alpha ) ~= alpha for alpha << 1

You also want to check for parallel edges in the edge test. A random normal can generate a false separation or penetration.

E.g. you could use: |e1 x e2| = |e1| * |e2| * sin( alpha ) *and* sin( alpha ) ~= alpha for alpha << 1

Thanks for pointing that out.

I'm skipping the edge-edge test if the cross product between them is small than 0.00001f.

Now (little off-topic), I'm facing with the problem of detecting the side planes of the reference face. The problem is that I'm not using an good structure (such the half-edge) to get the connected face planes.

The incident face is just the face of the second object that is most on the negative direction of the reference face right?

Do you have any recommendation?

I'm skipping the edge-edge test if the cross product between them is small than 0.00001f.

If you don't normalize the edge vectors you need to take their length into account. Otherwise this would just be an absolute tolerance. Here is a good discussion how to use relative and absolute tolerances together: http://realtimecollisiondetection.net/pubs/Tolerances/

Now (little off-topic), I'm facing with the problem of detecting the side planes of the reference face.

You don't clip against the neighboring planes. For every edge of the reference face you build a 'side' plane with the reference face normal. E.g. say you have a plane class which takes a normal and point on the plane:

// Build plane (v are the vertices and n is the normal of the reference face)

RnPlane ClipPlane( RnCross( v[ 2 ] - v[ 1 ], n ), v[ 1 ] );

ClipPlane.Normalize();

// Clip (e.g. using Sutherland-Hodgeman)

aPolyhedron.Clip( ClipPlane );

The incident face is just the face of the second object that is most on the negative direction of the reference face right?

Yes, essentially the most anti-parallel face! In practice just the face with the smallest (negative) dot product with the reference face normal.

Do you have any recommendation?

Did you see my presentations on the SAT? You can have a look at my 2013 and 2015 presentations here:

http://www.valvesoftware.com/company/publications.html

Oh, I see. However, I'm confused about the vertices connections. For example, I've a working Sutherland-Hodgman clipping, but it assumes that the vertices are wind ordered in order to get correct edges connections (A to B, A to C, etc.). Another example is that if the edges are not correctly ordered, the side planes creation won't generate correct planes (which I've checked).

For testing purposes, I've manually created an OBB which the edges orders are CCW. In the picture below, the edges are 0-3, 3-2, etc.



Nice GDC slides, BTW.

You mean A to B, B to C, C to D and then X to A I assume. Yes, that is correct, but all you need is an integer array for the edges and then store an offset into that array per face. At the first index you store the number of vertices for that face and the following entries contain the vertex indices for that face. In your example above the top face followed by the front face would be indexed like this { 4, 1, 2, 6, 5, 4, 0, 3, 2, 1, ... }

Then in code you have an array of face planes and a parallel array of offsets into the topology list. In code then this could look something like this:

for ( all faces i )
{
    int offset = mTopologyOffsets[ i ];

    int vertexCount = mFaceTopology[ offset ];
    for ( all vertices k = 1 as long as k <= vertexCount )
    {
        int vertexIndex = mFaces[ offset + k ]
        Vector3 vertex = mFaceTopology[ vertexIndex ];
    }

} 

This is easy and can get you going for a simple box and convex polyhedra.

- You compute the vertices, local face planes and topology during pre-processing. You then compute the edge cross products at runtime.

- Edges are just indices into the vertex array.

HTH, I am not sure if I understand what the question is.

Quickhull and HE are indeed a very good solution for this problem. But the one I showed here is fine as well and easy to construct for e.g. boxes. The half-edge structure becomes really useful if you start pruning edge pairs that don't build a Minkowski face. But this is an optimization and I would handle this at the end when everything is working correctly.