# VB:Tutorials:Building A Physics Engine:Basic Intersection Detection

Tutorial by Nicholas Gorski [GMan]

This article will discuss the basics of the Separating Axis Theorem. It is used for Intersection tests.

## Contents

## The Separating Axis Theorem

The Separating Axis Theorem is the idea that if you can put a line in between two convex polygons, they are not colliding. Pretty obvious, but you may have not actually thought about it (I sure didn't). Of course, you're probably thinking: "Well, buddy, there's an infinite number of lines I could test for!" True, but luckily there are *n* specific lines we need to check for, where *n* is the sum of the number of sides in each polygon.
```
Two squares [4 sides each]: 8 lines
1 Square, 1 triangle [4 sides and 3 sides]: 7 lines
Two Triangles [3 sides each]: 6 lines
100-sided and 570-sided polygons [100 sides and 570 sides]: 670
```

Okay, so if the number of lines we need to test is dependent on the number of sides in the polygons, that means only one thing...the lines we test for *are* the sides of the polygon.

//Reaver330 NB: This tut demonstrates the SAT in 2D only, to extrapolate to 3D check out the following link; [1]. Essentially the real reason Im making this edit is because in 3D the edge intersection tests require cross products as well as the expected polytope face dot products. Which totally messed up my brain. (not a hard thing to do admittedly.) //Reaver330

## Testing polygons against lines

Well, how is that useful? Try this: Imagine you have a line and a box. Now smash the box against the line. What do you get? Something like this:

See how the box was smashed into the line? Now imagine with two shapes:

Now see how the 'smashed' lines are overlapping? Just like how they were overlapping when not smashed...this can be applied in code. What this 'smashing' is called is `projecting`. Because we 'projected' the shapes onto the line.

Well, now we are getting somewhere.

But there is one thing I have not yet said...that is about the actual checking for intersections. As you can see from the samples bove, it only took one line to determine if they were colliding. However, imagine the triangle had been outside and behind the box (next to the 'A'). Projecting onto that line would have said "Yes, they are overlapping". And that is true! To that line only, however. If we were to test for another line, say, a line above the box, they would **not** be overlapping.

So when checking for intersections, we are looking for the situation when they are **NOT** touching, then we know they are not intersecting. Only when all the projected lines show intersection are the shapes intersecting.

Now, the axis itself is not simply the side of the polygon. It is the `normal` of it. The `normal` of a line is just the line perpendicular to it. Like this:

The `normal` of *A* is *B*. It can be defined in math too. If the slope of a line is:

Then the `normal` of it is:

### Review

What are the key concept's in this section?

- To determine if two polygons are intersecting, project their vertices onto a line. If the resulting lines intersect, the shapes may intersect.
- The lines to project onto are the
`normals`to the sides. - The normal of a line is the line perpendicular to it.
- Even though the projection may show the shapes intersect, they are intesecting if and only if
**all**the projections return true.

## Mathematics

So, what's the math behind this magic concept? Assuming you read about vectors (see Introduction), you know that to project one vector onto another you use this:

Okay, so applying the Theorem, is a vertex of the polygon and is the axis we are 'smashing' (testing) against. Well, let's say that when creating and storing the axis, we normalized it. Now . The new formula is:

Now, ignore the dot product section for a moment and you see this:

We know this is normalizing. When you project, your values become distorted, and normalizing puts them back into the proper range. Because this is purely mathematical, we do not need any graphical corrections. Take that out and our final formula becomes:

Look familiar? It's the Dot Product.

Since we are projecting a point onto a line, we will get one scalar value (distance along the line). Now, to determine if two 1D lines intersect (i.e. a line on the 'number line'), you need two numbers:

|-0-1-2-3-4-5-6-7-8-9-| *-----* *-----* 1 2

Here we see lines 1 and 2. 1 spans from zero to three, and 2 from five to eight. For line 1, zero could be considered the **minimum** number, and three the **maximum**. For line 2, five would be the **minimum** and eight would be the **maximum**.

Now that we have a way of determining where these lines are (minimum and maximum), we need a way to find them.

When you project multiple vertices, you will get multiple values. Most of these (in fact, all but 2) will be useless. Why? Take a look:

|-0-1-2-3-4-5-6-7-8-9-| *----**---*--**---*

You can see all the points (asterisks) speckled throughout the line. However, we only need the two endpoints. So we can throw away everything in between:

|-0-1-2-3-4-5-6-7-8-9-| *-----------------*

So, project all the vertices onto the line. Compare their values to the current minimum and maximum. If it's lower than the minimum, throw the old one away and keep the current value; same for the maximum.

After both shapes have been projected and the each have a minimum and maximum, you can compare the minimums and maximums to determine if the projections intersect.

## The Code

This is just bits and chunks from the demo. I will explain the major areas of it.

### Creating The Polygon

There are two functions for creating polygons: `CreateRegular` and `CreatePolygon`. `CreateRegular` makes a regular polygon with `NumberSides` sides with a radius of `Radius`.

`CreatePolygon`, however, is the more useful function. It allows you to create a polygon using coordinates you provide. Note that these are `Local Coordinates`.

So if you wanted to create a square with sides the length of 4, with the top-left corner positioned at [50,50], **DO NOT** pass the coordinates: [50,50][54,50][54,54][50,54]. Pass the coordinates: [0,0][4,0][4,4][0,4]. Then set the X/Y values to [50,50].

However in both functions, after the vertices are stored, there is this:

```
'Fill in line list
For i = 0 To NumVertices
```

```
``` t = i + 1
If t > NumVertices Then t = 0
With LineList(i)
.LineStart = VertexList(i)
.LineEnd = VertexList(t)
'Store the axis
.LineNormal = VectorCreate(-(.LineEnd.Y - .LineStart.Y), .LineEnd.X - .LineStart.X)
VectorNormalize .LineNormal
End With

```
Next i
```

The first part is simple. `.LineStart` is the first vertex of the side and `.LineEnd` is the other. But what is `.LineNormal`? It is the `normal` of the side, as described above. Then it is normalized, so that .

### Intersection Test

(a C port: IntersectionTestInC)

This is the part you've been waiting for...the intersection code. It looks like so:

```
Public Function PolyPolyCollision(ByRef PolygonA As P_Polygon, _
```

```
``` ByRef PolygonB As P_Polygon) As Boolean

Dim min0 As Single, max0 As Single 'The min and max values that the
Dim min1 As Single, max1 As Single 'points had projected onto
Dim vAxis As P_Vector 'this line
Dim sOffset As Single 'Offset from A to B
Dim vOffset As P_Vector 'Vector representation of sOffset
Dim d0 As Single, d1 As Single 'Distance between projected vertices
Dim i As Long, j As Long, t As Single 'Counting & temp variables
Dim P1() As P_Vector, P2() As P_Vector 'Vertices

'Get vertices
PolygonA.GetVertices P1()
PolygonB.GetVertices P2()

'Get offset
vOffset = VectorCreate(PolygonA.X - PolygonB.X, PolygonA.Y - PolygonB.Y)

For i = 0 To PolygonA.VertexCount - 1

vAxis = PolygonA.GetAxis(i) 'The axis that the points will be projected onto
'Project polygon A
min0 = VectorDotProduct(vAxis, P1(0))
max0 = min0
For j = 1 To PolygonA.VertexCount - 1
t = VectorDotProduct(vAxis, P1(j))
If t < min0 Then min0 = t
If t > max0 Then max0 = t
Next j
'Project polygon B
min1 = VectorDotProduct(vAxis, P2(0))
max1 = min1
For j = 1 To PolygonB.VertexCount - 1
t = VectorDotProduct(vAxis, P2(j))
If t < min1 Then min1 = t
If t > max1 Then max1 = t
Next j
'Shift polygon A's projected points
sOffset = VectorDotProduct(vAxis, vOffset)
min0 = min0 + sOffset
max0 = max0 + sOffset
'Test for intersections
d0 = min0 - max1
d1 = min1 - max0
If (d0 > 0) Or (d1 > 0) Then
'Found a seperating axis, they can't possibly be touching
PolyPolyCollision = False
Exit Function
End If

Next i

'Now do ALL of that for polygon B
For i = 0 To PolygonB.VertexCount - 1

vAxis = PolygonB.GetAxis(i) 'The axis that the points will be projected onto
'Project polygon A
min0 = VectorDotProduct(vAxis, P1(0))
max0 = min0
For j = 1 To PolygonA.VertexCount - 1
t = VectorDotProduct(vAxis, P1(j))
If t < min0 Then min0 = t
If t > max0 Then max0 = t
Next j
'Project polygon B
min1 = VectorDotProduct(vAxis, P2(0))
max1 = min1
For j = 1 To PolygonB.VertexCount - 1
t = VectorDotProduct(vAxis, P2(j))
If t < min1 Then min1 = t
If t > max1 Then max1 = t
Next j
'Shift polygon A's projected points
sOffset = VectorDotProduct(vAxis, vOffset)
min0 = min0 + sOffset
max0 = max0 + sOffset
'Test for intersections
d0 = min0 - max1
d1 = min1 - max0
If (d0 > 0) Or (d1 > 0) Then
'Found a seperating axis, they can't possibly be touching
PolyPolyCollision = False
Exit Function
End If

Next i

```
'None of the axis's seperated the two polygons, they are indeed colliding
PolyPolyCollision = True
End Function
```

#### Variables

Looks big at first, but if you go through it one line at a time, it is actually pretty easy to follow. First, what are all these variables? The min and max variables hold the final projected values. We need to have min and max because the projected points won't come out 'in order'.

Take a look at that first projected box back at the top. Note how although 4 points were projected, there are only two sides to the smashed line. Those two points are min and max.

Now the next variable, `vAxis` is simple. It is the axis the vertices are being projected onto.

The next two, however, are a new concept. Up until now, all coordinates have been in `Local Coordinates`. So when we do the testing, rather than adding X & Y to **every** single vertices in both polygons, we add an offset to the final min/max set (to the first polygon).

Where `P` is position. `sOffset` is calculated later by projected `vOffset` onto `vAxis`.

The rest are pretty easy. `d0 & d1` are used for the final testing.

#### The Main Code

From there on, it's very self-explainatory--The code is well commented. As you can see, the two main loops are exactly identical apart from one thing: the axis. In the first loop the axis is extracted from `Polygon A` and in the second loop it is from `Polygon B`.

# Done

In the next article, the algorithm will be extended for `Collision Detection`. For now, play around with the demo. It demonstrates everything presented here, as well as how the engine is used (calling functions, setup and all that goodness). It requires a graphics card capable of DirectX8. Nothing fancy, just some sprites.

NOTE: You'll notice that the intersection test is nearly pixel perfect...:)