4
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the reply. I'm still a bit lost. What do you mean by 'the two edges are supporting'? \$\endgroup\$
    – Pris
    Jul 12, 2014 at 16:57
  • \$\begingroup\$ Given a cross product result between two edges n, both edges are supporting if n and -n contribute to supporting points on both polyhedra. If you don't understand support points I recommend re-reading Dirk's lecture. \$\endgroup\$
    – RandyGaul
    Jul 12, 2014 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .