What to do when cross products are zero with Separating Axis Theorem (SAT)

Question

I have two 3D convex, flat, polygons P0 and P1. I wish to detect if they collide. I will use the separating axis theorem. In this theorem a subset of the test axes are generated from the cross products of pairs edges in P0 and P1

axes = for all 
       | 0 <= n < N ; N is the count of edges on P0
       | 0 <= m < M ; M is the count of edges on P1
       Vector3.Cross(P0.Edge[n].Vector,P1.Edge[m].Vector);

However what is missing in all descriptions of the SAT I have found is what to do when the cross product of the two generating vectors is zero.

I'm of two minds. I can either

Discard this axis from the test set
Generate a random axis in the plane normal to the two edge vectors

Or perhaps there is another correct way to handle this problem.

samgak samgak · Accepted Answer · 2017-06-23T09:29:46

You can safely discard it.

The reason is this: If the cross product is zero, it means the two edges are parallel. If the two edges are parallel, then the 4 faces that are adjacent to the two edges can be projected onto 2 dimensions using the vector of the two parallel edges as your Z, and collapsing this dimension: faces become edges, edges become vertices. You can picture these 4 faces as the edges of a polygon that has been extruded along the vector. In the 2D version of the separating axis theorem you only need to consider edges, not pairs of vertices.

So if there is a separating plane that intersects either of these two parallel edges, one of the adjacent faces will also be a separating plane, and these faces are considered separately in the algorithm. The algorithm only needs to find one separating axis, so the faces will take care of it.

You can visualize this fairly easily. Picture 2 non-intersecting convex figures with 2 parallel edges held close to each other. It's fairly easy to see that one of the 4 adjacent faces always forms a separating plane, and that this isn't the case if you rotate the figures so that the edges are no longer parallel.

What to do when cross products are zero with Separating Axis Theorem (SAT)

1 Answers