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=<ux,uy> 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>
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.
Vectors can have any number of components. Usually, in computer graphics you'll deal with 2D and 3D vectors, or vectors of the form A=<x,y>, B=<x,y,z>. An n-dimensional vector has the form C=<c1, c2, c3, …, cn>. n-dimensional vectors are used to represent sets of variables rather than geometrical space, because after 3D, you enter hyperspace.
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)
|U| = sqrt(ux2 + uy2 + uz2)
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=<nx,ny>, the normalized version of N is usually written in lowercase as n and is computed like this:
n = N/|N|
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.
Let U=<ux, uy>
-1*U = -1*<ux, uy> = <-ux, -uy>
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>
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
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.
q = cos–1 (ux*vx + uy*vy/|U|*|V|)
Or, more compactly, assume that (U.V) means (ux*vx + uy*vy) 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|2 = |V|2.
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=<ux, uy, uz> and V=<vx, vy, vz>, 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.
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.
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>
P = p1 + |V|*v = p1 + V = <p1+V> = <p1x+Vx, p1y+Vy> = p2 = <p2x, p2y>
Vectors as Linear Combinations
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!