Category: Math and Physics

Game Programming: Math Libraries

Most game engines define their own custom set of math libraries for use in their games.  Unity, for example, has defined its own Mathf library for  performing common operations on floating point numbers.  You may wonder what is wrong with just using System.Math as apposed to UnityEngine.Mathf.  Some people use Mathf instead of Math because it saves them the trouble of having to do double to float conversions.  However, in most cases Math is considered faster than Mathf.  Standard math libraries are certainly convenient and will most often be more efficient than any math libraries that you roll yourself, so why go to the trouble of implementing a custom library.  The problem with standard math libraries is that they may not always have the kinds of functions that are most important to game programming.  Other times it may be better to forgo accuracy in favor of efficiency by replacing expensive operations such as cos, sin and ex with less expensive and less accurate approximations of these functions.  In this article I will discuss some of the most commonly used functions found in Unity’s Mathf library and how you may implement them yourself.

Approximately:

Due to the nature of floating point numbers it is very common for operations performed on them to result in some form of rounding error.  This can lead to problems when trying to compare the equality of floating point numbers.  For example we may end up comparing a number like 2.0 to a number like 1.999999999.  For all effects and purposes these numbers are practically the same but when we check for equality we get a false statement.  This is why we sometimes need to take into account some margin of error when comparing floats.  This is exactly what the Mathf.Approximately function does.  It can be implemented in the following way:

bool Approximately(float a, float b) {
    return Abs(a - b) < Epsilon;
}

Here we take the absolute value of the difference between the two input variables and check if it is less than some arbitrarily small value called Epsilon.  It should be noted however that although some standard math already have a predefined value for epsilon, it may actually be better for the programmer to define their own value for epsilon since the standard math library’s definition of epsilon may be too small to make any difference from straight equality comparison.  An alternative approach could also be to define an Approximately function that takes the tolerance as a parameter and just replace Epsilon with this tolerance value.

Clamp:

Clamp is such a useful tool that it is any wonder why it is not a common tool found in every math library, especially since it is so simple to write.  Perhaps it is just so simple that some programmers feel it is not necessary to include it in a standard math library.  Simply put, clamp ensures that its input value lies within a certain range of values.  If the number lies between the given range it simply returns the number itself, otherwise it returns the nearest endpoint.  An example where this might be useful is in the case where the programmer wants to ensure that a player character never goes past the edges of the screen.  All the programmer has to do is Clamp the player’s position to within the screen boundaries.  Clamp can be implemented in the following way:

float Clamp(float value, float min, float max) {
    return (value < min)? min : (value > max)? max : value;
}

This function is so useful that Unity has even included a Clamp01 function that specifically clamps a floating point value to between 0 and 1.

Linear Interpolation (Lerp):

Linear interpolation is the process by which we find a point somewhere between two input values.  We can visualize it as a line drawn between two points.  Using the equation for a line we can write the formula for the desired value y as y = a + (b - a)x where a and b are the start and end values respectively and x represents what fraction of the way we are between our two values.  Note that we only get a value between a and b when x lies within the range [0, 1]; any other value for x results in some value outside the interval [a, b].  We also see that y = a when x = 0 and y = b when x = 1.  However, to avoid rounding error caused by floating point arithmetic, it is best to rewrite the equation as y = a(1 - x) + bx (this ensures that y = b when x = 1).  Depending on how you want your Lerp function to behave for certain values of x you may wish to clamp it to between 0 and 1 so as to never overshoot the endpoints.  However, in some rare cases it may be better to leave the value unclamped.  The following code sample shows how we may implement the former:

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

For more help learning the proper use of linear interpolation, see How to Lerp like a Pro by Robert Utter.

Move Towards:

While linear interpolation certainly has its uses, it is sometimes not entirely practical since it requires the programmer to know what point we started at and what fraction of the way between the two points we are at a given time.  But suppose instead we want to procedurally step some value towards some target using some kind of displacement value.  We want a way to find our new value while making sure that we do not overshoot our target.  To do this we simply compare our expected displacement to the difference between our current value and our target value.  If our expected displacement is greater than the actual distance to our target then we just return our target value.  Here is an example:

float MoveTowards(float current, float target, float maxDelta) {
    float delta = target - current;
    return (maxDelta >= delta) ? target : current + maxDelta;
}

Note that in the implementation above a negative value of maxDelta will cause our output to procedurally step away from  our target value.

Smooth Damp:

While MoveTowards generally serves its intended purpose it can often result in game mechanics that look somewhat jerky since it forces something to come to a sudden stop once it reaches its goal.  If we want our game to look somewhat cleaner we need to apply smoothing to our calculations.  One way that we can apply smoothing is to apply some kind of S-curve to give us that smooth ease-in/ease-out motion.  One commonly used formula is x = 6t^5 - 15t^4 + 10t^3 which gives us such an S-curve and can be used with little computing cost.

C2 S-curve

Another technique to achieve smoothing is through exponential decay.  This is a kind of ease-out method of smoothing and can be accomplished by the statement x = x + (desiredX - x) * 0.1f * timeDelta where timeDelta is the time step between updates.  The advantage of this type of smoothing is that you can smooth toward a changing target and you do not need to know how much time has elapsed since the start.  However, the problem with this type of smoothing is that the initial motion is sudden.

Exponential Decay Diagram

The approach we will be using, however, will rely on the model for a critically damped spring.  This model fixes the problem we have with the exponential decay model by maintaining the ease-in property found in the S-curve.

Crtically Damped Spring Diagram

A spring will always try to maintain a certain length by exerting a force that pushes it towards that desired length.  Without damping this system will oscillate back and forth past the desired length forever.  We say the system is critically damped when it returns to equilibrium in the least possible amount of time.  We can write the equation for the force acted on the spring as F = -k(x - x_d) - bv where k is the spring constant, x_d - x is the displacement from our desired position, b is the damping coefficient and v is the velocity of the end of the spring that works to slow the spring down.  Using Newton’s second law of motion, F = ma, and writing the velocity and acceleration as the first and second derivatives of the position, we can obtain the ordinary differential equation (ODE):

m\frac{d^2x}{dt^2} + b\frac{dx}{dt} + kx = kx_d    (1)

The next step requires us to know how to solve for an equation of x.  The above ODE will have a solution of the form x(t) = x_p(t) + x_c(t) where x_p(t) is a particular solution of the equation and x_c(t) is the complementary solution of the associated homogeneous DE.  We see that the particular solution is of the form x_p(t) = A where A is a constant since the right side of Equation 1 is constant.  By taking the first and second derivatives of x_p(t) and plugging them into Equation 1 we see that A = x_d.

That was our particular solution; now let us find our complementary solution.  The homogeneous DE gives us the characteristic equation mr^2 + br + k = 0 which has the roots:

r = \frac{-b \pm \sqrt{b^2 - 4mk}}{2m}

It can be shown that the system will be critically damped when our equation has the real repeated roots r = -\sqrt{\frac{k}{m}} which only occurs when b^2 = 4mk.  We can use this to simplify Equation 1:

\frac{d^2x}{dt^2} + 2\omega\frac{dx}{dt} + \omega^2(x_d - x) = 0 where \omega = \sqrt{\frac{k}{m}}    (2)

In the above formula \omega is the spring’s natural frequency and represents the stiffness or strength of the spring.  But now we also have our complementary solution which is x_c(t) = (c_0 + c_1t)e^{-\omega t}.  So our general solution is:

x(t) = x_d + (c_0 + c_1t)e^{-\omega t}

Solving for the constants c_0 and c_1 using the initial conditions x(0) = x_0 and x'(0) = v_0 gives us the actual solution:

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

This formula now tells us everything we need to calculate the new position and by taking the derivative we can find the new velocity of the object after after this time step:

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

Now the only parameters we need for our smoothing function are our current position and velocity, our target position our elapsed time and finally our smoothness factor \omega.  But how do we figure out what we should use for our smoothness factor?  It would be much more intuitive to control our function based on how long we want it to take to reach equilibrium.  If we define this smooth time as being the expected time to reach the target when at maximum velocity, then we solve for it quite simply by setting the acceleration to zero and the maximum velocity to \frac{x_d - x_0}{t_{sm}} where t_{sm} is the smooth time and plugging these values into Equation 2.  We then see that \omega = \frac{2}{t_{sm}}.

One final note before we write our smoothing function is that Equation 3 and 4 contain e^x.  We talked before about how operations such as these are expensive so the following code shows a polynomial that can be used to approximate e^x.  While I do not know exactly how this polynomial is produced, I would hazard a guess and say that it is probably constructed by approximating a higher order Taylor series polynomial down to a third order polynomial.  Finally to make our function exactly like the SmoothDamp function of Unity’s Math library we also need to clamp the speed according to some defined max speed.

float SmoothDamp(float current, float target, float& currentVelocity, float smoothTime,
        float maxSpeed = Infinity, float deltaTime = Time.deltaTime) {
    smoothTime = Max(0.0001f, smoothTime);
    float omega = 2.0f / smoothTime;
    float x = omega * deltaTime;
    float exp = 1.0f / (1.0f + x + 0.48 * x * x + 0.235 * x * x * x);
    float deltaX = target - current;
    float maxDelta = maxSpeed * smoothTime;

    // ensure we do not exceed our max speed
    deltaX = Clamp(deltaX, -maxDelta, maxDelta);
    float temp = (currentVelocity + omega * deltaX) * deltaTime;
    float result = current - deltaX + (deltaX + temp) * exp;
    currentVelocity = (currentVelocity - omega * temp) * exp;

    // ensure that we do not overshoot our target
    if (target - current > 0.0f == result > target) {
        result = target;
        currentVelocity = 0.0f;
    }
    return result;
}

Resources:

Kirmse, Andrew.  (2004).  Game Programming Gems 4.  Charles River Media.  ISBN 9781-58450-295-1.

Zill, Dennis G.  (2009).  A First Course in Differential Equations with Modeling Applications.  Brooks Cole.  ISBN 978-0-495-10824-5

External Links:

Critically Damped Spring Smoothing

How to Lerp like a Pro

Unity Scripting API: Mathf

Unity Forum: Formula behind SmoothDamp

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