Cardinal Splines Part 2

Continuing from part 1 of this series, consider a knot sequence, P0, P1, P2, … Pn-1 . The Cardinal spline fits a sequence of cubic polynomials to these knots, the first of which is between P0 and P1.  The second polynomial curve is between P1 and P2, and so forth.  Hermite interpolation is used to compute the polynomial coefficients, so start- and end-tangents are required at each knot.

Cardinal splines specify the tangents at interior points based on the vector from previous point to subsequent point. Each tangent is parallel to this vector and some multiple of its length. For example, the tangent direction at point P1 is parallel to the vector P2 – P0, or we could simply write something like T1 = s(P2 – P0) where s is a real number.

An astute reader immediately notices that this is very similar to the approach taken with the Catmull-Rom spline. As it happens, the C-R spline is a special case of the cardinal spline with a fixed multiplier value. It would be helpful to review this TechNote [PDF] on Catmull-Rom splines.  The complete derivation of the Cardinal spline basis matrix is provided in the pages leading up to equation 5b.

The Cardinal spline provides an extra control parameter in terms of s.  Adjusting this parameter controls the degree to which the spline follows the tangent vector leading into and exiting from the join point.

One item not discussed in detail in the C-R TechNote is that that of locality in terms of knot movement.  In some splines, changing the location of a knot has a ‘ripple’ effect through the entire spline.  With Cardinal splines, individual cubic polynomials are constructed with overlapping sets of four knots.  The sets are

[P0, P1, P2, P3]
[P1, P2, P3, P4]
[P2, P3, P4, P5]
.
.
[Pn-4, Pn-3, Pn-2, Pn-1]

Denoting an arbitrary set by

[Pa, Pb, Pc, Pd]

Hermite interpolation is applied to points Pb and Pc with start tangent s(Pc – Pa) and s(Pd – Pb).

So, each knot participates in at most four spline segments. This tends to localize the effect of moving any single knot. Hermite interpolation is very efficient, so there is no system of equations to be solved to compute polynomial coefficients. A price is paid, however, for this convenience and this is loss of second-derivative continuity. A Cardinal spline is at best C-1 continuous.

The next part of this series looks at the s parameter in more detail. While it is tempting to think of it directly as a tension parameter, it is related to tension.  It will be shown that the Catmull-Rom spline is a zero-tension or ‘neutral’ Cardinal spline.  We will also discuss tangent directions at the initial and terminal knot as these are clearly arbitrary in the above analysis.

Cardinal Splines Part 1

When anyone hears the term ‘cardinal spline’ for the first time, the most common question is why the name ‘cardinal?’  Yes, that was my first question way back in the day 🙂  As it happens, there is a subtle relation between the spline and the cardinal series [1].  I’ll leave it to interested readers to pursue the history and mathematics of the series as an aside.

I believe it was Schoenberg who said that the cardinal spline bridges the gap between linear splines and the cardinal series [2].  Again, I’ll leave the details to those who want to either read Schoenberg’s book or pursue the matter to whatever degree it is documented online.  In this series, we will be interested in how to construct cardinal splines and get them into Degrafa.

First, let’s back up and look at cubic Hermite interpolation.  Quadratic Hermite interpolation was discussed in the Quadratic Hermite Curve series (see the Degrafa page for links to the entire series).  This case involved interpolating two points with a quadratic polynomial.  The three degrees of freedom were resolved by forcing the curve to interpolate the two points and assigning a start tangent.  This selection inferred an end tangent as shown below.

Start and End Tangents for a polynomial curve
Start and End Tangents for a polynomial curve

Instead of selecting the start tangent, T0 and forcing the end tangent, T1, what if we allowed both tangents to be variable?  This introduces an extra degree of freedom, allowing a cubic curve to be constructed.  The cubic curve has more flexibility, but requires both T0 and T1 to be initially specified.

The natural question is why not develop a cubic Hermite spline?  We could, although it requires two initial parameter selections.  Most designers prefer to have a single element of control or have everything automatically done for them.  An alternative approach is to examine specialized cases of Hermite interpolation where the tangents are automatically chosen.

In part 2, we will look at one such specification and how this method produces a computationally efficient interpolant with an adjustable tension parameter for shape control.

References:

[1]  Higgins, J.R., “Five Short Stories About the Cardianal Series”, Bulletin of the American Mathematical Society, Vol. 12, No. 1, 1985.

[2] Schoenberg, I.J., “Cardinal Spline Interpolation”, The Mathematics Research Center, Univ. of Wisconsin-Madison, Regional Conference Series in Applied Mathematics, Capital City Press, 1993.

Algebrator Special Offer

SoftMath, the makers of Algebrator have put together a limited offer for readers of this blog.  I’ve mentioned Algebrator in the past.  It is a tool that is suitable for students, teachers and anyone using algebra in their profession.  I even experimented with their function graphing capability recently to help validate my AS3 freeform function grapher.

The offer is available here.

Degrafa Quadratic Hermite Spline

The quadratic Hermite spline is now available in the Origin branch.  It works pretty much like any of the other splines with the exception of the method to manually assign the start tangent.  The default is automatic selection of start tangent, which uses the reflection discussed in this post.  A screenshot is provided below.

Automatic Selection of Start Tangent
Automatic Selection of Start Tangent

The blue curve results from plotting the low-level utility upon which the Degrafa spline is based.  It is plotted old-school, point-to-point with manual start tangent.  The red curve is the Degrafa spline fitting the same set of points in MXML with automatic selection of start tangent, and approximated by quadratic Beziers in the Degrafa command stack.

The relevant MXML is

<?xml version="1.0" encoding="utf-8"?>
 <mx:Application xmlns:mx="http://www.adobe.com/2006/mxml"
 xmlns:paint="com.degrafa.paint.*"
 xmlns:splines="com.degrafa.geometry.splines.*"
 layout="absolute"
 width="600" height="500" >

 <mx:Canvas id="quadSpline" />
 <paint:SolidStroke id="redstroke" weight="2" color="#FF0000"/>
 <splines:QuadraticHermiteSpline id="hermiteSpline" graphicsTarget="{[quadSpline]}"
 stroke="{redstroke}" knots="90,250 250,230 330,320 410,250" />

The next screenshot shows what happens if the start tangent is arbitrarily set to the point (100,100).

Assigning 100,100 as the start tangent
Assigning 100,100 as the start tangent

The only change to the MXML is the line

<splines:QuadraticHermiteSpline id=”hermiteSpline” graphicsTarget=”{[quadSpline]}” stroke=”{redstroke}” knots=”90,250 250,230 330,320 410,250″ startTangent=”100,100″ />

A very wide variety of interesting curves can be created by changing knot coordinates and the start tangent point.  Update your SVN and enjoy 🙂

Babolat Revenge Review Part 2

Continuing from part 1, I hit with Revenge as a fullbed for a little over eight hours under a variety of conditions.  Tension loss was less than a pound.  The string grew on me, but I was still anxious to test it in a hybrid.  Fortunately, the gut on my regular hybrid became mushy and it was time to restring.  So, I had both racquets restrung with VS Team 17 on the crosses.  One was strung with Revenge 17 on the mains at 51 lb and the other with the usual Pro Hurricane Tour 17 at 53.  My racquet is a Prince Speedport Black.

I was pleased with the control provided by Revenge as a fullbed at lower tension, so I wanted to experiment at the low end of my normal range.  If I strung a hybrid with say xCel Power on the mains at 51, I would be guranteed to spray balls into the fence from the first shot 🙂  The hybrid Revenge configuration performed pretty much  the same as the fullbed.  Solid control even at lower tension and this from a so-called ‘power’ string.

There was increased feel from groundstrokes by crossing with the gut, which helped alleviate my concerns from the first part of the review.  Next, I wanted to see how the configuration volleyed.  At 51lb, I expected a slight mushy feel from volleys.  The opposite was true.  Response was crisp from the very first volley.   With the VS Team/Pro Hurricane Tour hybrid, I get a serious feel of the ball being pocketed and ‘launched’ from stringbed.  This affects volleying to some extent based on the pace of the ball coming towards  you.  With VS Team/Revenge, response is consistent whether it is a light touch volley or responding to a very hard passing shot.

You will pick up a bit more feel and spin from the hybrid configuration on serve, but overall response is quite muted compared to Pro Hurricane Tour on the mains. Again, the expectation for Revenge is to provide  reasonable power while maintaining control.  With a power configuration, it’s up to you to provide the control.

My first conclusion is that Revenge is better suited for a hybrid configuration if you already play a hybrid (especially a gut/poly hybrid).   Control is quite good even at lower tension.  Given the combination of control and response on volleys, I’m probably going to keep the VS Team/Revenge hybrid as a doubles racquet.  It is not as powerful or responsive as the VS Team/Pro Hurricane Tour combination, leading me to believe that Babolat should be advertising this as more of a control string as opposed to a power string.

You can get plenty of power from Revenge by stringing at lower tension and just hitting out on the ball.   The response is adequate and the control ensures that if you miss, it’s all on you.   Spin is average; about what I would expect from any 17 -gauge hybrid configuration.  As might be expected, it is noticeably less than I achieve with the VS Team/Pro Hurricane Tour configuration.  However, given Revenge’s reputation for tension maintenance, you can hold that power/control level for longer periods of time than other configurations.  I expect more frequent restringing with VS Team/Pro Hurricane Tour.

Given the pace I experience from 4.5/5.0 players, my general conclusion is to stick with the VS Team/Pro Hurricane Tour hybrid for singles play.  I’m viewing VS Team/Revenge as more of a specialty configuration, for use in windy conditions when control is at a premium or doubles play.

Reflecting a Point About a Line

This is a pretty elementary operation in analytic geometry, but it’s come up in a few emails.  Although the solution is available online, programmers often have problems with equations expressed in vector notation.  That seems to be the common thread in the emails. I don’t have time for a comprehensive demo, so here is a quick Actionscript code snippet.

The problem at hand is how to reflect the point P2 about the line segment through points P0 and P1.  Let R be the reflection of P2 about the line segment.  I suspect the issue some people have problems with is the requirement to normalize the vector from P0 to P1.

If rx and ry are the x- and y-components of R, then

  var nx:Number = p1.x - p0.x;
  var ny:Number = p1.y - p0.y;
  var d:Number  = Math.sqrt(nx*nx + ny*ny);
  nx /= d;
  ny /= d;

  var px:Number = p2.x - p0.x;
  var py:Number = p2.y - p0.y;
  var w:Number  = nx*px + ny*py;
  var rx:Number = 2*p0.x - p2.x + 2*w*nx;
  var ry:Number = 2*p0.y - p2.y + 2*w*ny;

I’ll be using this method in an upcoming development, so we will have a chance to see it in action. In the mean time, I hope this helps the people who have been asking.

Quadratic Hermite Curves Part 6

Part 5 of this series introduced the mathematical foundation for a quadratic Hermite spline with segments comprised of individual quadratic Hermite curves (C-1 continuity at the joins). Since the system of equations for the start tangent of each curve is underdetermined, a start tangent for the first curve is required.

Selection of an initial tangent is entirely arbitrary.  For the Degrafa spline, I intend to have a method that provides an automatic selection.  This allows the spline to fit a set of knots without any further user interaction.  It is important to understand that no matter what algorithm is chosen, there is no theory that makes any one method ‘better’ than any other.  It’s entirely a method of designer preference.

This is a feature that I really like about this type of spline.  Because of the ‘coupling’ in the upper bi-diagonal system shown in part 5, the selection of a start tangent for the first segment ‘ripples’ through the entire curve.  This allows a wide variety of interesting curves to be created under the control of a single parameter.

To see what I mean, two screenshots are provided from the program I’m using to test the base utility on top of which the Degrafa spline will be created.

hermitespline1

hermite2

Two dramatically different curves are obtained  from the same set of knots by adjusting one parameter; the start tangent of the first quad. Hermite segment.

Quadratic Hermite Curves Part 5

Part four of this series illustrated how to join two quadratic Hermite curves with C-1 continuity at the join.  This part examines the mathematical foundation of creating a spline that interpolates an arbitrary number of knots using quadratic Hermite segments.

To begin, review the two-segment case that interpolates three points, P0, P1, and P2.   The start tangent vector for the first segment is T0 and the start tangent for the second segment is T1.  Both tangents are functions of t.  T0 is shorthand notation for the tangent at t=0 for the first segment. T1 refers to the tangent at t=0 for the second segment.  T0(1) refers to the end tangent of the first Hermite segment.  T1(1) refers to the end tangent for the second segment.  It is necessary to introduce superscripts and subscripts into the notation at this time.

The boundary condition at the join (P1) is that T0(1) = T1.  Recall from part 2 of this series that T0(1) = 2(P1 – P0) – T0, so T1 = 2(P1 – P0) – T0 or T0 + T1 = 2(P1 – P0).   Note that T1 can not be computed until T0 is fixed.   If another segment is added, there is a similar boundary condition for T2 in terms of T1(1).  You can show that that the vector of tangents is represented by the equation AT = b, where

A = | 1 1 0 0 0 ... 0 |
    | 0 1 1 0 0 ... 0 |
    |       . . .     |
    | 0 0 0 0 ... 1 1 |

T = [ T0 T1 ... Tn-1 ]t
b = 2[P1-P0 P2-P1 ... Pn-1-Pn-2]t

For n data points, A is n-1 x n.   The system of equations is underdetermined as expected since the choice of initial start tangent is arbitrary.  Once this value is fixed, the system of equations can be easily solved.  With T0 fixed, there are n-1 tangents to be computed.  The first row of A yields one equation in one unknown, T1.  Once T1 is computed, the second row yields an equation for T2 in terms of T1.  Solving the complete system is a generalization of the approach in part four of this series.

To draw the spline it is not strictly necessary to compute the last tangent, although it is handy to have in the case that new knots are added onto the spline.

Notice that the polynomial coefficients are not directly part of the solution.  They follow once the start tangents are set for each segment.  It is possible to create a matrix equation for the coefficients, but that requires more effort and we already have software that automatically computes the coefficients once the start tangents are provided.

Although it’s nice to see how the theory all ‘fits together,’ I know you want to see some code, so the final part of this series will introduce a quadratic (interpolative) spline in Degrafa 🙂

Quadratic Hermite Curves Part 4

Part 3 of this series introduced a method to draw the tangent segment to the quadratic Hermite curve at a fixed length at any parameter value.  This was contrasted to the geometric interpretation of the end  tangent to the first segment.

By directly computing the end tangent using the methodology in part 2, we have a vector that can be used as an initial tangent for a second Hermite curve with a common join point at P1.  What is the maximum continuity that could be achieved at the join?  The derivative of a quadratic curve is linear in t (first-degree polynomial) so the second derivative is a constant, namely 2c in terms of the polynomial coefficients.

Recall from part 1 that c = P1 – P0 – T1 for the first curve (where T1 is the start tangent for the first segment).  If the join point is P1 and the second curve interpolates some point P2, then its corresponding coefficient is P2 – P1 – T2.  The second derivatives can only be equal if P1 – P0 – T1 = P2 – P1 – T2 or 2P1 = P0 + P2 + (T1-T2).

In general, only C-1 continuity can be achieved.

This continuity is easy to achieve based on the simplicity of the curve construction.   The end tangent for the first curve is used to set the start tangent for the second curve.  This is illustrated in following screenshot.

Joining two quadratic Hermite curves with C-1 continuity
Joining two quadratic Hermite curves with C-1 continuity

To experiment with the demo, the first Hermite curve is drawn as in prior demos.  A crosshair appears in the drawing area.  Click to define the P2 point and the second segment is drawn.  You may study the code to see the algorithm in action.

In the next part of this series, we will look at extending this method to an aribtrary number of interpolation points.

View demo.

View source.