All Topics  
Separating axis theorem

 

 
   Email Print
   Bookmark   Link
 

 

Separating axis theorem
 
 
  Topics Separating axis theorem Topic Home

For objects lying in a plane
Plane (mathematics)

In mathematics, a plane is a curvature surface. Planes can arise as subspaces of some higher dimensional space, as with the walls of a room, or they may enjoy an independent existence in their own right, as in the setting of Euclidean geometry....
 (2-dimensional space), the separating axis theorem states that, given two convex
Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object....
 shapes, there exists a line onto which their projections will be separate if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
 they are not intersecting. A line for which the objects have disjoint projections is called a 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.






Discussion
Ask a question about 'Separating axis theorem'
Start a new discussion about 'Separating axis theorem'
Answer questions from other users
Full Discussion Forum



Encyclopedia


For objects lying in a plane
Plane (mathematics)

In mathematics, a plane is a curvature surface. Planes can arise as subspaces of some higher dimensional space, as with the walls of a room, or they may enjoy an independent existence in their own right, as in the setting of Euclidean geometry....
 (2-dimensional space), the separating axis theorem states that, given two convex
Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object....
 shapes, there exists a line onto which their projections will be separate if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
 they are not intersecting. A line for which the objects have disjoint projections is called a 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 a 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
Euclidean space

Around 300 Before Christ, the Ancient Greece mathematician Euclid undertook a study of relationships among distances and angles, first in a plane and then in space....
 is called the separating hyperplane theorem. This theory is due to Hermann Minkowski
Hermann Minkowski

Hermann Minkowski was a Germans mathematician of Jewish and Poles descent, who created and developed the geometry of numbers and who used geometrical methods to solve difficult problems in number theory, mathematical physics, and the theory of relativity....
.

A related result is the supporting hyperplane theorem.

Uniqueness

Separating axes are not unique, as any line parallel to a separating axis is also a separating axis. Further, if the convex sets are compact, they will be separated by a positive distance on a separating axis, and thus any line whose slope is close enough to the separating axis will also be a separating axis

Separating lines may be unique, if the sets are distance 0 apart (properly, if there are points in each that are arbitrarily close to points in the other) – for instance, if one set is the open left half-plane and the other is the open right half-plane then the y-axis is the only separating line. This can also hold for closed sets (if unbounded), if the sets are

However, for compact sets, separating lines are not unique: non-intersecting compact sets are a positive distance apart, by applying the extreme value theorem
Extreme value theorem

In calculus, the extreme value theorem states that if a real-valued Function f is Continuous function in the closed set and bounded interval [a,b], then f must attain its maximum and minimum value, each at least once....
 to the distance between points. Thus given a separating line between compact sets, a close enough parallel line will also be a separating line: visually, there is wiggle room.

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
Collision detection

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
 between polygon meshes. Each face
Face (geometry)

In geometry, a face of a polyhedron is any of the polygons that make up its boundaries. For example, any of the square s that bound a cube is a face of the cube....
's normal
Surface normal

A surface normal, or simply normal, to a Flatness is a vector which is perpendicular to that surface. A normal to a non-flat surface at a Point P on the surface is a vector perpendicular to the Tangent space to that surface at P....
 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.

External links