Game Math: Approximation with Polynomial Curves

This post is part of my Game Math Series.

Polynomials

A polynomial is an expression consisting of linear combination of products of variables raised to non-negative integer powers. In this post, I will specifically focus on polynomials of a single variable, namely polynomials of the form:

    \[ P(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n = \sum_{i = 0}^{n}{a_i x^i} \]

The polynomial above are said to have degree n if the coefficient a_n is non-zero.

Polynomial Curves

We can create curves with polynomials by using the equation y = P(x).

For instance, we can create a parabola with y = x^2:

parabola

Or a down-facing parabola shifted from the origin: y = -(x - 0.5) ^ 2 + 1.

parabola2

Approximating Curves with Polynomial Curves

For games, some mathematical functions are so expensive that it is beneficial to approximate them using polynomial curves. In general, the higher the degree of polynomial we use to approximate the function, the better the approximation will be.

So we have a function that we want to approximate, y = f(x), and a polynomial of degree n, P(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n. We need to find all the coefficients a_i of the polynomial. That gives us (n + 1) unknowns, which means we will need (n + 1) equations to obtain all the coefficients.

How do we get the (n + 1) equations? It depends on how you want the curve to match the function f(x). If we want the curve to perfectly match the curve at x = 0 and x = 1, then we get these two equations:

    \[ \begin{aligned}   P(0) = f(0) \\   P(1) = f(1) \\ \end{aligned} \]

Sometimes matching the points on the function curve is not enough. We might want to also match the slopes of the curve at certain points. Say we also want to match the function curve’s slopes at x = 0 and x = 1, then we get another two equations:

    \[ \begin{aligned}   \left.{\frac{\mathrm{d} P}{\mathrm{d} x}}\right|_{x = 0}    =    \left.{\frac{\mathrm{d} f}{\mathrm{d} x}}\right|_{x = 0}   \\   \left.{\frac{\mathrm{d} P}{\mathrm{d} x}}\right|_{x = 1}    =    \left.{\frac{\mathrm{d} f}{\mathrm{d} x}}\right|_{x = 1} \end{aligned} \]

Four equations means four conditions for our approximation. In order to satisfy n conditions when approximating a function with a polynomial, we need the polynomial to have a degree of at least (n - 1), giving us n coefficients.

In this case, we need a cubic polynomial, P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3.

Let’s pick the exponential function, f(x) = e^x to be the function we want to approximate with P(x). Using the four equations above, we can solve for the four coefficients (a_0, a_1, a_2, and a_3).

     \begin{flalign*}   P(0) &= a_0  = f(0) = 1   \\   P(1) &= a_0 + a_1 + a_2 + a_3 = f(1) = e   \\   \left.{\frac{\mathrm{d} P}{\mathrm{d} x}}\right|_{x = 0}   &=    a_1    =    \left.{\frac{\mathrm{d} e^x}{\mathrm{d} x}}\right|_{x = 0}    =    1   \\   \left.{\frac{\mathrm{d} P}{\mathrm{d} x}}\right|_{x = 1}   &=    a_1 + 2 a_2 + 3 a_3    =    \left.{\frac{\mathrm{d} e^x}{\mathrm{d} x}}\right|_{x = 1}    =    e \end{flalign*}

After removing all the noise, we get:

     \begin{flalign*}   a_0 &= 1   \\   a_0 + a_1 + a_2 + a_3 &= e   \\    a_1 &= 1   \\   a_1 + 2 a_2 + 3 a_3 &= e \end{flalign*}

We can then solve this system of equations and obtain the coefficients:

     \begin{flalign*}   a_0 &= 1   \\   a_1 &= 1   \\    a_2 &= 2e - 5   \\   a_3 &= -e + 3 \end{flalign*}

And here’s the polynomial that we’ll use to approximate y = f(x) = e^x:

    \[ P(x) = 1 + x + (2e - 5) x^2 + (-e + 3) x^3 \]

Let’s see how close we are by plotting y = e^x and y = P(x) on top of each other.

exponential match

The blue curve is the exponential curve, and the red curve is the polynomial approximation. They are almost identical between x = 0 and x = 1. They are exactly the same up to the first-order derivative at x = 0 and x = 1, because these are the four conditions we used to come up with the polynomial.

The approximating polynomial will be accurate around the points you choose for the conditions (in this example, x = 0 and x = 1). If you’d like the polynomial curve to match at other points of the curve, then you’ll need a polynomial of higher degree and more equations to solve for the coefficients of the polynomial.

Approximation with Polynomial Curves

This is how you would approximate a function with polynomial curves. In general, the more accurate you want the polynomial curve to be, the higher the degree of the polynomial will be, and the more coefficients you’ll have to solve for.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Gamedev, Math. Bookmark the permalink.

Leave a Reply