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.
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
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:
An open-spline interpolates all P-points but not P[last] to P
A closed-spline (loop) interpolates all P-points including P[last] to P
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 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 has only P.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 has only P.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 ]
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
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] +
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.RR (=P.L) is mirrored from P.R through P,
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'' = 6(P - 2P.R + P.RR) = 0
We want to find P.R (P segment first control point) so we isolate and get:
P.R = (P + P.RR)/2
Which geometrically means first control point of P segment is exactly half way
between P and its second control point P.RR (mirrored from P.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.R to be colinear
with P and P at some part of the way between them (regardless of P.RR position).
Symmetrically, P[last].L is placed part of the way from P[last] to P[last-1].
P.out = t(P-P) // t ∈ [0..1]
P.R = P + t(P-P)
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.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
=> P.leftLeg = 0
=> P.triBase = P.rightLeg = P-P
=> P.out = P.triBase/6 = 1/6(P-P)
precisely "colinear" with t = 1/6.
With point-reflection we reflect (mirror) P through P to create P[-1] so:
P[-1] = P - (P-P)
=> P.leftLeg = P.rightLeg
=> P.triBase = 2P.rightLeg = 2(P-P)
=> P.out = 2P.rightLeg/6 = 1/3(P-P)
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
Two new control-points
3) Natural (relaxed).
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:
Israel Eisenberg Sep 2012