Geometry plays a central role in game programming, underlying not only graphics, but also physics and spatial AI. A lot has happened since geometry was first formalised by the Greeks more than two thousand years ago, most notably the invention of coordinates and vectors. These inventions are indispensible for doing geometry on machines (at least, the kind of geometry that is useful for games).

This article introduces the basic concepts of vectors. In a following article, we will look at how vectors can be used to solve geometric problems that arise in computer graphics, physics and AI.

Introduction

(I am assuming here that you already know about coordinates, axes and points; if you don’t, check out this link.)

A vector specifies the relationship between two points; in essence, it says how to get from point A to point B.

Suppose point A is given by the coordinates (a_x,a_y), and B is given by the coordinates (b_x, b_y). Then the vector from A to B is defined as [b_x – a_x,b_y – a_y]. The two values are called the components or sometimes the coordinates of the vector. We can use a variable \( \bv{v} \) to denote a vector; vectors are sometimes printed with an over-bar \( \bar{v}\) or arrow \( \vec{v} \).

Examples

Notice that even though the first two examples have different pairs of points, the same vector results. Vectors at different positions are the same as long as the vector components are the same. This is convenient when we draw pictures – we can translate the vector everywhere, without changing it.

In the last example, the vector from the origin has the same coordinates as the point B. This useful fact makes it possible to drop the distinction between points and vectors – we always think of a point as a vector with the same coordinates. For the remainder of this article, when I say point A, I really mean the vector from the origin to point A.

When we operate with vectors, an operand or result that is not a vector is referred to as a scalar. A scalar is simply a real number; the terminology is useful to distinguish it from a vector component.

In this article, we will use letters

• u, v, and w for vectors (with components v_x , v_y , etc.);
• a and b for scalars; and
• \(\alpha\) for angles.

Addition and Subtraction

Suppose v is a vector from point A to point B, and w is a vector from point B to point C. Then the sum of the vectors v and w gives a vector from point A to point C. Here is how to calculate the sum of two vectors:

If v = [v_x,v_y] and w = [w_x,w_y], then

$$ \bv{v} + \bv{w} = [v_x + w_x, v_y + w_y]. $$

Examples

Notice in the figures that the second vector starts where the first vector ends. In this configuration, the sum starts where the first vector starts, and ends where the second vector ends.

We can find a vector in the opposite direction (with the same size) by inverting the signs of the components. We can also write a minus in front of a vector to show that the components should be inverted.

If v = [v_x ,v_y], then

$$ -\bv v = [-v_x, -v_y] .$$

Examples

Subtraction is performed by subtracting vector components.

If v = [v_x,v_y] and w = [w_x,w_y], then

$$\bv v – \bv w = [v_x – w_x, v_y – w_y].$$

Examples

In the figures, both vectors are drawn to start from the same point. In this configuration, the difference is from the endpoint of the second vector to the endpoint of the first vector.

The vector with all components equal to 0 is called the zero vector, and we denote it by 0.

Vector addition and subtraction have properties that mimic addition and subtraction of real numbers. These properties, and those listed for other vector operations, can be exploited for two purposes.

Firstly, when tackling a geometric problem, they are used to manipulate the equations that you write. Typically, the problem is to express some unknown quantity in terms of known quantities; properties of vector operations make this possible.

Secondly, when implementing geometric code on a computer, they can be used to implement algorithms more efficiently and with less code. In particular, they can help reduce the number of cases to handle.

Many properties have names (given in the right-hand columns of property tables). The names are not so important for understanding and using vector operation properties, but as always names are useful when talking about stuff. In particular, they can help make comments that state your assumptions and reasoning precise. Even if a fellow coder (such as your future self!) does not know what the term means, using standard terms will serve as helpful keywords that can be searched on the Internet.

Properties of vector addition

Scalar Multiplication

We can multiply vectors with real numbers by multiplying each of the components with a real number.

If v = [v_x,v_y], then

$$ a \bv v = [av_x, av_y].$$

The multiplication does not affect the direction in which the vector is pointing, only its length.

Examples

Division by a scalar is defined as multiplication with the scalar’s reciprocal, that is

$$v / a = (1 / a) v.$$

When a = 0, v/a is undefined.

Properties of scalar multiplication

Unary Vector Operations

Vector Length

The length of a vector is given by Pythagoras’s Theorem. We denote the length of a vector v by |v|.

If v = [v_x,v_y], then

$$|\bv v| = \sqrt{v_x^2 + v_y^2}.$$

Vector length is also called the Euclidean norm (yes, there are many other norms as well).

Example

Properties of vector length

Normalisation

It is sometimes necessary to work with a vector that points in the same direction as a given vector, but is of unit length. If the given vector is v, then the unit vector in the same direction is denoted by v^* , and is called the normalised vector of v:

$$\bv{v}^* = \bv v / |\bv v| $$

Example

Many formulas simplify drastically if the vectors in them are normalised; this can be exploited to gain a performance benefit in code.

Perpendicular Operator

The perpendicular operator gives a vector of the same length, rotated 90º counter clockwise, and is denoted by \(\bv v ^ \perp\):

$$\bv v ^ \perp = [-v_y, v_x].$$

This operator is useful for doing some cheap rotations of special angles. For example, \((\bv v + \bv v^\perp) / \sqrt{2}\)gives a vector of the same size as v, rotated 45º counter clockwise.

Example

Properties of the perpendicular operator

Vector Products

There are at least six ways to define useful vector products. Of these the dot product, perp dot product and cross product are the most useful in game programming. The dot and perp dot products are defined in this section; the cross product only applies to 3D, and is defined in the next section.

Dot Product

The dot product of two vectors is defined as follows:

If v = [v_x,v_y] and w = [w_x,w_y], then

$$\bv v \cdot \bv w = v_xw_x + v_yw_y.$$

The most useful property of the dot product is that it gives us an easy way to calculate the cosine of the (smaller) angle between two vectors:

$$\bv v \cdot \bv w = |\bv v||\bv w|\cos \alpha,$$

where \(\alpha[\latex] is the smaller of the angles between two vectors. This formula is the key to many geometric algorithms, and you should memorise it.

Examples

Properties of the dot product

Perp dot product

The 2D perp dot product is defined as follows:

If v = [v_x,v_y] and w = [w_x,w_y], then

$$\bv v * \bv w  = v_xw_y – v_yw_x.$$

(Note: the notation for the perp dot product used here is not conventional. It is usually written [latex]\bv v^\perp \cdot \bv w[\latex]. The star notation is used to emphasise that the perp dot product is an operation in its own right, and not merely a derivative of the dot product.)

The perp dot product’s most useful property is that it gives us an easy way to compute the sine of the smaller angle between two vectors:

$$\bv v * \bv w| = |v||w|\sin \alpha.$$

Note the absolute value marks in the formula above. The product v*w can be either positive or negative, but [latex]|\v v| |\bv w| \sin \alpha\) is always positive or zero (since \(0^\circ \leq \alpha < 180^\circ \)). If we work with directed angles, so that clockwise angles are negative, and counter clockwise angles are positive, we can drop the absolute value markers. Then the perp dot product also gives us a convenient way to determine in which direction something was rotated.

Examples

Properties of the perp dot product

Relationships between the dot and perp dot product

The dot and perp dot products are closely related. The table below shows those relationships.

Relationships between the dot and perp dot product

Projections and Perpendiculars

Any vector v can be written as the sum of a vector in the same direction as another vector w, and a vector perpendicular to w (as long as w is not the zero vector). The first vector is called the projection ofv onto w; the second is the perpendicular of v on w. We denote these vectors by proj_w v and perp_w vrespectively.

A little bit of trigonometry help us find projections and perpendiculars in terms of dot and perp dot products:

$$ \bproj _\bv w \bv v = \frac{\bv v \cdot \bv w}{|\bv w|^2 }\bv w$$

and

$$ \bperp _\bv w \bv v = \frac{\bv v * \bv w}{|\bv w|^2 }\bv w^\perp$$

Examples

Properties of proj and perp

Three Dimensions

In three dimensions, we use three components to denote a vector: [x,y,z].

Most of the definitions in 3D are analogous to the 2D case, and all properties in the tables hold in 3D as well. Here is a quick summary of definitions for vector operations in 3D:

• \( \bv v + \bv w = [v_x + w_x, v_y + w_y, v_z + w_z] \)
• \( – \bv v = [-v_x, -v_y, -v_z] \)
• \( \bv v \cdot \bv w = v_xw_x + v_yw_y + v_zw_z \)
• \( |\bv v| = \sqrt{v_x^2 + v_y^2 + v_z^2} \)

The exception is the perp dot product, which is only defined for 2D. In 3D, we make use of the cross product (see the next section). This also means that we cannot calculate the perpendicular of a vector on another vector in terms of the perp dot product; instead, we use the identity

$$ \bperp_\bv w \bv v = \bv v – \bproj_\bv w \bv v.$$

Cross Product

The cross product replaces the 2D perp dot product in 3D. It differs from other vector products defined so far in that the result is a vector, not a scalar. The somewhat complicated definition looks like this:

$$\bv v \times \bv w = [v_yw_z – v_zw_y,v_zw_y – v_yw_z,v_xw_y – v_yw_x]. $$

The usual trick to remember this formula requires a bit a math that is not covered here. I will ignore the mathematical aspects, and show the basic trick in any case. The mnemonic is this diagram:

To calculate the x component, cross out the row and column containing x.

Now subtract the product of the orange components from the product of the blue components.

Do the same for y: cross out the row and column containing y, and subtract orange from blue (note, the blue and orange components are reversed).

And finally, do the same with z: cross out the row and column containing z, and subtract blue from orange (here the blue and orange components are as they were for x).

If this confuses you, do not worry. You can look for a better trick, or just learn the formula straight.

The cross product in 3D gives a vector with the property that it is perpendicular to both operands. There are two such vectors, the right one is given by the right hand rule: when the fingers of the right hand curl from v to w, the thumb points to v × w.

Like the 2D perp dot product, we can use the cross product to calculate the sine of the angle between two vectors:

$$|\bv v \times \bv w| = |\bv v||\bv w|\sin \alpha.$$

When efficiency is a concern, a problem in 3D that requires the sine of an angle is converted to a problem that requires the cosine instead – this is computed efficiently using the dot product.

Properties of the cross product

Relationships between the dot and cross product

The dot and cross products are closely related. The table below shows those relationships.

Relationships between the dot and cross products

\( |\bv v \times \bv w| / \bv v \cdot \bv w = \tan \alpha \)
This gives us a way to caclulate the tangent of the angle between two vectors.

\( |\bv v \times \bv w|^2 + (\bv v \cdot \bv w)^2 = (|\bv v||\bv w|) \)
This is the 3D vector translation of the familiar trigonometric identity [\latex]\sin^2 \alpha + \cos^2 \alpha = 1 [/latex].