The interpolation between a set of points is a common task in computer graphics.
The ▷Darc Library for example uses interpolation to compute smooth camera trajectories.
One very elegant way to do this are B-Splines.
The following section offers a short mathematical introduction and some code snippets to get started.
Without going into too much details let's agree on the following definitions.
Every B-Spline \(c(t)\) requires an \(m\)-sized knot vector:
\begin{align}
[t_0 \leq ... \leq t_{m-1}]
\end{align}
However the B-Spline is only defined on a shorter subset of this \(m\)-sized vector. That subset contains the 'internal knots'. For a B-Spline with degree \(n\) and \(p\) control points they are:
\begin{align}
[t_n \leq ... \leq t_p]
\end{align}
This equals the B-Spline domain which means \(t\) must lie within the interval spanned by \(t_n\) and \(t_p\), otherwise the function is undefined.
The relation between the number of knots \(m\), control points \(p\) and the degree \(n\) is:
\begin{align}
p + n + 1 = m
\end{align}
Usually \(c(t)\) is a smooth function if set up properly. However sometimes it is desired to have sharp corners. This can be implemented by assigning identical values to adjacent knots. Each duplicated knot reduces the smoothness \(C^k\) by one. That means if \(n\) adjacent knots share the same value \(x\), the spline gets a corner at \(t_x\). Duplicating the first and last \(n+1\) knots will cause endpoint interpolation. Note that the first and last knot are mathematically irrelevant as far as the B-Spline domain is concerned. However most implementations need those extra knots to evaluate base function values easier without any case differentiation. For the B-Spline domain this is equivalent to duplicating \(n\) knots on the shortened vector:
\begin{align}
[t_1 \leq ... \leq t_{m-2}]
\end{align}
Consequently \(t_0\) and \(t_{m-1}\) remain available both in the theoretical definition and in the actual implementation.
To evaluate your B-Spline function \(c(t)\) at \(t\) you need to multiply each control point with a base function \(b_{i,n}\) and sum it all up. In particular the evaluation looks like this:
\begin{align}
c(t) = \sum_{n=0}^{p-1} p_i \cdot b_{i,n}(t)
\end{align}
As you can see in the applet each interval (within the internal knots) is spanned by \(n\) base functions. Thus you can accelerate the above equation by selecting the contributing base functions in a pre-processing step.
The base functions are defined recursively as follows:
\begin{align}
b_{i,n}(t) = \frac{t-t_i}{t_{i+n}-t_i}b_{i,n-1}(t) + \frac{t_{i+n+1}-t}{t_{i+n+1}-t_{i+1}}b_{i+1,n-1}(t)
\end{align}
\begin{align}
b_{i,0}(t)=\begin{cases} 1 & t\in[t_i, t_{i+1}]\\ 0 & else \\ \end{cases}
\end{align}
When \(n\) reaches zero you simply return whether the value \(t\) lies within the interval spanned by the base function at \(i\).
Here \(n\) is the initial degree of \(c(t)\). You might want to take a look at the applet to get a better understanding.
This interactive Java applet demonstrates non-uniform B-Splines of arbitrary degree.
The corresponding knot vector is generated automatically. You can also download this applet as a ▷jar file for your machine. The file can be executed as a standard Java application and doesn't need to be started from a browser.
You can also download this applet as a ▷jar file for your machine. The file can be executed as a standard Java application and doesn't need to be started from a browser.
