Archive

Archive for September, 2009

Cardinal Splines Part 2

September 28, 2009 1 comment

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.

Advertisements
Categories: Degrafa, Math

Cardinal Splines Part 1

September 24, 2009 1 comment

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.

Categories: Math

Algebrator Special Offer

September 21, 2009 Comments off

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.

Categories: General, Math Tags: , ,

Degrafa Quadratic Hermite Spline

September 17, 2009 Comments off

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

September 16, 2009 Comments off

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

September 15, 2009 2 comments

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.

Categories: Flash, Math

Quadratic Hermite Curves Part 6

September 11, 2009 Comments off

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.