FANDOM


IntroductionEdit

The method of separating axes is a simple and often powerful tool for determining whether two convex sets intersect. The method is generally discussed in the context of convex polyhedra, although generalizations can be made for parametric and implicit surfaces with convex interior. Besides its simplicity, an attractive aspect of the method is its tendency to simplify dramatically when the type of objects is restricted; for instance, the separating axes test between a box and a plane reduces to just two dot products. While more efficient algorithms can be found in the case of general convex polyhedra, in specific cases such as boxes, triangles, and other simple shapes, adaptations of this algorithm are often very efficient.

The exposition is divided into two parts: the theoretical background and foundation (the Background and Separating Axes sections), and the implementation (the Implementation and Case Studies sections). The former can be skipped by anyone only interested in the implementation specifics.

BackgroundEdit

Let$ B_1 $ and $ B_2 $ be two non-intersecting convex objects. Then there exists a line $ L $ such that the projections of $ B_1 $ and $ B_2 $ onto $ L $ are disjoint. Proof: let $ x_1 $ and $ x_2 $ be the closest points on the two objects, with $ x_1 \in B_1 $ and $ x_2 \in B_2 $ . Let $ L $ be the line through the two points. Consider the planes $ P_1 $ and $ P_2 $ , perpendicular to $ L $ , and passing through $ x_1 $ and $ x_2 $ respectively (if dealing with objects in 2d, replace planes with lines). Let the normals of the two planes point toward each other along $ L $ . Since $ x_1 $ is the closest point to $ x_2 $ and vice versa, the planes are tangent to $ B_1 $ and $ B_2 $ respectively. By convexity, this means that no point of $ B_1 $ is in front of $ P_1 $ , and no point of $ B_2 $ is in front of $ P_2 $ . Therefore, the projection of $ B_1 $ and $ B_2 $ onto $ L $ contains no points between the projections of $ x_1 $ and $ x_2 $ , which concludes the proof.

Similarly, it's easy to see that if $ B_1 $ and $ B_2 $ intersect, then no line $ L $ exists; for a sketch of a proof of this, suppose that $ L $ does exist, take the interval along $ L $ on which the projections are disjoint, and construct a plane through its midpoint, with the normal along $ L $ . Then the two objects are on opposite sides of the plane, contradicting the assumption that they were intersecting.

This is not terribly useful yet; we've shown that a separating axis $ L $ exists if and only if the two objects do not intersect, and we've shown a means of finding such a line -- but finding the points $ x_1 $ and $ x_2 $ is a different problem (see Lin-Canny, for instance). The next section narrows down the number of lines we need to consider.


Separating AxesEdit

We discuss the method for triangle meshes in 3d, although the approach here can be readily generalized to polyhedra with arbitrary faces.

It's easy to see that the translation of any separating axis is a separating axis itself; therefore, we only need to consider lines through the origin. Given two triangle meshes, we can begin by attempting to enumerate the potential separating axes. In the previous section, we alluded to our choice of $ L $ as a line that is perpendicular to the tangent planes at $ x_1 $ and $ x_2 $ . This arose from the definition of $ x_1 $ and $ x_2 $ as the closest points between $ B_1 $ and $ B_2 $ , since the gradient of distance to $ x_1 $ is, by definition, perpendicular to the tangent plane at $ x_1 $ . At this point, we discard the idea of finding the closest two points, but keep the idea of finding lines that are perpendicular to tangent planes. This brings up a problem with triangle meshes: the tangents are discontinuous at vertices and edges, and thus not well-defined. Keeping this in mind, we first start with the tangents that are well-defined: that is, triangle planes. Since we want to pick lines $ L $ that are perpendicular to tangent planes, this gives us triangle normals as one set of directions for potential separating axes.

This leaves out edges -- and, by extension, vertices. To visualize why it is necessary to consider edges, take two cubes, pick an edge from each, and align the midpoints of the two edges in such a way as to make the edges reside in the same plane, and form a 90 degree angle to each other. The cubes are disjoint, but the face normals fail to provide a separating axis. Intuitively, we will want to consider pairs of edges, one from $ B_1 $ , and the other from $ B_2 $ , and come up with a function of the edge vectors that will return a separating axis whenever a separating axis exists, and is perpendicular to tangent planes at both edges.