Game Math: Curve Approximation via Curve “Projection”

Posted on February 4, 2017 by Allen Chou

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 \vec{a}, \vec{b}, and \vec{c}, the closest vector on the plane formed (or “spanned” in linear algebra jargon) by \vec{b} and \vec{c} is the projection of \vec{a} onto the plane. This projection, denoted \vec{d}, is a combination of scaled \vec{b} and \vec{c}, in the form of \vec{d} = u \vec{b} + v \vec{c}, that has the least error from \vec{a}.

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

    \[ err(\vec{a}, \vec{d}) = |\vec{a} - \vec{d}| \\ \]

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

    \[ \text{minimize} \enspace err(\vec{a}, \vec{d}) \enspace \Leftrightarrow \enspace \text{minimize} \enspace RMSE(\vec{a}, \vec{d}) \]

This is what the relationship of \vec{a}, \vec{b}, \vec{c}, and \vec{d} looks like visually:

The projection of \vec{a} onto the plane spanned by \vec{b} and \vec{c}, is the vector \vec{d} on the plan that has the least error from \vec{a}, and the difference vector \vec{a} - \vec{d} is orthogonal to the plane.

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

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

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

    \begin{flalign*} \vec{n} &= \vec{b} \times \vec{c} \\ \vec{d} &= \vec{a} - proj(\vec{a}, \vec{n}) \\ \end{flalign*}

But, I want to talk about another way of performing the projection, which is easier to translate to curves later. \vec{b} and \vec{c} are not necessarily orthogonal to each other. Let’s find two orthogonal vectors that lie on the plane spanned by \vec{b} and \vec{c}. Then, we split \vec{a} 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 \vec{a} 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 (1, 0, 0) and (0, 0, 1). To project a vector (4, 5, 6) onto the X-Z plane, we split it into a part that is parallel to (1, 0, 0), which is (4, 0, 0), and a part that is parallel to (0, 0, 1), which is (0, 0, 6). Combining those two parts together would give us (4, 0, 6). 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 \vec{b} and \vec{c} that span a plane, we can generate two orthogonal vectors, denoted \vec{e}_0 and \vec{e}_1, by using a method called the Gram-Schmidt process. The first vector \vec{e}_0 would simply be the \vec{b}. To compute the second vector \vec{e}_2, we take away from \vec{c} its part that is parallel to \vec{b}; what’s left of \vec{c} is orthogonal to \vec{b}:

    \begin{flalign*} \vec{e}_0 &= \vec{b} \\ \vec{e}_1 &= \vec{c} - proj(\vec{c}, \vec{e}_0) \\ \end{flalign*}

To compute \vec{d}, we combine the parts of \vec{a} that are parallel to \vec{e}_0 and \vec{e}_1, respectively:

    \begin{flalign*} \vec{a}_0 &= proj(\vec{a}, \vec{e}_0) \\ \vec{a}_1 &= proj(\vec{a}, \vec{e}_1) \\ \vec{d} &= \vec{a}_0 + \vec{a}_1 \end{flalign*}

More on Gram-Schmidt Process

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

The first vector \vec{q}_0 would simply be \vec{p}_0. To compute the second vector \vec{q}_1, we take away from \vec{p}_1 its part that is parallel to \vec{p}_0. To compute the third vector \vec{q}_2, we take away from \vec{p}_2 its part that is parallel to all previously generated orthogonal vectors, \vec{p}_0 and \vec{p}_1. Repeat this process until we have reached \vec{p}_{M-1} and produced \vec{q}_{M-1}:

    \begin{flalign*} \vec{q}_0 &= \vec{p}_0 \\ \vec{q}_1 &= \vec{p}_1 - proj(\vec{p}_1, \vec{q}_0) \\ \vec{q}_2 &= \vec{p}_2 - proj(\vec{p}_2, \vec{q}_0) - proj(\vec{p}_2, \vec{q}_1) \\ ... \\ \vec{q}_{M-1} &= \vec{p}_{M-1} - \sum^{M-2}_{i=0}{proj(\vec{p}_{M-1}, \vec{q}_i)} \\ \end{flalign*}

Projecting an N-dimensional vector onto this M-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, M = 2 and N = 3. 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 0 \leq t \leq 1. Given a 3rd-order polynomial curve f(t) = 1 + t - t^2 + t^3, 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 f_2(t) = 1 + t - t^2 and f_1(t) = 1 + t? Here’s what they look like:

At first glance, I’d say f_2(t) and f_1(t) are not what we want. We can definitely find a parabolic curve and a line that approximate f(t) better. Look at just how far apart f_2(t) and f_1(t) are from f(t) at t = 1. Clearly, f_2(t) and f_1(t) are not the 2nd-order and 1st-order polynomial curves that have the least RMSEs from f(t). 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 f(t) lives in. The lower-order polynomial curve that has the least RMSE from f(t) is the projection of f(t) into that lower-order polynomial space. Let’s start with finding the 2nd-order polynomial curve that has the least RMSE from f(t).

The 2nd-order polynomial subspace is 3-dimensional, since a 2nd-order polynomial curve has the form x + y t + z t^2. Let’s first find 3 curves that span the subspace. An easy pick would be j_0(t) = 1, j_1(t) = t, and j_2(t) = t^2. Now we need to use them to generate a set of orthogonal curves, k_0(t), k_1(t), and k_2(t) using the Gram-Schmidt process:

    \begin{flalign*} k_0(t) &= j_0(t) \\ k_1(t) &= j_1(t) - proj(j_1(t), k_0(t)) \\ k_2(t) &= j_2(t) - proj(j_2(t), k_0(t)) - proj(j_2(t), k_1(t)) \\ \end{flalign*}

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

Here are the results:

    \begin{flalign*} k_0(t) &= 1 \\ k_1(t) &= \dfrac{-1}{2} + t \\ k_2(t) &= \dfrac{1}{6} - t + t^2 \\ \end{flalign*}

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

    \begin{flalign*} s_0(t) &= proj(f(t), k_0(t)) = \dfrac{25}{12} \\ s_1(t) &= proj(f(t), k_1(t)) = \dfrac{-29}{10} + \dfrac{29}{20}t \\ s_2(t) &= proj(f(t), k_2(t)) = \dfrac{5}{12} - \dfrac{-5}{2}t + \dfrac{5}{2}t^2 \\ \end{flalign*}

Here’s what s_0(t), s_1(t), and s_2(t) look like alongside f(t):

s_1(t) and s_2(t) might not look like they are close to f(t), but they are the closest curves you can get along the axes k_1(t) and k_2(t) that have the least RMSEs from f(t).

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

    \begin{flalign*} g(t) &= s_0(t) + s_1(t) + s_2(t) \\ &= \dfrac{21}{20} + \dfrac{2}{5}t + \dfrac{5}{2}t^2 \\ \end{flalign*}

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 f(t) by simply dropping s_2(t) from g(t):

    \begin{flalign*} h(t) &= s_0(t) + s_1(t) \\ &= \dfrac{19}{30} + \dfrac{29}{10}t \\ \end{flalign*}

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!

About Allen Chou

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:
    March 23, 2017 at 03:08

    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?

    Reply

Leave a Reply