Game Math: Faster Sine & Cosine with Polynomial Curves

This post is part of my Game Math Series.

We have seen how to approximate a function using polynomials in this post. A good candidate for polynomial approximation would be the sine function, for it is used a lot in games and is not a cheap function to call. This is essentially the same task as approximating the consine curve, since the cosine curve is just a shifted sine curve.

The sine curve is periodic, so will just focus on the domain x \in [0, 2\pi)

sine

We will first try to match a quarter of the sine curve, a downward “hill”.

hill

We will impose four conditions, the positions and slopes of the hill top and the hill bottom. This means we have to use a polynomial of degree 3 (a cubic curve) to match this hill.

    \[ P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 \]

And we get these equations from the four conditions:

     \begin{flalign*}   P(0) &= 1 \\   P(\frac{\pi}{2}) &= 0 \\   P'(0) &= 0 \\   P'(\frac{\pi}{2}) &= -1 \\ \end{flalign*}

where f'(x) denotes the first-order derivative of the function f(x).

So here’s the system of equations we have to solve in order to obtain the coefficients of the polynomial:

     \begin{flalign*}   a_0 &= 1 \\   a_0 + \frac{\pi}{2} a_1 + \frac{\pi^2}{4} a_2 + \frac{\pi^3}{8} a_3 &= 0 \\   a_1 &= 0 \\   a_1 + \pi a_2 + \frac{3 \pi^2}{4} a_3 &= -1 \\ \end{flalign*}

After solving the system of equations, we get:

     \begin{flalign*}   a_0 &= 1 \\   a_1 &= 0 \\   a_2 &= \frac{2}{\pi} - \frac{12}{\pi^2} \\   a_3 &= \frac{16}{\pi^3} - \frac{4}{\pi^2} \\ \end{flalign*}

Let’s do a quick check by plotting the polynomial curve along with the original hill curve on the same figure:

double hill

The blue curve is the original hill curve, and the red curve is our polynomial. It looks like they are about the same. Good.

The final step is to copy this hill four times, and piece them together so they make up an approximation of the sine curve.

sines

The blue curve is the original sine curve, and the red curve is our four hill curves pieced together. Looking good.

Here’s the C++ code for implementing the faster sine with the polynomial we just derived:

#define PI         (3.1415926535f)
#define HALF_PI    (0.5f * PI)
#define TWO_PI     (2.0f * PI)
#define TWO_PI_INV (1.0f / TWO_PI)

inline float Hill(float x)
{
  const float a0 = 1.0f;
  const float a2 = 2.0f / PI - 12.0f / (PI * PI);
  const float a3 = 16.0f / (PI * PI * PI) - 4.0f / (PI * PI);
  const float xx = x * x;
  const float xxx = xx * x;

  return a0 + a2 * xx + a3 * xxx;
}

float FastSin(float x)
{
  // wrap x within [0, TWO_PI)
  const float a = x * TWO_PI_INV;
  x -= static_cast<int>(a) * TWO_PI;
  if (x < 0.0f)
    x += TWO_PI;

  // 4 pieces of hills
  if (x < HALF_PI)
    return Hill(HALF_PI - x);
  else if (x < PI)
    return Hill(x - HALF_PI);
  else if (x < 3.0f * HALF_PI)
    return -Hill(3.0f * HALF_PI - x);
  else
    return -Hill(x - 3.0f * HALF_PI);
}

And the cosine curve is just the sine curve shifted by \frac{\pi}{2}.

float FastCos(float x)
{
  return FastSin(x + HALF_PI);
}

The performance gain is about 3.5x on my machine. This is probably not as impressive as some other hacks you may find on the internet, but it’s faster than the original sine function nonetheless. Besides, you get to practice approximating a function using polynomials!

By the way, it is not a good idea to approximate the tangent function using polynomial approximation, because there are points in the function that have infinite slopes. Trying to approximate such functions near the points of infinite slope with polynomials would produce polynomials that fluctuate in grate magnitude. You may approximate the tangent function using the trigonometric identity tan \theta = \frac{sin \theta}{cos \theta} with sin \theta and cos \theta approximated by polynomials. The performance gain is about 1.5x on my machine using this approach.

About Allen Chou

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

7 Responses to Game Math: Faster Sine & Cosine with Polynomial Curves

  1. glen english says:

    One thing about using LUTs- when they get big they are BAD for cache misses …. OK on small SRAM micros where there is no cache.

  2. For such crucial operations like sine/cosine, I’d get rid of those branches. Maybe something
    like this:

    float a = HALF_PI - x;
    float b = 3.0f * HALF_PI - x;
    
    int s0 = sign_bit(x - HALF_PI);
    int ns0 = 1 - s0;
    
    int s1 = sign_bit(x - PI);
    int ns1 = 1 - s1;
    
    int s2 = sign_bit(x - 3.0f * HALF_PI);
    int ns2 = 1 - s2;
    
    // f(s0, s1, s2) -> (a, b, -a, -b), 
    // maps the sign bits to the values a, b, -a or -b
    float t = 
      (s0) * a + (ns0*ns1*s2)*b 
      + (ns0*s1*s2)*(-a) + (ns0*ns2) * (-b);
    
    int s = s1 - ns1;
    return s * Hill(t);
    

    The branches were removed, but at the expense of more mults/adds. I don’t know if these mults by 0/1 will be optimized, need to read the generated code/measure etc, but that’s just the idea.

    Very nice post though, obtaining complex functions like trig with just a few mults/adds is great! 🙂

    • Allen Chou says:

      I did a quick test on my machine using your code. Looks like the extra multiplications are not faster than the 4 branches. The branch-less implementation is only about 1.5x faster than std::sin on my machine.

  3. LittleBird says:

    Wrapping x is std::fmod, shouldn’t line 21 be x -= static_cast(a) * TWO_PI?

    • Allen Chou says:

      VC++’s implementation of std::fmod is just about the same speed as std::sin on my machine, so I avoided using it. And yes, line 21 should be x -= static_cast(a) * TWO_PI. Thanks for pointing it out.

Leave a Reply