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…

5 Responses to Cardinal Splines (Interpolation, part IV)

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

  2. silver account says:

    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.

  3. gold price says:

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

  4. rom says:

    There’s a mistake in your final 4×4 matrix. The element which currently has the value (3 – Bt) should actually be (3 – 2Bt).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 74 other followers

%d bloggers like this: