Cardinal Splines (Interpolation, part IV)

In the last installment of this series, we left off Hermite splines asking how we should choose the derivatives at end points so that patches line up nicely, in a visually (or any other context-specific criterion) pleasing way.

Cardinal splines solve part of this problem quite elegantly. I say part of the problem because they address only the problem of the first derivative, ensuring that the curve resulting from neighboring patches are $C^0$ -continuous, that is, the patches line up at the same point, and are $C^1$ -continuous, that is, the first derivatives line up as well. We can imagine splines what are (up to) $C^k$ -continuous, that is, patches lining up, and up to the $k$ -th derivatives lining up as well.

So, cardinal splines just worry about the first derivative. Recall the Hermite spline equation system:

$\left[\begin{array}{cccc}x_{i}^3 & x_{i}^2 & x_{i} & 1\\x_{i+1}^3 & x_{i+1}^2 & x_{i+1} & 1\\3x_{i}^2 & 2x_{i} & 1 & 0\\3x_{i+1}^2 & 2x_{i+1} & 1 & 0\end{array}\right]\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{c} y_{i}\\ y_{i+1}\\ y_{i}^\prime\\ y_{i+1}^\prime\end{array}\right]$

where $y_{i}^\prime$ and $y_{i+1}^\prime$ are the wanted derivatives at $y_i$ and $y_{i+1}$ , respectively. Cardinal splines will set

$y_i^\prime=\frac{1}{2}(1-t)(y_{i+1}-y_{i-1})$

$y_{i+1}^\prime=\frac{1}{2}(1-t)(y_{i+2}-y_{i})$

where the term $\frac{1}{2}(1-t)$ will be denoted as $\beta_t$ from now on (because it is cumbersome to write). We will explain how we get these equations, and come back to $\beta_t$ in a short while.

Again, for the sake of simplicity, we assume that the $\{x_i\}_{i=1}^n$ are spaced by 1 exactly (so that we have $x_i=0$ , say, and $x_{i-1}=-1$ , $x_{i+1}=1$ , etc., allowing us to ignore scale-related renormalizations). Let us have a look around $x_i$ . The $y$ variation between $x_{i-1}$ and $x_i$ is $y_i-y_{i-1}$ . Between $x_i$ and $x_{i+1}$ , it is $y_{i+1}-y_i$ . If we combine the two to have some kind of average (using $\beta_t$ ) around $x_i$ , we get the following equation around $x_i$ :

$y_i^\prime=\beta_t\left((y_i-y_{i-1})+(y_{i+1}-y_i) \right)$ ,

$=\beta_t\left( y_i-y_{i-1}+y_{i+1}-y_i \right)$ ,

we rearrange:

$=\beta_t\left( y_i-y_i+y_{i+1}-y_{i-1}\right)$ .

We simplify:

$=\beta_t\left(y_{i+1}-y_{i-1}\right)$ ,

which is the first of the above equations. We get the second one exactly in the same way. We rewrite the Hermite system as:

$\left[\begin{array}{cccc}x_{i}^3 & x_{i}^2 & x_{i} & 1\\ x_{i+1}^3 & x_{i+1}^2 & x_{i+1} & 1\\ 3x_{i}^2 & 2x_{i} & 1 & 0\\ 3x_{i+1}^2 & 2x_{i+1} & 1 & 0 \end{array}\right]\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{c} y_{i}\\ y_{i+1}\\ \beta_t(y_{i+1}-y_{i-1})\\ \beta_t(y_{i+2}-y_i)\end{array}\right]$

And we solve as if a Hermite system to get $\left[~a~b~c~d~\right]$ .

*
* *

The $\beta_t$ term, controlled by a parameter $t$ , the “tension”, controls how the derivatives at the end points are boosted or suppressed. Setting $t=0$ yields splines where $\beta_0=\frac{1}{2}$ and they are then called Catmull Rom splines (and please notice that in the linked page, the order is inverse of what we used so far: they use $\left[~1~u~u^2~u^3~\right]$ rather than $\left[~u^3~u^2~u~1~\right]$ , leading to seemingly reversed equations relative to what I presented so far). The reader may explore the effects of $t$ , but personally I find that $t=0$ is conceptually the simpler, and values quite different from zero are hard to interpret geometrically.

*
* *

The right-hand side containing terms in $\beta_t\left(y_j-y_k\right)$ may seem “non-canonical” to some, but we can move this computation into the matrix $M^{-1}$ (that, until now, has been the same as with Hermite splines).

First we have to find that

$\left[\begin{array}{cccc}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ -\beta_t & 0 & \beta_t & 0\\ 0 & -\beta_t & 0 & \beta_t\\ \end{array}\right]\left[\begin{array}{c} y_{i-1}\\ y_i\\ y_{i+1}\\ y_{i+2}\end{array}\right]=\left[\begin{array}{c} y_{i}\\ y_{i+1}\\ \beta_t(y_{i+1}-y_{i-1})\\ \beta_t(y_{i+2}-y_i)\end{array}\right]$

We can re-write the Hermite system using the above “input transformation” matrix:

$\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{cccc}0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 0\\ 3 & 2 & 1 & 0\end{array}\right]^{-1}\left[\begin{array}{cccc}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ -\beta_t & 0 & \beta_t & 0\\ 0 & -\beta_t & 0 & \beta_t\\ \end{array}\right]\left[\begin{array}{c} y_{i-1}\\ y_i\\ y_{i+1}\\ y_{i+2}\end{array}\right]$

combining $M^-1$ and the input transform matrix, say $P$ :

$\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=M^{-1}P \left[\begin{array}{c} y_{i-1}\\ y_i\\ y_{i+1}\\ y_{i+2}\end{array}\right]$

We expand:

$\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{cccc}2 & -2 & 1 & 1\\-3 & 3 & -2 & -1\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\end{array}\right]\left[\begin{array}{cccc}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ -\beta_t & 0 & \beta_t & 0\\ 0 & -\beta_t & 0 & \beta_t\\ \end{array}\right]\left[\begin{array}{c} y_{i-1}\\ y_i\\ y_{i+1}\\ y_{i+2}\end{array}\right]$

and combine:

$\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{cccc}-\beta_t & 2-\beta_t & \beta_t-2 & \beta_t\\ 2\beta_t & \beta_t-3 & 3-\beta_t & -\beta_t\\-\beta_t & 0 & \beta_t & 0\\ 0 & 1 & 0 & 0\end{array}\right]\left[\begin{array}{c} y_{i-1}\\ y_i\\ y_{i+1}\\ y_{i+2}\end{array}\right]$

Which yields the desired solution.

*
* *

So, what does it look like, when we actually finally compute the spline?

Let us take 4 “random points”: $\{(-1,1), (0,-\frac{1}{2}), (1,1), (2,-2)\}$ . Using the last solution above, we find that $\left[~a~b~c~d~\right]=\left[~-\frac{15}{4}~\frac{21}{4}~0~-\frac{1}{2}~\right]$ .

Consider:

The points are shown in black; as is the spline. The derivatives are shown using arrows, one in purple (averaging the red and the blue vectors), and one in cyan (averaging the blue and the green vectors). We see that both ends of the spline line up with the arrows (which is expected) and that the spline varies rather smoothly between its two extremes.

*
* *

The cardinal spline (with $t=0$ therefore $\beta_t=\beta_0=\frac{1}{2}$ ) seems to be doing well, but it is not $C^2$ (or more) continuous. How can we add more constraints to the equation system to yield splines with a higher continuity?

To be continued…

This entry was posted on Tuesday, June 26th, 2012 at 10:24 am and is filed under algorithms, Mathematics, programming. 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.

4 Responses to Cardinal Splines (Interpolation, part IV)

Hermite Splines (Interpolation, part III) « Harder, Better, Faster, Stronger says:

June 26, 2012 at 10:25 am

[...] Cardinal Splines (Interpolation, part IV) [...]

Reply
Fast Interpolation (Interpolation, part V) « Harder, Better, Faster, Stronger says:

July 3, 2012 at 9:29 am

[...] the last four installments of this series, we have seen linear interpolation, cubic interpolation, Hermite splines, and lastly [...]

Reply
silver account says:

July 7, 2012 at 7:09 am

The curve is named after Edwin Catmull and Raphael Rom . In computer graphics , Catmull–Rom splines are frequently used to get smooth interpolated motion between key frames . For example, most camera path animations generated from discrete key-frames are handled using Catmull–Rom splines. They are popular mainly for being relatively easy to compute, guaranteeing that each key frame position will be hit exactly, and also guaranteeing that the tangents of the generated curve are continuous over multiple segments.

Reply
gold price says:

July 18, 2012 at 4:13 am

There are two kinds of spline function: interpolating splines and smoothing splines. For most surface design work, smoothing splines are used.

Reply

Harder, Better, Faster, Stronger