User login

Separation of Axis

Introduction

Separation of Axis is an algorithm used for collision detection in some physics engines. The algorithm is very straightforward, and easy to understand geometrically. It also incurs a high computational cost $ O(mn) $, where $ m $ and $ n $ are the number of faces for each polygon, so it is best to perform this test only when absolutely necessary. Most physics engines have a few phases of collision detection. These phases might include some kind of spatial partitioning like quad-trees in 2-dimensions or oct-trees in 3-dimensions, or cheap bounding box or bounding sphere checks.

 

The Basics

If you can draw a line between two convex polygons in 2-dimensions without that line intersecting one of the polygons, then they don't intersect. If no such line exists, then they do intersect. The image below shows an example of a non-intersecting polygon pair. The dotted line is the separating line and the green line is the separating axis

The Algorithm

For two convex polygons, first choose a face. In the diagram below each $ \vec{x} $ is a vertex. The superscript identifies the shape, and the subscript is the vertex. So let's choose $ \vec{x}^1_2 - \vec{x}^1_1 $. The separating axis, $ \vec{p} $, is the perpendicular of the face. Once we have our separating axis, we project each vertex of both polygons onto that separating axis. Notice that since $ \vec{x}^1_2 $ and $ \vec{x}^1_1 $ are perpendicular to the separating axis that we only need to choose one of those vertices to project. The bounds of each shape's projections form what are called projection intervals shown in red. The idea is that if these intervals do not overlap, then we know that these two polygons do not intersect. If, on the other hand, we iterate through each face of each polygon and perform this test and find that each and every set of projection interval overlap, then we know that these two polygons intersect. So back to the algorithm. For each vertex compute the length of the projection along the separating axis

$ d=|proj_p(\vec{x})|=\hat{p}\cdot \vec{x} $

where $ \hat{p} $ is the unit vector of $ \vec{p} $. So $ d $ is the distance along $ \vec{p} $ to $ proj_p(\vec{x}) $. Using this distance is convenient because all we care about is whether or not these intervals overlap. For each shape, the minimum, $ d_{min} $, and maximum, $ d_{max} $, projection distances represent its projection interval. The intervals overlap if $ d^2_{min}<d^1_{max} $ and $ d^1_{min}<d^2_{max} $. If they don't overlap, then we can exit the immediately because they don't intersect. If, on the other hand, each set of projection intervals overlap for each separating axis of both polygons, then there is a collision.

One thing I really like about Separation of Axis is that it provides a cheat to calculate the point of contact given that two polygons are intersecting. All you have to do is find the axis with the least interval overlap, shown in white in the figure below. Then just project the vertex of the shape that does not own that separating axis, onto the face that created that separating axis. So, in the figure below, the point of contact becomes

$ \vec{k}_{contact}=\vec{x}^2_3+\hat{p}^1_{12}(d^1_{max} - d^2_{min}) $

Interactive Demo

Try playing around with the demo below to get a feel for the geometry. The color coding is the same as in the figures above. Just follow the direction in the right hand column.

Separation of Axis Visualizer

Get Adobe Flash player