Archive

Posts Tagged ‘Splines’

FDL Cubic Bezier Spline

April 30, 2012 1 comment

The cubic bezier spline drawing engine in the Freehand Drawing Library is now complete.  As I mentioned in the prior post, the drawing engine fits into the FDL architecture and allows a spline to be treated as a stroke.  The CubicBezierSpline drawing engine contains a reference to a FDLCubicBezierSpline, which handles all the spline computations except for tangents.  Tangents are implemented via a Command pattern (with the spline as the receiver of the Command).  Three tangent commands are now available for cubic splines.  The NormalBisector Command uses the same algorithm as described in this TechNote.  The CatmullRom Command uses an algorithm similar to that in Catmull-Rom splines.  The Corner Command can be applied on a per-vertex basis and constructs splines with hard ‘corners’ or only G-0 continuity at a join point.

While the CubicBezierSpline engine manages the internal spline and tangent commands, the spline and tangent computations can be easily used outside the FDL in a purely computational context.

Every FDL spline is arc-length parameterized by default, using a fast algorithm for on-the-fly parameterization.  So, every coordinate request, i.e. getX(t) and getY(t) is actually computed based on normalized arc length in [0,1].  So, getX(0.5) returns the x-coordinate at approximately half the length along the spline.

Splines are implemented as drawing engines for a PolyLine stroke.  As always, a drawing engine is injected into the stroke,

__data.drawingEngine = “net.algorithmist.freehand.engine.CubicBezierSpline”;

Arbitrary parameters (name-value pairs) may be assigned to any drawing engine.  All splines require a ‘tangentCommand’ parameter to inject the Command used for tangent computations.  The normal bisector algorithm is applied as follows.

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.NormalBisector”};

or, substitute the Catmull-Rom algorithm, if desired,

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.CatmullRom”};

then, assign the data provider to the stroke,

__stroke.data = __data;

The cubic bezier spline supports auto-closure with G-1 continuity across the full set of tangent commands since the closure algorithm is inside the Command itself. Here is a screenshot,

and here is a screenshot of an open spline using the Catmull-Rom algorithm for tangent computations,

The next step is editing the spline by adjusting knots and tangents.  I was originally skeptical how far the architecture could be pushed in terms of a ‘drawing’ that was not in line with a traditional stroke motion, i.e. press-move-release.  Editing the mathematical properties of something like a spline seemed out of the question at first thought.  So far, I’m glad the architecture is holding up without having to hack anything in.  I suppose a demo containing a spline editor will be the ultimate test 🙂

As an aside, spline editing facilities are not part of the library; they are provided as one of the many demos available to FDL users.

Cardinal Splines Part 4

October 6, 2009 6 comments

Continuing from part 3 of this series, a formal tension parameter, T = 1-2s, was introduced. All we noted about tension was that T=0 corresponds to s = 1/2. At s=1/2, the Cardinal spline takes on the form of the more familiar Catmull-Rom spline. The Catmull-Rom spline may, however, be derived independently from the notion of Cardinal splines as the blending of two parabolas [1]. The zero-tension Cardinal Spline happens to conforms to a well-known C-1 continuous spline.

What happens as the tension parameter is moved away from zero? Can it reasonably be both positive and negative? To better understand the effect of the tension parameter on the spline, the Cardinal-spline basis matrix is

[ -s  2-s  s-2   s ]
[ 2s  s-3  3-2s -s ]
[ -s   0    s    0 ]
[  0   1    0    0 ]

Given four arbitrary knots,

[P1, P2, P3, P4]

the following vector equation applies for an aribrary point P(t) on the curve from P2 to P3

P(t) = s(-t3 + 2t2 – t)P1 + s(-t3 + t2)P2 + (2t3 – 3t2 + 1)P2 + s(t3 – 2t2 + t)P3 + (-2t3 + 3t2)P3 + s(t3 – t2)P4

We have already looked at T = 0, so consider T = 1, corresponding to s = 0. The equation for P(t) reduces to

(2t3 – 3t2 + 1)P2 + (-2t3 + 3t2)P3, which can be simplified to

(3t2 – 2t3)(P3 – P2) + P2. If u = 3t2 – 2t3, then

P(t) = (1-u)P2 + uP3, which is the parametric equation of a line from P2 to P3.

While u does vary from 0 to 1, the primary curve parameter is t. At t varies from 0 to 1, u is approximately sigmoid but very close to linear throughout its range. So, we can say that as T approaches 1, the spline approaches a straight-line interpolation between knots.

The following screenshot shows a four-knot example with a black line connecting the knots and the spline drawn in blue with T=1. The Degrafa Catmull-Rom spline is drawn in red, which corresponds to the Cardinal spline with zero tension. This allows a comparison of the range of fits available in the tension range from zero to one.

Tension Ranges in a Cardinal Spline

Tension Ranges in a Cardinal Spline

The natural tension range is from zero to one. Values outside this range are possible, although rarely practical. These factors are discussed in the next section of this series.

References:

[1] Salomon, D. “Computer Graphics and Geometric Modeling”, Springer Verlag, NY, 1999.

Categories: Degrafa, Math Tags: , ,

Cardinal Splines Part 3

October 1, 2009 1 comment

Continuing from part 2 of this series, the tension in a Cardinal spline is controlled by the s-parameter. Given a four-tuple of control points or knots,

[Pa, Pb, Pc, Pd]

cubic Hermite interpolation is applied with start-tangent s(Pc – Pa) and end-tangent s(Pd – Pb) .

Theoretically, s could vary from zero to positive infinity. A very long tangent vector, indicated by a large s-value causes the curve to follow the tangent very closely in and out of the join point. A very small tangent vector, indicated by a small s-value, causes the curve to approach and leave the join point more like a straight line.

Intuitively, this is the opposite of how we expect tension to behave. Larger tension should ‘pull’ the curve closer to a straight-line interpolation of the knots, with exactly straight lines as a limiting case. This gives rise to the convention of a formal tension parameter, T, that is inversely related to s.

The typical convention is to define s = (1-T)/2 or T = 1 – 2s. Note that the zero-tension case corresponds to s = 1/2 or a relatively ‘loose’ movement into and out of each join. This special case corresponds to the Catmull-Rom spline. For this reason, the C-R spline is sometimes called the zero-tension or neutral Cardinal spline.

The tension parameter will be discussed in more detail in subsequent posts in this series. Tangent vectors are arbitrary at the initial and terminal knots, just as with the Catmull-Rom spline. Fortunately, there are several methods for automatically assigning these tangents. The C-R spline in Degrafa implements two methods; point duplication and point reflection.  Line segment reflection can be added as a third option. It is also possible to allow designers to set these tangents interactively.

Local control via knot placement, tension control, and adjustment of initial/terminal tangent vectors provides artists with a variety of methods to design specific curves using Cardinal splines.