Tag: linear algebra

Operator Overloading in C++

One of the advantages of working with C++ is the ability of the programmer to overload not only functions, but also operators as well.  With operator overloading most operators can be extended to work not only with built-in types like floats and ints but also classes.  This gives the programmer the freedom to change how a built-in operator is used on objects of that particular class.  For example, we can overload the plus, minus and star operators to perform vector addition, subtraction and scalar multiplication on the components of our Vector3 class.  (I will be using this Vector3 class as an example of operator overloading for the remainder of this post.  For more on vector math see Vectors Part 1.)

The following code sample is an example of a three  dimensional vector class which uses operator overloading for many the the various operators that are available.  We will examine the syntax of each of these operators individually.

class Vector3 {
public:
    float x;
    float y;
    float z;

    //Constructor method
    Vector3(float x, float y, float z) : x(x), y(y), z(z) {}

    //unary operations
    Vector3 operator- () const { return Vector3(-x, -y, -z); }

    //binary operations
    Vector3 operator- (const Vector3& rhs) const {
        return Vector3(x - rhs.x, y - rhs.y, z - rhs.z);
    }
    Vector3 operator+ (const Vector3& rhs) const {
        return Vector3(x + rhs.x, y + rhs.y, z + rhs.z);
    }
    Vector3 operator* (const float& rhs) const {
        return Vector3(x * rhs, y * rhs, z * rhs);
    }
    friend Vector3 operator* (const float& lhs, const Vector3& rhs) {
        return rhs * lhs;
    }
    Vector3 operator/ (const float& rhs) const {
        return Vector3(x / rhs, y / rhs, z / rhs);
    }
    bool operator!= (const Vector3& rhs) const {
        return (*this - rhs).sqrMagnitude() >= 1.0e-6;
    }
    bool operator== (const Vector3& rhs) const {
        return (*this - rhs).sqrMagnitude() < 1.0e-6;
    }

    //assignment operation
    Vector3& operator= (const Vector3& rhs)  {
        //Check for self-assignment
        if (this == &rhs)
            return *this;
        x = rhs.x;
        y = rhs.y;
        z = rhs.z;
        return *this;
    }

    //compound assignment operations
    Vector3& operator+= (const Vector3& rhs) {
        x += rhs.x;
        y += rhs.y;
        z += rhs.z;
        return *this;
    }
    Vector3& operator-= (const Vector3& rhs) {
        x -= rhs.x;
        y -= rhs.y;
        z -= rhs.z;
        return *this;
    }
    Vector3& operator*= (const float& rhs) {
        x *= rhs;
        y *= rhs;
        z *= rhs;
        return *this;
    }
    Vector3& operator/= (const float& rhs) {
        x /= rhs;
        y /= rhs;
        z /= rhs;
        return *this;
    }

    //subscript operation
    float& operator[] (const int& i) {
        if (i < 0 || i > 2) throw std::out_of_range("Out of Vector3 range\n");
        return (i == 0) ? x : (i == 1) ? y : z;
    }
    const float& operator[] (const int& i) const {
        if (i < 0 || i > 2) throw std::out_of_range("Out of Vector3 range\n");
        return (i == 0) ? x : (i == 1) ? y : z;
    }

    //typecast operations
    operator Vector2() { return Vector2(x, y); }
    operator Vector4() { return Vector4(x, y, z, 0.0f); }

    ...

};

Unary Operators:

First let us take a look at the negate (-) operator.  The body of this operator simply returns a new Vector3 object with each of its floating point components negated.  But what we are most interested in is its declaration.  Like a typical function it has a return type which is Vector3 and a parameter list enclosed by parenthesis.  But instead of a function name we follow the return type with the keyword operator and then the symbol for the particular operator that we wish to overload, which in this case is the minus sign.

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

Overloaded operators can be defined either as class member functions or as non-member functions.  Here we define them as class member functions.  This means that we do not have to include one of the objects involved in the operation in the parameter list since we can reference that object through the this operator  (we could have just as easily written the x parameter in the body of the function as this->x).  The parameter list for our unary operator is empty because we are only operating on the current object.  If we were to write this as a non-member function its declaration would look something like this:

Vector3 operator- (const Vector3& a) { return Vector3(-a.x, -a.y, -a.z); }

Note that the const written after the parameter list in the class member function simply ensures that the function cannot make changes to the original object.  The same functionality is accomplished by the presence of the const keyword in the parameter list of the non-member function.  If you do wish the operator to make changes to the original object then you would simply remove the const in either of these places.

Binary/Comparison Operators:

Next let us observe the binary operations of addition and subtraction.

Vector3 operator- (const Vector3& rhs) const {
    return Vector3(x - rhs.x, y - rhs.y, z - rhs.z);
}
Vector3 operator+ (const Vector3& rhs) const {
    return Vector3(x + rhs.x, y + rhs.y, z + rhs.z);
}

As you can see their declarations are hardly any different from the unary operator except that they have an additional parameter which we have named rhs to indicate that it is the object that appears on the right-hand side of the operator.  Note that the parameter is passed as a constant reference.  We already discussed what purpose the const holds in this context, but why pass as reference?  Often when we pass an object by reference it is because we want to be able to make changes to the object within the body of the function, but in this case we pass it as constant to prevent that from happening.  So why do we do this?  The answer is simple.  Passing an object by value means that we have to take extra time to make a copy of the object that is passed.  Passing by reference allows us to skip that step by simply passing the address of the object, thus making our code more efficient.  Comparison operators generally work the same way with the exception that they simply return a boolean value.

Now let us take a look at our multiplication operator.

Vector3 operator* (const float& rhs) const {
    return Vector3(x * rhs, y * rhs, z * rhs);
}
friend Vector3 operator* (const float& lhs, const Vector3& rhs) {
    return rhs * lhs;
}

The first thing we notice is that we actually have two multiplication operator functions.  The first one looks just like our addition/subtraction operator declarations except that the parameter is of type float.  The second one on the other hand is actually a non-member function that we declare to be a friend of the Vector3 class to ensure that it has access to the Vector3 class’ private methods and variables.  Although this class does not have any private methods or variables we still need to declare this function as a friend because otherwise the compiler expects the function to have only one parameter.  But why do we need both of these functions in the first place?  Strictly speaking, we don’t need both unless we wish to ensure that scalar multiplication is a commutative property of our Vector3 class.  Our first function does a scalar multiplication operation for the case where we have a Vector3 object on the left and a scalar (float) on the right of our operator but would not work if we were to reverse the order.  That is why we need the second function to perform the operation when the order is reversed.  Note that we did not need to do the same thing for the addition operator despite it also being commutative because both the left and the right hand sides are of type Vector3.

Assignment Operators:

Next we will see how we can override the assignment operator.

Vector3& operator= (const Vector3& rhs)  {
        //Check for self-assignment
        if (this == &rhs)
            return *this;
        x = rhs.x;
        y = rhs.y;
        z = rhs.z;
        return *this;
    }

Most of the time we do not really need to override the assignment operator because the compiler generated constructor and assignment operator are usually sufficient.  But if our class contains pointers the default assignment operator can sometimes lead to problems because we end up with objects that have pointers to the same location.  To avoid these problems you will want to know how to override the assignment operator so that it makes a deep copy as well as how to make a copy constructor.  I will not be covering how to do either of these things in this post.  The example that I give here has no practical purpose since the default assignment operator does exactly the same thing.  However, there are two things worth mentioning if you ever do decide to overload the assignment operator.  The first is that, if you want your class to support chain assignment (see example below), the function should return the address of the current object.  The second is that you should always check for self-assignment before altering any data otherwise your class may end up releasing the resources that it is trying to copy from.

Compound assignment operators are generally simpler to understand.  They combine normal binary operations with an assignment operator.

Vector3& operator+= (const Vector3& rhs) {
    x += rhs.x;
    y += rhs.y;
    z += rhs.z;
    return *this;
}

Unlike normal binary operators they are generally meant to make changes to the original object, but like the assignment operator they usually return the address of the object.  This allows the programmer to write statements like the following:

a = b += c -= d *= e;  //example of chain assignment

Subscript/Function Call Operators:

Next we have the subscript operator.

float& operator[] (const int& i) {
    if (i < 0 || i > 2) throw std::out_of_range("Out of Vector3 range\n");
    return (i == 0) ? x : (i == 1) ? y : z;
}
const float& operator[] (const int& i) const {
    if (i < 0 || i > 2) throw std::out_of_range("Out of Vector3 range\n");
    return (i == 0) ? x : (i == 1) ? y : z;
}

Here I define it so that the subscript operator returns one of the vector components based on the integer value passed.  Notice however that once again we have two functions.  The first behaves just as we would expect.  The second one on the other hand is written as a constant function that returns a constant reference.  Here the const at the end of the second member function allows the function to be called even on an object that is defined as constant.  Without this function the programmer would not be able to access the contents of a constant object using the subscript notation.  The reason we return a constant reference is to ensure that the caller cannot modify the contents of our constant vector object.

If we were overloading the function call operator we would similarly wish to define two functions, one for constant objects and one for non-constant objects.  We do not override the function call operator in the Vector3 class, but something to keep in mind is that, unlike other operators, the function call operator can have as many parameters as the programmer likes.  An example where this might be useful is in a matrix class where the programmer wishes to look up a matrix element by its row and column.  You cannot do this with the subscript operator because it only takes one parameter, but it can be done in the following way:

class Matrix4x4 {
private:
    float data[16];
public:
    float& operator() (const int& row, const int& col) {
        return data[row + (col * 4)];
    }
    const float& operator() (const int& row, const int& col) const {
        return data[row + (col * 4)];
    }

    ...
};

Typecast Operators:

Operator overloading can even be used to define typecasting operations for our user-defined classes.  Suppose elsewhere we have defined a two-dimensional and a four-dimensional vector class and we want our compiler to know how to cast our Vector3 object into one of these types.  We can accomplish this in the following way:

operator Vector2() { return Vector2(x, y); }
operator Vector4() { return Vector4(x, y, z, 0.0f); }

Here we simply write the operator keyword followed by the type we want to cast our object into followed by open and close parentheses.  We do not need to define a return type since C++ assumes that we will return the correct type.  With the help of these functions we should be able write lines of code like the following without our compiler spitting out an error:

Vector2 v2 = Vector2(1.0f, 2.0f);
Vector3 v3 = Vector3(3.0f, 4.0f, 5.0f);
Vector4 v4 = Vector4(6.0f, 7.0f, 8.0f, 9.0f);
v2 = v3; //compiler implicitly typecasts to Vector2
v4 = v3; //compiler implicitly typecasts to Vector3

End of Lesson:

Well that is it for my lesson on operator overloading.  I hope the things you have learned here will be of use to you in designing your C++ applications.  If you are interested in reading some more of my postings, you may follow the links below:

 

Vectors Part 2: Programming in C++

In my last post I covered the basics of vector arithmetic.  In it I wrote about vector addition, subtraction, scalar multiplication, magnitude, normalization, dot products and cross products.  This time will we be learning about some more advanced uses of vectors in game programming.  Some of these operations you may recognize as methods of the Vector3 class of the Unity Game Engine.  Here I will be explaining how you may implement some of these methods for yourself.

I will be presenting the sample code in C++.  I chose this language largely because it supports the concept of operator overloading.  It is possible to adapt the code to be written in languages like Java by creating free or static member functions for operations like addition, subtraction and scalar multiplication.  But if you wish to know more about operator overloading in C++, you may visit my blog post on Operator Overloading.

Projection:

When we have two vectors \vec{a} and \vec{b} we can visualize the first vector \vec{a} as the sum of two vectors \vec{a}_1 and \vec{a}_2 where \vec{a}_1 is the vector component of \vec{a} parallel to vector \vec{b} and \vec{a}_2 is vector component of \vec{a} orthogonal to vector \vec{b}.  Because \vec{a}_1 is in the same (or opposite) direction as \vec{b} it is called the vector projection of \vec{a} onto \vec{b} or proj_{\vec{b}}\vec{a} and its magnitude is called the scalar projection of \vec{a} onto \vec{b} or comp_{\vec{b}}\vec{a}.  Similarly \vec{a}_2 is called the vector rejection of \vec{a} from \vec{b}.

Vector Projection Diagram

Sometimes in video games it is necessary to calculate one of these component vectors.  Fortunately, since \vec{a} = \vec{a}_1 + \vec{a}_2 we can easily calculate \vec{a}_2 in terms of \vec{a}_1.  So we just need to find \vec{a}_1.  We can find the length of \vec{a}_1 using the definition of \cos{\theta} where \theta is the angle between \vec{a} and \vec{b}.  We know that \cos{\theta} is adjacent over hypotenuse.  So we have:

\cos{\theta} = \frac{\|\vec{a}_1\|}{\|\vec{a}\|} \implies comp_{\vec{b}}\vec{a} = \|\vec{a}_1\| = \|\vec{a}\|\cos{\theta}

If we recall the geometric definition of the dot product we can simplify this equation to:

comp_{\vec{b}}\vec{a} = \|\vec{a}\| \|\hat{b}\|\cos{\theta} = \vec{a} \bullet \hat{b} = \frac{\vec{a} \bullet \vec{b}}{\|\vec{b}\|}

Now that we have its magnitude we can find \vec{a}_1 by multiplying this by the unit vector in the direction of \vec{b}.  So we get:

proj_{\vec{b}}\vec{a} = \vec{a}_1 = \|\vec{a}_1\|\hat{b} = (\frac{\vec{a} \bullet \vec{b}}{\|\vec{b}\|})(\frac{\vec{b}}{\|\vec{b}\|}) = \frac{\vec{a} \bullet \vec{b}}{\|\vec{b}\|^2}\vec{b} = \frac{\vec{a} \bullet \vec{b}}{\vec{b} \bullet \vec{b}}\vec{b}

Reflection:

Now that we know how to calculate the vector projection, we can now calculate the reflection of a vector.  This is useful in computer graphics for creating mirror effects.  To calculate the reflection of a vector we need only the vector \vec{v} that we are reflecting and the normal \hat{n} of the surface that our vector is reflecting off.  For simplicity we will assume that the normal vector is normalized.

Vector Reflection Diagram

We can see by the diagram that proj_{\hat{n}}\vec{r} is the same as proj_{\hat{n}}-\vec{v}.  Similarly, the projection of \vec{r} onto the plane whose normal is \hat{n} is the same as the projection of \vec{v} off the plane.  This projection can be found by simply subtracting proj_{\hat{n}}\vec{v} from \vec{v}.  So by summing the components together we get:

\vec{r} = proj_{\hat{n}}-\vec{v} + (\vec{v} - proj_{\hat{n}}\vec{v}) = (-\vec{v} \bullet \hat{n})\hat{n} + \vec{v} - (\vec{v} \bullet \hat{n})\hat{n} = \vec{v} - 2(\vec{v} \bullet \hat{n})\hat{n}

Orthonormalization:

To understand the process of orthonormalization, we first need to understand the concept of vector spaces and bases.  A vector space V is quite simply a set, whose elements are vectors, for which we have defined two operations:  vector addition and scalar multiplication.  One example of V would be the n-dimensional Euclidean space \mathbb{R}^n.  For the following operation we will be looking specifically at \mathbb{R}^3.  A basis of a vector space is a subset of vectors \vec{v}_1, \dots, \vec{v}_n in V which span the vector space and are linearly independent, that is \vec{v}_i \neq k\vec{v}_j for any scalar constant k when i \neq j.  We say that a basis spans a vector space so long as any vector \vec{v} in the vector space can be uniquely written as:

\vec{v} = a_1\vec{v}_1 + a_2\vec{v}_2 + \dots + a_n\vec{v}_n

for some set of scalar values a_1, a_2, \dots , a_n.  An orthonormal basis is simply a basis whose vectors are normalized and whose inner product is \langle \vec{v}_i, \vec{v}_j \rangle = 0 when i \neq j.  The inner product is just a generalization of the dot product as it is applied to a set of vectors.  So what \langle \vec{v}_i, \vec{v}_j \rangle = 0 means is that all the vectors in the set are mutually orthogonal to one another.  For example the standard basis of the Cartesian coordinate system defines a point in 3D space by:

\vec{A} = x\hat{i} + y\hat{j} + z\hat{k} = x \begin{pmatrix}1 \\ 0 \\ 0\end{pmatrix} + y \begin{pmatrix}0 \\ 1 \\ 0\end{pmatrix} + z \begin{pmatrix}0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix}x \\ y \\ z\end{pmatrix}

where the set of unit vectors (\hat{i}, \hat{j}, \hat{k}) are an orthonormal basis representing the x, y and z coordinates of Cartesian space.

Orthonormalization is the process by which we take a vector space basis and transform it into an orthonormal basis.  The following code shows how this can be achieved in two and three dimensions using vector rejection (projection in the orthogonal direction).

//OrthoNormalize in two dimensions
void OrthoNormalize(Vector3& normal, Vector3& tangent)  {
    normal.Normalize();
    tangent = (tangent - Vector3::Project(tangent, normal)).normalized();
}

//OrthoNormalize in three dimensions
void OrthoNormalize(Vector3& normal, Vector3& tangent, Vector3& binormal) {
    OrthoNormalize(normal, tangent);
    binormal = binormal - Vector3::Project(binormal, normal);
    binormal = (binormal - Vector3::Project(binormal, tangent)).normalized();
}

Linear Interpolation (Lerp):

Sometimes in games we will need to be able to find a point that is some fraction of the way between two  points.  The formula to achieve this is quite simply as we would use the exact same formula that we would use for two scalar values (See Game Programming: Math Libraries).  The formula is c = a(1 - t) + bt.  The only difference is that instead of scalar values we are using vectors for a and b.  Like with scalar values it is often a good idea to clamp our t value to somewhere between 0 and 1 so as to never overshoot the endpoints.  A code sample might look like this:

Vector3 Lerp(Vector3 a, Vector3 b, float t) {
    t = Clamp01(t);
    return a * (1 - t) + b * t;
}

Spherical Linear Interpolation (Slerp):

Standard linear interpolation works nicely when we are interested in interpolating between two points, but what if our vectors are used to represent directions instead.  In this case it might be more practical to use spherical interpolation.  Spherical interpolation allows us to smoothly interpolate between two orientations as if we are moving along the surface of a circle or sphere.  The general equation for the spherical interpolation of vectors is defined as:

\vec{v}' = \frac{\sin (1 - t)\theta}{\sin \theta}\vec{v}_1 + \frac{\sin t\theta}{\sin \theta}\vec{v}_2

However, when we write our function we need to perform a check to see whether the two input directions are parallel to one another.  This case is special because we do not know about which axis we should rotate our direction vector.  We can handle this situation in one of two ways: we can either do nothing and return one of the two input vectors or we can simply plug our parameters into our Lerp function and return the result.  How we implement it depends on how we want this function to behave.  Play around with it and see which implementation works best for you.  The following code sample uses Lerp to handle the special case:

Vector3 Slerp(Vector3 from, Vector3 to, float t) {
    float dot = Dot(from.normalized(), to.normalized());
    if (Mathf.Approximately(abs(dot), 1.0f, 1.0e-6)) {
        // use linear interpolation
        return Lerp(from, to, t);
    }

    float theta = acos(dot);
    float temp = sin(theta);
    return from * (sin(theta * (1.0 - t)) / temp) + to * (sin(theta * t) / temp);
}

For more information on the proper use of linear interpolation you can read the following blog post titled How to Lerp like a Pro written by Robert Utter.

Move Towards:

While linear interpolation certainly has its uses, it is sometimes better to procedurally step a vector towards some target point as opposed to trying to guess what fraction of the way between two points an object should be at a given time.  In this case we want a way to find our new position while making sure that we do not overshoot our target.  We can do this in much the same way we do it for scalar values (See Game Programming: Math Libraries).  To do this we simply compare our expected displacement to the actual distance between our current position and our target.  If our expected move distance is greater than the actual distance to our target then we just return our target vector.  Here is an example implementation:

Vector3 MoveTowards(Vector3 current, Vector3 target, float maxDistanceDelta) {
    Vector3 delta = target - current;
    float mag = delta.magnitude();
    return (maxDistanceDelta >= mag) ?
        target : current + maxDistanceDelta * (delta / mag);
}

One nice thing about this function is we can also use it to move a position vector away from a certain point by simply inputting a negative value for the maxDistanceDelta parameter.

Rotate Towards:

Similarly we may find that we want to procedurally step a direction vector towards a certain orientation and magnitude.  The magnitude is easy enough to step towards since we can simply use a MoveTowards function that works for scalar values instead of vectors.  Unfortunately, to step the rotation is a bit more complicated.  While it is not to hard to handle the cases where we have overshot our target rotation, the rest of the time rotating our vector is best handled using quaternions:

Vector3 RotateTowards(Vector3 current, Vector3 target,
        float maxRadiansDelta, float maxMagnitudeDelta) {
    float targetMag = target.magnitude();
    float currentMag = current.magnitude();
    Vector3 targetNorm = target / targetMag;
    Vector3 currentNorm = current / currentMag;
    float newMagnitude = Mathf.MoveTowards(currentMag, targetMag, maxMagnitudeDelta);

    float dot = Dot(currentNorm, targetNorm);
    if (Mathf.Approximately(abs(dot), 1.0f, 1.0e-6)) {
        // only change the magnitude
        return currentNorm * newMagnitude;
    }

    //check if we overshoot our rotation
    float angle = acos(dot) - maxRadiansDelta;
    if (angle <= 0.0f) {
        return targetNorm * newMagnitude;
    } else if (angle >= Mathf.PI) {
        // if maxRadiansDelta is negative we may be rotating away from target
        return -targetNorm * newMagnitude;
    }

    Quaternion q = Quaternion::AngleAxis(maxRadiansDelta, Cross(current, target));
    Vector3 p = q * current;
    return p.normalized() * newMagnitude;
}

In the code above we construct a Quaternion  object using the angle and axis of the rotation we wish to apply to our vector.  Quaternions have the special property that when multiplied by a vector the result is a rotated direction vector.  So we simply multiply our vector object by our Quaternion object and then set its magnitude before returning our final direction vector.  For more on Quaternion rotation visit my blog pages at:

[not yet available]

or see the the blog post titled Understanding Quaternions by Jeremiah van Oosten.

Smooth Damping:

MoveTowards works to move a vector towards a desired goal and then come to a sudden stop when the target is reached.  This often results in some jerky and unexpected behavior, especially when our velocity is relatively large.  Sometimes we may want our object to decelerate as we get closer to our target position.  This is the purpose of SmoothDamp.  We will be using the formula for a critically-damped spring and its derivative as the model for this algorithm.  The formula is:

x(t) = x_d + ((x_0 - x_d) + (v_0 + \omega(x_0 - x_d))t)e^{-\omega t}

and its derivative is:

v(t) = (v_0 - (v_0 + \omega(x_0 - x_d))\omega t)e^{-\omega t}

In the formulas above  x_0 and v_0 are the initial position and velocity, x_d is our target position, t is our elapsed time and \omega is the frequency of the spring which can be represented as 2 divided by the smooth time.  To understand how we get these formulas you can read my posting on Game Programming: Math Libraries.

Now we just need to adapt this formula for smoothing vectors.

Vector3 SmoothDamp(Vector3 current, Vector3 target, Vector3& currentVelocity,
        float smoothTime, float maxSpeed, float deltaTime) {
    // check if we are already at target;
    if (current == target) return target;

    smoothTime = Mathf.Max(0.0001f, smoothTime);
    float omega = 2.0f / smoothTime;
    float x = omega * deltaTime;
    float exp = 1.0f / (1.0f + x + 0.48f * x * x + 0.235f * x * x * x);
    Vector3 delta = current - target;
    float mag = delta.magnitude;
    float maxDelta = maxSpeed * smoothTime;

    // ensure we do not exceed our max speed
    float deltaX = Mathf.Min(mag, maxDelta);
    delta = (delta * deltaX) / mag;

    Vector3 temp = (currentVelocity + omega * delta) * deltaTime;
    currentVelocity = (currentVelocity - omega * temp) * exp;
    Vector3 result = current - delta + (delta + temp) * exp;

    // ensure that we do not overshoot our target
    if ((target - current).sqrMagnitude <= (result - current).sqrMagnitude) {
        result = target;
        currentVelocity = Vector3::zero;
    }
    return result;
}

Summary:

We have now covered a preponderance of the things that we can do with vectors, but they are not the only concept from linear algebra important to game programming.  Next time we will be covering the basics of matrices and how they are applied to three dimensional transformations of game objects and setting up the projection plane of our game camera.

Resources:

Lay, David C.  (2005).  Linear Algebra and its Applications Third Updated Edition.  Addison Wesley.  ISBN 978-0-321-28713-4.

External Links:

Orthonormal Basis

Scalar and Vector Projections pdf

Vectors Part 1: An Introduction to Linear Algebra

The first thing any good game programmer needs to understand when creating either 2D or 3D platform games is a basic understanding of linear algebra.  The first thing we need to know about linear algebra is how to use vectors.  Everything from the complex calculations of rigidbody mechanics to the simple positioning of a button in a graphical interface requires the use of vectors.  A vector is a geometric object that is defined as having a direction and a magnitude (or length).  How vectors are perceived often depends on whether the vector is a bound vector or a free vector.  A bound vector is defined by having an initial point and a terminal point while a free vector has no definite start or end point.

Vectors themselves are generally categorized into two types: position vectors and direction vectors.  Position vectors represent a particular point in space.  However they are considered a form of bound vector since they can also be visualized as an arrow starting at the origin whose terminal point is its given position in space.  Direction vectors are simply a form of free vector, since they generally do not have any one start or end point.  Velocity, acceleration and forces are some of the most commonly used direction vectors.  Rays are different from either of these types of vectors since they can be considered a kind of semi-bound vectors.  That is to say that they have a definite start point and a direction, but no specific end point (See Raycasting).  To understand how useful these constructs are, let us look at some of the operations that we can perform on vectors.  For the sake of consistency, I will use capital letters to represent position vectors and lowercase letters to represent direction vectors.

Scalar Multiplication of Vectors:
A scalar is simply a one-dimensional vector and is wholly defined by its magnitude.  Time is a common example of a scalar value often found in game logic.  Often in games we will want to be able to update the position of an object based on its current velocity.  To do that we will need to calculate the displacement.  We can get this displacement vector easily through scalar multiplication.  All we have to do is multiply each of the components of the velocity vector by the scalar value of time.  In the following example \Delta\vec{x} is the displacement vector, \vec{v} is the velocity vector, and t is the time elapsed since the last update:

\Delta\vec{x} = t\vec{v} = t * \begin{pmatrix}v_x \\ v_y\end{pmatrix} = \begin{pmatrix}t * v_x \\ t * v_y\end{pmatrix}

This property is both commutative, i.e. t\vec{v} = \vec{v}t, and distributive, meaning that:

s(\vec{u} + \vec{v}) = s\vec{u} + s\vec{v}      and      (s + t)\vec{u} = s\vec{u} + t\vec{u}

Vector Addition:

Vector Addition Diagram

Here we have two vectors \vec{a} and \vec{b} which sum to form a third vector \vec{c}.  We see \vec{c} is the vector we obtained when we place the vectors \vec{a} and \vec{b} head to tail and draw a new vector from the free tail to the free head.  It also represents the diagonal of the parallelogram formed by \vec{a} and \vec{b}.  This is achieved by simply adding the individual components of the first vector to the corresponding components of the second vector.   In two dimensions we would get:

\vec{a} + \vec{b} = \begin{pmatrix}a_x \\ a_y\end{pmatrix} + \begin{pmatrix}b_x \\ b_y\end{pmatrix} = \begin{pmatrix}a_x + b_x \\ a_y + b_y\end{pmatrix} = \begin{pmatrix}c_x \\ c_y\end{pmatrix} = \vec{c}

where \vec{a} = (a_x, a_y) and \vec{b} = (b_x, b_y).  Vector addition is both commutative and associative.  Associative means that:

(\vec{a} + \vec{b}) + \vec{c} = \vec{a} + (\vec{b} + \vec{c}).

This is how we can apply changes in position due to velocity as well as changes in velocity due to acceleration.

Vector Subtraction:
Suppose we have two points \vec{A} and \vec{B} and we want to find the displacement vector \overrightarrow{AB} from a point \vec{A} to point \vec{B}.  We can achieve this by simply subtracting the vector components of initial point \vec{A} from the components of the terminal point \vec{B} like so:

\overrightarrow{AB} = \vec{B} - \vec{A} = \begin{pmatrix}b_x \\ b_y\end{pmatrix} + \begin{pmatrix}a_x \\ a_y\end{pmatrix} = \begin{pmatrix}b_x - a_x \\ b_y - a_y\end{pmatrix}

Vector Subtraction Diagram
From the picture we see that vector subtraction can be represented as a compound operation of both scalar multiplication and vector addition by negating the first vector (multiplying it by -1) and taking the sum of -\vec{A} and \vec{B}.

Magnitude:
Sometimes it is important to know how long a vector is along its direction.  To do this we simply plug the vector components into the Pythagorean Theorem.  I will use the notation \|\vec{v}\| to represent the magnitude or length of a vector \vec{v} with components v_x and v_y.  So by the Pythagorean Theorem:

\|\vec{v}\|^2 = v_x^2 + v_y^2 \implies \|\vec{v}\| = \sqrt{v_x^2 + v_y^2}

The Pythagorean Theorem also works to find the magnitude of higher dimension vectors as well. For example, in three dimensions we have:

\|\vec{v}\|^2 = v_x^2 + v_y^2 + v_z^2 \implies \|\vec{v}\| = \sqrt{v_x^2 + v_y^2 + v_z^2}

This is useful because it gives us the absolute scalar distance between the vector’s initial and terminal point.

Normalization:
When we are dealing with directions, sometimes it is helpful to make sure that they have unit length (a magnitude of exactly one unit of measurement).  Suppose we have a unit direction vector and a scalar velocity.  To get the velocity as a vector we simply multiply the direction vector by the scalar velocity.  But how do we get a normalized vector?  Simple, we merely divide each of the vector components by its magnitude.  I shall use the notation \hat{v} to denote a normalized vector.  So the formula for a normalized vector is simply:

\hat{v} = \frac{\vec{v}}{\|\vec{v}\|} = \begin{pmatrix}v_x / \sqrt{v_x^2 + v_y^2} \\ v_y / \sqrt{v_x^2 + v_y^2}\end{pmatrix}

Dot Product:
The dot product  is one of the most useful operations in linear algebra and has many practical uses in making video games.  It is often called the scalar product because it produces a numerical quantity.    The dot product of two vectors \vec{a} and \vec{b} is defined algebraically for three dimensional vectors by the following formula:

\vec{a} \bullet \vec{b} = a_x b_x + a_y b_y + a_z b_z

Not very interesting at first, although it is worth mentioning that the dot product of a vector with itself is equivalent to the square of its magnitude.  Also note that this property is not only commutative, but also distributive. That is:

(\vec{a} + \vec{b}) \bullet \vec{c} = \vec{a} \bullet \vec{c} + \vec{b} \bullet \vec{c}

However, where this formula draws meaning from is its geometric definition.  Geometrically the dot product is defined as:

\vec{a} \bullet \vec{b} = \|\vec{a}\| \|\vec{b}\| \cos{\theta}

where \theta is the minimum angle between the vectors \vec{a} and \vec{b}.  The angle \theta holds significant importance in a variety of situations from vector projection to collision detection.  We can calculate the angle quite simply by rearranging the formula to get:

\theta = \arccos(\frac{\vec{a} \bullet \vec{b}}{\|\vec{a}\| \|\vec{b}\|})

If \vec{a} and \vec{b} are normalized vectors, this formula simplifies to:

\theta = \arccos(\hat{a} \bullet \hat{b})

However, there are many cases where it is not necessary to calculate the angle since the dot product is sufficient.  This is convenient to programmers since the dot product is a much cheaper and more efficient operation than say the inverse cosine and anything that saves CPU cycles is a great boon to game programmers.

Cross Product:
The cross product is used in game logic in a variety of ways from game camera projection to quaternions.  Since the cross product is most commonly used in terms of three dimensional space I will not cover how the cross product is applied to higher order vectors, despite the fact that their are applications for higher order cross products in game logic and computer graphics.  Also keep in mind that all the vector operations covered thus far can be easily expanded to higher dimensions as well but are typically restricted to 2-4 dimensions (4 dimensional vectors are most commonly used in shaders to represent RGBA values).

In general the cross product is a binary operation used to calculate a vector which is orthogonal to each of its input vectors.  In the more practical terms of three dimensional space, it takes two vectors \vec{a} and \vec{b} and forms a third vector \vec{c} which is perpendicular to both \vec{a} and \vec{b} and thus normal to the plane that contains \vec{a} and \vec{b}.

An important note to make is that the cross product of two vectors is NOT commutative.  The order does matter in determining which direction the resulting vector points.  In fact, the vector products \vec{a} \times \vec{b} and \vec{b} \times \vec{a} are related in the following way:

\vec{a} \times \vec{b} = - \vec{b} \times \vec{a}

So although they have equal magnitude they point in opposite directions.  Additionally, how we actually calculate the cross product of two vectors depends on whether we are using left-handed or right-handed coordinates.  It is important to understand this distinction because it depends on which computer graphics API you use as to which coordinate system you should use to write your cross product implementation.  DirectX, for example, uses a left-handed coordinate system, whereas OpenGL uses a right-handed coordinate system.

A right-handed coordinate system is simply a three dimensional coordinate system that satisfies the right-hand rule.  The right-hand rule states that the orientation of the vectors’ cross product is determined by placing the x-axis and the y-axis tail-to-tail, flattening the right hand, extending it in the direction of the x-axis, and then curling the fingers in the direction that the angle the y-axis makes with the x-axis.  The thumb then points in the direction of the z-axis.  The left-hand rule simply follows the same procedure but with the left hand (See below).

The cross product in right-handed coordinates is defined as follows:

\vec{a} \times \vec{b} = \begin{pmatrix} a_y b_z - a_z b_y \\ a_z b_x - a_x b_z \\ a_x b_y - a_y b_x \end{pmatrix}    (right-handed)

In left-handed coordinates we get:

\vec{a} \times \vec{b} = \begin{pmatrix} a_z b_y - a_y b_z \\ a_x b_z - a_z b_x \\ a_y b_x - a_x b_y \end{pmatrix}    (left-handed)

Summary:

With this you should have a basic understanding of vector math and some of the ways it can be applied to video games.  In my next post I will cover some more advanced things that can be accomplished with vectors along with some sample code written in C++.  Click here for Part 2.

Resources:

Lay, David C.  (2005).  Linear Algebra and its Applications Third Updated Edition.  Addison Wesley.  ISBN 978-0-321-28713-4.

External Links:

Linear Algebra for Game Developers

Vector Math

Captain Polly’s Booty

Captain Polly’s Booty is a side-scrolling platform game originally based on the game Super Mario Bros. 3 for the NES. Super Mario Bros. 3 was the first video game I ever played and I have loved video games ever since. That is why for my college course on Game Programming I decided to create a platform game using one of my favorite sprites from Super Mario Bros. 3 as the model for my player character. Not weighted to the ground like in most games, the player is free to soar the skies as they guide Captain Polly in the search for his stolen loot.

The goal of the game is simple – to collect all of the crackers stolen from Captain Polly’s private collection. Though free to fly most places, the Captain must beware of strong winds that would push him into dangerous enemies and traps. Enemies may be disposed of with heavy objects dropped from above, but be careful because carrying heavy objects weighs him down. He must flap his wings even harder when laden, however being weighted down can sometimes be to his advantage.

Captain Polly’s Booty is written in C++ and uses Open GL and SDL libraries as well as standard C++ libraries. I built the game engine from scratch, but used the source documentation for the Unity3D Game Engine to model the objects and libraries that make up the core functionality of my engine. The application is single threaded and all the in-game logic is done within the main game loop.

At the start of each game loop the application stores the current input and time data into the static Input and Time objects so that it may be accessed by the behavior scripts attached to the various game objects. Then the game loop calls the Update functions of all the Game Objects and their Components. The next step is to update the physics portion of the game engine and to resolve any collisions that may have occurred due to a previous update. The physics runs on a different timeline than the rest of the updates and only updates if a specific amount of time has passed, but still runs on the same thread as the main game loop. Next the engine handles any events that have been added to the event queue. Lastly the engine draws the scene after sorting the various renderer objects according to their draw layer.

Many of the objects that I created for this engine are based closely on the Unity Engine. Some of these include the use of static Input and Time objects for retrieving up-to-date system information. Another element that I based off of Unity was the hierarchical relationship between Objects, Game Objects, and Components. I also put my math skills to the test when I created my own Math, Matrix, Vector, Transform, and Physics components and libraries. Among the other components that I have implemented are Behaviors, Animations, Colliders and Renderers.

While the Animation and Renderer objects are extremely stripped down for the sake of 2D drawing, the Colliders and Physics libraries should (theoretically) be easily expandable to apply to 3-dimensional space. Using support functions provided by the Collider objects, the Physics library uses the Gilbert Johnson Keerthi (GJK) collision detection algorithm as explained by Casey Muratori on mollyrocket.com. Click here to visit his blog. I also use the Expanding Polytope algorithm to determine collision depth and normal. For more on the mathematical concepts I used in my game engine please visit the following pages:

Game Programming: Math Libraries

Vectors Part 1: Introduction to Linear Algebra

Vectors Part 2: Programming in C++

Matrices and Transformations (Not yet available)

Quaternions (Not yet available)

Raycasting (Not yet available)

GJK Collision Detection (Not yet available)

Expanding Polytope (Not yet available)

Shapecasting (Not yet available)