Separating axis theorem
From Wikipedia, the free encyclopedia
For objects lying in a plane (2-dimensional space), the separating axis theorem states that the projection of two convex shapes onto some line will be separate if and only if they are not intersecting. The line for which the objects have disjoint projections is called the separating axis. An equivalent way of stating the theorem is to say that two convex shapes in the plane are not intersecting if and only if a line can be placed with one shape to one side of the line and the other side. Such a separating line will be perpendicular to the separating axis.
For three-dimensional space, an axis can be found where the projection of two convex shapes can be separated if and only if they are not intersecting. In 3D, lines and planes are duals, and you can thus turn the separating axis theorem for 3D into the separating plane theorem. The general result in n dimensions is called the separating hyperplane theorem. This theory is due to Hermann Minkowski.
A related result is the supporting hyperplane theorem.
[edit] Use in collision detection
The separating axis theorem says that if two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap. This is an important definition, because it suggests an algorithm for testing whether two convex solids intersect or not -- and, in fact, it's heavily used in computational geometry, including computer games. It is also an important definition, because no matter what the dimensionality, the separating axis is always an axis. For example, in 3D, there is still a separating axis. That axis is the dual of a separating plane.
The separating axis theorem can be applied for fast collision detection between polygon meshes. Each face's normal or other feature directions is used as a separating axis, as well as the cross products. Note that this yields possible separating axes, not separating lines/planes.
If the cross products were not used, certain edge-on-edge non-colliding cases would be treated as colliding. For increased efficiency, parallel axes may be calculated as a single axis.
[edit] References
- Golshtein, E. G.; Tretyakov, N.V.; translated by Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley, page 6. ISBN 0471548219.
- Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers, page 19. ISBN 0792398211.
