Using Vector Mathematics, Cross Products

Cross products are the most complicated use of vectors we've covered so far. One thing you'll need to know is if your game engine's coordinate system is left-handed or right-handed. If you're unfamiliar with coordinate system handedness, you might read over this article on Wikipedia.

The cross product method is very handy for finding the vector that is perpendicular/orthogonal to two other vectors. Any two non-parallel vectors will form a plane, and the line perpendicular to that plane that passes through the two vectors will always exist, that line can be found with a cross product. You might be asking how this is useful in 3D games? It's often used for finding an object's forward, up, or right vector. An object's forward vector is the vector that goes from the position of the object outward through the front of the object, an up vector is a vector that goes from the position of the object upward out of the top of the object, and the right vector goes from the position of the object out the right side of the object. Any vectors parallel to those vectors qualify as well. A picture might help clarify (or it might confuse you more):

Don't worry, this stuff confused me when I first started as well, a large part of being comfortable doing vector mathematics in games is just being able to picture multiple points and vectors in 3D, so you can picture exactly what it is you're trying to get. If you still want some info on Cross Product after this blog post, this video on YouTube might clarify.

Anyway, let's move on to explaining the math behind a cross product. Here's the exact formula:

If A and B are vectors, and x, y, z, denote the parameter within the vector

A (cross) B = ( Ay*Bz - Az*By, Az*Bx - Ax*Bz, Ax*By - Ay*Bx )

Don't feel bad if you don't memorize this, I haven't got it memorized either.

So let's take some vectors we know to be orthogonal, and see if the cross product gets us the same result:

Vector A = (1, 0, 0)

Vector B = (0, 1, 0)

Vector C = (0, 0, 1)

A (cross) B, should result in C given the three vectors we defined just above.

A (cross) B = ( 0*0 - 0*1, 0*0 - 1*0, 1*1 - 0*0 ) = (0, 0, 1)

As you can see A (cross) B, does indeed give us Vector C as we had defined it above.

And to give a real world scenario I often run into in actual game development. If we take an NPC that is always upright (by upright I mean that it's not laying on its side or something), if we want to get its right or left vectors, we just need the forward vector, and since its always upright we already have the up vector. Based on having the forward and up vector, forward (cross) up will give you the right vector.

Here's a guide of what vectors crossed (in a left-handed coordinate system) will give you:

Forward (cross) up --> Right

Up (cross) Forward --> Left

Forward (cross) right --> Down

Right (cross) Forward --> Up

Up (cross) right --> Backward

Right (cross) up --> Forward

If you read that first link I gave to Wikipedia about coordinate handedness, you'll find you can use your pointer finger, thumb, and middle finger to represent the three axes to determine the cross product order and what it will give you. 

I'll try and explain. Hold out your left hand in closed fist and give a thumbs up, now point your pointer finger straight ahead of you now point your middle finger out perpendicular to your thumb and pointer finger. In this position you can think of the cross product as:

Pointer (cross) Thumb --> Middle

Using this you can use whatever vectors you have to figure out which order to use the cross product. For example let's say you want an UP vector. Hold out your hand like I explained earlier, but turn your arm or wrist so that your middle finger is pointed upward now, and you will now see that your pointer finger is pointing Forward, and your thumb is pointed Left. Therefore: Forward (cross) Left --> Up, and you can always reverse the order to get Down, so Left (cross) Forward --> Down.

Hope this all makes sense. And here's the function for a cross product:

Vector3 Vector3::Cross(const Vector3& rhs) const
{
    return ( (y * rhs.z) - (z * rhs.y),
             (z * rhs.x) - (x * rhs.z),
             (x * rhs.y) - (y * rhs.x) );
}

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

Using Vector Mathematics, utilizing squared lengths

As we've learned in the Optimizing Methods blog post, the most expensive part about doing distance checks is the square-root calculation. There are some cases where we need to do things like compare distances, but we can forego the square-root calculation.

If we want to compare two vectors to see which is longer we can do that without a square-root calculation. We don't need to know the exact length of each vector, we just need to know which is longer, so if we just skip the square-root calculation during the Length() function, when instead end up getting a squared length, which is all we want in this case.

Here's a static/helper method:

float GetSquaredLength( const Vector3& inVect )
{
    return ( inVect.x * inVect.x
           + inVect.y * inVect.y
           + inVect.z * inVect.z );
}

Here's the method you might find in a Vector class:

inline float Vector3::SquaredLength() const
{
    return ( x*x + y*y + z*z );
}

So if we put this two the test, with two vectors, (2, 2, 2) and (2, 2, 3).

The squared length of (2, 2, 2) is ( 2² + 2² + 2² ), or 12.

The squared length of (2, 2, 3) is ( 2² + 2² + 3² ), or 17.

Based on the calculations we know that (2, 2, 2) is the shorter of the two vectors, which may have been obvious, but now we've seen the proof. The actual length of these vectors isn't needed to know which is shorter, but just for some more proof, to find the actual lengths now is very easy because we already have the squared length, so we can now just do the square-root calculation:

The length of (2, 2, 2) is √12, or 3.4641.
The length of (2, 2, 3) is √17, or 4.1231.

In the Optimizing Methods blog post I mentioned that sometimes is isn't the method itself that needs to be optimized, but rather that sometimes you can avoid needing the expensive methods together. Using squared lengths for distance comparisons is just one example of this.

Here's a helper function for returning the longest of two vectors:

Vector3 Vector3::GetLongest(const Vector3& first,
                            const Vector3& second) const
{
    if ( first.SquaredLength() > second.SquaredLength() )
        return first;

    return second;
}

Using Vector Mathematics, finding direction from one point to another

Finding the direction from one point to another is fairly easy, in order to do this you'll need to understand how to unitize vectors and how to do vector subtraction, please make sure you've read up about unitizing vectors from this blog post, and read up about vector subtraction from this blog post.

If you understand unitizing vectors and vector subtraction, then this will be incredibly simple.

Let's imagine our player is standing at position (10, 4, 7), and an enemy is standing at position (5, 9, -9), and we want to find the direction from the player to the enemy. To do this we first subtract the player's position from the enemy's position, and this gives us the vector from the player to the enemy.

(5 - 10, 9 - 4, -9 - 7) = (-5, 5, -16).

Now we simply unitize this vector and we have our direction.
Get the length of the vector √(-5 * -5 + 5 * 5 + -16 * -16) = √(25 + 25 + 256) = √306 = 17.4928556
Now using the inverse of length we can get unitize the vector:

Inverse length = 1 / 17.4928556, or 0.05711619.

Multiple inverse length by each element of our vector:
( -5 * 0.05711619, 5 * 0.05711619, -16 * 0.05711619 ) = ( -0.28583097, 0.28583097, 0.91385904 )


The code for this is very simple, we'll use the Unitize() method from our previous blog post, which is this:

inline void Vector3::Unitize()
{
    const float inverseLength = 1.0f / GetLength(); 
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
}

Here's our simple function from getting the direction from the first point to the second:

Vector3 GetDirectionFromFirstToSecond( const Vector3& first,
                                       const Vector3& second )
{
    const Vector3 differenceVector = second - first;
    differenceVector.Unitize();
    return differenceVector;
}

Here's what the original sample vectors about would look like in code:

Vector3 playerPos = (10, 4, 7);
Vector3 enemyPos = (5, 9, -9);

Vector3 dirPlayerToEnemy = GetDirectionFromFirstToSecond( 
                                       playerPos, enemyPos );

// dirPlayerToEnemy is ( -0.28583097, 0.28583097, 0.91385904 )