Israel Eisenberg Sep 2012

Splines to SVG

The idea was first introduced by [ Doug Schepers ] in his [ blog post ].
Relevant resolutions already made by the [ W3C SVG Working Group ]:

[ RESOLUTION ] (2011/10/28):
We will include smooth path between points functionality in SVG2.

Definition: Given ordered set of points, an interpolating-spline connects them in sequence with a smooth curve.

[ RESOLUTION ] same session, specific spline adopted:
We will have Catmull Rom Curves (with 0 tension) in SVG 2.

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

The main goal of this article is to simplify the drawing of famous splines directly to an SVG page. "Directly" means bypassing 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 really 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 above definition can be considered a decent description of an interpolating-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 "guide" 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 uses previous points for calculation, but it can *never* interpolate the first and last input points with its own algorithm (we deal with that issue later).

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

The following demo considers the 2nd point we create to be the control point of a quadratic Bezier between 1st and 3rd points. Other than this single guide, every new point is (automatically) smoothly interpolated by the SVG-Spline.

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

The updated d attribute of the spline path is without decimals for readability.
Note 2nd coordinates-pair is the only control-point, rest are points.

Common to all demos - mousedown to create new point which is dragable when 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 C1-smooth interpolating-spline.

Fonts use T intensively. The "@" glyph of "Times" uses 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 are referenced as members of JavaScript array P.

An open-spline interpolates all P-points but not P[last] to P[0]
A closed-spline (loop) interpolates all P-points including P[last] to P[0]
maintaining its smoothness at all points.
P-polygon is created by a closed linear-interpolation (straight-lines).

- 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.
junction i is simply the junction P[i].
We sometimes refer to a junction as a join or a knot.

- P[i] segment (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] - (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 (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 cubic Bezier, it's the 2nd control point of P[i-1] segment.
- P[i].R (Right) is the first Bezier control point to the right of P[i] i.e. -
1st control point of P[i] segment.

When we talk about junction i control-points we mean P[i].L and P[i].R
Please note each of these control-points belongs to a *different* segment.
On a closed-spline each point has both P[i].L and P[i].R
On an open-spline P[0] has only P[0].R and P[last] has only P[last].L

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.
For cubic Bezier segments P[i-1].RR = P[i].L and P[i].RR = P[i+1].L

When we talk about P[i] segment control-points we mean P[i].R and P[i].RR

- 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 junction i control-vectors we mean P[i].in and P[i].out
On an open spline P[0] has only P[0].out and P[last] has only P[last].in

Please note that the important building blocks of a spline are not its Bezier segments per-se but rather the joins between them combined with their immediately-adjacent control-points/vectors (P[i].L, P[i], P[i].R) as the relations between them is what dictates the spline smoothness.

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

Above definitions are more than enough for describing the drawing of all the article splines directly as SVG path elements. 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 and Catmull-Rom can interpolate 3 points in a loop):

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 their 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 Catmull-Rom spline. Officially we say it has an L4 locality means moving a knot can change the shape of only 4 segments, 2 on each side of the moving knot.

To compare to a not-so-good locality (gently put), go back to demo 1.
Moving a knot affects the shape of previous segment and of all segments from the moving knot to the end of the spline.

Control-vectors behavior shows particularly well on a four knots closed-spline.
To observe the local behavior on a closed-spline, we need at least five knots (so when we move a knot, at least one segment is undisturbed).



To explain the above algorithm, we need to examine the 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 Bezier which grandma I consider to be [ Mary Everest Boole ]).

Following section, the article I reference is Wikipedia [ Cubic Hermite spline ].

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 h's are the cubic Hermite basis-functions which in functionality are equivalent to the cubic Bezier basis-functions.
Note 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.

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 are actually the basis-functions of the cubic Bezier.
Which means we can draw the exact same cubic Hermite curve as a cubic Bezier curve (this btw is true not only for Hermite but for any cubic spline).

Few lines down the article, 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 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]

Notice tangent m[i] of segment i is the same as tangent m[i] of segment i-1.

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 extract from the above two connected segments and get:

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

If we remember that m[i] is actually a vector (hence also m[i]/3), the symmetry of these 3 points makes the C1 continuity at junction P[i] very clear.

Now is the time to visit the Catmull-Rom algorithm and learn how it calculates the tangent m[i]. We find it few lines down 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

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

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

Note Catmull-Rom calculates tangent for a junction simply as half 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 = 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.

Simple rules for quick C1 check from inputs:
Hermite: P[i] start tangent coincides with P[i-1] end tangent.
Bezier: P[i] 1st control is a reflection of P[i-1] 2nd control through p[i]

Demo 3: Hermite and Bezier inputs for the same 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 input points, 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 other splines as well so the following discussion is generally 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 (linear interpolation) 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 invent at least one new control-point
per end segment.

First new control-point (per end segment) calculated by most common methods the same way, is the one closest to first/last junction which is simply mirrored from the control-point on the other side of the same junction i.e. - P[0].RR (=P[1].L) is mirrored from P[1].R through P[1], and symmetrically, P[last-1].R mirrored from P[last-1].L through P[last-1].

This solution is actually self requested for Catmull-Rom which implicitly does that mirroring at every internal junction (an internal-junction is a junction with a neighbor *junction* on each side). It extends the C1 continuity to the entire spline, definitely contributing to a more homogenous look of the spline.

With this single new control-point we can already complete the spline nicely by drawing end segments as quadratic Beziers. Spline is not wholly cubic but
still nicely smooth as wholly C1.

Rest of the methods discussed here invent one more control-point.

With no constrains, If all we want is a nice looking or "fair" curve, then by far the most commonly used method is the "natural" or "relaxed" end-segments.
The name comes from real mechanical splines which ends are left without pegs to curve them, thus having 0 curvature which, if translated to math terms, means second derivative at end points is 0.
Using Bezier math we can equate:

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

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

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

Which geometrically means first control point of P[0] segment is exactly half way between P[0] and its second control point P[0].RR (mirrored from P[1].R thus calculated). Symmetrically, last control point of the spline (P[last].L) is half way between P[last] and P[last-1].R

Note that with last two methods, quadratic and natural, shape of the end segments is pretty similar (see next demo) still, the quadratics are always closer (tighter) to the P-polygon than the naturals.

But even with this knowledge, it's generally not trivial to predict the exact tangents at end points. Sometimes though, either for artistic reasons or for some functionality, we want to know the end tangents precisely.
Next two methods allow us just that, one explicitly and the other implicitly, hence belong to the category of "constrained" splines.

First solution, and the more versatile, 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.
As the name implies, In this method we explicitly provide the end tangents.
Now, to connect our spline smoothly to any design/spline, all we need is to match the end tangents of both and make sure their end points coincide.
The great freedom we gain is that we can move any junction freely without affecting the continuity at the connection points.

Second in this category is the "colinear" spline.
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].
Formally:

      P[0].out = t(P[1]-P[0])    //  t ∈ [0..1]
      P[0].R = P[0] + t(P[1]-P[0])

and at the far end:

      P[last].in = t(P[last]-P[last-1])
      P[last].L = P[last] - t(P[last]-P[last-1])

Where t is the "part" of the way hence bound to 0 ≤ t ≤ 1
In the following demo we use t=1/3 for the "colinear" end type and Doug Schepers Catmull-Rom [ dotty ] uses (implicitly - see discussion below) t=1/6.

The 1/3 and 1/6 values are also implicit results of applying the point-reflection and point-duplication methods respectively. Though "colinear" is more versatile, we discuss those methods because they are widely used to shape open Catmull-Roms ([ Degrafa ] allows both and Dotty uses point-duplication).

Their basic idea is to invent new end-points (so far we invented control-points, not points) and let the Catmull-Rom algorithm do the rest.
i.e. - invent P[-1] and P[last+1] and operate Catmull-Rom on the extended P.

As the newly invented points are now end-points, the old end-points become junctions so Catmull-Rom can interpolate the whole original P.
Only question left is where are the new control-points (P[0].R and P[last].L):

For the following calculations remember Catmull-Rom slices 1/6 of P[i].triBase for each one of P[i] control-vectors.

With point-duplication we simply duplicate end points, so for first segment:

         P[-1] = P[0]
      => P[0].leftLeg = 0
      => P[0].triBase = P[0].rightLeg = P[1]-P[0]
      => P[0].out = P[0].triBase/6 = 1/6(P[1]-P[0])

precisely "colinear" with t = 1/6.

With point-reflection we reflect (mirror) P[1] through P[0] to create P[-1] so:

         P[-1] = P[0] - (P[1]-P[0])
      => P[0].leftLeg = P[0].rightLeg
      => P[0].triBase = 2P[0].rightLeg = 2(P[1]-P[0])
      => P[0].out = 2P[0].rightLeg/6 = 1/3(P[1]-P[0])

equivalent to "colinear" with t = 1/3.

Symmetrically of course, those methods applied to shape last segment.

To conclude - the "colinear" method allows us more freedom to choose t,
with 1/6 and 1/3 of the point-invention methods being just private cases.

The "colinear" spline always starts/ends in the direction of the first/last leg of its P-polygon, hence can be smoothly connected to any design which
end/start tangent-direction is the same as the "colinear" first/last leg direction.

Summary of open spline end types:

No new control-points
0) Don't draw.
1) Straight line.

One new control-point
2) Quadratic.

Two new control-points
3) Natural (relaxed).
4) Clamped.
5) Colinear (including point-duplication/reflection).

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.

Following demo is pretty busy trying to pack all open-spline end-types (other than straight lines). Spline between junctions (lime) is Catmull-Rom.

Onload, the constrained end segments (clamped aqua, colinear yellow) are C1 connected to the side designs. Moving the middle junction does not affect either constrained 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 of the colinear to C0 (connected but not smooth).
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, and assuming we use the original Catmull-Rom algorithm which cannot operate on less than 4 points, there is actually no curve to draw.

Hiding all end types but with at least 4 points, only the spline between junctions and internal control-vectors are drawn, though end points are still active (try move them), affecting the shape of 2nd and 2nd-to-last segments.

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 methods of shaping open-spline end-segments. [ Full page ]

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

Further more, since our "direct Catmull-Rom to Bezier" algorithm calculates the two control-vectors of a junction from only 3 points, from here on, any Catmull-Rom demo will draw 3 points open-spline as 2 smoothly-connected natural end-segments.

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

Splines to SVG cont’d

Israel Eisenberg Sep 2012