The last time Hackerfall tried to access this page, it returned a not found error. A cached version of the page is below, or click here to continue anyway

Bezier Interpolation

After becoming frustrated with Apple's SpriteKit and it's lack of features, I decided to go all out and implement the missing ones myself. One of these features Apple forgot to implement (or half-assedly implemented )was easing on their animations. When my needs eventually called for easing along a specific path, I was flat out of luck. Although easing in itself is relatively easy to implement when moving objects from A to B in a straight line, moving along a curve is another story entirely. So I set out to learn about bezier curves. It's wasn't a particularly fun task because most of the online resources were either to verbose or just showed unhelpful snippets of code with loads of tiny, unlabeled variables. Then, which should have been my first stop, I stumbled on Bezier Curves on Wikipedia and it all clicked when I hit this gif.

Bezier curve animation. Whoever makes these gifs, I love you.

This is a cubic bezier curve. A cubic bezier curve is, in essence, four points. Po is the start point, P1 and P2 are control points 1 & 2 and P3 is the end point. The start and end point denote the beginning and end points of the path and the control points dictate how the path moves from the start to the finish. As you can see from the gif, the only variable changing is t which denotes how far the path has progressed from P0 to P3 (think percent).

Take a look at how the green point moves along the line P0 to P1. All it's doing is moving from A to B, linearly, with T. To get this point at T on P0 to P1, we'll create a function called pointInLine. This function takes in three parameters, point A the start of a line, point B the end of a line and percent T. It returns the point at T between A and B.

CGPoint pointInLine(CGPoint A, CGPoint B, float T) {
CGPoint C;
C.x = A.x - ((A.x - B.x) * T);
C.y = A.y - ((A.y - B.y) * T);
return C;
}

The formula in this function is the same for each axis. It get's the length of the line (on each axis respectively) by taking A - B and multiplies it by the percent T (between 0-1). It then adds the new, shortened line segment back onto the original point A to get a new point C. This function is the basis of all our calculations.

Let's take a look at our gif again, except freeze it on this specific frame stopped at t = 50.

I've marked where the algorithm is getting the points at T = 50 on each line. a is on the line p0-p1, b is on the line p1-p2, c is on the line p2-p3. Let's get a, b and c using our pointInLine function from earlier at T = 0.50.

float T = 0.50;
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
CGPoint C = pointInLine(p2, p3, T);

Moving further, we get d and e using the same method as above with instead of p0, p1, p2 and p3, we use a, b and c.

float T = 0.5;
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
CGPoint C = pointInLine(p2, p3, T);
CGPoint D = pointInLine(A, B, T); // The new D
CGPoint E = pointInLine(B, C, T); // and E

Now were down to our last point, f, which is the actual point on the curve. The one were looking for.

float T = 0.5;
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
CGPoint C = pointInLine(p2, p3, T);
CGPoint D = pointInLine(A, B, T);
CGPoint E = pointInLine(B, C, T);
CGPoint F = pointInLine(D, E, T); // The juicy one

All that's left now is to generate the curve of all points. Of course it's not possible to generate all the points but what you can do is generate enough to generate a smooth curve.

// Get 100 points
for(CGFloat T = 0; T &lt; 1; T += 0.01) {
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
CGPoint C = pointInLine(p2, p3, T);
CGPoint D = pointInLine(A, B, T);
CGPoint E = pointInLine(B, C, T);
CGPoint F = pointInLine(D, E, T);
drawPoint(F); // And draw the point on the screen
}

And there we go, a cubic bezier curve. What about quad curves, the 2nd degree bezier curve? Quad curves are simply half a bezier curve. Instead of 2 control points, we have one. A quad curve can be generated by drawing the change in position of percent T along line A-C.

// We have 3 points
CGPoint p0, p1, p2;
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
CGPoint D = pointInLine(A, B, T); // The point in the quad curve

Notice anything interesting here? The exact code for generating a point on the quad curve exists in the cubic curve. Let's break it up even further.

CGPoint pointInQuadCurve(CGPoint p0, CGPoint p1, CGPoint p2) {
CGPoint A = pointInLine(p0, p1, T);
CGPoint B = pointInLine(p1, p2, T);
return pointInLine(A, B, T); // The point in the quad curve
}

Now use this in our cubic curve, since a cubic curve is made up of two quad curves.

CGPoint pointInCubicCurve(CGPoint p0, CGPoint p1,
CGPoint p2, CGPoint p3) {
CGPoint A = pointInQuadCurve(p0, p1, p2);
CGPoint B = pointInQuadCurve(p1, p2, p3);
return pointInLine(A, B, T);
}

How about a quintic curve?

CGPoint pointInQuinticCurve(CGPoint p0, CGPoint p1, CGPoint p2,
CGPoint p3, CGPoint p4) {
CGPoint A = pointInQuadCurve(p0, p1, p2, p3);
CGPoint B = pointInQuadCurve(p1, p2, p3, p4);
return pointInLine(A, B, T);
}

You should have noticed by now the recurring pattern in the curve generation. You use the nth-1 degree function twice and then find the point in the line at T to get the nth degree curve point. Quintic is probably the most you'll ever need, if ever need it.

Hope you enjoyed my fairly informal and (probably too) detailed introduction to bezier curves. Have fun drawing your curves! The above code is implemented in my SKMech Spritekit utility library, if you were wondering.