Bézier Interpolation
Create smooth shapes using Bézier curves.
In this article, we will see how we can use cubic Bézier curves to create a smooth line that goes through a predefined set of points. If you don’t know what Bézier curves are, you might want to check out this post I have written which could do as an introduction, or simply browse Wikipedia!
Cubic Bézier Curves
The goal is to fit n+1 given points (P0, …, Pn). In order to fit these points, we are going to use one cubic Bézier curve (4 control points) between each consecutive pair of points.
So in this figure, G0, G1, and G2 are three different cubic Bézier curves that start and end at (P0, P1), (P1, P2), and (P2, P3) respectively. Since any Bézier curve always starts and ends at the first and last control points, we are left with 2 control points for each curve that we will have to find so that the resulting line looks smooth.
You might want to refer back to fig. 1 during the article to understand the indices we will be using.
The general equation of the cubic Bézier curve is the following:
Where K are the 4 control points. In our case, K0 and K3 will be two consecutive points that we want to fit (e.g. P0-P1, or P1-P2, etc.), and K1 and K2 are the remaining 2 control points we have to find.
Problem Setup
Given that we have n+1 points to fit, we will use a cubic Bézier curve to fit each consecutive par of points. We denote Γi the Bézier curve that fits Pi to Pi+1:
Where ai and bi are left to find. Notice that there are n curves.
If we want the final curve to be smooth, we need to ensure that the transition between Γi and Γi+1 is smooth around Pi+1. In other words, that the curvature of Γi matches the curvature of Γi+1 around Pi+1. Mathematically, this means respecting the following conditions:
We need to find all the ai and bi. Since we have one pair of them in each Bézier curve, and since we have n curves, we need to find 2n variables. However, here we have 2(n-1) equations. We are missing 2 equations to solve the system. Therefore, we impose the following (arbitrary) boundary conditions:
Write the system
Before solving the system, we need to calculate the first and second derivatives of Γi and write the system down.
and,
Inject the equations
Injecting eq. 7 into eq. 3:
Injecting eq. 8 into eq. 4:
Injecting eq. 8 into eq. 5:
Finally, injecting eq.8 into eq. 6:
Solve the system
To sum up, we have the following 2n equations:
In order to solve the system are going to eliminate all the bi by injecting eq. 9 into eq. 10, 11, 12. Using eq. 9:
Injecting eq. 13 into eq. 10:
Injecting eq. 13 into eq. 11:
Almost there! We now need to inject eq. 13 into the fourth equation, eq. 12. However, eq. 12 has bn-1 but eq. 13 holds until bn-2. Good news, we can use eq. 14 to get rid of bn-1 then inject bn-2.
All right! To summarise we have in this order eq. 15, 13, 16:
We can write this system as a matrix multiplication and solve it. Hold on, we’re there!
As you can see, the first matrix has only 3 diagonal filled with values, others are zeros. This kind of matrix is called, reasonably enough, a tridiagonal matrix. Algorithms exist to solve this type of systems efficiently, such as Thomas Algorithm which runs linearly in time. For the sake of simplicity, we won’t bother optimising further and we will simply use the built-in functions of Numpy in Python to solve the system.
However, we are still missing the bi points. To find these we simply make use of eq. 13 which works out all the bi up until bn-2 and then eq. 12 which gives the last term, bn-1.
We are done at last! Let’s see how we can program this using Python.
Python Code
I did my best to make the code as clear as possible, and I added comments. If you can’t get your head around something don’t hesitate to comment!
Finally, this is how we would use this code:
In my case, I got this:
This is it for this article! I hope you enjoyed it and don’t hesitate to comment any question you might have!
