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

From GPWiki
Jump to: navigation, search

Tutorial by Nicholas Gorski [GMan]

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

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:

VB PhysEng ProjectBox.gif

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

VB PhysEng ProjectShapes.gif

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:

VB PhysEng Normal.gif

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


\mathrm{Slope} = \frac{\mathrm{Rise}}{\mathrm{Run}}

Then the normal of it is:


\mathrm{Normal} = \frac{- \mathrm{Run}}{\mathrm{Rise}}

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:


\mathrm{proj}(\vec A, \vec B) = \vec A \frac{\vec A \cdot \vec B}{\left|\vec A\right| \left|\vec B\right|}

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


\mathrm{proj}(\vec A, \vec B) = \vec A \frac{\vec A \cdot \vec B}{\left|\vec A\right|}

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


\mathrm{proj}(\vec A, \vec B) = \frac{\vec A}{\left|\vec A\right|}

We know this \frac{\vec A}{\left|\vec A\right|} 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:


\mathrm{proj}(\vec A, \vec B) = \vec A \cdot \vec B

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 \left|\vec B\right| = 1.

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).


\mathrm{vOffset} = \vec P_a - \vec P_b

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.

DEMO ~29 kb

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