Math Proofs

The Dot Product and Cosine

2006-07-01T10:37:00.000-07:00

Next, we'll show that the dot product of two vectors is the product of their lengths and the cosine of the angle between them.

First consider two arbitrary vectors A and B. We'll form a triangle with these two sides and a third side connecting the ends of A and B, which we'll call C. Also, let θ be the angle between sides A and B

Notice that C = A - B, and so

These simplifications rely on properties of the dot product that I worked out last week. Also, since the dot product of a vector with itself is equal to its squared length, we have

and according to the Law of Cosines

Combining these two we can see that

The Dot Product

2006-06-21T09:48:00.000-07:00

This week I just want to go over the definition of the dot product, and a few of its properties.

The dot product of two vectors is the sum of the product of each of the components of two vectors.

First, observe that for any vector A,

which is the squared length of A

Also, the dot product is commutative ...

... distributive (with respect to vector addition) ...

... and associative (with respect to scalar multiplication) ... or perhaps bilinear as suggested by the first comment down below ...

Next time I'll show some more interesting properties of the dot product.

The Law of Cosines

2006-06-20T09:35:00.000-07:00

This week I'd like to prove the Law of Cosines.

The Law of Cosines states that given any triangle with side lengths a, b and c and opposing angles A, B and C

First we'll divide the triangle into two right triangles by drawing the line that passes through B and is perpendicular to b.

Now we have a right triangle with c as the hypotenuse. And so according to the Pythagorean Theorem

The last step uses the result shown in the previous post which was that

The Definition of Cosine and Sine

2006-06-18T23:40:00.000-07:00

In this post I'd just like to briefly give the definition of cosine and sine, and also show a simple property involving both of them.

Consider a right triangle containing an angle θ. All such triangles are just scalar multiples of each other. Therefore the ratio of the adjacent side to the hypotenuse is a fixed value.

We'll call this ratio the cosine of θ. Similarly, we can define the sine of θ as the ratio of the opposite side to the hypotenuse

Now, we can show that

First we'll substitute

And by the Pythagorean Theorem

And so

Pythagorean Theorem

2006-06-11T17:51:00.000-07:00

After a long break from posting, I'm back with something a bit more fundamental. I'd like to offer a graphical version of Euclid's proof to the Pythagorean Theorem (I'm just going to draw the shapes, rather than name them by their vertices).

First, though, we need to make sure that you're comfortable with the fact that shearing a shape doesn't change its area. In the following diagram, I've shown that shearing a rectangle doesn't change its area, because you can get the same shape by chopping off a triangle from one side of the rectangle and putting it on the other side.

So you can see that if shearing a parallelogram maintains its area, shearing any triangle (since a triangle is just half of a parallelogram) should maintain its area, as well.

Now, we'll move on to the Pythagorean Theorem. We'll take an arbitrary right triangle, and attach squares to each of the sides.

Now, we'll show that the c square has the area of both the a square and the b square. We'll accomplish this by showing that, in the following diagram, the two blue rectangles have the same area, and the two green rectangles have the same area as well.

First, notice that these two triangles (in the following diagram) are identical, and so they have the same area.

Now shear the first triangle so that it becomes half of the a square.

Then shear the second triangle so that it becomes half of the left portion of the c square.

And since the two brown triangles have equal area, the two blue rectangles must have the same area as well (since they each have twice the area of one of the brown triangles)

Now, we will use the same logic on another pair of identical triangles.

Shear the first triangle so that it becomes half of the b square.

Shear the second triangle so that it becomes half of the right portion of the c square.

And since these two triangles have equal area, the two green rectangles must have the same area as well.

And so the c square has an area equal to the sum of the areas of the a square and the b square. In other words c² = a² + b²

Number Divisibility Tricks

2005-09-25T20:49:00.000-07:00

I didn't need these for anything I'm working on currently, but I thought it was interesting and I haven't had anything to write about in a while anyway. Also, these tricks assume the number is in base ten, although similar tricks can be divised for other bases (in case you want to do something with a number stored in binary, say).

Everyone's heard of the trick for finding out if a number is divisible by 9. Just add up all the digits, and if the result is divisible by 9, then the original number is divisible by 9 as well. Another trick for finding if a number is divisible by 11 is to add, and then subtract alternatively each digit of the number, and if the result is divisible by 11, then the original number is divisible by 11.

These tricks (as well as others) can be explained pretty easily with modular arithmetic. Modular arithmetic is another way of thinking about numbers that places all the integers into what are called equivalence classes. For example, when considering the integers modulo 9, there are 9 equivalence classes, let's call them 0, 1, 2, 3, 4, 5, 6, 7 and 8. And a number is placed into the equivalence class given by the remainder when you divide by 9. So the numbers in the 0 equivalence class are 0, 9, 18, 27, 36, etc (as well as -9, -18, -27, etc), and the numbers in the 1 equivalence class are 1, 10, 19, 28, -8, -17, etc. An interesting consequence is if you pick 2 classes, A and B, then regardless of the elements you choose from those classes, when you add them, the result is always in the same equivalence class, namely A + B mod 9. Similarly when you multiply any 2 elements from those classes, the result is always in the same equivalence class, namely A * B mod 9.

Okay, now we get back to the divisibility tricks. For the divisible-by-9 trick, let's look at the numbers modulo 9 (or mod 9 for short). Notice that 1, 10, 100, 1000 and all positive integer powers of 10 fall into the same equivalence class, namely the 1 class. Given a number

and modulo 9, this is

And so a number is in the same class modulo 9 as the sum of its digits.

The divisible-by-11 rule follows from the fact that the numbers 1, 100, 10000, etc are all in the 1 mod 11 class, and the numbers 10, 1000, 100000, etc are all in the 10 mod 11 class. The 10 mod 11 class also has -1, so the number can be written

Here's a list of tricks for finding if a number is divisible by the numbers 2 through 15. All they actually do is tell you how to get another number in the same equivalence class that tends to be much smaller, so that it's easier to tell if it's in the 0 equivalence class (meaning that it's divisible).

2 : Just take the ones digit (if the ones digit is divisible by 2, then the whole number is divisible by 2)

3 : Add all the digits. If the result is divisible by 3, then the original number was also.

4 : The ones digit plus two times the tens digit.

5 : The ones digit by itself

6 : The ones digit minus two times the sum of the rest of the digits

7 : The ones digit, plus three times the tens, plus two times the hundreds, minus the thousands, minus three times the ten-thousands, minus two times the hundred-thousands, plus the millions, etc (the pattern is 1, 3, 2, -1, -3, -2, repeat). This is because

8 : The ones digit plus two times the tens digit plus four times the hundreds digit

9 : Add all of the digits

10 : The ones digit by itself

11 : The ones digit, minus the tens digit, plus the hundreds digit, minus the thousands digit, etc

12 : The ones digit, minus two times the tens digit, plus four times the sum of the rest of the digits

13 : The ones digit, minus three times the tens, minus four times the hundreds, minus the thousands, plus three times the ten-thousands, plus four times the hundred-thousands, etc (the pattern is 1, -3, -4, -1, 3, 4, repeat)

14 : The pattern is 1, -4, 2, 6, 4, -2, -6, then go to -4 and repeat

15 : The ones digit, minus 5 times the sum of the rest of the digits

I'll leave it at that. I'm sure its obvious enough how to create these tricks by now (and they're getting a little too complicated anyway).

Smooth Interpolation

2005-08-13T13:53:00.000-07:00

It is often useful when interpolating to accelerate into the interpolation and/or decelerate out of the interpolation. For example, an object moving from one place to another looks a little better if it accelerates from its stationary state into the move, and then slows down before stopping again. Here I'll talk about how to smooth out a linear interpolation as much (or as little) as you want.

Without any smoothing, you just linearly increase the interpolation factor from zero to one. Instead of this linear movement, let's try increasing the interpolation factor as a function of time f(t). Now let's say that the length in time of the interpolation is 1 (you can easily scale this to any interpolation over any time length), and that the length of the acceleration is a, and the length of the deceleration is b. Then we want the derivative of f(t) to look something like this

Now we just need to determine the height of this trapezoid, such that the area under f'(t) is 1 so that f(1) = 1. The area under the curve is

So for the acceleration (0 ≤ t < a)

And for the linear part (a ≤ t < 1-b)

Our initial condition for this part is that f is continuous at f(a), so

So the linear segment is

And finally, for the deceleration (1-b ≤ t ≤ 1) we have

Again, to satisfy continuity at f(1-b), we need

So the deceleration segment is

And the function with the desired acceleration and deceleration is

Here is a graph of f(t) for various values of a and b.

Mapping a Cube to a Sphere

2005-07-06T03:05:00.000-07:00

After the last post, I got to thinking about how to come up with a mapping from the cube

to the points in the unit sphere. In the last post I used the mapping

Taking the length of the new point gives

So you can see that if x or y are either -1 or +1, this yeilds a vector with unit length. So, beginning with this, I decided that I'd work backward from the guess that if I had a mapping from the cube to the unit sphere, the length of a generated point would need to be

Which leads to the mapping

Trying this out yields some pretty nice results. This is the cube and its mapping onto the unit sphere. The thick lines are lines where at least two of the components are -1 or +1.

And here's another view from inside the sphere

Sorry this post is a little light on justification. I might try to explain this by looking at the level curves defined by constant x, y and z, but I'll save that for another day (maybe).

Mapping a Square to a Circle

2005-07-05T00:20:00.000-07:00

I wanted to come up with a nice way to map all the points in the square

to the points in the unit circle, such that the points along the axes are unchanged, and the corners get normalized. The way I went about this was to think of a line of constant x (as well as a line of constant y) getting mapped to an ellipse in the circle. So for our first requirement to hold true, the ellipse for some constant x has the equation

Now we want to make sure that points along the curve at the top of the circle (from 45 degrees to 135 degrees) are all accounted for. So for x between -1 and 1, we want the ellipse to pass through the point

So we'll plug that in, and that should give us the b coefficient for our ellipse

So the ellipse for constant x is

Similarly, for a line of constant y, we get the ellipse

Solving the first for x', we get

Plugging this into the second equation gives

and by symmetry we can see that the mapping

takes the square from -1 to 1 on the x and y axes, to the unit circle. Here's a demonstration of that mapping, which shows its effect on various grid lines.

I'd like to find a way to map a cube to the unit sphere. Hopefully I can get that ready for the next post.

Smoothing a Sequence of Points (Part 2)

2005-06-26T02:09:00.000-07:00

This is the second part of a method to smooth out sequences of points such that they maintain their rough shape, but loose all the high frequency noise. Refer to Part 1 for definitions and background.

The second special case we'll consider is a zig-zag pattern, where the angle between consecutive points is always the same, the distance is consistent, and all the points are coplanar.

The desired result is that a sequence of points like this will get flattened out to a straight line in a single application of the filter.

This can be accomplished if

Using this fact along with the constraint from Part 1 that

gives us

Here's a couple of demos that show the effects of this filter over 30 iterations. Each point alternates in color from blue to red, so that you can see the concentration of points along the line list. The first is like the points generated from a character swinging a weapon around in a circle, with infrequent samples. If you lay down 4 or 5 points per sample (along the straight lines between the samples), and then apply the filter, you'll get results like this

The next example is more of a noisy data set, and you can see how the noise gets eliminated, but the general shape is preserved.

So finally, the filter that accomplishes both of our goals is

Smoothing a Sequence of Points (Part 1)

2005-06-12T18:27:00.000-07:00

The problem came up of rendering a ribbon and making sure that the points used for the ribbon are nice and smooth. This list of points is generated from an animated object that moves and rotates quickly, and sampling the animation tends to give really jagged results. One solution is to evaluate the animation multiple times per frame to get extra samples to smooth the ribbon out. This seems a little costly, so I wanted to figure out if there was some way to smooth out the ribbon without having to do extra animation updates.

Let's call the nth point in the point sequence P_n. Also (for convenience) let's define

We'll try to smooth out this point sequence by applying a filter to each point in the sequence that adds in bits of nearby points to try to smooth out the sequence.

Note that specifying a filter as the sum of coefficients on the points P_n-2 through P_n+2 requires that all the coefficients add up to 1 (otherwize the filter will yield different results depending on where P_n is relative to the origin). Using coefficients on the A_i vectors and the P_n point, the requirement is that the coefficient on P_n is 1 and the coefficients on the A_i vectors can be whatever we want.

The first idea that came to mind to shave off sharp corners was to calculate the filtered P_n (call it P'_n) as a weighted average of P_n and the midpoint between P_n-1 and P_n+1.

Not only would this flatten out sharp corners, but it also takes a non-uniformly distributed sequence of collinear points, and (after a number of iterations) distributes them evenly along the line. In terms of the A_i we get

This filter, however, tends to either flatten out curves quickly (for values of a close to zero), or not have much effect (for values of a close to one). So I thought it might be worthwhile to introduce A_-2 and A₂ multiplied by a coefficient b, and then subtract that sum from the previous filter. The idea is to try to push out points on a smooth curve that would otherwise get flattened, while still allowing more high frequency noise to get flattened out.

Over the next few weeks we'll consider two uniform cases, and try to find coefficients a and b that will accomplish these goals. The case that we'll consider this week is one of constant curvature, where the distance between each pair of consecutive points is the same, the angles formed between P_n-1, P_n and P_n+1 is consistant, and all the points are coplanar.

Its easy to see that these points fall on a circle, and a vector toward the center of the circle (from P_n) is (A_-1 + A₁). So to measure whether a filter will shrink or grow one of these point sequences, we just need to check the sign of

Equation (1)

Setting this to zero and solving for b gives

Equation (2)

Given a particular θ and a particular a, this tells us what b will provide a root of equation (1). Also, we can see that for any θ from π/3 to π, cos θ + cos 2 θ < 0. So in this range (1) increases as b increases. For θ from 0 to π/3, cos θ + cos 2 θ > 0, so equation (1) increases as b decreases.

Graph of Equation (2) for a = 0.5 with extrema at 0 and π

Therefore the allowable range of values for b is bounded below by the maximum for (2) with θ in the range 0 to π/3, and above by the minimum of (2) with θ in the range π/3 to π. So to find these extrema of (2), we'll take it's derivative, and set it equal to zero.

This equals zero where sin θ = 0. And so the extrema are at θ = 0 and π. These extrema give the range

This maximum ((1-a)/6) turns out to work very well. We haven't really proven anything about filtering general 3D point sequences, but this line of reasoning can be used on the 2D projections of 3D curves, and its pretty easy to see that the 2D projection of a filtered sequence is the same as filtering the 2D projection of the original sequence. We'll leave it for next week to pursue this subject further and come up with another constraint in order to decide on a pair of values for a and b that will accomplish another desirable effect.

Player Position Prediction

2005-05-22T18:47:00.000-07:00

In this post I'll describe a simple way to predict where the player will be in a few moments. This method works well in the games I've worked on, and I would imagine this would work for any third person game with a free camera.

The idea is that if a player pushes the analog control in any particular direction and holds it there, his character will move in either a straight line, or a circle (assuming it doesn't hit any obstacles). So let's assume that the best way to predict the players position is to assume that the current turning speed and linear speed will stay the same over the desired prediction time.

This method of prediction fixes the naive approach of just adding the current linear velocity times the number of seconds forward. All the player has to do to fool this prediction is run in very tight circles. The whole time the player would have a very large linear velocity, but he doesn't end up going anywhere, because of the large angular speed. So this post will show you how to take the player's angular speed into account.

So let's say P(t) is the position of the player at time t, and dt is the change in time from the last update. So the estimated velocity is

Let's call D(t) the heading direction at time t, and s(t) is the speed (scalar) at time t. Also, let's assume that the player moves mostly in the xz-plane, and the positive y-axis is the natural up vector. We will only attempt to predict the player's xz movement, since jumping, double jumping, etc. tend to make the vertical movement more erratic. So we'll calculate the speed and direction by

First, if s(t) = 0, then the predicted position is just the current position, P(t), and we're done. Otherwise the players current heading direction is

So now we can get a turning rate (angular velocity about the y-axis) as

Given that D(t) is a unit vector with no y-component, we can calculate a "left" vector with

So now that we have an angular velocity, and a linear velocity, we can extrapolate the player's position u seconds forward. If a(t) = 0, then

and

Otherwise (for non-zero a(t)), we have

Integrating this gives us

And solving for C

And so, the player's position at time t+u is given by

Once you have this set up, you'll probably notice that the predicted position jumps around quite a bit. To help alleviate this, just keep track of the current linear and angular speeds, and smooth them out over a few updates.

You can also use some fraction of their current linear and/or angular speed when evaluating a particular prediction in order to "lead" the player less (or not at all). Or you can use multipliers greater than 1 to overshoot the player.

Uniformly Distributed Random Unit Quaternions

2005-05-17T03:44:00.000-07:00

Okay, sorry it took me so long to get back to this problem, but I've been busy with getting ready for E3. So I finally have a solution for uniformly distributed unit quaternions (or 4 vectors, whatever you want to call them)

For background (and previous definitions) see the previous post about random unit 3 vectors

Now, we'll derive a way to randomly generate points on the surface of a 4-dimensional sphere. Again, we'll calculate a formula for A. The surface measure of a section swept out by

is

So the probability of getting a point whose θ₂ is between 0 and x is

This would be difficult to invert, so instead, we'll use the fact that we can make θ₂ a function of multiple random numbers, as long as the probability comes out right. So let's guess that it would take the form

We multiply X by π, and add π/2 to arcsin(Y) to change the range of both expressions to (0, π). If this guess is correct, the two coefficients will probably add up to 1 (making this a weighted average of the two expressions)
So the probability that θ₂ is less than x (for x between 0 and π) is the sum of all probabilities (for all possible m's) that X is less than m and arcsin(Y)+π/2 is less than (x- m). Therefore

And setting these two equal gives

so that means

Which initially looks over constrained (3 equations and 2 unknowns), but fortunately we guessed well, and it turns out that

So, finally, we can say that to generate a uniformly random point on the surface of a 4-dimensional sphere

And it's pretty easy to see that (in terms of random number generation)

yields the same results as

Which looks a little nicer (you don't need to add the π/2).
I'll leave it as an excersize for the reader to figure out that to generate a uniformly random point throughout the sphere (not just on the surface) you just need to pick a random radius by

where n is the number of dimensions of the sphere

Uniform Random Distribution on a Sphere

2005-04-30T17:00:00.000-07:00

Today we'll derive how to pick a uniformly distributed random point on the surface of a sphere (as well as on the surface of a 4-dimensional sphere .. useful for picking random orientations by generating random quaternions).

Note : When you refer to an n-sphere, the n refers to the dimension of the manifold, but in this topic, I consider a sphere as a solid (rather than just a manifold), and refer to the manifold as its border. So a 3-dimensional sphere is a ball in R³, rather than the 3-dimensional border of a ball in R⁴. Sorry for the confusion to all the math majors out there, but I think the average person thinks of a "normal" sphere as a 3-dimensional solid (rather than a 2-dimensional manifold) .. thanks, Andy.

First, let's say that we have a random number generator UnitRand() that generates a uniformly distributed number on the interval [0, 1). Given a generator of random points on the border of a circle, the probability of getting a point whose angle is between 0 and x is

So our random circle point generator needs to be

Now, to get a random point on a sphere, we'll need to derive the surface area of a part of a sphere defined by sweeping a certain angle in longitude and latitude. We'll use this to write a formula for the probability of generating a point in that section, which we'll use to derive a random sphere point generator.

Let's define a function A(r, θ₀, ... , θ_n-1) that is the surface "measure" of a portion of an n-dimensional sphere (1-dimensional sphere is a line segment, 2-dimensional sphere is a circle, etc) subtended by (n-1) ranges of angles (1 for a circle, 2 for a sphere .. longitude and latitude, etc). We know that A(r,θ) = rθ is a formula for the arc length of a circular arc of θ radians and radius r. I'll propose that the formula for the surface area of a portion of a sphere is based off of it

In fact, you can always find the next formula from the previous one by the relation

I won't prove this part (this is going to be long enough already). So, the part of the surface of a sphere swept out by

has the area

With a uniform distribution on the surface of a sphere, the probability of getting a point whose θ₁ is between 0 and x is

Therefore the formula for θ₁ is

So, a formula for an evenly distributed random point on the surface of a sphere is

The rest of this post has been removed until I can figure out what I did wrong. Look forward to having a nice formula for uniformly distributed points on the surface of a sphere in R⁴ soon.

Nth Term of the Fibonacci Sequence

2005-04-24T19:24:00.000-07:00

I can't remember how I first found this proof .. I think it might have been a homework assignment. Regardless, it's been one of my favorite proofs ever since, so I figured I should probably include it here. The object is to come up with a closed form solution for the nth term of the Fibonacci sequence f={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...} (I start with zero for the zeroth fibonacci number, and one for the first, but you'll see that this method allows you to easily compute a Fibonacci-like sequence with any two initial values)

Now lets write an iterative formula for the nth and (n+1)th term, and then we'll solve for a closed form solution.

So you can see, by multiplying this matrix repeatedly, it yields the nth and (n+1)th term

Now to simplify that nasty nth power of A, we'll use a trick known as diagonalization. If we can write A as a product of 3 matrices P, D and P inverse, where D is a diagonal matrix, it gives us an easy way to write the nth power of A

Now, I won't get into proving that this method of diagonalization works. If you want that much detail you can go here. Now, the next step is to find the eigenvectors and eigenvalues of A. So first we'll solve the characteristic equation of A.

So, now we find the eigenvectors for the two eigenvalues. For the eigenvalue

we find

So our first eigenvalue-eigenvector pair is

Now, for the second eigenvalue

we find

So our second eigenvalue-eigenvector pair is

Now we can construct our matrices

And to calculate P inverse, we'll need the determinant of P (the invese of P is the transpose of the cofactor matrix times one over the determinant)

and so

And now we plug it all in to find a formula for the nth power of A

And so we can see (from our second equation) that the formula for the nth number in the Fibonacci sequence is the lower left entry in this matrix

Using this result, you can easily find a formula for the nth term of any Fibonacci-like sequence (same rules for generating the sequence, but with different starting numbers) just by changing the vector that you multiply with the nth power of A.

Trig Identities

2005-04-24T16:36:00.000-07:00

This is a simple trick that helps me remember a number of useful trig identities in one derivation. We'll derive formulas for both cos(A+B) and sin(A+B) at the same time. First we'll derive a useful relationship between the exponential function, sine and cosine. The Taylor expansion of a function is

So the Taylor expansion of the the exponential function is

And the Taylor expansion of sine and cosine are

and

Now, expanding the exponential function of i (a square root of -1) times a number theta gives

So, now we'll use the fact that the product of two exponentials is the exponential of the sum of their powers to give

Now given that the real parts of both sides must be equal, as well as the imaginary parts, this one equation yields the following two identities

and

And that wraps her all up. Now you can easily derive cos(2A) and sin(2A) (the double angle identities) by plugging in A for B in the above equations. Similarly, you can derive sin(A-B) and cos(A-B) by substituting -B for B, and remembering that sin(-x) = -sin(x) and cos(-x) = cos(x).

Blog Intro

2005-04-24T08:07:00.000-07:00

I just started this blog as a way to keep track of the different interesting results I find in my day to day work as a video game programmer. You can look forward to seeing solutions to specific problems I've encountered, or just general mathematical grab-bag type stuff. I'll try to make at least one new post a week.