Matrices and Vectors in Game Development

Games, especially game graphics, are made up of a lot of mathematics. The mathematics used in game graphics, physics, and so forth can become quite complex and advanced. Having a firm understanding of the different types of mathematics that are used in game development can allow you to have an easier time understanding and implementing the information.

In this article we review briefly the different types of mathematics that are common in game development. One could write an entire book on game math, so this article will serve as a quick review of the topics you should be familiar with coming into game development.

Vectors, Vertices, and Points

Vectors are the fundamental mathematical objects that are used in every 3D game and game engine. Vectors define a direction in virtual space, but they can also be used to define points called vertices (plural of vertex), orientations, or even surface normals, which are the directions surfaces face. For example, a triangle is made up of three of these points. In game related books the terms vertex and vector are often used synonymously to refer to a virtual point.

Technically, vectors and vertices are different, but they are used the same way most of the time in games. Vectors are spatial directions, and vertices are points of a primitive.

Vectors come in many types, with the most common ones being 2D, 3D, and 4D. A vector is made up of n number of dimensions that describe the total number of axes it uses. For example, a 2D vector only has an X and Y axis, a 3D vector has an X, Y, and Z axis, and a 4D vector has the same axes as a 3D vector in addition to a W axis. A vector can generally be written as shown below.

V = (V1, V2, ..., Vn)

In a language such as C or C++ a 3D vector can have the following structures:

struct Vector3D {    float x, y, z; };struct Vector3D {    float pos[3]; }

Vectors can be operated on by scalars, which are floating-point values. For example, you can add, subtract, multiply, and divide a vector with another vector or a scalar. Adding a vector to a scalar, A, can be written as shown below.

V.x = V1.x + V2.xV.y = V1.y + V2.yV.z = V1.z + V2.zV.x = V1.x + A V.y = V1.y + AV.z = V1.z + A

The same goes for subtraction, multiplication, and division of vectors with other vectors or scalars.

The length of a vector, also known as the vectors magnitude, is very common in computer graphics. A vector with a magnitude of 1 is called a unit-length vector or just unit vector, and it refers to a vector that is perpendicular to a point on a surface. The magnitude can be calculated as shown below.

Magnitude = Square_Root( V.x2 + V.y2 + V.z2 )

To create a unit vector from a nonunit vector, all that needs to occur is dividing the vectors magnitude by the vector itself. This is shown below, where the square root of the square of each added component is divided by the vector.

V = V / Square_Root( V.x2 + V.y2 + V.z2 )

A normal refers to a unit-length vector.

Turning a vector into a unit vector is known as normalization and is a highly common operation in computer graphics. Other very common operations are the dot product and cross product vector operations. The dot product of two vectors, also known as the scalar product, calculates the difference between the directions the two vectors are pointing. The dot product is used to calculate the cosine angle between vectors without using the cosine mathematical formula, which can be more CPU expensive, and the result is not another vector, but a scalar value.

This calculation is used to perform lighting methods. I will write another detailed article on lighting. To calculate the dot product, multiply each component of the two vectors then add them together. This is shown below.

d = ( V1.x * V2.x + V1.y * V2.y + V1.z * V2.z )

The equations used in this article follow the order of operations when calculating values. For example, multiplication occurs before addition and subtraction.
Being able to find the angle of difference between two vectors is useful in lighting, which we look at later. If the dot product between two vectors is 0, the two vectors are perpendicular to one another and are orthogonal. Another thing to note is that the sign of the dot product tells us what side one vector is to another. If the sign is negative, the second vector is behind the first; if it is positive, then it is in front. If it is 0, they are perpendicular.

The cross product of two vectors, also known as the vector product, is used to find a new vector that is perpendicular to two tangent vectors. This is commonly used to find the direction a polygon is facing by normalizing the cross product of the edge vectors of a triangle. The cross product is calculated by multiplying the cross components together and then adding them all together component by component. This is shown below.

To find a triangles normal, for example, we first find two edge vectors. This is done by calculating a vector between the first and second point of a triangle and normalizing the result (edge 1) and by doing the same things with the first and third points of the same triangle. The next step is to find the cross product of these two vectors and normalize the results to find the surfaces normal. The direction of the normal depends on the order in which the vertices were defined. If the vertices are clockwise, the direction will point in the opposite direction that it would point if they were counterclockwise, even though it is the same information.

That equation shows how to find a polygons normal.

e1 = normalize( V1  V2 )e2 = normalize( V1  V3 )normal = normalize( cross_product( e1, e2 ) )

To find a normal of a polygon you only need three points, which form a perpendicular triangle to the surface. Even if the polygon has more than three points, you only need three to find the normal. This assumes that all points fall perpendicular to the polygons plane.

Transformations

When data is submitted in a 3D game, the information is passed to the graphics hardware as 3D data. This data must be processed in a way so that it can be displayed onto a 2D view, which is the screen. During the rendering process of the rendering pipeline, various coordinate spaces are used together to perform this task.

3D computer graphics incorporate the idea of many different coordinate spaces. A coordinate space represents an objects relationship to the rest of the scene. For example, the vertices of a 3D model are often stored in object-space, which is a space local to the model itself. To render out an object that is in object-space, it must be transformed to the worldspace position at which you want to render it. World-space is the virtual position and orientation (rotation) of 3D models in the scene.

It is efficient to specify geometry in one space and then convert it whenever necessary during the rendering process. Say you have two boxes that you want to draw in a 3D scene. If these boxes are 100% identical, it would not be efficient to have two (or more) boxes loaded into memory with different vertex positions if you can just load one box and position it throughout the scene as many times as necessary.

As another example, imagine that you have a complex scene that youve created, and you want to change the positions of objects throughout the scene. Being able to position these object-space models is more efficient than trying to alter the individual points of every model that was specified in world-space.

When rendering objects in a 3D scene, we use positions and orientations to represent how an object is located. This information is used to create a mathematical matrix that can be used to transform the vertex data of rendered geometry from one space to another. The positions and orientation, which well call orientation for short, are specified in worldspace, which is also known as model-space.

Once an object in object-space is transformed to world-space, it is transformed to screen-space, which corresponds to the X and Y axes that are aligned to the screen. Since the 3D information has depth and distance with objects that are farther from the camera, a projection is applied to the geometry to add perspective to the data. The projection matrices that are used on geometry are called homogeneous clip space matrices, which clip the geometry to the boundaries of the screen to which they are being rendered. Two types of projection are generally used in video games: orthogonal projection and perspective projection.

By altering the projection matrix you can alter the field-of-view and other properties of the view to create different visual effects, such as a fish-eye lens, for example. You can also apply a view to the world matrix to account for a virtual camera position and orientation. This is known as the world-view (or model-view) matrix.

Orthogonal projection maps a 3D object to a 2D view, but objects remain the same size regardless of their distance from the camera. In perspective projection perspective is added to the rendered scene, which makes objects smaller as they move farther from the camera. A comparison of orthogonal and perspective projection is shown below, where both scenes use the exact same information but different projections. Perspective projection uses a horizon, which represents the vanishing point of the view.

These coordinate spaces are represented by matrices. Matrices have the ability to be concatenated together into one matrix. For example, if the world-space matrix is combined with the eye-space matrix, it is the model-view matrix and can be used to transform geometric object-space models directly into eyespace. Combining the world, view (camera), and projection together gives you the model-view projection matrix, which is used to transform a vertex into screen space.

Other spaces such as texture space (tangent space) and light space, for example, are normally used when performing a number of special effects such as bump mapping, shadow mapping, and so on.

In 3D games, matrices have a lot of uses and are very important. Vectors and matrices are among the most important topics to understand in video games and game graphics.

Matrices

A matrix is a mathematical structure that is used in computer graphics to store information about a space. In computer graphics matrices are often used for storing orientations, translations, scaling, coordinate spaces, and more. In game development we usually work with 3x3 and 4x4 matrices. A matrix is essentially a table, for example,

float matrix3x3[3][3];matrix3x3[0] = 1; matrix3x3[1] = 0; matrix3x3[2] = 0;matrix3x3[3] = 0; matrix3x3[4] = 1; matrix3x3[5] = 0;matrix3x3[6] = 0; matrix3x3[7] = 0; matrix3x3[8] = 1;

A matrix is a table that can be represented in code as a 2D array or as a set of vectors. Matrices with the same number of rows as columns are called square matrices. A vector can be considered a 1D array, whereas a matrix can be considered an array of vectors that together represent a space. For example, a 33 matrix can be created out of three 3D vectors, as follows:

struct Matrix{   Vector3D col1;   Vector3D col2;   Vector3D col3;}struct Matrix{   Vector3D mat[3];}

When it comes to orientations in video games, a matrix is used to store rotational and positional information along with scaling. Mathematically, matrices can be added and subtracted by other matrices of the same size by performing each operation on their equivalent table elements. This can be seen as follows:

M[0] = M1[0] + M2[0], M[1] = M1[1] + M[2], ...

Multiplying matrices is not as straightforward as adding or subtracting. To multiply each matrix, start by multiplying the first element in the first row in matrix A by the first element in the first column in matrix B. The result of this operation is stored in the first columns first element in a new matrix; lets call it N. This continues until every element has been processed in the matrices. Travel along the first matrixs rows and along the second matrixs columns. To be multiplied, matrices must have the same number of rows and columns, which is not referring to square matrices specifically. When it comes to multiplication, it is not commutative with matrices, and they preserve the determinant.

Multiplying matrices works as follows:

new_mat[0] =  m1[r1_c1] * m2[r1_c1] *              m1[r2_c1] * m2[r1_c2] *              m1[r3_c1] * m2[r1_c3];new_mat[1] =  m1[r1_c2] * m2[r1_c1] *              m1[r2_c2] * m2[r1_c2] *              m1[r3_c2] * m2[r1_c3];new_mat[2] =  m1[r1_c3] * m2[r1_c1] *              m1[r2_c3] * m2[r1_c2] *              m1[r3_c3] * m2[r1_c3];new_mat[3] =  0;new_mat[4] =  m1[r1_c1] * m2[r2_c1] *              m1[r2_c1] * m2[r2_c2] *              m1[r3_c1] * m2[r2_c3];new_mat[5] =  m1[r1_c2] * m2[r2_c1] *              m1[r2_c2] * m2[r2_c2] *              m1[r3_c2] * m2[r2_c3];new_mat[6] =  m1[r1_c3] * m2[r2_c1] *              m1[r2_c3] * m2[r2_c2] *              m1[r3_c3] * m2[r2_c3];new_mat[7] =  0;new_mat[8] =  m1[r1_c1] * m2[r3_c1] *              m1[r2_c1] * m2[r3_c2] *              m1[r3_c1] * m2[r3_c3];new_mat[9] =  m1[r1_c2] * m2[r3_c1] *              m1[r2_c2] * m2[r3_c2] *              m1[r3_c2] * m2[r3_c3];new_mat[10] = m1[r1_c3] * m2[r3_c1] *              m1[r2_c3] * m2[r3_c2] *              m1[r3_c3] * m2[r3_c3];new_mat[11] = 0;new_mat[12] = m1[r1_c1] * m2[r4_c1] *              m1[r2_c1] * m2[r4_c2] *              m1[r3_c1] * m2[r4_c3];new_mat[13] = m1[r1_c2] * m2[r4_c1] *              m1[r2_c2] * m2[r4_c2] *              m1[r3_c2] * m2[r4_c3];new_mat[14] = m1[r1_c3] * m2[r4_c1] *              m1[r2_c3] * m2[r4_c2] *              m1[r3_c3] * m2[r4_c3];new_mat[15] =1;

A matrix is considered an identity matrix if the elements starting from the first element going downward in a diagonal direction are set to 1. As we will discuss later, if we transform a vector against an identity matrix, then nothing will change since we will be literally multiplying the components of a vector by 1, which does not change the value.

An example of an identity matrix is as follows:

matrix[0] = 1; matrix[1] = 0; matrix[2] = 0; matrix[3] = 0;matrix[4] = 0; matrix[5] = 1; matrix[6] = 0; matrix[7] = 0;matrix[8] = 0; matrix[9] = 0; matrix[10] = 1; matrix[11] = 0;matrix[12] = 0; matrix[13] = 0; matrix[14] = 0; matrix[15] = 1;

You can calculate the transpose of a matrix by swapping its rows and columns.

The determinant of a matrix is like the length of a vector. You can only find the determinant of a square matrix, which has the same number of rows and columns. Matrices that have a nonzero determinant can be inverted. For a matrix to be inverted, not only does it have to be a square matrix, but it cannot contain a row with all zeros.

A vector can be transformed by a matrix by multiplying the vector against the matrix. This is used in the rendering pipeline to convert vectors from one space to another. When you multiply a vector by a matrix you are applying the matrixs information to the vector.

This occurs as follows:

Vector3D out;out.x = (v.x * matrix[0]) + (v.y * matrix[4]) +        (v.z * matrix[8]) + matrix[12];out.y = (v.x * matrix[1]) + (v.y * matrix[5]) +        (v.z * matrix[9]) + matrix[13];out.z = (v.x * matrix[2]) + (v.y * matrix[6]) +        (v.z * matrix[10]) + matrix[14];

A matrix can be used to store a translation (position). In computer graphics, 3x3 matrices are used to store the scaling and rotational information, but if another row is added, for example, if we create a 3x4 or have a 4x4 matrix, the last row can literally store the X, Y, and Z positional information. To translate a matrix, set the last row to the position you want.

This is shown in the following pseudo-code (assuming M is an array that represents the matrix):

M[12] = X, M[13] = Y, M[14] = Z, M[15] = 1;

A vector can be scaled by a matrix. Check out the examples we made. By multiplying a vector against the matrix, we would have effectively multiplied each component of the vector with the three values in the matrix that represent the X, Y, and Z axes. If each of these elements in the matrix is equal to 1, that is the same as multiplying a vector by 1, which does not change its value. However, a value other than 1 scales the vector, with values less than 1 making it smaller and values greater than 1 making it larger. If you are working with matrices in video games, these three elements of a matrix are used to store the scaling information.

An example of a scaling matrix (the 3x3 part of a 4x4 matrix) is as follows:

mat[0] = scale_val; mat[1] = 0; mat[2] = 0;mat[4] = 0; mat[5] = scale_val; mat[6] = 0;mat[8] = 0; mat[9] = 0; mat[10] = scale_val;

You can also use matrices for rotations. To perform rotations in 3D you need at least a 3x3 matrix. Rotations can be performed around an axis or arbitrary axes. When you multiply a vector by a matrix that stores rotation values, it rotates the vector based on that information.

This can be seen as follows, where you can rotate along the X, Y, and Z axes by creating a rotation matrix:

void Rotate(float *matrix, double angle, float x, float y, float z){  float sine = (float)sin(angle);  float cosine = (float)cos(angle);  float sinAngle = (float)sin(3.14 * angle / 180);  float cosAngle = (float)cos(3.14 * angle / 180);  float oneSubCos = 1.0f - cosAngle;  matrix[0] = (x * x) * oneSubCos + cosAngle;  matrix[4] = (x * y) * oneSubCos - (z * sinAngle);  matrix[8] = (x * z) * oneSubCos + (y * sinAngle);  matrix[1] = (y * x) * oneSubCos + (sinAngle * z);  matrix[5] = (y * y) * oneSubCos + cosAngle;  matrix[9] = (y * z) * oneSubCos - (x * sinAngle);  matrix[2] = (z * x) * oneSubCos - (y * sinAngle);  matrix[6] = (z * y) * oneSubCos + (x * sinAngle);  matrix[10] = (z * z) * oneSubCos + cosAngle;}

Note that cos2() + sin2() = 1, which means the vector is not scaled by the matrices that are strictly rotation matrices. If a scale is added, that information is added to the rotational information, which applies both operations on a vector. Rotations and translations are among the most common uses for matrices in computer graphics, along with representing coordinate spaces.