G-Engine #7: Vectors

We have added a basic math library to the 3D engine, but we’re still missing several fundamental mathematical building blocks to move forward and build full-fledged 3D environments. In particular, I want to implement Vectors, Matrices, and Quaternions. This post will cover Vectors, which enable the engine to represent important spacial concepts such as “position” and “direction”.

Before we talk about coding vectors, we need to understand what vectors are and what they can do. This section provides a “crash course” in vectors and vector operations. If you’re already familiar with vectors and just want to read about coding them, skip down to Writing a Vector Class.

Coordinate Systems

Let’s start by stating something obvious: in video games (and the real world), objects have different positions! When you play Pac-Man, the ghosts and Pac-Man each have different positions in the maze. When you’re driving in the real world, your car has a different position compared to other cars and stationary objects around you.

The positions of objects are important for both rendering and gameplay reasons. As you might expect, an object’s position affects where it renders on screen. And gameplay events are often tied to position - if Pac-Man’s position is too near to a ghost’s position, Pac-Man will die (unless he has eaten power pellet).

In video games, we represent object positions relative to a coordinate system. A coordinate system is defined by its origin and its axes. In 2D, there are horizontal and vertical axes, which we refer to as the x-axis and y-axis respectively. In 3D, we have an additional “depth” axis (often called z-axis).

2D and 3D Coordinate Systems

In 2D, the x-axis is always horizontal and the y-axis is always vertical. In 3D, different engines use different conventions! For example, some engines use z-axis for depth, others use y-axis for depth. We’ll discuss this more in a future post.

We can define the positions of objects relative to a coordinate system’s origin using cartesian coordinates.

For example, an object that is 2 units from the origin on the x-axis, -4 units from the origin on the y-axis, and 10 units from the origin on the z-axis can be said to have the position (2, -4, 10).

The origin of a coordinate system is always at (0, 0) in 2D or (0, 0, 0) in 3D. This might seem obvious, but it’s worth pointing out!

We can also define offsets between objects using cartesian coordinates. For example, if one object is positioned at (3, 4, 2) and another object is at (2, 5, 5), we can calculate that the offset from the first to second object is (-1, 1, 3).

Given an offset between two objects, you can also calculate the distance between them - we’ll discuss that in a bit. Obviously, if two objects have the same position, the offset between the them will be (0, 0, 0) and they are occupying the same point in 3D space!

Vectors

We’ve established that we can define the positions of objects and the offsets between objects in a 3D coordinate system with 3 numbers (for the x-axis, y-axis, and z-axis). A game engine could potentially store these numbers as three float variables.

However, a vector is a convenient way to group those numbers together in a meaningful way and treat them as one consolidated object. Vectors also define a variety of operations that make them easier and more convenient to use than separate float values.

At its core, a vector is just a collection of numbers. A 2D vector has 2 numbers, a 3D vector had 3 numbers, a 4D vector has 4 numbers, and so on. We could write very simple 2D & 3D vector structs in C++ like this:

struct Vector2
{
    float x;
    float y;    
};

struct Vector3
{
    float x;
    float y;
    float z;
};

Vectors convey displacement along coordinate system axes. A 2D vector with the values (2, 4) conveys a displacement of 2 units along the x-axis and 4 units along the y-axis. A 2D vector (-10, 6) conveys displacement of -10 units along the x-axis and 6 units along the y-axis. The two numbers are often called the vector’s x-component and y-component.

For 3D, we simply add an additional component to the vector. A 3D vector (5, 2, -4) conveys a displacement of 5 units on the x-axis, 2 units on the y-axis and -4 units on the z-axis. As you might guess, that additional value is the z-component of the vector.

We can represent vectors graphically by drawing them in a coordinate system. To graphically represent the vector (4, 2), pick any arbitrary point to start at, then locate the point that is 4 units to the right (along the x-axis) and 2 units up (along the y-axis). Draw a line between those two points.

To differentiate between (4, 2) and (-4, -2), we draw an arrow at one end of the line to represent the direction of the vector. We call the end with the arrow the head and the other end the tail.

Two Vectors

A vector’s components convey direction and magnitude. Changing a vector’s components will change the vector’s magnitude, direction, or both.

For example, the vectors (-1, 0) and (1, 0) point in exactly opposite directions but have the same magnitude. Similarly, (1, 0) and (8, 0) point in the same direction (both down the positive x-axis), but the latter is eight times longer - it has a larger magnitude.

When using vector variables in mathematical equations, the variables representing vectors are usually bolded to differentiate them from non-vectors (also called scalars). For example, b=sa shows a vector a multiplied by a scalar s, resulting in the vector b.

Vectors as Points

If two vectors have equal components, then those vectors are equal to one another. A vector’s components do not constrain the position of the vector in any way…so we can move vectors to different locations in a coordinate system and they are all equal.

Equal Vectors All the vectors in this image are equal to one another, despite being positioned at different spots visually.

Vectors convey displacements along axes, but we CAN use vectors to represent points in a coordinate system! To do so, we must assume that the vector represents a displacement from the coordinate system’s origin.

For example, the point (2, 3) is 2 units along the x-axis and 3 units along the y-axis. The point’s displacement from the origin is also (2, 3).

Using a Vector to Represent a Point The point (2, 3) can be represented by the vector (2, 3), if we assume the tail of the vector is at the origin.

A “point” and a “vector” are technically different things, but in a game engine, it’s common to use vectors to represent points.

It is important to keep track of which vectors represent points and which don’t. Some mathematical operations won’t make sense if the vectors used don’t represent the right things. Clear variable naming is helpful!

Vector3 shipPos; // represents the position of the ship (i.e. a point)
Vector3 shipDir; // represents the direction the ship is facing (i.e. a vector)
Vector3 shipToEnemy; // represents a displacement from the ship to the enemy (i.e. a vector)

Why Vectors?

You don’t need vectors to make a successful 2D or 3D video game, but they are a powerful tool in your toolbox.

Most video games attempt to build a virtual world of some kind, and the various objects that make up that world are in different positions and have different distances between them. The spatial relationships between objects in the world can be important for building interesting gameplay.

For example, consider a stealth game. Guards should raise an alarm if the player is within a certain distance AND the guard is facing the player. If a weapon is fired, the player should only take damage if their position was in the line of fire. A melee attack is only effective if the player is very near to the guard.

Vectors provide a convenient and consistent way to represent the following basic concepts in a video game world:

  • The displacement (or offset) between two objects.
  • The direction an object is facing.
  • The position (or point) of an object in the world.

Vectors are also useful for conveying any other axis-relative data, such as velocities, accelerations, or forces in physics simulations. Without vectors, you’d have to implement ad-hoc solutions anytime you needed the above sorts of behaviors.

Vector Operations

Vectors are pretty handy just to group axis-related data into a single structure, but the real power of vectors is in the mathematical operations you can perform with them. Here, we’ll review the most important ones for 3D games.

Vector Length

The length (or magnitude) of a vector is calculated using the Pythagorean Theorem: given a right-triangle, the squared length of the hypotenuse is equal to the the squared lengths of the other sides summed: C2 = A2 + B2

You can think of a vector as forming the hypotenuse of a right-triangle. The x-component corresponds to the adjacent side while the y-component corresponds to the opposite side.

Vector Length Calculation The components of a vector form the sides of a right triangle.

Given this, we can calculate the length of v as:

length = sqrt(v.x * v.x + v.y * v.y)

The Pythagorean Theorem also works for calculating the length of 3D vectors - just add Z to the equation!

length = sqrt(v.x * v.x + v.y * v.y + v.z * v.z)

The notation used to convey vector length is ||a||. If we have vector a with values (3, 4), we’d say that ||a|| is equal to 5.

||a|| = sqrt(3 * 3 + 4 * 4) = sqrt(9 + 16) = sqrt(25) = 5

A vector’s length can be modified by multiplying the vector by a scalar value. For example, multiplying by 2 doubles the length of the vector. Multiplying by 0.25 makes a vector a quarter its original size. Multiplying by a negative number also flips the direction of the vector!

(2, 4) * -10 = (2 * -10, 4 * -10) = (-20, -40)

A vector with a length of 1 is called a unit vector and is said to have “unit” length. Unit vectors are important for certain algorithms. Any vector can be converted to unit length by dividing the vector by its own length, a process is called normalization:

a_unit = a / ||a||

Displacement vs Direction

In some cases, the difference between displacement and direction can be important.

A “direction” is just a displacement that has been normalized. Because the length of the vector is 1, multiplying by a scalar will result in a vector that gets its direction from the original vector and its magnitude from the scalar value.

Multiplying a direction vector by a scalar gives you a displacement vector. Dividing a displacement vector by its own length (normalization) gives you a direction vector.

Let’s say I have a position vector A and a direction vector F. I want to calculate the point 10 units from A in the direction of F. I can do this:

A + (10 * F)

Since F is normalized (pure direction vector), we multiply it by 10 to get a vector in the direction of F with a length of 10 (a displacement vector). We then add that vector to A to get a point 10 units from A in the direction of F (a position vector).

Easy, right? However, consider what would happen if the direction vector F were not normalized! The result of 10 * F would not be the right length! And so the math would be wrong.

As a rule of thumb, any time you want to represent a direction (perhaps the direction that an object is facing or the normal of a surface), you should probably be using a unit-length vector for that purpose to avoid any unexpected side-effects.

Vector Addition

If you have two or more vectors, you can add them together to obtain a new vector representing the combination of those vectors. Mathematically, we simply add together the corresponding components of the two vectors.

(2, 4) + (3, -5) = (5, -1)

You can visualize this as laying vectors end-to-end and then drawing a vector from the tail of the first vector to the head of the last vector.

Vector Addition Vector addition is commutative, so we can add in any order and get the same final result. A+B == B+A

Vector addition is often useful to combine multiple displacement vectors OR to apply a displacement to a position. For example, if the player’s position is (5, 2, 0) and we want to move them by a displacement of (1, 0, 0) for the current frame, the updated position would be:

(5, 2, 0) + (1, 0, 0) = (6, 2, 0)

Vector Subtraction

To subtract one vector from another, simply subtract the corresponding components.

(2, 4) - (3, -5) = (-1, 9)

Vector subtraction can be viewed as adding a negated vector. The following two statements are equivalent:

(3, 4) - (2, 2) = (1, 2)
(3, 4) + (-2, -2) = (1, 2)

You can visualize vector subtraction by putting the two vectors with their tails at the same spot. The result of vector subtraction will go from the head of the second vector to the head of the first vector.

Vector Subtraction As with normal subtraction, vector subtraction is not commutative. The direction of the result depends on the order of the subtraction. A-B != B-A

A common use of vector subtraction is finding the displacement between two points. This can be used to determine distance or direction between points. For example, given a player at (4, 5) and an enemy at (8, 12), we can calculate:

EnemyToPlayer = PlayerPos - EnemyPos = (8, 12) - (4, 5) = (4, 7)
PlayerToEnemy = EnemyPos - PlayerPos = (4, 5) - (8, 12) = (-4, -7)

The vectors are exactly opposite of one another. To move from point A to point B requires a vector a; to move from B to A requires -a.

Vector Multiplication

There are two ways to multiply a vector by another vector - one is called the Dot Product and the other is called the Cross Product. Both take two vectors as inputs, but the outputs (and meanings of the outputs) are very different.

Dot Product

The result of the dot product is a scalar value that can be interpreted in several ways to derive meaningful information about the input vectors. Since the result is a scalar value, this operation is also sometimes called the Scalar Product.

To calculate the dot product, simply multiply the corresponding components of the two vectors and then add everything together:

A • B = (3, 4) • (8, 10) = (3 * 8) + (4 * 10) = 24 + 40 = 64

The operator for the dot product is (a dot).

The dot product has three common uses: determining how “similar” two vectors are to one another, calculating the angle between two vectors, and vector decomposition.

Similar Vectors

The dot product can tell us how “similar” two vectors are to one another:

  • A result of 0 indicates that the vectors are perpendicular to one another.
  • A result greater than 0 indicates that the angle between the two vectors is acute (i.e. the vectors are facing roughly the same direction).
  • A result less than 0 indicates that the angle between the two vectors is obtuse (i.e. the vectors are facing roughly in opposite directions).

Dot Product Similarities

If the input vectors are both unit-length, the dot product also tells us this:

  • For unit vectors, the dot product result will always be in the range -1 to 1.
  • If the result is 1, the two vectors are parallel and pointing in the same direction.
  • If the result is -1, the two vectors are parallel and pointing in opposite directions.

Dot Product Unit Similarities

One scenario where this is useful is for determining whether two objects are “facing” one another in a game. We can use the vectors representing the two objects' facing directions, take the dot product, and determine if they are facing or not.

Angle Between Vectors

In conjunction with the arc-cosine function, the dot product can be used to calculate the angle between two vectors:

θ = acos(a • b / ||a|| * ||b||)

This equation divides by the lengths of a and b to ensure the vectors are unit length. If you already know the vectors are unit length, the equation can simplify:

θ = acos(a • b)

The resulting angle will always be in the range of 0 to π radians (or 0 to 180 degrees). This is because the result of the dot product between unit vectors is always in the range -1 to 1.

Often, you can check the dot product between unit vectors to determine whether the vectors are or aren’t facing one another. But it is sometimes helpful to know the exact angle in radians or degrees - you can use arc-cos to achieve that.

Vector Decomposition

If vector addition allows us to combine two or more vectors into one vector, vector decomposition allows us to split a single vector into multiple vectors. The dot product plays a key role in this operation.

Say we’ve got a vector a and a unit-vector b. Though not obvious, the dot product when one vector is unit length gives us the magnitude of a in the direction of b.

Scalar Projection This operation isolates the portion of the magnitude of a that’s in the direction of b.

This value is called the scalar projection of a onto b. Once known, you can multiply it by b to get the projection of a onto b.

Vector Projection

From there, you can subtract the projection from the original vector a to get the rejection of a from b.

Vector Projection

The result of this process is to take a vector and decomposed it into two smaller vectors - the opposite of vector addition. If you add the projection and the rejection together, you get the original vector back!

Cross Product

The result of the cross product is a vector. For that reason, it is also sometimes called the Vector Product. The operator for the cross product is (a cross).

The cross product only works in 3D, whereas most other vector operations work in ANY dimension. The math is a bit harder to remember than other vector operations:

// c = a ✕ b
c.x = a.y * b.z - a.z * b.y
c.y = a.z * b.x - a.x * b.z
c.z = a.x * b.y - a.y * b.x

There is a handy mnemonic if you need to memorize it!

The result of the cross product is a vector perpendicular to the two input vectors. There are two possible perpendicular vectors! The order in which you perform the cross product determines which of the two will be the result!

Cross Product Assuming a right-handed coordinate system, the cross products axb and bxa.

We’ll discuss the difference between right-handed and left-handed 3D coordinate systems later on. But the results in the image would be exactly opposite if we were using a left-handed coordinate system.

The cross product will be useful in a variety of situations where we need to know a vector that is perpendicular to two other vectors.

Writing Vector Classes

Whew, that’s a lot of info! Hopefully you now have a basic understanding of what vectors are, why they’re useful, the data they contain, and the operations we can perform on them. To use them in our game engine, we need to create some classes representing vectors and their operations.

A vector class ideally needs to support the following:

  • Assignment and equality checks
  • Get and set components
  • Addition and subtraction
  • Scalar multiplication
  • Length
  • Normalization
  • Dot product
  • Cross product

A 3D game engine will usually need to support these operations for 2D, 3D, and 4D vectors. The inclusion of 4D vectors may be puzzling, but we’ll discuss that more in the future! A 4D vector simply has an additional component, often called “w”.

The vector classes used by G-Engine can be found here:

Next, I’ll highlight some considerations to make when writing these classes.

Naming

It’s fairly common to call vector classes something like Vector2, Vector3, and Vector4. The names Vector2D, Vector3D, or Vector4D are also common. Of course, you could name them however you’d like!

Data Layout

Let’s say you have an array of float where every three elements represent the x/y/z components of a point in 3D space. You may want to reinterpret that memory as an array of Vector3 without allocating new memory.

Likewise, you may want to do the opposite: treat a Vector3 as an array of three float.

To achieve this, it’s important that a Vector class ONLY stores the relevant component data, stores it in the correct order, and DOES NOT store any additional data.

The only data members in the class should be x and y for a 2D vector; x, y, and z for a 3D vector; and x, y, z, and w for a 4D vector. In a 4D vector, the w component should go last.

Don’t Inherit

It may be tempting to inherit Vector4 from Vector3, and inherit Vector3 from Vector2. Resist the temptation!

From a purely pedantic perspective, inheritance should be used for “is-a” relationships. A Vector4 is not a Vector3.

If you do choose to inherit, you’ll find that the only thing you achieve is not having to repeat the x or y components in the new class. All operations defined in Vector2 needs to be overridden or redefined for Vector3. And introducing virtual function calls to our Vector class adds overhead - we want our vector classes to be lightning fast low-level math functionality.

Public Data Members

If you’re big on data encapsulation and writing shy classes (like me), you’d think that the x/y/z components of a vector should not be public data.

However, you do need to be able to get and set component values, so you’ll end up writing getters and setters anyway. The data will effectively be public. Furthermore, using getters and setters makes some vector math harder to read:

// Which do you prefer?
v1.x += v2.x * someVal;
v1.SetX(v1.GetX() + v2.GetX() * someVal);

You may notice that I don’t have public components in my Vector classes - I regret making that choice. I would recommend public access to vector components. I’ll probably change this in the future.

Squared Length

In addition to a Length function, provide a LengthSq function. There are many cases where the squared length of a vector will work as well as regular length, and it’s a cheaper operation to perform.

For example, we could say if(v.GetLengthSq() < 9) rather than if(v.GetLength() < 3).

Constants

It’s pretty common to provide a number of handy constants. These include: the zero vector, a vector where each component is one, and a unit vector pointing down each axis. For example, you might call these Zero, One, UnitX, UnitY, UnitZ.

Conversions

Implicit conversions between Vector2 and Vector3 and Vector4 are usually desirable. To do this, define constructors that take as arguments the other types of vectors.

To convert from a larger vector to a smaller one, simply discard the extra components. To convert from a smaller vector to a larger one, assume the added components have a default value of zero.

Operator Overrides

When you perform vector math on paper, you generally use a number of common mathematical operators to represent concepts like vector addition, subtraction, and scalar multiplication or division.

a += ((b + c) - (v - u)) * 5; // some fairly complex vector math

We’d like to write our code in a similar way, if we can. As a result, operator overrides for vector addition, subtraction, scalar multiplication, and scalar division are recommended.

Operations like dot product and cross product do have nice mathematical notation, but C++ doesn’t support overrides for those types of operators. As a result, you’ll have to simply create functions called Dot and Cross. These are usually static functions.

Careful Naming to Signal Usage

If you call vector.Normalize(), does it normalize the vector OR does it return a normalized vector, leaving the original vector untouched?

In many of the math classes we will discuss, there are certain functions like this where you need to be careful that the public API is clear, easy to use, and not prone to error.

Subtle naming differences can imply usage:

v.Normalize(); // normalizes v
Vector3 n = v.Normalized(); // returns a normalized vector, v is unchanged

Subtle naming differences are also easy to miss, so maybe making it more obvious is a good idea:

v.Normalize(); // normalizes v
v.GetNormalized(); // returns a normalized vector, v is unchanged

Vector I/O

When running your game, you probably want to be able to print out Vectors to the log for debugging or data recording purposes. Assuming you use C++’s I/O stream to output to the console, you will likely want to define operator<< for your Vector classes:

std::ostream& operator<<(std::ostream& os, const Vector3& v)
{
    os << std::setprecision(9) << "(" << v.GetX() << ", " << v.GetY() << ", " << v.GetZ() << ")";
    return os;
}

Conclusion

In this post, I’ve tried to provide a crash course in vectors and vector math, but if this all seems extremely confusing and needs further explanation, there are a ton of helpful resources online and in book form to become a vector math ace. I’d recommend the following:

G-Engine  C++  Math 
comments powered by Disqus