Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In SAT collision detection how do I calculate the axes for projection?

share|improve this question
1  
This question shows lack of research :) –  Byte56 Nov 16 '12 at 17:33
add comment

1 Answer

up vote 1 down vote accepted

We'll initially stick to 2D collisions detection for simplicity. (I'll discuss 3D at the end).

The axes used in SAT are the normal vectors of all of the edges of the two objects being considered.

Consider the box in this diagram; enter image description here

The box has 4 edges: AB,BC,CD & DA (if using the clockwise convention). Each of these edges can be written as a vector;

  1. edge AB is the vector B-A. (That is vectorB minus vectorA)
  2. A & B are points, the expression (B-A) is the vector which encapsulates the distance and direction from point A to point B.
  3. We need the normal to this edge, A normal is vector at right angles to the edge. We can calculate this by swapping x and y of the edge and multiplying the y value by -1.

I'll do a numerical example;

A=(100,100)
B=(150,175)

edgeAB B-A=(150-100,175-100)=(50, 75)

normalAB=(-75, 50)

For SAT we need also to find normalBC, normalCD and normal DA. We also need to find the normals to all the edges of the other object in the collision detection.

All these normals are the set of axes which we will project both objects' vertices onto.

In some tutorials you will be advised to normalise the axes. this is not necessary, although I find it does make visualising the process easier.

Note, in the diagram, normalAB is parallel with normalCD in this case the result of projection on these axes will be the same (overlap or non-overlap) will be the same so there is no need to project on to both of them. You can eliminate normal CD. Similarly normal BC and normal DA are parallel, so you can eliminate one of these.

3D normals

For 3D you will need to find the normals for all the faces, you will also need to get the cross product of all the edges of one object with all the edges of the other.

share|improve this answer
    
Just a note that the component you negate when finding the normal depends on winding order. If clockwise, negate the X component after swapping. If counter-clockwise, negate the Y component after swappibg. –  Sean Middleditch Nov 16 '12 at 17:37
1  
@SeanMiddleditch, that's true if you want 'outward' pointing normals, but it turns out that for SAT it doesn't really matter if you use 'outward' or 'inward' normals. Either will give you the same result –  Ken Nov 16 '12 at 19:50
    
That's a good point. I didn't think that one through. :) –  Sean Middleditch Nov 17 '12 at 3:47
    
Is there a reason you keep answering your own questions ( full articles answered within a minute of posting the question ) and then selecting it as the accepted answer? gamedev.stackexchange.com/questions/40011/… and gamedev.stackexchange.com/questions/38841/… –  rootlocus Nov 17 '12 at 8:32
    
@rootlocus, I'm trying to maximize the value of my keystrokes codinghorror.com/blog/2007/05/… If I have to answer a programming question for someone(outside of SE), I'll put it up here for future reference –  Ken Nov 17 '12 at 9:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.