Vectors

Vectors are a game programmer's best friend. They're basically nothing more than line segments and are defined by a starting point and an endpoint, as shown in Figure C.3.

Referring to Figure C.3, you see a vector U defined by the two points p1 (the initial point) and p2 (the terminal point). The vector U=<u_x,u_y> is from p1(x1,y1) to p2(x2,y2). To compute U, you simply subtract the initial point from the terminal point:

U = p2 – p1 = (x2-x1, y2-y1) = <ux, uy>

Also, you usually represent vectors with boldface uppercase letters, like this: U. And the components are written within angled brackets, like this: <u_x,u_y>.

Okay, so a vector represents a line segment from one point to another, but that segment can represent a lot of concepts, such as velocity, acceleration, or whatever. Be warned: Vectors, once defined, are always relative to the origin. This means that once you create a vector from p1 to p2, the initial point in vector space is always at (0,0), or (0,0,0) in 3D. This doesn't matter because the math takes care of everything, but if you think about it, it makes sense.

A vector is only two or three numbers in 2D and 3D space, so it really only defines an endpoint in 2D or 3D space. This means the starting point is always thought of as the origin. This doesn't mean that you can't translate vectors around and perform various geometrical operations with the vectors themselves. It just means that you need to keep in mind what a vector really is.

The cool thing about vectors is the operations that you can perform on them. Because vectors are really sets of ordered numbers, you can perform many of the standard mathematical operations on them by performing a mathematical operation on each component independently.

Vector Length

The first thing that will pop up time and time again when you're working with vectors is how to compute the length. The length of a vector is called the norm and is represented by two vertical bars, like this: |U|. This is read as "the length of U."

The length is computed as the distance from the origin to the tip of the vector. Hence, you can use the standard Pythagorean theorem to find the length. Therefore, |U| is equal to

|U| = sqrt(ux2 + uy2)

And if U happened to be a 3D vector, the length would be

|U| = sqrt(ux2 + uy2 + uz2)

Normalization

Once you have the length of a vector, you can do something interesting with it. You can normalize the vector, or shrink it to make sure that its length is 1.0. Unit vectors have a lot of nice properties, just like the scalar 1.0 does, so your intuition probably agrees with me. Given a vector N=<n_x,n_y>, the normalized version of N is usually written in lowercase as n and is computed like this:

n = N/|N|

Very simple. The normalized version of a vector is simply the vector divided (multiplied by the inverse) by the length of a vector.

Scalar Multiplication

The first operation that you might want to perform on a vector is scaling. You perform this operation by multiplying each component by a single scalar number. For example:

Let U=<ux, uy>
k*U = k*<ux, uy> = <k*ux, k*uy>

Figure C.4 shows the scaling operation graphically.

In addition, if you want to invert the direction of a vector, you can multiply any vector by –1. This will invert the vector, as shown in Figure C.5.

Mathematically:

Let U=<ux, uy>

The vector in the opposite direction of U is

-1*U = -1*<ux, uy> = <-ux, -uy>

Vector Addition

To add two or more vectors together, you simply add the respective components. Figure C.6 illustrates this operation graphically.

Vector U is added to V, and the result is R. Notice how the addition was performed geometrically. I took V and moved it to the terminal point of U, and then I drew the other side of the triangle. Geometrically, this is equivalent to the following operation:

U + V = <ux, uy> + <vx, vy> = <ux+vx, uy+vy>

Thus, to add any number of vectors together on graph paper, you can simply add them "tip to tail." Then, when you add them all up, the vector from the origin to the last tip is the result.

Vector Subtraction

Vector subtraction is really vector addition with the opposite pointing vector. However, it is sometimes helpful to see subtraction graphically also. Take a look at Figure C.7 to see U–V and V–U.

Notice that U–V is computed by drawing a vector from V to U, and V–U is computed by drawing a vector from U to V. Mathematically, it's

U - V = <ux, uy> - <vx, vy> = <ux-vx, uy-vy>

This expression may be easier to remember, but a piece of graph paper can sometimes be a much better "computer" when you're doing the math manually because you can visualize the data more quickly. Hence, it's a good idea to know how to add and subtract vectors on graph paper when you're rendering algorithms—trust me!

The Inner Product, or the "Dot" Product

At this point you might be asking, "Can you multiply two vectors together?" The answer is yes, but as it turns out, the straight component-wise multiplication isn't very useful. In other words:

U * V = <ux*vx, uy*vy>

This expression doesn't really mean anything in vector space. However, the dot product does. It's defined like this:

U . V = ux*vx + uy*vy

The dot product, usually represented by a dot (.), is computed by adding the products of the individual terms. Moreover, the result is a scalar. Well, heck, how does that help? There aren't even vectors anymore! True, my young Jedi, but the dot product is also equal to this expression:

U . V = |U|*|V|*cos q

This expression states that U dot V is equal to the length of U multiplied by the length of V multiplied by the cosine of the angle between the vectors. If you combine the two different expressions, you get this:

U . V = ux*vx + uy*vy
U . V = |U|*|V|*cos q
ux*vx + uy*vy = |U|*|V|*cos q

This is a very interesting formula; it basically gives you a way to compute the angle between two vectors, as shown in Figure C.8, and that's a really useful operation.

If you can't see how this expression works, take a look at the equation after rearranging and taking the inverse cosine of both sides:

q = cos–1 (ux*vx + uy*vy/|U|*|V|)

Or, more compactly, assume that (U.V) means (u_x*v_x + u_y*v_y) and just write

q = cos–1 (U.V/|U|*|V|)

The dot product is a very powerful tool and is the basis of many 3D graphics algorithms. The cool thing is that if the length of U and V are already 1.0, their product is 1.0 and the formula simplifies even more to

q = cos–1 (U.V), for |U|=|V| = 1.0

And here are a couple interesting facts:

Fact 1: If the angle between U and V is 90 (perpendicular), U.V = 0.

Fact 2: If the angle between U and V is < 90 (acute), U.V > 0.

Fact 3: If the angle between U and V is > 90 (obtuse), U.V < 0.

Fact 4: If U and V are equal, U.V = |U|² = |V|².

These facts are all shown graphically in Figure C.9.

The Cross Product

The next type of multiplication that can be applied to vectors is called the cross product. However, the cross product makes sense only on vectors with three or more components, so let's use 3D space vectors as an example. Given U=<u_x, u_y, u_z> and V=<v_x, v_y, v_z>, the cross product written U X V is defined as

U X V = |U|*|V|*sin q * n

All righty, then! Let's take this expression apart piece by piece. |U| denotes the length of U, |V| denotes the length of V, and sin q is the sin of the angle between the vectors. Thus, the product (|U|*|V|*sin q) is a scalar—that is, a number. Then you multiply it by n. But, what is n? n is a unit vector, which is why it's in lowercase. In addition, n is a normal vector, meaning that it's perpendicular to both U and V. Figure C.10 shows this cross product graphically.

So the cross product tells you something about the angle between U and V and the normal vector to both U and V. But without another equation, you aren't going to get anywhere. The question is how to compute the normal vector from U and V so that you can compute the sin q term or whatever. The cross product is also defined as a very special vector product. However, it's hard to show without matrices, so bear with me. Assume that you want to compute the cross product of U and V written U X V. First, you build a matrix like this:

|i     j     k |
|ux     uy    uz|
|vx    vy    vz|

Here, i, j, and k are unit vectors parallel to the x, y, and z axes, respectively.

Then, to compute the cross product of U and V, you perform this multiplication:

N=(uy*vz-vy*uz)*i + (-ux*vz+vx*uz)*j + (ux*vy-vx*uy)*k

That is, N is just a linear combination of three scalars, each multiplied by mutually orthogonal (perpendicular) unit vectors that are each parallel to the x, y, and z axes, respectively. Thus, you can forget the i, j, and k and rewrite the equation as

N=<uy*vz-vy*uz, -ux*vz+vx*uz, ux*vy-vx*uy>

N is the normal vector to both U and V. However, it's not necessarily a unit vector (if U and V were both unit vectors, N would be), so you must normalize it to find n. Once that's done, you can plug everything into your cross product equation and do what you will.

In practice, though, few people ever use the U X V = |U|*|V|*sin q * n formula. They simply use the matrix form to find the normal vector. Again, normal vectors are very important in 3D graphics, and you will be computing a lot of them in Volume II! Normals are great not only because they are normal to two vectors, but they also are used to define planes and to compare the orientation of polygons—useful for collision detection, rendering, lighting, and so forth.

The Zero Vector

Although you probably won't use the zero vector much, it's still there. The zero vector has zero length and no direction. It's just a point, if you want to get technical. Thus, in 2D the zero vector is <0,0>, in 3D it's <0,0,0>, and so on for higher dimensions.

Position Vectors

The next topic I want to talk about is position vectors. They are really useful when you're tracing out geometrical entities like lines, segments, curves, and so on. I used them during clipping and during the computation of segment intersection in Chapter 13, "Playing God: Basic Physics Modeling," so they're important. Take a look at Figure C.11, which depicts a position vector that can be used to represent a line segment.

The line segment is from p1 to p2, V is the vector from p1 to p1, and v is a unit vector from p1 to p2. You then construct P to trace out the segment. P looks like this, mathematically:

P = p1 + t*v

Here, t is a parameter that varies from 0 to |V|. If t=0, you have

P = p1 + 0*v = <p1> = <p1x, p1y>

Thus, at t=0, P is pointing to the beginning of the segment. On the other hand, when t=|V|, you have

P = p1 + |V|*v = p1 + V = <p1+V>
               = <p1x+Vx, p1y+Vy>
               = p2 = <p2x, p2y>

Vectors as Linear Combinations

As you saw in the cross product calculation, vectors can also be written in this notation:

U = ux*i + uy*j + uz*k

Here, i, j, and k are unit vectors parallel to the x, y, and z axes. There's nothing magical about this notation; it's just another way to write vectors that you might need to know. All the operations still work exactly the same. For example:

let U = 3i + 2j + 3k
let V = -3i – 5j + 12k

U + V = 3i + 2j + 3k – 3i – 5j + 12k
      = 0i – 3j + 15k = <0, -3, 15>

Nothing but notation, really. The cool thing about thinking of vectors as linear combinations of independent components is that as long as each component has its vector coefficient, the components can never "mix." Thus, you can write very long expressions and then collect terms and factor out the vectors.

That's it for the math review; now read it once more!