Showing posts with label angle between. Show all posts
Showing posts with label angle between. Show all posts

Monday, November 7, 2011

Using Vector Mathematics, finding a signed angle between two vectors

In the last blog post we talked about finding the angle between two vectors, but sometimes you will find it necessary to know which side of a vector another vector is. This is especially useful for A.I. steering, having an enemy know that it needs to turn 50 degrees isn't useful unless you also can tell it which way to turn.

Here's a handy little function you can use to get the angle between vectors in a signed format (+/-). You'll pass in your source vector (which is generally the way something is facing), the destination vector (the way something is wanting to turn to), and an angle that is 90 degrees to the right of the destination angle (we'll call it 'DestsRight'). To get an angle 90 degrees to the right of the destination angle you may need to use a Cross Product, which we'll be going over in the this blog post.
float GetSignedAngleBetweenVectors( const Vector3& Source, 
                                    const Vector3& Dest,
                                    const Vector3& DestsRight ) 
{    // We make sure all of our vectors are unit length
    Vector3 SourceCopy = Source;
    SourceCopy.Unitize();
    Vector3 DestCopy = Dest;
    DestCopy.Unitize();
    Vector3 DestsRightCopy = DestsRight;
    DestsRightCopy.Unitize();
    
    float forwardDot = Vector3.Dot( SourceCopy, DestCopy );
    float rightDot = Vector3.Dot( SourceCopy, DestsRightCopy );

    // Make sure we stay in range no matter what, so Acos
    // doesn't fail later
    if ( forwardDot < -1.0f )
    { 
        forwardDot = -1.0f;
    }
    else if ( forwardDot > 1.0f )
    {
        forwardDot = 1.0f;
    }

    float angleBetween = acos( forwardDot ); 

    if ( rightDot < 0.0f )
    {        
        angleBetween *= - 1.0f;
    }        

    return angleBetween;
}

If we were to use this above function with these vectors:
The dot between S and D would be greater than 0, dot between S and R would be less than 0, so the final result angle would be negative, so we would know if D is the way we're facing we'd need to turn left to get to S.
The dot between S and D would be greater than 0, dot between S and R would be greater than 0, so the final result angle would be positive, so we would know if D is the way we're facing we'd need to turn right to get to S.

I'm too lazy right now to do a math proof of the above function, so you'll just need to trust me that it works (I've used something like this in production code).

Using Vector Mathematics, finding angle between two vectors

In the last blog post we learned about Dot Products, and how it could be used to find relative differences between two vectors, but now we will learn how to find the exact angle between those two vectors.

For this example we will use two very simple vectors. To get the angle between two vectors you will need to unitize your vectors or make sure they're already unit-length, for simplicity I will just use two unit-length vectors to start with in this example:

Vector a = (1, 0, 0)
Vector b = (0, 0, 1)

You'll notice the above vectors are both along an axis, which means they're perfectly perpendicular, which also means we know already that they're 90 degrees apart ( π/2 radians apart ), but we'll use that knowledge as proof that what I'm about to show you does in fact work. Also, for future reference, please note that any vectors that are perpendicular to each other are also known as orthogonal, this term is often used when referring to vectors, so it's important to know.

Ok, so first we'll get the dot product of the vectors, which should end up being 0 since the vectors are orthogonal.

a (dot) b = (1*0 + 0*0 + 0*1) = 0

And now to get the angle between the vectors, we will use the trigonometric function for arc-cosine, called acos(). Please note that acos() requires a value between -1 and 1, anything outside of that range will cause acos() to return a non-number return value, which you don't want. It's safest to range check what you're about to pass it just in case.

acos(0) = π/2 radians, which is 90 degrees.

If you have two vectors that are parallel, you'll always get a dot product of ±1, and acos(-1) or acos(1) is always 0 radians/degrees as you would expect. But lets test it with a dot product just for fun:

Vector c = (1, 0, 0)
Vector d = (1, 0, 0)

c (dot) d = (1*1 + 0*0 + 0*0) = 1
acos(1) = 0 radians/degrees

Vector e = (-1, 0, 0)

c (dot) e = (1*-1 + 0*0 + 0*0) = -1
acos(-1) = 0 radians/degrees

And.....now some code:
inline float FindAngleBetweenVectors( const Vector3& first,
                                      const Vector3& second )
{
    // You might leave these Unitize calls out if you know
    // you're always passing in Unitized vectors. However
    // I recommend having two versions of this function,
    // one that takes unit vectors, and one that will unitize
    // them for you.
    // Copies are required because we're passing in 'first'
    // and 'second' by const reference, which allows the
    // user to pass in vectors and not worry about them
    // unintentionally getting unitized.
    Vector3 firstCopy = first;
    firstCopy.Unitize();

    Vector3 secondCopy = second;
    secondCopy.Unitize();

    const float dotProduct = firstCopy.Dot(secondCopy);

    // A range check here is a good idea for safe code, I'll
    // leave it out for this sample though.

    return acos(dotProduct);
}

Using Vector Mathematics, Dot Products

Dot product is one of the properties of vectors that you can get when multiplying them. The dot product has many useful properties with vectors, in fact, the Dot Product and Cross Product are probably some of the most important properties of vectors in 3D math used in video games. The Dot Product is most often used to tell us information about the angle between two vectors, this can be used, for example, to tell if a point is in front of a player, or behind them.

To get a dot product, you multiply each component of two vectors, and then add each component together, like such:

Vector a = (3, -5, 7)
Vector b = (5, -2, -9)

a (dot) b = ((3 * 5) + (-5 * -2) + (7 * -9)) = 15 + 10 - 63 = -38

While the above method is using the dot product, most often you'll find you need the dot product of two unit-length vectors, which will always yield a result between -1 and +1, and as we'll discuss later on, that is extremely useful. So, we will unitize the two vectors from our above example, which will basically give us two direction vectors.

Length of a = √(3*3 + -5*-5 + 7*7) = √(9 + 25 + 49) = √83 = 9.110433
Inverse length of a = 1 / 9.110433  = 0.1097642
Unitized vector a = (3 * 0.1097642, -5 * 0.1097642, 7 * 0.1097642) = (0.3292926, -0.548821, 0.7683494)

Length of b = √(5*5 + -2*-2 + -9*-9) = √(25 + 4 + 81) = √110 = 10.488088
Inverse length of b = 1 / 10.488088 = 0.0953463
Unitized vector b = (5*0.0953463, -2*0.0953463, -9*0.0953463) = (0.4767315, -0.1906926, -0.8581167)

Alright, now that we have unit vectors let's try the dot product again:
a (dot) b = (0.3292926 * 0.4767315) + (-0.548821 * -0.1906926) + (0.7683494 * -0.8581167)
              = 0.1569842 + 0.1046561 + -0.65933345
              = -0.39769315, or let's just round it to -0.4

So, what does -0.4 really mean to you in this case? Well here's the cool part. With a dot product, if we treat the two vectors as directions, then a value less than 0 means that vector 'b' is behind vector 'a'. A value greater and 0 means it would be in front, and a value of 0 means it's directly to the left or right of 'a'.

So in this particular example, if we think of 'a' as the direction an object is facing, and think of vector 'b' as a point in space than that means that the point 'b' is behind the object. This is extremely useful for things like artificial intelligence, if an enemy knows the player is behind them, then it can be told to start turning around to face the player, or if the enemy knew the player was in front of them then they might know they are able to attack the player. Knowing where one object is in relation to another, especially based on that object's rotation, is essential for all kinds of things that require steering, not just A.I. So if you plan on making a 3D game, then the Dot Product is your friend. Learn it, live it, love it.


Here's a rough sketch of what this looks like, in this example I've done a top-down perspective, so I left the Y component out of the sketch, but based on the Y-components if this were in-game the enemy would be slightly higher than the player. Anyway, in the picture the arrow is the direction the player is facing, the line perpendicular to the arrow would be the left and right of the player, and as you can see the position of the enemy (which is 5, -9) is behind the player (and a bit to the right as well).




And finally, here's the code for our above example:

The Dot function would be a member of a Vector class most likely:
inline float Vector3::Dot( const Vector3& rhs ) const
{
    return (x * rhs.x
          + y * rhs.y
          + z * rhs.z);
}

And now to put our new Dot function to use:
Vector3 first = Vector3(3, -5, 7);
Vector3 second = Vector3(5, -2, -9);

first.Unitize();
second.Unitize();

float dotProduct = first.Dot(second);

// dotProduct is approx. -0.4