Spoiler alert: It’s not so complicated.
Let’s say you were given an interesting function f(x) that describes an arbitrary curve, for 0 ≤ x ≤ 1.
You can only solve for f(x) through an API, but cannot represent it any other how.
How you will you send this curve over a network?A simple method would be to sample (solve f(x)) at many points and then send those coordinates over the network.
The receiving client can then connect the dots and form an (almost) smooth curve, without actually solving for f(x).
This solution works for small sets of data; however, we want to have a more concise and human-friendly way of storing those curves.
In this article, I’ll talk about the bezier curve.
Bezier curves for the laymanBezier curvesBezier curves are described by a set of control points, which are repeatedly linearly interpolated.
The resulting curve passes through the initial and final control points, but is only attracted to the other points.
This curve’s degree is directly related to the number of control points.
This bezier curve has four control points; hence, it is a cubic polynomial.
I like to think bezier curves as recursive, weighted averaging of points.
Take two points A(x,y) and B(x’,y’): how do we connect these two points?Let’s say a variable point C cuts AB at a ratio t:(1 – t), then C is the average of A and B, where A is given weight t and B is given weight (1-t).
Essentially,C = t*A + (1 – t)*BLinear bezier curve formation from WikipediaNow, the mid-point is when t=1/2, where C = A/2 + B/2.
If you sample this equation from 0 to 1, then you will connect A and B.
Congrats, you’ve already learnt the linear Bezier curve.
Extending the linear Bezier curve to higher degreesLet’s first make a notation for a point between A and B, that is calculated by parameter t in the equation we formed.
That point can be P(A, B, t).
That means P(A, B, 1/2) is the mid-point of AB and P(A, B, 1/3) and P(A, B, 2/3) divide AB into three parts.
Now, we want to form a quadratic curve that goes from A to C, and is attracted towards point B.
Just like we took the weighted average of A and B in the linear bezier curve, we will take the weighted average of corresponding points on AB and BC.
P(A, B, C, t) = t * P(A, B, t) + (1 – t) * P(B, C, t)Quadratic Bezier Curve from WikipediaSimilarly, you can this to the next level and take the weighted average of two points on two quadratic bezier curves (P⁰P¹P² and P¹P²P³), which are indicated by the blue dots.
and form a cubic curve.
Cubic Bezier Curve from Wikipedia; the green dots are control points for a quadratic bezier curve; blue for linear bezier curve; the black one for the final point.
You can generalize an algorithm from these animations:Each curve has n+1 control points, where n is the degree of the bezier polynomial.
To evaluate a point at parameter t, you take the weighted average of each line segment at t, then you get another set of points (with one less point) that represent a polynomial of degree n – 1.
You repeatedly take weighted averages at t again and again, until you reach one point.
To draw the whole curve, you use the above algorithm repeatedly for 0≤t≤1.
De Castelijau’s algorithm is another way to draw a bezier curve.
If you take a point evaluated at parameter t, then the curve can be split into left and right curves at that point.
Hence, you repeatedly split curves until a certain depth, and store the splitting points in an array.
Bezier curves are good for a few points.
However, several points cannot be connected using one bezier curve.
This is because the degree of the resulting curve will be very, very high.
A higher degree means more computation power is used and the curve will be excessively “smooth” and will be barely “attracted” to any one point.
In practice, bezier curves are knitted together piecewise for many points.
Final notes: Bezier curves are just interpolation of control points.
They are the basis for B-Splines, which can be thought of knitting together lower degree bezier curves for more than n+1 points.
.