Aidan Delaney’s weblog

The following may make more sense when the latex-mathjax plugin is enabled. You’ll see the equations then, not the LaTeX source.

I’ve got a set of $(x,y)$ points. What I want to do is draw a reasonably smooth curve through all of them, rather than a set of straight lines connecting them. To do so, I need some higher order function such as a cubic. In particular the cubic Bezier function is a well known graphics primitive. Therefore, given a set of points and the definition of a cubic Bezier, I need to calculate the control points for each curve.

A cubic Bezier function interpolates between $K_0$ and $K_1$ using control points $C_{0,1}$ and $C_{0,2}$ in the following manner
$$
B(t)=(1-t)^3K_0+3t(1-t)^2C_{0,1}+3t^2(1-t)C_{0,2}+t^3K_1.
$$
We may extend the idea to a spline. The knots of the spline are $\langle K_0, K_1,\ldots,K_n\rangle$. This leads to $n-1$ cubic functions $B_0, B_1, \ldots, B_{n-1}$. Where $B_i$ interpolates between $K_i$ and $K_{i+1}$ with control points $C_{i,1}$ and $C_{i,2}$.

We want $C^2$ continuity so that our curve is nice and smooth. Therefore, for each $i$ we require
\begin{eqnarray*}
B^\prime_i(1)&=&B^\prime_{i+1}(0)\textrm{ and}\\
B^{\prime\prime}_i(1)&=&B^{\prime\prime}_{i+1}(0).
\end{eqnarray*}
Furthermore,
$$
B_i^\prime(t)=3K_{i+1}t^2-3C_{i,2}t^2+6C_{i,2}\left(1-t\right)t-6C_{i,1}\left(1-t\right)t+3C_{i,1}\left(1-t\right)^2-3K_i\left(1-t\right)^2
$$
and
$$
B_i^{\prime\prime}(t)=6 K_i (1 – t) + 6 C_{i,1} t – 12 C_{i,1} (1 – t) – 12 C_{i,2} t + 6 C_{i,2} (1 – t) + 6 K_{i+1} t.
$$

Evaluating $B^\prime_i(1)$ gives
\begin{eqnarray*}
B_i^\prime(1)&=&3K_{i+1}1^2-3C_{i,2}1^2+6C_{i,2}\left(1-1\right)1-6C_{i,1}\left(1-1\right)1+3C_{i,1}\left(1-1\right)^2-3K_i\left(1-1\right)^2\\
&=&3K_{i+1}-3C_{i,2}+6C_{i,2}(0)1-6C_{i,1}(0)1+3C_{i,1}(0)^2-3K_i(0)^2\\
&=&3K_{i+1}-3C_{i,2}.
\end{eqnarray*}
and evaluating $B_{i+1}^\prime(0)$ gives
\begin{eqnarray*}
B_{i+1}^\prime(0)&=&3K_{i+2}0^2-3C_{i+1,2}0^2+6C_{i+1,2}\left(1-0\right)0\\
&=&-6C_{i+1,1}\left(1-0\right)0+3C_{i+1,1}\left(1-0\right)^2-3K_{i+1}\left(1-0\right)^2\\
&=&3C_{i+1,1}-3K_{i+1}
\end{eqnarray*}
Therefore, for each $i$
\begin{eqnarray*}
B_i^\prime(1)&=&B_{i+1}^\prime(0)\\
3K_{i+1}-3C_{i,2}&=&3C_{i+1,1}-3K_{i+1}\\
6K_{i+1}&=&3C_{i,2}+3C_{i+1,1}\\
K_{i+1}&=&0.5C_{i,2}+0.5C_{i+1,1}.
\end{eqnarray*}

Evaluating $B_i^{\prime\prime}(1)$ gives
\begin{eqnarray*}
B_i^{\prime\prime}(1)&=&6 K_i (1 – t) + 6 C_{i,1} t – 12 C_{i,1} (1 – t) – 12 C_{i,2} t + 6 C_{i,2} (1 – t) + 6 K_{i+1} t\\
&=&6K_i(0)+6C_{i,1}-12C_{i,1}(0)-12C_{i,2}+6C_{i,2}(0)+6K_{i+1}\\
&=&6C_{i,1}-12C_{i,2}+6K_{i+1}\\
\end{eqnarray*}
and evaluating $B_{i+1}^{\prime\prime}(0)$ gives
\begin{eqnarray*}
B_{i+1}^{\prime\prime}(1)&=&6 K_{i+1} (1 – t) + 6 C_{i+1,1} t – 12 C_{i+1,1} (1 – t) – 12 C_{i+1,2} t + 6 C_{i+1,2} (1 – t) + 6 K_{i+2} t\\
&=&6 K_{i+1} (1 – 0) + 6 C_{i+1,1} 0 – 12 C_{i+1,1} (1 – 0) – 12 C_{i+1,2} 0 + 6 C_{i+1,2} (1 – 0) + 6 K_{i+2} 0\\
&=&6 K_{i+1} – 12 C_{i+1,1} + 6 C_{i+1,2}.
\end{eqnarray*}
Therefore, for each $i$
\begin{eqnarray*}
B_i^{\prime\prime}(1)&=&B_{i+1}^{\prime\prime}(0)\\
6C_{i,1}-12C_{i,2}+6K_{i+1}&=&6 K_{i+1} – 12 C_{i+1,1} + 6 C_{i+1,2}\\
0&=&-6C_{i,1}+12C_{i,2}-12 C_{i+1,1} + 6 C_{i+1,2}\\
0&=&-C_{i,1}+2C_{i,2}-2 C_{i+1,1} + C_{i+1,2}\\
\end{eqnarray*}

We now have $(2\times n-1)-2$ equations and $(2\times n-1)$ unknown control points. We construct the linear system
$$
\left(
\begin{array}{ccccccc}
0&0.5&0.5&0&0&0&\ldots\\
-1&2&-2&1&0&0&\ldots\\
0&0&0&0.5&0.5&0&\ldots\\
0&0&-1&2&-2&1&\ldots\\
%0&0&0&0.5&0.5&0&\ldots\\
%0&0&1&-2&2&-1&\ldots\\
\vdots&&&&&&
\end{array}
\right)
\times
\left(
\begin{array}{c}
C_{0, 1}\\
C_{0, 2}\\
C_{1, 1}\\
C_{1, 2}\\
\ldots
\end{array}
\right)
=
\left(
\begin{array}{c}
K_1\\
0\\
K_2\\
0\\
\ldots
\end{array}
\right).
$$

We also have the natural boundary conditions that $B^{\prime\prime}_0(0)=0$ and $B_{n-1}^{\prime\prime}(1)=0$. The linear system then becomes
$$
\left(
\begin{array}{ccccccccc}
2&-1&0&0&0&0&\ldots&0&0\\
0&0.5&0.5&0&0&0&\ldots&0&0\\
-1&2&-2&1&0&0&\ldots&0&0\\
0&0&0&0.5&0.5&0&\ldots&0&0\\
0&0&-1&2&-2&1&\ldots&0&0\\
%0&0&0&0.5&0.5&0&\ldots&0&0\\
%0&0&1&-2&2&-1&\ldots&0&0\\
\vdots&&&&&&&&\\
0&0&0&0&0&0&\ldots&-1&2
\end{array}
\right)
\times
\left(
\begin{array}{c}
C_{0, 1}\\
C_{0, 2}\\
C_{1, 1}\\
C_{1, 2}\\
\ldots
\end{array}
\right)
=
\left(
\begin{array}{c}
0\\
K_1\\
0\\
K_2\\
0\\
\ldots\\
0
\end{array}
\right).
$$

This entry was posted on Sunday, January 30th, 2011 at 6:39 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.