Calculating distance for Gauss Map optimized SAT

Question

There's an optimization method for the separating axis test in 3D that uses Gauss Maps to discard certain redundant axes from the set of axes that need to be tested generated by edge-edge cross products.

A detailed presentation can be found here. Along with some source code.

The presentation also states that using the Gauss Map method lets you compute the distance between the two polyhedra along the separating axis orthogonal to corresponding edges (i.e. ones that the Gauss Map method doesn't discard) in O(1).

This is done by considering the plane formed by the cross product of the two corresponding edges fixed on one edge, and finding the minimum distance from a vertex to the plane on the corresponding edge.

My question is:

• Why isn't the distance found this way in the general case when testing the axis formed from the cross product of two edges (i.e. when not using the Gauss Map optimization)?

Generally the method I see used is projection intervals, or fixing the plane for the separating axis to its corresponding edge or face on one polyhedron, and ensuring all vertices of the other polyhedron fall outside.

Answer 1

When you take two edges on two polyhedra you don't know if they form a face on the Minkowski difference. Only feature pairs that form a face can be a potential axis of separation. Since this information is unknown you must naively test all edges against all edges.

This means a supporting point must be computed for each cross product axis since it is not known if the two edges in question are supporting or not.

Since testing for Voronoi region overlap (aka Gauss Map arc intersection test) will tell you whether or not the two edges are supporting, support points can be directly computed in constant time by computing the closest points between the two segments.