Vector


A Vector is a quantity which has both magnitude and direction, but no position.

Figure 1

Figure 1 shows an example. You should be able to see our vector V, along with its magnitude (which is just the length of the vector, i.e. a single number, a scalar, like the height of a person). Our vector also has a direction, which in this case is positive in the x and y axis.

The direction of our vector is two dimensional, because its flat on screen and as such is described by two numbers which indicate how much it ‘points’ in each of the two axis directions. A vector can have any number of dimensions – in games, they are commonly two or three dimensional depending on the game.

The demo above shows the world axis x and y and the vector v which follows the mouse position. Note the x and y values of V change sign as the vector is changed and how x and y shrink and grow depending on the mouse.

Magnitude

We can find the magnitude of any vector quite easily using Pythagoras.

Figure 2

He said that the area of the green square is equal to the sum of the areas of the red and blue squares. Since the edges a, b and c are exactly the lengths of the edges of the squares they reside within, the area of each square is:

green = c*c
red = b*b
blue = a*a

So you could write:

c*c = a*a + b*b

With that in mind, lets take another look at the diagram.

Figure 3

So, handily Pythagoras’ a and b edges look remarkably like the x and y axis of the space our vector resides within. We can now write:

magnitude*magnitude = V.x*V.x + V.y*V.y

Of course, we don’t want magnitude squared, we just want regular magnitude, so we take the square root of both sides:

magnitude = sqrt(V.x*V.x + V.y*V.y)

And there we have it. Vectors with more than two dimensions are handled with an extra term, for example a three dimensional vector:

magnitude = sqrt(V.x*V.x + V.y*V.y + V.z*V.z)

Unit Vector

A unit vector is simply a vector whose length (or magnitude) is 1. These are extemely important in geometry because they allow transformations which do not alter the scale of the things being transformed. Such a vector is said to be normalised – i.e. divided by its length:


magnitude = sqrt(V.x*V.x + V.y*V.y)
V.x /= magnitude
V.y /= magnitude

We can also write the magnitude of V as ||V||.

Notice how the length of V is always the same in the above demo.

The Dot Product

This is one of, if not the most important operator(s) in geometry. Its so important because it gets used for many tasks, such as projecting a vector along another, or to help in finding the magnitude of a vector. It works consistently in any number of dimensions (unlike the cross product, which is only defined in 3d).

The text book definition is, for two vectors U and V:

U.V = ||U||*||V||*cos θ

Which says that the dot product of two vectors is equal to the magnitude of each multiplied together all multiplied by the cosine of the angle between them. Of course, if you start out with unit vectors then the magnitude disappears from the equation (it is simply 1) and the answer is directly equal to the cosine of the angle between them.

This in itself is useful because we can then calculate the angle between the two vectors θ in radians by inverting the equation:

θ = cos-1UV

or in code:

θ = acos(U.x*V.x + U.y*V.y)

In games we can perform a dot product like this:

dot = U.x*V.x + U.y*V.y

This is a whole lot more convenient than the text-book definition and a hell of a lot faster to compute. It should look familiar as we’ve already used this to calculate the magnitude of a vector above.

The result of the dot product of two vectors can be visualised as being either on the positive or negative side of a tennis court with an infinite net down the middle at 0. There are two poles at +1 and -1, with 0 at 90o on each side.

In the demo, you control unit vector V as it is dotted against unit vector U. Notice how the dot product is 0 when the vectors are at 90o to each other? Also, note that when they are totally opposite, the dot is -1.

So when two unit vectors point exactly the same way, the result of the dot product is 1 and when they are exactly opposite -1. The dot product returns 0 for any two vectors (unit or otherwise) at 90o to each other in some plane.

Its very useful in games when we want to tell if an enemy is facing the player, for instance (the dot product of their forward vectors will be negative – although we must also check the dot of their right vectors to make sure they’re not back to back (the dot should be negative as well), since the dot product will only tell us if two vectors are opposed, which is true of facing *and* opposing).

The really useful part comes when we realise that this geometric description also allows us to tell how much of a vector is in the direction of another, because when we know that we can calculate this new projected vector which is useful in all sorts of geometric problems, rotation being one of the most fundamental.

Projection

What is projection? It is the procedure of taking something in n dimensions and collapsing it down to the dimension below (n-1). So in 3d rendering we often want to project the 3d world onto the near plane of the camera. When we do a dot product we are projecting one vector onto another and the by product is a scalar.

We start out with two vectors, one being unit (A) and the other not (V). A is the projection axis and the V the vector we want to project onto this axis, resulting in a scalar d, which tells us how far along A V is.

Figure 4

We can compute d using the dot product:

d = VA

or

d = V.x*A.x + V.y*A.y

We can even get the full projected vector (the vector between the black and green dots in Figure 4):

Vaxis = A*d

or

Vaxis.x = A.x*d
Vaxis.y = A.y*d

Because A was a unit vector, the projection of V onto it resulted in a quantity with the same length units as V. I.e. If they both pointed in exactly the same direction the dot product tells us the length of V.

If both vectors were unit length we get the same result except that the lengths drop out of the equation and we are left with the cosine of the angle between the two vectors.

Optimisation

If neither vector is unit length we can still find d, but it will be in parametric units along A (i.e. from 0 to 1):

d = V A / A A

You can see why this works if you consider what happens when V = A. The first quantity is the squared length of both vectors and so is the second quantity; thereyby giving a value of 1, which corresponds to the end “time” along the axis. Similarly total squared length divided by half the squared length = 0.5, which is exactly what we expect.

Often this is more useful than having d in axis length units, which is nice.

The Cross and Wedge Products

In many ways the wedge-product (^) is the opposite of the dot product as it does the reverse of projection: extension. In 2d the wedge product of two vectors gives the signed area of the parallelogram formed by the extension of one vector by the other.

In Figure 5, the area A^B is formed from the wedge product of vectors A and B.

This is useful in backface culling and tells us when our triangles face the “wrong” way because the area will be negative:

Two vectors A and B

area = A.x*B.y - A.y*B.x

Notice that when the vectors in this demo are coplanar the area goes to 0? This fact is useful when inverting a matrix because it tells you whether the matrix is degenerate or not (i.e. cannot be inverted). This signed area is called the determinant of a 2d matrix (formed by axis vectors A and B). In 3d the determinant is a volume, but the principle is the same and can again be computed using the wedge product of three vectors.

You can also use the wedge-product to compute the area of a triangle; its simply:

area = A^B / 2.

Indeed, you can compute the area of a convex polygon using this as well; here is a code snippet from this site which does exactly that:

public function GetArea( ):Number
{
	var area:Number = 0;
	for ( var i:int = 0; i<m_numPoints; i++ )
	{
		var P0:Vector2 = m_localSpacePoints[i];
		var P1:Vector2 = m_localSpacePoints[(i+1)%m_numPoints];
 
		area += P0.Wedge( P1 );
	} 
 
	return area/2;
}

In 3d, the wedge product is equivalent to what we know as the cross product. The cross product produces a vector perpendicular to the input vectors:

x area = A.y*B.z - A.z*B.y
y area = A.z*B.x - A.x*B.z
z area = A.x*B.y - A.y*B.x

You will notice that the z area in 3d is the same equation which gave us the wedge product in 2d.

The textbook definition of the cross-product is:

||A x B|| = ||A||*||B||*sin θ

Which says that the magnitude of resultant vector is equal to twice the area of the triangle formed by A B with an implicit missing edge.

The cross product results in a vector perpendicular to the other two vectors which is useful in all sorts of applications (generating face normals for example).

Perpendicular P = A x B

The cross product does not preserve magnitude generally, so that two unit vectors A and B crossed will only result in a unit vector C if A and B are at 90o to each other in some plane. Most of the time the resulting vector will be smaller than the two input vectors and indeed, tends toward 0 as the two inputs move towards being parallel.

Interestingly you can also use the cross product operator for projection of a vector onto a plane which is useful in lots of circumstances: (e.g. in physics when you want to calculate the tangential velocity given a plane and the velocity):

Plane partially defined by normal N
Vector for projection V

New vector Q = (NxV)xN

The Perpendicular operator

This is a handle little operator which only works in 2d. It simply gives a vector which is perpendicular to the original. Its especially useful in 2d physics engines for finding the tangential velocity given a contact normal.

Figure 6

Figure 6 shows A and the perpendicular vector. This is a length preserving operator and is computed quite simply:

Aperp.x = -A.y
Aperp.y = A.x

There is of course another perpendicular vector, opposite this one, but convention seems to be to chose this one, presumably because if you take the unit right vector {1,0} and apply this operator you get the unit up vector {0,1}.

14 Responses to Vector

  1. Dunge says:

    “Its very useful in games when we want to tell if an enemy is facing the player, for instance (the dot product of their forward vectors will be negative).”

    This will tell if the enemy and player are facing each other. The facing vector of the player have nothing to do with whether the enemy is facing him or not.

    • Dunge says:

      And even there, if they are back to back it won’t work.

      • Paul Firth says:

        Yes, this is true – I will update the post to say you need to check the dot of their right vectors as well :)

        • jc_lounge says:

          Love the article. But I’m not sure how dotting the right vectors helps here either.

          Maybe dotting the offset vector between the entities with the facing vector of one of them is more useful?

          • dtc says:

            yeah i didn’t get quite get this either. wouldn’t the position be sufficient? they’re facing the same direction regardless of back-to-back or not so the right vector would be the same. (not sure what right vector is but im assuming it’s just 90 degrees to the right of the direction the player is facing)

    • Paul Firth says:

      Isn’t that what I described? Sorry, maybe I misunderstand your question :)

  2. Pingback: Fun with convex polygons | Paul's blog@Wildbunny

  3. ghafoor says:

    Product of two Vectors
    Product of vectors, cross product, scalar product, dot product, vector product, properties of vector product.
    http://www.infoaw.com/article.php?articleId=865

  4. Robert says:

    The last part of the last sentence in the first paragraph shouldn’t be there. The part about a single value d, which I see is actually part of the Projection section.

  5. Eric says:

    Stupid question,

    How do I generate the forward and right facing vectors for my sprite? Do I use the existing sprite I have for movement? If so, I would have the forward/directional facing vector but how would I get the right vector? Is there some sort of transformation I can apply to it?

  6. lapin says:

    Your article mentions an interesting bit at the end of the section titled cross & wedge products:

    “Interestingly you can also use the cross product operator for projection of a vector onto a plane which is useful in lots of circumstances: (e.g. in physics when you want to calculate the tangential velocity given a plane and the velocity):

    Plane partially defined by normal N
    Vector for projection V

    New vector Q = (NxV)xN”

    Can you go into detail (possibly with a diagram) on this please ? I’d love to understand it.

    thanks

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing