A Better Bezier Curve — A Polynomial in SwiftUI
Bernstein’s polynomials are an alternative to De Casteljau Beziers
During my research for the second article, I found myself talking to a chap in the U.S. called Alan Wolfe. A man who it seems has done a lot of work in this area. Not only did Alan help me understand De Casteljau’s formula and fix a bug in my code, but he also suggested I try Bernstein’s power basis polynomials as an alternative formula to build Bezier curves.
Polynomials sometimes make more sense. First, what’s wrong with the De Casteljau method anyway? The problem is that, well, it has a complexity of O(n2). This basically means it quickly starts to get computationally expensive as the number of control points you add increases.
Let’s revisit it briefly. Now the leading GIF of the second piece I wrote had three control points and six start/endpoints, which makes sense… only it doesn’t. You see, you’re not looking at a single Bezier curve on that GIF. You’re looking at three individual Bezier curves that I tagged together. I modified the placement of the endpoints and created another GIF to illustrate the point. The control points here are the purple, red, and yellow crosses. The start/endpoints are the red, green, blue, and yellow circles:
If I draw a single Bezier curve with two control points, I end up with something with far less movement. You can see a single Bezier curve in this GIF:
The single Bezier curve is far more stable, at least in part because of the opposing pink control point. You can also see with more points on the grey curve some incongruity with the grey line as it warps. A classic case of less is more since you don’t notice it will have fewer points (in the earlier GIF).
Hey, you still may not see the problem. The clue is in fact in the code. Ironically, to calculate the black line here (single Bezier curve with multiple control points), I needed a dozen more lines of code and temporary storage for the combined sets. Had I used Bernstein’s method, it would have been far simpler.
So how do you use Bernstein’s power base polynomials? They work like this. The variable t is time and the variable s = 1 -t. You have a distinct formula linked to the number of control points you need. There are three equations below. Obviously, you can build bigger ones using the same pattern:
- Linear Bezier (aka linear interpolation): y = A*s + B*t
- Quadratic Bezier: y = A*s² + 2*B*st + C*t²
- Cubic Bezier: y = A*s³ + 3*B*s²t + 3*C*st² + D*t³
The magic numbers in the formulae correspond to Pascal’s triangle, which looks like this:
What does this look like in code and, perhaps more importantly, on paper (some electronic grid paper, that is)? Here you go:
I call this method with a single line in my code:
altPoints = bPolyCubicBezier(fp:redPoint,sp:purplePoint,tp:yellowPoint,lp:orangePoint)
This will build a cubic Bezier curve that is drawn here with triangles. There is more movement in the black line because it doesn’t take the red control point into account. If the red point swung that the same way as the purple and yellow crosses, the lines would track each other.
Which method do you use in which situation? Well, if you have a very specific case where you know the number of control points isn’t going to change, then Bernstein’s solution looks better. It takes less CPU and less code. But if your requirement is more generic and may change, then the De Casteljau method makes more sense — even it takes more CPU and more code.
This brings me to the end of the article. I hope you enjoyed reading it as much as I did writing it and learned something new in the process.
Here is the code to generate and animate a polynomial. As you can see, 95% of it is simply setting up the initial values and then changing the values within them. The
poly function is itself is just over a dozen lines:
Keep calm, keep coding…