BSpline Theory

Cubic Functions

At its core, BSplines are cubic functions, a function with a degree of 3. For example, a simple linear equation: \(f(x)= mx+b\) has a degree of 1, because the highest power in the equation, is 1.
A quadratic: \(f(x)= Ax^2+Bx+C\) has a degree of 2. When increasing the degree,the base equation just gets a new coefficient and degree. For example, a quintic equation would be \(f(x) = Ax^5 + Bx^4 + Cx^3 + Dx^2 + Ex + F\)
Let’s substitute \(x\) as \(t\), the time it takes between the beginning and end of a curve, usually expressed as \(t \in [0,1]\) which basically means that all curves happen on a range from 0 to 1.
This means that any t value that is plugged into the equation, for example \(t = 0.6\), will give you the vector, or coordinate that is exactly \((t*100)\)% along the line.
With this in mind, let’s write the cubic function equation: \(f(t) = At^3 + Bt^2 + Ct +D\)

2D curves

For a given function \(f(t)\), it is important to note that this function cannot have multiple outputs for the same input. If it weren’t for this, it wouldn’t be considered a function.
However, we can get around this by essentially assigning \(t\) values. We must keep in mind that although \(t\) is a substitution of \(x\), it does directly correspond to the X-Axis.
Therefore, a vector/coordinate at \((x:5,y:5)\) could have a \(t\) value of \(0.2\).
Then, if you were to create another vector at \((x:5,y:10)\), and assign it at a \(t\) value of \(0.4\), you could create a curve between the two.
Unfortunately, simply creating a function passing through both vectors runs into the same issue.
This is where 2D curves come in. Imagine that each \(x\) and \(y\) value of a function relates to another function. This allows you to model 2 functions, one for \(x\) and one for \(y\).
As a result, the function doesn’t pass through 2 points on the same \(x\) value, but passes through one point on the \(x\) function and 2 on the \(y\) function.
This can be modeled as \((x:f(t),y:g(t))\) where \(f(t)\) is the \(x\) function, and \(g(t)\) is the \(y\) function.
Imagine a coordinate plane where the \(x\) axis is represented as \(t\) and the \(y\) axis is represented by \(x\). This is the \(x\) function’s ‘space’
In the ‘space’, the coordinates from earlier could be written as \((0.2,5)\) and \((0.4,5)\), following the scheme of \((t,x)\).
Similarly, the coordinates on the \(y\) function’s ‘space’ would be \((0.2,5)\) and \((0.4,10)\). Each function can be solved by interpolation (more on that later), because now, there is only one output for each input. Then, just plug the functions back into \((f(t),g(t))\).
Interpolation is the process of inputting control points and generating a curve that passes through those points.
To gain a more in-depth understanding of 2D splines, we recommend watching this.YouTube video .

BSpline Features

BSplines possess multiple advantageous properties making them a perfect fit for FTC pathing!

BSplines are \(C_2\) continuous: Their curves are connected, their first derivatives are connected, and the second derivatives, or the derivatives of the derivatives are connected.
This translates to exceptionally smooth pathing without any sudden jerks, and enables efficient computing.
BSplines are \(G_1\) continuous, meaning that the curvature is continuous. This essentially means that the robot won’t experience any acceleration jumps while traveling the path.
BSplines are somewhat similar to Bezier Curves as they do not interpolate ANY control points. As a result, BSplines do not pass through any of the specified control points, but, these control points do influence the shape of the curve, By using a clever mathematical concept, we are also able to make BSplines interpolate their specified enpoints, allowing for better control of the curve.
BSplines have complete local control. This means that adjusting a control point will only affect a small part of the curve, and not the whole thing. For example, adjusting a control point near one of the spline’s endpoints will not change anything near the other endpoint.

The Math

How is a BSpline actually formed? To acquire an in-depth understanding of the formation of a BSpline, the matrix form of a function must be understood first.

The matrix form of a function is defined as \(f(t) = T*C*P\) where \(T\), \(C\), and \(P\) are all matrices representing the function’s polynomial form. T is a matrix \(\begin{bmatrix}1 & t & t^2 & t^3 \end{bmatrix}\) that represent the \(T\) value in the polynomial. The \(C\) matrix, or Characteristic matrix is the matrix that defines the curve. Below is a representation of how the matrix would look:

\(\begin{bmatrix} c_0 & c_1 & c_2 & c_3 \\ c_4 & c_5 & c_6 & c_7 \\ c_8 & c_9 & c_{10} & c_{11} \\ c_{12} & c_{13} & c_{14} & c_{15} \\ \end{bmatrix}\)

This matrix is constant based on the type of spline you are using. For example, all cubic bezier curves will have the same \(C\) matrix, but a BSpline will have a different one for all types of BSplines. Lastly, we have the \(P\), the point matrix. This is expressed as:

\(\begin{bmatrix} P_0\\ P_1\\ P_2 \\ P_3 \\ \end{bmatrix}\)

The BSpline matrix form also has a static coefficient before the \(C\) matrix.

\(\begin{bmatrix}\dfrac{1}{6}\end{bmatrix}\)

Now, let’s input the values into the \(C\) matrix and add the coefficient to assemble it all together!

\(f(t) =\) \(\begin{bmatrix}1 & t & t^2 & t^3 \end{bmatrix}\) \(\begin{bmatrix}\dfrac{1}{6}\end{bmatrix}\) \(\begin{bmatrix} 1 & 4 & 1 & 0 \\ -3 & 0 & 3 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \\ \end{bmatrix}\) \(\begin{bmatrix} P_0\\ P_1\\ P_2 \\ P_3 \\ \end{bmatrix}\)

After obtaining the matrix form, we can utilize matrix multiplication to transform the matrices into a polynomial. Let’s look at the polynomial coefficient form. This is where the matrix is expressed in terms of \(t\), using the \(P\) matrix as coefficients.

When multiplying the \(C\) and \(P\) matrices, we can just multiply each element in the \(P\) matrix by their corresponding column in the \(C\) matrix. For example. The \(P_0\), which is the first element in the \(P\) matrix, is multiplied by each element in the first column. You repeat this for each element and row in the \(P\) and \(C\) matrices respectively. The outcome of our operation is:

\(\begin{bmatrix} 1*(P_0) & 4*(P_1) & 1*(P_2) & 0*(P_3) \\ -3*(P_0) & 0*(P_1) & 3*(P_2) & 0*(P_3) \\ 3*(P_0) & -6*(P_1) & 3*(P_2) & 0*(P_3) \\ -1*(P_0) & 3*(P_1) & -3*(P_2) & 1*(P_3) \\ \end{bmatrix}\)

Finally, each element in the \(T\) matrix is multiplied by the the rows of the \(C\) matrix, instead of the columns. This is because \(T\) is defined as a \(1\)x\(4\) matrix, so the elements are multiplied by the rows instead of columns, as opposed to the \(P\) matrix wich was \(4\)x\(1\).

\(\begin{bmatrix} (1)*1*(P_0) & (1)*4*(P_1) & (1)*1*(P_2) & (1)*0*(P_3) \\ (t)*-3*(P_0) & (t)*0*(P_1) & (t*3)*P_2 & (t)*0*(P_3) \\ (t^2)*3*(P_0) & (t^2)*-6*(P_1) & (t^2)*3*(P_2) & (t)^2*0*(P_3) \\ (t^3)*-1*(P_0) & (t^3)*3*(P_1) & (t^3)*-3*(P_2) & (t)^3*1*(P_3) \\ \end{bmatrix}\)

When multiplying matrices,the inside values of the resulting matrix are added together. Let’s also multiply each row with our coefficient. The resulting equation looks like this:

\(f(t)=\)

\(\tfrac{1}{6}(P_0 + 4P_1 + P_2)\) \(+\)

\(\tfrac{1}{6}t(-3P_0 + 3P_2)\) \(+\)

\(\tfrac{1}{6}t^2(3P_0 - 6P_1 + 3P_2 )\) \(+\)

\(\tfrac{1}{6}t^3(-P_0 + 3P_1 + -3P_2 + P_3)\)

Because BSplines take the entire position of the control points and not just x, we can conclude that BSplines are 2D. However, you do not need to assign t values for the spline. This happens automatically.

Ghost points

Ghost points are the final piece of the BSpline puzzle, enabling the interpolation of end points on a spline, something which wouldn’t have ever been possible otherwise
This is done by reflection of both the second control point and the second to last control point around their respective endpoints.
Say we have 2 points: One at \((x:0,y:0)\) which is the endpoint and one at \((x:4,y:4)\) which is our second control point
By utilizing the aforementioned process, we can calculate the ghost point to be at \((x:-4,y:-4)\)
By repeating this process for both endpoints and plugging it into our matrix form, we have the ability to control where the curve starts and ends with the ghost points doing all the heavy lifting
The formula for this can be expressed as \(2P_0 - P_1\), or if you’re writing it as a coordinate, \((x: 2x_0 -x_1,y:2y_0 - y_1)\) where the numbers with subscripts of \(0\) are the real endpoints and the numbers with subscripts of \(1\) are the second/second to last endpoints
As a result, we can easily construct straight lines with BSplines while eliminating the need to mirror each control point manually!
If you plug in 2 points into the ghost point formula, with the first point being the second to last point and the second being the second point, the ghost point formula can successfully generate 2 extra points, which is the minimum required for a BSpline.
If you create a BSpline that uses 2 specified points, and their ghost points, the resultant BSpline will always be a perfect straight line.