Today I’m going to get all mathy on you. Don’t worry about it – it’s going to be pretty simple math and in the end we’re going to learn how to split a cubic Bézier curve into two new curves.
First, let’s start off with parametric equations. This is a type of equation that adds a new variable, t, which can be thought of as time. In our world, t is going to range from 0 (the start) to 1.0 (the end). So for example, if I have a line segment from point A to point B, then point A is at time 0, point B is at time 1 and the midpoint is at time 0.5.
Let’s look at midpoint briefly – you probably learned midpoint as this:
x’ = (x1 + x0)/2
y’ = (y1 + y0)/2
or simply, the average of the x’s and the y’s. But let’s have some fun with this. I’m going to only work with x components, but I assure you that this works just fine with both. First, I’m going to rewrite that divide by 2 as a multiply by 0.5:
x’ = (x1 + x0) * 0.5
Now, let’s distribute this over the terms:
x’ = 0.5x1 + 0.5x0
Now, I’m going to rewrite the second term as an equivalent:
x’ = 0.5x1 + -0.5x0 + x0
We simplify and associate:
x’ = (x1 – x0) * 0.5 + x0
This is an equivalent, if slightly more general version of midpoint. So why did we do that? Because we can now replace that 0.5 with t as time and we have a complete parametric equation for a line:
x’ = (x1 – x0) * t + x0
y’ = (x1 – y0) * t + y0
I’ve also given you the formula for linear interpolation from one point to another – it’s the same. And to help you along, I’m going to give you a new verb, lerp, which means to linear interpolate from A to B.
P0 and P3 are end points and P1 and P2 are the control points. The parametric formula for this curve is this:
x = axt3 + bxt2 + cxt + x0
y = ayt3 + byt2 + cyt + y0
It looks like a handful, but it’s not really that bad – it’s a third degree polynomial that is a function of t and not of x or y. One tricky part is understanding the relationship between the four control points and the coefficients of the t terms. Again, let’s work with just the x side, since the y equation will work out the same. I’m not going to derive these for you – trust me.
ax = x3 – ( 3 * x2) + (3 * x1) – x0
bx = (3 * x2) – (6 * x1) + (3 * x0)
cx = (3 * x1) – (3 * x0);
The variables x0 through x3 correspond to the X coordinates for points P0 through P3 in the diagram above. So let’s look at splitting this Bézier in half. We’ll do this graphically by first drawing in some guides:
I’ve added a line between P1 and P2 and added three new points, P4, P5, and P6. Each of these points are at the midpoint of the segment on which they lie. Now, let's connect the midpoints together:
Here I’ve added two new midpoints, P7 and P8. Repeat again to leave us with a new line and midpoint:
And P9 is on the right on the curve. Furthermore, the first section of the split curve from P0 to P9 can be described with the four points, P0, P4, P7 and P9:
and the second part of the split curve and be described with points P9, P8, P6 and P3:
If you’re still with me, you’ll note that if you keep splitting the subcurves, you will eventually draw every point on the original curve. And you can do this all with calling midpoint successively. Generally speaking, in software we like this because midpoint is one add and one divide by two. If you’re working in fixed point, this is wonderful because that becomes an add and a bitshift, both very fast instructions. In theory, I could do the subdivision of a curve in 14 instructions (plus about 7 instructions of overhead) per coordinate. That’s really not a lot. There’s a problem though – splitting a Bezier this way to, say, draw it with a series of straight lines is not so good as it’s not obvious when you should subdivide further or be satisfied with what you have. In other words, a small change in t may make a substantial change in the distance traveled along the curve and the next change in t is likely NOT going to end up with the same change on the curve. So midpoint is not really the best way to do this. What if we wanted to use any arbitrary t? We could use the general formula above, but that may not be the best choice – we don’t like the cubes and squares so much and while that will give as a point on the curve, it won’t let us actually split the curve because we would be missing the new control points.
So let’s go back to our original midpoint formula and throw it away. Instead of using midpoint, we’re going to use the parametric equivalent. So give the T you want, you get P4 by lerping from P0 to P1, you get P5 by lerping from P1 to P2, you get P6 by lerping from P2 to P3. Moving to the next step (red), you get P7 by lerping from P4 to P5, you get P8 by lerping from P5 to P6. Finally, to get P9 by lerping from P7 to P8. In implementation, each lerp is a multiply and two adds. 6 lerps is therefore 6 multiplies and 12 adds, or about 30 instructions.
Now if we used the polynomial form each coordinate would be 5 multiplies and 3 adds per coordinate, but we wouldn’t have the control points of the new curves and getting them turns out to be more work than just doing all the lerping in the other solution.
There are two closely related problems that fall out from this work –
1. How do I draw a cubic Bézier with the fewest/optimal straight line segments?
2. What is the length of a cubic Bézier curve?
If you can solve the first problem, you can come up with an approximation for the second. We’ll save this for another time, though.
About the AuthorFollow on Twitter More Content by Steve Hawley