Using Vector Mathematics, Point against sphere intersection test

In this post we learn how to do a simple check to see if a point in 3D space intersects a sphere. It is common practice in games to approximate complicated shapes with a sphere for collision or proximity checks, for example if you want to fire a bullet and see what objects that bullet may hit, you could approximate the bullet path with a straight line (which isn't entirely accurate), and approximate certain objects with spheres (also not entirely accurate).

This is a very simple intersection test. We just need to know how far the point is from the center of the sphere, and if that distance is greater than the radius of the circle. As per usual for distance comparisons we can used squared lengths for this to save us a square-root calculation.

For a simple example we'll place a sphere at (0, 0, 0), with a radius of 5, and we'll check against a point in space at (4, 4, 4).

Squared radius of sphere = 5² = 25
Difference vector between point and center of sphere = (4 - 0, 4 - 0, 4 - 0) = (4, 4, 4)
Squared length of difference vector = ( 4² + 4² + 4² ) = ( 16 + 16 + 16 ) = 48
Because the length of the difference vector is greater than the sphere's radius, we know the point does intersect the sphere.

Here is the code for this intersection test:

bool Vector3::IsWithinSphere(const Vector3& SphereCenter,
                             const Vector3& SphereRadius)
{
    Vector3 diffVector = Vector3(x - SphereCenter.x,
                                 y - SphereCenter.y,
                                 z - SphereCenter.z);

    return (diffVector.LengthSqr() < (SphereRadius * SphereRadius));
}

Using Vector Mathematics, Point against axis-aligned box intersection test

In this post we will talk about how to determine if a point is intersecting with an axis-aligned box. Axis-aligned boxes are highly common in games due to being highly efficient, they're often used with culling techniques and other techniques that require spatial partitioning. If you're not familiar with the term "axis-aligned", I recommend reading this, and this. If you're not familiar with the term "spatial partitioning" I recommend reading this.

An axis-aligned box can be fully described using only two points, a min and max point, so all that is needed to see if a point lies inside the box is checking each component of the point to see if it is outside of the min or max range for the box.

For example, lets define a box with a minimum point of (-1, -1, -1) and a maximum point of (1, 1, 1). If we want to check the point (-5, 0, 0.5), we first check the x component, which is -5, and we can see it's less than the minimum x, which is -1, so it cannot be in the box. If we check another point, of (0.5, 1.5, 0), we first check the x component, which is 0.5, and find that it is not less than the minimum x of -1, or greater than the maximum x of +1, so it could lie within the box. We then check the y component, which is 1.5, and find it is not less than the minimum of -1, but it greater than the maximum of +1, so this point cannot be within the box. With a maximum of 6 comparisons we can tell if a point lies within an axis-aligned box, this is why they are so efficient. Checking against a box that isn't axis-aligned, would likely be about 10-20x as expensive. I may cover that kind of intersection test in a later post.

Here's the function to perform a point/axis-aligned box intersection test:

bool Vector3::IsWithinAxisAlignedBox(const Vector3& minPt,
                                     const Vector3& maxPt)
{
    if ( x < minPt.x )
        return false;

    if ( y < minPt.y )
        return false;

    if ( z < minPt.z )
        return false;

    if ( x > maxPt.x )
        return false;

    if ( y < maxPt.y )
        return false;

    return ( z < maxPt.z );
}

Using Vector Mathematics, Line segment against sphere intersection test

This post is about checking for intersection between a line segment and a sphere. Please make sure you read the previous post about finding the closest point on a line from another point, located here.

Luckily, using the formula for finding the closest point on a line, there's not much work left to do to find out if the sphere is touching the line segment. The first step we have is to use that same formula, and the point we use is the center of the sphere.

We'll keep the same points and line from the last example, which we've already seen the math for, and we'll use a sphere (or circle if you're using 2D vectors) with a radius of 1. Judging from the image below, you already know the circle isn't touching the line segment that goes from (0, 0) to (5, 0), but lets prove it with some math.

We already know the point at the center of the sphere (3, 0, -2), and the closest point on the line segment (3, 0, 0) from our last blog post, so all we have to do is find out how far apart those two points are; And, since we only need that distance for a comparison with the sphere's radius, we can just get the squared-length and skip the square-root calculation.

Difference vector = (3, 0, -2) - (3, 0, 0) = (0, 0, -2)
Squared length of difference vector = (0² + 0² + -2²) = 4
Squared radius of sphere = 1² = 1

Because the squared radius is less than the squared length, we can say for certain that the sphere is not intersecting the line segment.

And now we'll use a circle that we know should touch, one with a radius of 2.2 units.

Difference vector = (3, 0, -2) - (3, 0, 0) = (0, 0, -2)
Squared length of difference vector = (0² + 0² + -2²) = 4
Squared radius of sphere = 2.2² = 4.84

And now because the squared radius of the sphere is greater than (or equal to) the squared length of the difference vector, we know it's intersecting or touching the line segment.

There is a caveat though. In our last post we said that points A and C in the example could be ignored because they weren't in the range of the line segment. While this is true, a large enough sphere centered at those points may still intersect with the line segment, so they cannot be ignored. The trick in the case of either of those points is to simply used the ends of the line segments for distance checks. In the case of point A, it will give a percentage along the line of less than 0.0, so we can use the starting point, and point C will give a value greater than 1.0, so we can use the end point of the line segment. So, rather than bailing out of the function if the percentage along the line is not between 0.0 and 1.0, we instead clamp the value in that range, if it's less than 0.0 we'll just pretend it's 0.0, and the same with 1.0.

So here's the function for determining line segement intersection with a sphere:

bool DoesLineSegmentIntersectSphere(const Vector3& LinePointStart,
                                    const Vector3& LinePointEnd,
                                    const Vector3& SphereCenter,
                                    const float SphereRadius)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = SphereCenter - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if ( percAlongLine < 0.0f )
    {
       percAlongLine = 0.0f;
    }
    else if ( percAlongLine > 1.0f )
    {
       percAlongLine = 1.0f;
    }

    const Vector3 IntersectionPt = ( LinePointStart 
              + (  percAlongLine  * ( LinePointEnd - LinePointStart ));

    const Vector3 SpherePtToIntersect = IntersectionPt - SphereCenter;
    const float SqrLengSphereToLine = SpherePtToIntersect.LengthSqr();

    return (SqrLengSphereToLine >= SphereRadius);
}

If we try this method with point C (pictured above), and the same sphere radius of 2.2, it looks like it should intersect with the sphere, so lets find out:

First we need to find the closest point on the line segment
line diff ( dot ) line to point = ( 5.7*5 + 0*0 + -1.8*0 ) = 28.5
Percentage along line = 28.5 / 25 = 1.14


1.14 is greater than 1.0 so we'll just clamp it to 1.0


And finding the closest point on the line finally requires this:
P1 + ( percAlongLine * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 1.0 * ( 0, 0, 5 ) ), which simplifies to ( 5, 0, 0 )


This confirms that clamping the percentage along the line to 1.0 left us with the end point of the line segment as the closest point on the line segment to the center of the circle. From here we can continue on just like with the example we used earlier for point B.



Difference vector = (5.7, 0, -1.8) - (5, 0, 0) = (0.7, 0, -1.8)
Squared length of difference vector = (0.7² + 0² + -1.8²) = (0.49 + 0 + 3.24) = 3.73
Squared radius of sphere = 2.2² = 4.84

And finally we see here that the radius of the sphere is indeed greater than the distance from the point on the line segment closest to the center of the sphere, which verifies the sphere is intersecting the line segment.

Using Vector Mathematic, Finding closest point on a line

In this post we will be looking at determining the closest point on a line from another point. This technique by itself isn't worth much, but it's required as part of other techniques, such as an intersection test between a line and a sphere, which I may post about later.

Describing how this works using only words is going to be tough. Lets start with a picture to help:

Of the points in this picture, only point B lies along the line segment. Technically you could say that the closest point on the segment to point A is P1, and to C is P2, but in most cases where you want the closest point on a line segment you want to exclude points that aren't going to lie in that segment, so we will exclude them for our purposes.

First we need to get some information setup that we'll be able to test with.

1. We need a vector from P1 to P2, which is achieved by doing P2 - P1.
   Line difference vector is (5 - 0, 0 - 0, 0 - 0) = (5, 0, 0)
2. We need the squared length of the vector we just got in step 1.
   I'm not even doing the math for this part, only one component is non-zero, which is the 5, so the   length in this case is 5, leaving squared length at 25.
3. We need a vector from P1 to our test point (point B), which is B - P1.
   Point difference from P1 is (3 - 0, 0 - 0, -2 - 0) = (3, 0, -2)

Now we do the dot product between our line difference vector and our line to point vector
line diff ( dot ) line to point = ( 3*5 + 0*0 + -2*0 ) = 15

Notice that unlike previous posts, we don't unitize our difference vectors before doing a dot product. In this case we take that dot product and now divide it by the squared length.

Percentage from start to end point = 15 / 25 = 0.6 (0.6 is the same as saying 60%)

Note: We didn't test points A or C because we could see from the picture they weren't on the line segment, but normally you won't be able to just pick which point you want to test, you test every point, and if your value above (which for point B is 0.4) is less than 0.0 or greater than 1.0, then you know it's outside of the line segment.

Now, the closest point is calculated as such:
P1 + ( U * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 0.6 * ( 0, 0, 5 ) ), which simplifies to ( 3, 0, 0 )

Here's the code for this:

Vector3 GetClosestPointOnLineSegment(const Vector3& LinePointStart, const Vector3& LinePointEnd,
                                     const Vector3& testPoint)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = testPoint - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if (  percAlongLine  < 0.0f ||  percAlongLine  > 1.0f )
    {
        // Point isn't within the line segment
        return Vector3::ZERO;
    }

    return ( LinePointStart + ( percAlongLine * ( LinePointEnd - LinePointStart ));
}

Using Vector Mathematics (and a bit of trig), Point against cone intersection test

In this post we're going to see how to check if a point lines within a 3D cone. To be clear, it's not exactly a cone, it's like a cone that goes on forever, or if we give a max distance it's like a cone with a round bottom instead of flat.

You might wonder what this kind of intersection test is good for; It's mostly used for things like checking if a point is within an object's field-of-view.

So for checking if a point is within an object's field of view, we need 4 parameters.
We need the position of the object, the direction it is facing, the position of the point we're checking, and the field of view of the object.

We'll pick some convenient values to make things easier to understand.
Object position = (0, 0, 0)
Object facing direction (0, 0, 1)
Point position = (0.5, 0, 1.5)
Field of view = π/3 radians (60 degrees)

We need to get the direction from the object to the point:
Difference vector = (0.5 - 0, 0 - 0, 1.5 - 0) = (0.5, 0, 1.5)

Now that we have the difference, we need to unitize it to get a direction.
length = √( 0.5² + 0² + 1.5² ) = √( 0.25 + 0 + 2.25 ) = √2.5 = 1.5811388
inverse length = 1 / 1.5811388 = 0.63245554
direction = (0.5 * 0.63245554, 0 * 0.63245554, 1.5 * 0.63245554) = (0.31622777, 0, 0.94868331)

Now that we have the direction from the object to the point we get the dot product between that vector and the object's facing direction.

Facing direction (dot) direction to point = (0 * 0.31622777 + 0 * 0 + 1 * 0.9486331) = 0.9486331

Now we need to calculate the cosine of half of the player's field of view. We use half because we want the angle from the center of the cone of FOV, just like dot product is the angle from the center.

half of FOV = π/6
cosine(π/6) = 0.866025

And finally, what determines if the point is in the object's FOV is if the dot product (0.9486331) is greater than or equal to the cosine of half of the FOV (0.866025). In this case it is greater than or equal to the cosine of the FOV, so that point is in the object's FOV.

And here's the function for doing this type of calculation:

bool IsPointWithinCone(const Vector3& coneTipPosition,
                       const Vector3& coneCenterLine,
                       const Vector3& point,
                       const float FOVRadians)
{
    Vector3 differenceVector = point - coneTipPosition;
    differentVector.Unitize();

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians ) );
}

The above function assumes a cone the continues on forever. If the we assume that our object cannot see for an infinite distance then we can add a distance check.

bool IsPointWithinFiniteCone(const Vector3& coneTipPosition,
                             const Vector3& coneCenterLine,
                             const Vector3& point,
                             const float FOVRadians,
                             const float maxDistance)
{
    Vector3 differenceVector = point - coneTipPosition;

    // Notice that Unitize() is returning a float. The
    // original one we wrote didn't return a float, we'll
    // cover this change in an upcoming blog post
    float length = differentVector.Unitize();

    if ( length > maxDistance )
    {
        return false;
    }

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians );
}

In our original example at the top of the post our point was 1.58 units away, so if we used a finite distance check like the function just above and passed a max distance of 1.5 in, the object would be considered outside of the view.

Using Vector Mathematics, Complete Vector3 Class

After a large series of vector mathematics blog posts, here is a full Vector3 class that I wrote, it's fairly efficient and should be enough to suit your needs if you would like to use it. There are other 3rd-party math libraries out there if you'd like to browse your options.

Header file: Vector3.h

#pragma once // Most compilers are compatible, remove if yours isn't
#ifndef VECTOR_3
#define VECTOR_3

#include <math.h>
#include <ostream>

class Vector3
{
public:
Vector3(void);
explicit Vector3(const float x, const float y, const float z);

// Copy constructor
Vector3(const Vector3& rhs);

~Vector3(void);

bool operator==(const Vector3& rhs) const { return ( (x == rhs.x) 
                                                  && (y == rhs.y)
                                                  && (z == rhs.z));}
bool operator!=(const Vector3& rhs) const { return ( (x != rhs.x)
                                                  || (y != rhs.y)
                                                  || (z != rhs.z));}
Vector3 operator+(const Vector3& rhs) const;
void operator+=(const Vector3& rhs);
Vector3 operator-(const Vector3& rhs) const;
Vector3 operator-(void) const;
void operator-=(const Vector3& rhs);
void operator*=(const int scalar);
void operator*=(const float scalar);

// Non-member operators get a friend declaration
friend Vector3 operator*(const Vector3& vector, const int scalar);
friend Vector3 operator*(const Vector3& vector, float scalar);
friend Vector3 operator*(const int scalar, const Vector3& vector);
friend Vector3 operator*(const float scalar, const Vector3& vector);
friend std::ostream& operator<<(std::ostream& ofs,const Vector3& rhs);

inline void Flip(void) { x = -x; y = -y; z = -z; }

inline float Dot(const Vector3& rhs) const { return (x * rhs.x
                                                   + y * rhs.y
                                                   + z * rhs.z); }

Vector3 Cross(const Vector3& rhs) const;

float Length(void) const { return sqrtf( LengthSqr() ); }

inline float LengthSqr(void) const { return (x * x + y * y + z * z); }

float Unitize(void);

void Reflect( const Vector3& rhs );

static Vector3 Reflect( const Vector3& first, const Vector3& second );
static Vector3 GetLongest(const Vector3& first, const Vector3& second);

static const Vector3 Left;
static const Vector3 Right;
static const Vector3 Up;
static const Vector3 Down;
static const Vector3 Forward;
static const Vector3 Backward;

static const Vector3 UnitX;
static const Vector3 UnitY;
static const Vector3 UnitZ;

static const Vector3 Zero;


float x;
float y;
float z;
};

#endif //VECTOR_3

Implementation File, Vector3.cpp:

#include "Vector3.h"

#include <sstream>

const Vector3 Vector3::Right(1.f, 0.f, 0.f);
const Vector3 Vector3::Up(0.f, 1.f, 0.f);
const Vector3 Vector3::Forward(0.f, 0.f, 1.f);
const Vector3 Vector3::Left(-1.f, 0.f, 0.f);
const Vector3 Vector3::Down(0.f, -1.f, 0.f);
const Vector3 Vector3::Backward(0.f, 0.f, -1.f);

const Vector3 Vector3::UnitX(1.f, 0.f, 0.f);
const Vector3 Vector3::UnitY(0.f, 1.f, 0.f);
const Vector3 Vector3::UnitZ(0.f, 0.f, 1.f);
const Vector3 Vector3::Zero(0.0f, 0.0f, 0.0f);

Vector3::Vector3(void) : x(0.0f), y(0.0f), z(0.0f)
{
}

Vector3::Vector3(const float x, const float y, const float z)
{
    this->x = x;
    this->y = y;
    this->z = z;
}

// Copy constructor
Vector3::Vector3(const Vector3& rhs)
{
    x = rhs.x;
    y = rhs.y;
    z = rhs.z;
}

Vector3::~Vector3(void)
{
}
Vector3 Vector3::operator+(const Vector3& rhs) const
{
    Vector3 newVector;
    newVector.x = x + rhs.x;
    newVector.y = y + rhs.y;
    newVector.z = z + rhs.z;
    return newVector;
}

void Vector3::operator+=(const Vector3& rhs)
{
    x += rhs.x;
    y += rhs.y;
    z += rhs.z;
}

Vector3  Vector3::operator-(const Vector3& rhs) const
{
    Vector3  newVector;
    newVector.x = x - rhs.x;
    newVector.y = y - rhs.y;
    newVector.z = z - rhs.z;
    return newVector;
}

Vector3 Vector3::operator-(void) const
{
    Vector3  newVector(-x, -y, -z);
    return newVector;
}

void Vector3::operator-=(const Vector3& rhs)
{
    x -= rhs.x;
    y -= rhs.y;
    z -= rhs.z;
}

void Vector3::operator*=(const int scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

void Vector3::operator*=(const float scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

Vector3 operator*(const Vector3& vector, const int scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const Vector3& vector, const float scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const int scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const float scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}
std::ostream& operator<< (std::ostream& os, const Vector3& vector)
{
    std::stringstream stream;
    stream << "X: " << vector.x << ", Y: " << vector.y << ", Z: " << vector.z; 
    os.write(const_cast<char*>(stream.str().c_str()),
             static_cast<std::streamsize>(stream.str().size() *
             sizeof(char)) );
    return os;
}

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

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

void Vector3::Reflect( const Vector3& normal )
{
    const float dotProductTimesTwo = Dot(normal) * 2.0f; 
    x -= dotProductTimesTwo * normal.x;
    y -= dotProductTimesTwo * normal.y;
    z -= dotProductTimesTwo * normal.z;
}

Vector3 Vector3::Reflect(const Vector3& vector, const Vector3& normal)
{
    Vector3  newVector;
    const float dotProductTimesTwo = vector.Dot(normal) * 2.0f;
    newVector.x = vector.x - (dotProductTimesTwo * normal.x);
    newVector.y = vector.y - (dotProductTimesTwo * normal.y);
    newVector.z = vector.z - (dotProductTimesTwo * normal.z);
    return newVector;
}

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

    return second;
}

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 )

Using Vector Mathematics, Vector addition and subtraction

3D Math in games is largely based on Vector Mathematics. If you're unfamiliar with this term, please read up on 'Vectors' before continuing.

If you're programming in C++, do not confuse vectors used for 3D math with the vector container used in the standard template library (STL).

In this post we'll talk about 3D vectors, 2D vector math is pretty much identical, just lacking calculations done in one of the dimensions. If you understand 3D vectors then you'll have no trouble understanding 2D vectors.

Vectors are defined by three components: x, y, and z. These components usually define either a position, direction, or velocity along the x, y, and z axes.



Vector Addition and Subtraction
Adding and subtracting vectors is just simple arithmetic, you add or subtract each component of the two vectors.

For example, addition:
(0, 0, 0) + (3, 5, 7) = (3, 5, 7)

Code:

Vector3 first = Vector3(0, 0, 0);
Vector3 second = Vector3(3, 5, 7);

Vector3 result = Vector3(first.x + second.x,
                         first.y + second.y,
                         first.z + second.z);

// result.x is 3, result.y is 5, result.z is 7 

If you're using a pre-defined vector class, it will probably have an addition and subtraction operator. Here's what vector addition will generally look like:

Vector3 result = first + second;

subtraction:
(0, 0, 0) - (3, 5, 7) = (-3, -5, -7)

Code:

Vector3 first = Vector3(0, 0, 0);
Vector3 second = Vector3(3, 5, 7);

Vector3 result = Vector3(first.x - second.x,
                         first.y - second.y,
                         first.z - second.z);

// result.x is -3, result.y is -5, result.z is -7

Common uses of vector addition and subtraction

• Applying force to an object.

If you wanted to apply gravity to an object, for example, you would add gravity to an object's velocity each frame. You would want to take the elapsed frame's time into account as well.

void ProcessGravity( float elapsedTime )
{
    Vector3 myVelocity = (5, 0, 5);
    Vector3 gravity = (0, -9.8f, 0);

    gravity *= elapsedTime;

    myVelocity = myVelocity + gravity;
}

In the above method I've defined the variables for velocity and gravity, but generally this method would be part of the object, so velocity would be a member variable. Also, gravity would usually be passed into the method, not defined within it. Finally, the vector class will likely have a += operator. So the function would be look closer to this:

void MyClass::ApplyGravity( const Vector3& gravity, float elapsedTime )
{
    m_Velocity += (gravity * elapsedTime);
}

You may notice that gravity is being multiplied by a float. That operation is generally an overloaded operator that works like such:

gravity.x *= elapsedTime;
gravity.y *= elapsedTime;
gravity.z *= elapsedTime;