Israel Eisenberg Sep 2012

Splines to SVG


Given an ordered set of points, a spline will connect them with a smooth curve.

This article is a contribution to the effort to include splines in the SVG spec.

The idea was first introduced by [ Doug Schepers ] in his [ blog post ].
Resolutions have been made by the SVG WG to include spline functionality in SVG2 and the first spline to be adopted specified as the Catmull-Rom spline with global tension parameter.

The main goal of this article is to simplify the drawing of famous splines directly to an SVG page. "Directly" means avoiding their geometrical matrices by adapting each spline essence directly to an SVG Bezier curve.



Before traveling to other planets for splines, it might be a good idea to pay a visit to our own home spline. The SVG-Spline exists since the dawn of SVG, and the only reason I can think of why even folks familiar with SVG might not recognize it, is that the SVG spec never described it for what it is - a kosher spline.

The SVG-Spline has the same C1 continuity like the Catmull-Rom spline which in Bezier curves means first control point of one segment is a reflection of the last control point of the previous segment through their join point.

In one respect the SVG-Spline is superior to the Catmull-Rom spline:

Though the first line of this article can be considered as a decent description of spline functionality, it is not entirely true. Give a Catmull-Rom spline 2 points and it will just sit there doing nothing. It needs 2 more points and only then, out of the 4 input points, it will interpolate only the mid points.
As the number of points grows, the Catmull-Rom spline can use previous points for calculation, but it can *never* interpolate the first and last input points with a curve (we deal with that issue later).

The advantage of the SVG-Spline, other than it needs only 1 extra "guide" point instead of 2, which is natural because it is quadratic, is that every new point is interpolated, i.e. - the curve is smoothly connected to the last point.

The following demo considers the second point we create to be the control point of the quadratic Bezier between the 1st and 3rd points. Other than that, every new point will be (automatically) smoothly interpolated by the SVG-Spline.

To observe how the C1 continuity is preserved, show the control-vectors.
The SVG-Spline automatically equates the 2 adjacent control-vectors of every join.

The d attribute of the spline path is updated constantly on the screen.
Other than that, there is not a single calculation performed. All necessary calculations are done transparently by the SVG-Spline.

Common to all demos - mousedown anywhere to create new point which is immediately dragable if hilighted by a ring.
mouseover top-right region to reveal the undo button. It usually undo last point
but sometimes, when last point might be connected, the one-before-last.

Demo 1: The SVG-Spline [ Full page ]

The simple magic of the SVG-Spline is a single T command. Coupled with SVG path element convention of repeating last command, it turns a path into a spline.

The "@" glyph of "Times" use T 29 times.

We'll revisit the SVG-Spline, but with a slightly different way of construction, later in the article on our journey to create C2 continuos cubic spline.



Before we draw our guest of honor, we name some creatures for clear and concise descriptions:

Points to be interpolated will be referenced as members of a JavaScript array P.

- A junction is a point with a neighbor point on each side. On a closed spline all points are junctions but on an open spline, P[0] and P[last] are not junctions.
junction i is simply the junction P[i].
We sometimes refer to a junction as a knot.

- P[i] segment or simply segment i, is the spline segment from P[i] to P[i+1]

Loosely speaking, we consider "left" of P[i] as the P[i-1] segment area,
and "right" of P[i] as the P[i] segment area.

- Junction P[i] triangle:
Its left leg (P[i].leftLeg) is the vector from P[i-1] to P[i] i.e. - (P[i] - P[i-1])
Its right leg (P[i].rightLeg) is the vector from P[i] to P[i+1] i.e. - (P[i+1] - P[i])
Its base (P[i].triBase) is the vector from P[i-1] to P[i+1] i.e. - (P[i+1] - P[i-1])

All edges of P[i] triangle are vectors thus we can slice them and add/subtract
the slices (which are also vectors) to/from points to create new points.

We reference P[i] triangle edges through P[i], for example, from the most basic vector addition definition it follows that

       P[i].triBase = P[i].leftLeg + P[i].rightLeg

- P[i].L (Left) is the closest Bezier control point to the left of P[i].
For junction i and a cubic Bezier, it is the second control point of P[i-1] segment.
- P[i].R (Right) is the first (and closest) Bezier control point to the right of P[i].

To reference two control-points of P[i] segment in terms of only P[i] we define:
- P[i].RR is the second Bezier control point of P[i] segment.
It should be obvious for cubic Bezier segments that P[i-1].RR = P[i].L and
P[i].RR = P[i+1].L

- P[i].in is the control-vector from P[i].L to P[i] (P[i] - P[i].L).
- P[i].out is the control-vector from P[i] to P[i].R (P[i].R - P[i]).

When we talk about P[i] control-vectors we mean P[i].in and P[i].out.

Unless otherwise stated, all splines discussed have a minimum continuity of C1 which for Bezier curves means P[i].in = P[i].out and that P[i].L and P[i].R are each a reflection of the other with respect to P[i] and in particular colinear with P[i].

These definitions are more than enough for describing the drawing of all the article splines directly to an SVG path element. Time to draw:

The Catmull-Rom spline

The algorithm to interpolate an array of points P with Catmull-Rom spline as piecewise cubic Bezier segments (for simplicity we assume a closed spline so all points are junctions):

For each junction P[i] do:

1) slice 1/6 of P[i].triBase, call it v
2) subtract v from P[i] to form P[i].L
3) add v to P[i] to form P[i].R

Spline is ready:

Demo 2: Geometry of direct Catmull-Rom to Bezier [ Full page ]

Observe:
Moving a knot does not change its control-vectors, they keep the same magnitude and direction is always parallel to the knot triBase.

Moving a knot does change the control-vectors of both previous and next knots but only them. This feature is the good locality of the Catmull-Rom spline. Officially we say it has an L4 locality means moving a knot influences only 4 segments, 2 on each side of the moving knot.

Both control-vectors behaviors show particularly well on a 4 knots closed spline.
To observe the local behavior on a closed spline, you need at least 5 knots.



To explain the above algorithm, we examine Catmull-Rom spline a bit more closely.

The Catmull-Rom spline was designed with the cubic Hermite spline in mind.
So by examining the cubic Hermite, we could extract the essence of the Catmull-Rom algorithm and apply it directly to something more suitable for an SVG application namely, a Bezier curve.

A small confession: we could extract the essence of the Catmull-Rom without examining the cubic Hermite, but I thought it's a good opportunity to take a slightly better look at the granddaddy of so many modern curves/splines (though not the Bezier curve which grandma I consider to be [ Mary Everest Boole ]).

In the following section, the article I reference is [ this article ].

cubic Hermite vs cubic Bezier

First thing to notice is the different inputs.
Out of four inputs each expects, common to both are the end points of the curve. As we know, for the cubic Bezier the other two inputs are also points (control-points) but for the cubic Hermite, the other two inputs are tangents, which are vectors. This can be clearly seen from the general form of the cubic Hermite formula for a single interval ("Representations" in the article):

P(t) = h00(t)P[i] + h10(t)m[i] + h01(t)P[i+1] + h11(t)m[i+1]

Where the m's are the tangents at the corresponding input points and the indices adjusted from 0 to i and from 1 to i+1 so we can examine this particular segment as one of all P segments. The h's are the cubic Hermite basis-functions which in functionality are equivalent to the cubic Bezier basis-functions.

Second and most important to notice is the decomposition of the cubic Hermite basis-functions into Bernstein polynomials (right column of the gray table in the article) which we know are the basis-functions of the cubic Bezier.
What it means is that we can draw the exact same cubic Hermite curve as a cubic Bezier curve (this by the way is true not only for Hermite but for any cubic spline).

Few lines later we find how to derive the Bezier inputs from the Hermite inputs:

   segment i: P[i], P[i] + m[i]/3, P[i+1] - m[i+1]/3, P[i+1]

Applying it to the previous segment of our P spline we get:

   segment i-1: P[i-1], P[i-1] + m[i-1]/3, P[i] - m[i]/3, P[i]

Please note we can assume tangent m[i] of segment i is the same as tangent m[i] of segment i-1 only because we assume C1 continuity at junction P[i].

Building Bezier splines we are mainly interested in junctions and their nearest control-points i.e. - P[i].L, P[i], P[i].R which we can easily extract from the above two connected segments and get:

       junction i: P[i] - m[i]/3, P[i], P[i] + m[i]/3

Which already make us happy as it is obvious we need to calculate m[i] only once per junction and then just add it and subtract it to/from P[i].

Now is the time to visit the Catmull-Rom algorithm and learn how it calculates the tangent m[i]. We find it few lines later in the same article:

       m[i] = (P[i+1] - P[i-1]) / (t[i+1] - t[i-1])

(indices simply adjusted from the article k to our i).

Now for final cosmetics.
Our spline is uniform, means the parameter t goes in each segment from 0 to 1 which allows us to calculate the parametric interval described in the denominator as simple indices interval i.e:

       t[i+1] - t[i-1] = i+1 - (i-1) = 1-(-1) = 2

We also remember that

       P[i+1] - P[i-1] = P[i].triBase

Plug the two last expressions into m[i] we get:

       m[i] = P[i].triBase/2

(Note Catmull-Rom calculates tangent for a junction simply as half of its triBase).

Plugging m[i] into the cubic Bezier junction i, we finally get:

junction i : P[i] - (P[i].triBase/2)/3, P[i], P[i] + (P[i].triBase/2)/3

junction i : P[i] - P[i].triBase/6,   P[i],   P[i] + P[i].triBase/6

Which is precisely the math expression of the algorithm described above for drawing the Bezier form of the Catmull-Rom spline with P[i].triBase/6 being v.

Last look at the cubic Hermite, following demo shows the geometry of the different Hermite and Bezier inputs for the same Catmull-Rom spline:

Demo 3: Hermite and Bezier inputs for the Catmull-Rom spline. [ Full page ]

Before examining more splines, we should handle the case so far left aside for simplicity, of an open ends spline.

Given four points as input, the Catmull-Rom algorithm interpolates only the two junctions, which leaves us with two end segments without any control-points.

This issue is common to many splines (but not to the cubic Hermite spline),
so the following discussion is not limited to just the Catmull-Rom spline.

Shaping open end segments

Other than the unlikely option of drawing the end segments as straight lines, the simplest solution is... to not draw them at all. The end points are still there shaping the curve, but the end segments are not drawn.

What is more commonly done, is to shape end segments guided by two aspects:

First is to make the end segments blend nicely with the rest of the spline.
This is achieved most sensibly by simply mirroring the end junctions tangents
(which we already did, drawing the Bezier form of the Catmull-Rom spline).
This solution is actually self requested as it extends the C1 continuity to the entire spline, which definitely contribute to a more homogenous look of the spline.

First goal achieved, we now left with only one control point per end segment missing. Second goal is largely dictated by use cases.
We examine two main categories: independent and dependent.

Dependency here is mainly on other designs in the scene. We discuss only two solutions from each category (or this article will become a small book):

Independent means no scene constrains so we just want nice looking ends.
Since "nice" is not really a math term, to achieve nice looking or "fair" curve,
the best we can do is to use common-sense and experience.

First is the "natural" or "relaxed" ends. Largely speaking, they are imported from C2 continuous cubic curves (discussed later) where their influence propagates to the rest of the segments. In C1 curves, their influence is confined to the end segments which just look nicer than with other ending choices.
The name comes from real mechanical splines which ends are left without pegs to curve them, thus having a 0 curvature which, if translated to math terms, means second derivative at the end points is 0. Using Bezier math we can equate:

       P''[0] = 6(P[0] - 2P[0].R + P[0].RR) = 0

We need to find P[0].R (first P[0] control point) so we isolate and get:

       P[0].R = (P[0] + P[0].RR)/2

Which geometrically means that the first control point of P[0] is exactly half way between P[0] and the second control point (which is also P[1].L - thus calculated). Applying the same end type to the last segment, the last control point of the spline (P[last].L) is half way between P[last] and P[last-1].R

Second independent solution is a lot easier than the natural. We simply use the first and last calculated control-points i.e. - P[1].L and P[last-1].R as single control-points and draw the end segments as quadratic Bezier curves. With this solution, end segments are slightly closer (tighter) to the P polygon than the natural spline.


Dependent spline usually means we need to connect one or both ends of our spline to other designs/splines, thus depend on their end tangents.

First of the two solutions in this category is the "clamped" spline. The name comes like the natural, from the real life splines to describe a spline which two ends are forced by clamps to have a certain tangent. This enables us to smoothly connect our spline to another design. All we need is to match the end tangents of both and make sure their end points coincide. The rigid part is that we can connect the clamped spline smoothly only to designs whith same tangent direction for G1 continuity and also same magnitude for C1 continuity. The freedom is that all junctions can move freely without affecting the continuity at the ends joins.

Second in this category is the "colinear". We simply place P[0].R to be colinear with P[0] and P[1] at some part of the way between them, regardless of P[0].RR position. Symmetrically, P[last].L is placed part of the way from P[last] to P[last-1].
This "part" of the way is entirely up to us. In the following demo we use 1/3 for the "colinear" end type and Dog Schepers Catmull-Rom [ demo ] uses 1/6.

Summary of open spline end types:

1) Natural (relaxed).
2) Quadratic.
3) Clamped.
4) Colinear.
5) Don't draw.

For reasons of symmetry, we usually apply the same end type to both ends of a spline, but this is not a must, two end segments of the same spline can be shaped by two different end types.

The following demo is pretty busy trying to pack all open end types.
Spline between junctions (lime) is Catmull-Rom, and quadratic ends, being integral part of the spline (no extra control-points invented), are painted the same color.

As the demo loads, the dependent end type segments are C1 connected to the side designs. Moving the middle junction does not affect either end type continuity. Moving the end junctions along the shadowed line keeps the colinear ends (yellow) at least G1 continuous but moving them off-line lowers the continuity to C0.
Same time, the clamped spline (aqua) continuity at end joins is unaffected.
The clamped spline can also be smoothly connected to the middle design to form a nice heart shape (nice here is of course subjective).

Dashed-lines on designs are their control polygons, to help examine continuity conditions when end segments control-vectors are visible.

Hiding all end types means we don't want to draw the end segments, so if there are only 3 points, other than the points and the single junction control-vectors, there is actually nothing to draw.
Further more, the only reason the junction control-vectors can be drawn with only 3 points, is that the underline algorithm is our "Bezier form" and not the "official" Catmull-Rom which practically speaking, cannot operate on less than 4 points
(but can draw 3 points closed curve taking points modulus 3).

If at least 4 points are marked while all end types hidden, only the spline between junctions and internal control-vectors are drawn, though end points are still there, contributing their share of shaping the spline.

Undoing a point deletes the one-before-last point to keep connections intact.
With at least 5 points, adding a point is junction insertion done the same way.

Demo 4: Different shapes of open spline end segments. [ Full page ]

From here on, unless otherwise stated, all open splines will be natural.

We are now ready to meet the rest of the Catmull-Rom family:

Splines to SVG cont’d

Israel Eisenberg Sep 2012