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.
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:
- 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 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 ]
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
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] +
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'' = 6(P - 2P.R + P.RR) = 0
We need to find P.R (first P control point) so we isolate and get:
P.R = (P + P.RR)/2
Which geometrically means that the first control point of P is exactly half way
between P and the second control point (which is also P.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.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.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].
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).
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:
Israel Eisenberg Sep 2012