# Game Math: Curve Approximation via Curve “Projection”

This post is part of my Game Math Series.

Also, this post is part 2 of a series (part 1) leading up to a geometric interpretation of Fourier transform and spherical harmonics.

Drawing analogy from vector projection, we have seen what it means to “project” a curve onto another in the previous post. This time, we’ll see how to find a the closest vector on a plane via vector projection, and then we’ll see how it translates to finding the best approximation of a curve via curve “projection”. This handy analogy can help us take another step closer to a geometric interpretation of Fourier transform and spherical harmonics later.

### Closest Vector on a Plane

Given vectors , , and , the closest vector on the plane formed (or “spanned” in linear algebra jargon) by and is the projection of onto the plane. This projection, denoted , is a combination of scaled and , in the form of , that has the least error from .

The error is measured by the magnitude of the difference vector:

As pointed out in the previous post, minimizing this error is essentially equivalent to minimizing the root mean square error (RMSE):

This is what the relationship of , , , and looks like visually:

The projection of onto the plane spanned by and , is the vector on the plan that has the least error from , and the difference vector is orthogonal to the plane.

So how do we compute ? In the previous post we’ve seen how to project a vector onto another, so would computing be as simple as projecting onto , and then project the result again onto ? Not really. Here’s why:

As you can see in the figure above, isn’t parallel to nor . Projecting onto would give you a vector that is parallel to , and a subsequent projection onto would leave you with a result that is parallel to , which is definitely not .

One way to do it is to calculate a vector orthogonal to the plane, i.e. a plane normal , by taking the cross product of the two vectors that span the plane: . Then, take out the part in that is parallel to by subtracting the projection of onto from . What is left of is the part of that is parallel to the plane, i.e. the projection:

But, I want to talk about another way of performing the projection, which is easier to translate to curves later. and are not necessarily orthogonal to each other. Let’s find two orthogonal vectors that lie on the plane spanned by and . Then, we split into two parts, one parallel to one vector and one parallel to the other vector. Finally, we combine these two parts together to obtain a vector that is essentially the part of that is parallel to the plane.

As a simple illustration, if the plane is the X-Z plane, then the obvious two orthogonal vectors of choice would be and . To project a vector onto the X-Z plane, we split it into a part that is parallel to , which is , and a part that is parallel to , which is . Combining those two parts together would give us . This makes sense, because projecting a vector onto the X-Z plane is just as simple as dropping the Y component.

Now, given two arbitrary vectors and that span a plane, we can generate two orthogonal vectors, denoted and , by using a method called the Gram-Schmidt process. The first vector would simply be the . To compute the second vector , we take away from its part that is parallel to ; what’s left of is orthogonal to :

To compute , we combine the parts of that are parallel to and , respectively:

### More on Gram-Schmidt Process

The Gram-Schmidt process is actually more general than described above. It can apply to higher dimensions. Given vectors, denoted to , in an -dimensional space (), and if the vectors are linearly independent, i.e. they span an -dimensional subspace, then we can generate vectors that are orthogonal to each other, denoted through , spanning the same subspace, using the Gram-Schmidt process.

The first vector would simply be . To compute the second vector , we take away from its part that is parallel to . To compute the third vector , we take away from its part that is parallel to all previously generated orthogonal vectors, and . Repeat this process until we have reached and produced :

Projecting an -dimensional vector onto this -dimensional subspace would involve combining the parts of the vector parallel to each of the orthogonal vectors. In our example above that involves 3D vectors, and . In higher dimensions, no simple 3D cross products can save you there.

Now we are done with vectors. Let’s take a look at curves!

### Curve Approximation

Let’s say our interval of interest is . Given a 3rd-order polynomial curve , what’s the best approximation using a 2st-order polynomial curve, or a 1th-order polynomial curve (flat line)? How about simply dropping the higher-order terms, so we get and ? Here’s what they look like:

At first glance, I’d say and are not what we want. We can definitely find a parabolic curve and a line that approximate better. Look at just how far apart and are from at . Clearly, and are not the 2nd-order and 1st-order polynomial curves that have the least RMSEs from . Simply dropping higher-order terms turns out to be a naive approach. The right way to do it is just like what we did with vectors: projection.

In the vector example above, we were operating in the 3D geometric space. Now we are working with a more abstract 3rd-order polynomial space where lives in. The lower-order polynomial curve that has the least RMSE from is the projection of into that lower-order polynomial space. Let’s start with finding the 2nd-order polynomial curve that has the least RMSE from .

The 2nd-order polynomial subspace is 3-dimensional, since a 2nd-order polynomial curve has the form . Let’s first find 3 curves that span the subspace. An easy pick would be , , and . Now we need to use them to generate a set of orthogonal curves, , , and using the Gram-Schmidt process:

If you forgot how to “project” a curve onto another, please refer to the previous post.

Here are the results:

You can say that , , and are a set of orthogonal axes spanning the 2nd-order polynomial subspace. Now we split into three orthogonal parts by projecting it onto , , and :

Here’s what , , and look like alongside :

and might not look like they are close to , but they are the closest curves you can get along the axes and that have the least RMSEs from .

Now, we can combine the three orthogonal parts of to form the 2nd-order polynomial curve that is the best approximation of :

This looks way better than the result of simply dropping the 3rd-order term, as shown in the figure above.

Since the three parts are already orthogonal, we can actually obtain the 1st-order polynomial curve that best approximates by simply dropping from :

Also looking good, compared to simply dropping the 3rd-order and 2nd-order terms.

That’s it. In this post, we’ve seen how to generate a set of orthogonal curves from a set of curves spanning a lower-dimensional subspace of curves, and use the orthogonal curves to find the best approximation of a curve via curve “projection”.

We now have all the tools we need to move onto Fourier transform and spherical harmonics in the next post. Finally, something game-related!

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Uncategorized. Bookmark the permalink.

### 3 Responses to Game Math: Curve Approximation via Curve “Projection”

1. Kamil says:

This is really great! 🙂 When we could expect the next part? I’m not trying to hurry you, I can imagine that writing on such topic is not an easy task (or at least not a quick task). I’m just wondering if you already scheduled the next part? Or is it postpone when you have more time?

• Allen Chou says:

It’s on my list. But there are other things going on right now, so it’s currently not my top priority.

• Kamil says:

I see. Thanks for the quick answer.