Separating Axis Theorem

Description

The separating axis theorem is a technique used to test if two convex polygons are intersecting. It states that if a line can be drawn between two convex shapes, then they are not colliding. This line is called the separating axis. (AJ Piergiovanni, 2010).

Simulation

The simulation consists of a car that the user can control (from now on "the player") using the directional keys and other static cars.

The player will have two bounding boxes, one is an AABB (axis aligned bounding box, drawn in the simulation in green) (Jeff Lander, 2000) which doesn't rotate and is big enough to enclose the player even if this one has rotated 180 degrees. It is used for the broad phase of the collision system.

The other one is an OBB (oriented bounding box, drawn in the simulation in red) that rotates with the player, it just enclose the mesh and is used in the narrow phase, meaning that it will be checking for intersection only if the AABBs are colliding.

In the demonstration, you can drive the car around, when you "hit" any other car (OBBs of both cars are touching) your health bar will decrement.

The separating axis theorem is an algorithm that is used in collision detection that determine if the two shapes are intersecting (Raigan Burns and Mare Sheppard, 2011). As shown in the simulation this algorithm give us more precision, as the bounding box is just the size of the mesh, and rotates with the player.

We are using OBBs in 3D, so each box will have 8 vertices, we need a center position and the extents (distance from center to each axis edge) of the box. With these two variables we can find out all of the 8 vertices. We are also using a matrix that represents the rotation of the box, we pass this matrix when creating the object then we multiply each vertex with this matrix.

Implementation of the algorithm

To check if the OBBs are intersecting we need to do the 3 separating axes for each box, but also we have to test the separating axes between the edges of the boxes.

To find out the separating axes between two edges we use the cross product.

We would have to find out the axis between each edge with all the other ones of the other box but as we can see there are only three unique edge directions for each box, the rest can be ignored because it will result in the same vector anyway, so 3x3=9 different separating axes that we need to calculate using cross product.

In total there are 6 face normals axes and 9 cross product axes = 15.

To find out the face normals separating axes of the boxes we subtract one of the vertices with the other one on the same axis.

For example, to get the X axis of this object we could do it by subtracting point 2 – 1, 1 – 2, 3 – 4 or 4 – 3. An example to get the Z axis would be 8 – 4. This will give us a vector, we are only interested on the direction so we normalize it.

Now we need to project each of the 8 vertices of the box onto the separating axis, we only keep the min and max, these two will give us an extent. We calculate the extent of the other box and check if they are colliding.

This is an example in 2D but it shows the idea, it is basically the same in 3D.

We subtract point 1 and 2 of B1 and we get a vector which is going to be 1 of the axis, the direction is shown in red.

Then we project each of the vertex on this axis using the dot product (blue lines), note that for B1 the projections of vertices 1 and 3, and 2 and 4 are equal, in box B2 we discard the projections of vertices 2 and 3 because we only need the most outer values.

In this example there is a bit of the lines touching (shown in green) meaning that they are intersecting on this axis.

If they are intersecting we need to keep testing, let's test now the axis given by point 2 – 1 of B2.

In this test, the projections are not intersecting.

Once we find a test that doesn't return an intersection, we stop testing the rest of the axes, because they can't possibly be colliding.

If all the tests are positive then the boxes are colliding. In this 2D example there are 4 axes to test, in 3D the idea is the same but we have to do more tests, 15 in total.

If all the 6 face normals intersection tests (in 3D) resulted in collisions then we keep on checking the cross product axes. We need to get the cross product axes between the 3 different face normals.

In this example the edges chosen are shown in yellow and the cross product between them is shown in blue, this will be the axis where we are going to test if the extents overlaps.

Another example with different edges:

There is a problem with this algorithm, in my demo both OBBs Y directions are the same (0, 1, 0) so if we do the cross product between them we will get a (0, 0, 0) axis. We can solve this problem by getting a vector between the same two points of both boxes, and get the cross product between one of the Y directions and this resulting vector. We check first and do this only if the axis we get is (0, 0, 0).

There is also another problem with the solution itself, if both points are exactly in the same position, the difference between them would be again (0, 0, 0). This is highly unlikely as we are using floats but if it happen, we can say for certain that the OBBs are intersecting.

We do the tests for the 9 different scenarios. If in any of them the extents don't overlap we stop, if all of them overlap (including the first 6 face normals axes) then we conclude that they are colliding.

The results can be seen on the demo with the "Health bar" that was implemented on the top left corner. The health bar decreases only when the OBB(in red) is colliding, but not when the AABB(in green).