Knot Intervals and Multi-Degree Splines
Thomas W. Sederberg
Brigham Young University
Jianmin Zheng and Xiaowen Song
Zhejiang University
May 23, 2003
Abstract
This paper studies the merits of using knot interval notation for B-spline curves, and presents formulae
in terms of knot intervals for common B-spline operations such as knot insertion, differentiation, and
degree elevation. Using knot interval notation, the paper introduces MD-splines, which are B-spline-like
curves that are comprised of polynomial segments of various degrees (MD stands for \multi-degree").
MD-splines are a generalization of B-spline curves in that if all curve segments in an MD-spline have the
same degree, it reduces to a B-spline curve. The paper focuses on MD-splines of degree 1, 2, and 3, as
well as degree 1 and n. MD-splines have local support, obey the convex hull and variation diminishing
properties, and are at least Cn??1, where n is the smaller of the degrees of two adjoining curve segments.
1 Introduction
B-spline curves are typically specified in terms of a set of control points, a knot vector, and a degree. Knot
information can also be imposed on a B-spline curve using knot intervals, introduced in [6] as a way to assign
knot information to subdivision surfaces. A knot interval is the difference between two adjacent knots in a
knot vector, i.e., the parameter length of a B-spline curve segment. For even-degree B-spline curves, a knot
interval is assigned to each control point, since each control point in an even-degree B-spline corresponds to
a curve segment. For odd-degree B-spline curves, a knot interval is assigned to each control polygon edge,
since in this case, each edge of the control polygon maps to a curve segment.
While knot intervals are basically just an alternative notation for representing knot vectors, knot intervals
offer some nice advantages. For example, knot interval notation is more closely coupled to the control polygon
than is knot vector notation. Thus, knot intervals have more geometric meaning than knot vectors, since
the effect of altering a knot interval can be more easily predicted. Knot intervals are particularly well suited
for periodic B-splines.
13
12 13
13
13
a. Degrees 2 and 3.
13
13
13
11
b. Degrees 1 and 3.
11
22
12
12
13
23
13
c. Degrees 1,2, and 3.
Figure 1: MD-spline examples.
1
The use of knot intervals to bind the knot information to the control polygon also enables us to explore
new possibilities, such as using a single control polygon to define a composite curve comprised of segments
of more than one degree. This paper introduces such a piecewise curve, and we refer to it as a multi-degree
spline, or MD-spline. Figure 1 shows three examples of MD-splines. The control polygon is labeled with
knot intervals, with a superscript denoting the degree of the corresponding curve segment. The MD-spline in
Figure 1.a is comprised of four cubic curve segments and one quadratic curve segment, all with knot interval
values of 1. The black dots on the curve indicate junction points between adjacent curve segments, and the
curves are C1. Figure 1.b shows an MD-spline comprised of three cubic segments and one linear segment. In
this case, the cubic segments are C1 with the linear segment. Figure 1.c shows an MD-spline with segments
of degree 1, 2, and 3. All pairs of neighboring curve segments are C1 except neighboring cubic segments are
C2.
One application for MD-splines is in font description, where outlines are typically expressed as a collection
of cubic Bezier curves and line segments. Figure 2.a shows the outline of a character whose Bezier control
points are shown in Figure 2.b. The outline is comprised of 12 line segments and 24 cubic curve segments,
and the Bezier form requires 85 control points. Figure 2.c shows the outline represented in cubic B-spline
form. This requires the line segments to be degree elevated to degree three and knots to be removed where
possible. The resulting B-spline control polygon contains 65 control points and 66 knots. The MD-spline
version shown in Figure 2.d contains 41 control points and 40 knot intervals. The conversion from Bezier to
B-spline and MD-spline introduces no error, and the MD-spline representation requires less data than the
other forms.
a. Font outline b. Bezier c. B-spline d. MD-spline
Figure 2: Font example.
MD-splines are generalizations of B-splines. In the case when all knot intervals are of the same degree,
the MD-spline specializes to a B-spline. MD-splines maintain many desirable properties of B-spline curves,
such as the convex hull and variation diminishing properties. They also have local support, with each degree
n segment being supported by n + 1 control points. However, each control point in an MD-spline of degree
1, 2, and 3 can support as many as seven curve segments.
The idea of constructing splines with non-uniform degree was proposed earlier in [1, 2, 4], where the goal
is shape-preserving interpolation. In these papers, the spline is comprised of segments of degree n 3 whose
basis polynomials are taken from a four dimensional subspace of the space of degree n polynomials. This
resembles a cubic B-spline in that the support for each segment consists of four control points, while the
variable degree is used as a tension parameter which can adjust the shape. In our scheme, each degree n
segment is supported by n + 1 control points.
Section 2 discusses the relationship between knot vectors and knot intervals, and describes how B-spline
operations such as knot insertion, knot doubling, degree elevation, and differentiation can be expressed using
knot intervals. Section 3 explains what it means when more than one knot interval is placed along a single
edge or vertex of a control polygon. Section 4 discusses MD-splines, and Section 5 summarizes the paper
and offers some questions for further study. Throughout the paper, we adopt the convention that when k is
odd, k=2 means bk=2c = (k ?? 1)=2.
2
2 Knot Intervals
One objective of this paper is to demonstrate that knot intervals have some advantages over knot vectors for
curve design. Knot intervals contain all of the information that a knot vector contains, with the exception
of a knot origin. This is not a problem, since the appearance of a B-spline curve is invariant under linear
transformation of the knot vector|that is, if you add any constant to each knot the curve's appearance does
not change. B-splines originated in the field of approximation theory and were initially used to approximate
functions. In that context, parameter values are important, and hence, knot values are significant. However,
in curve and surface shape design, we are almost never concerned about absolute parameter values.
For odd-degree B-spline curves, the knot interval di is assigned to the control polygon edge Pi|Pi+1. For
even-degree B-spline curves, knot interval di is assigned to control point Pi. Each vertex (for even degree)
or edge (for odd degree) has exactly one knot interval. If the B-spline is not periodic, n??1
2 \end-condition"
knot intervals must be assigned past each of the two end control points. They can simply be written adjacent
to \phantom" edges or vertices sketched adjacent to the end control points; the geometric positions of those
phantom edges or vertices are immaterial. Figure 3 shows a cubic B-spline curve. The control points in
P(1,2,3)
P(2,3,4)
P(3,4,6)
P(4,6,9)
P(6,9,10)
P(9,10,11)
t=3 t=4
t=6
t=9
Knot Vector = [1,2,3,4,6,9,10,11]
P0
P1
P2
P4 P3
P5
d-1=1
d0=1
d1=1
d2=2
d3=3
d4=1
d5=1
t=3 t=4
t=6
t=9
Knot Vector = [1,2,3,4,6,9,10,11]
Figure 3: Sample cubic B-spline
Figure 3.a are labeled with polar values, and Figure 3.b shows the control polygon edges labeled with knot
intervals. End-condition knots require that we hang one knot interval off each end of the control polygon.
Note the relationship between the knot vector and the knot intervals: Each knot interval is the difference
between two consecutive knots in the knot vector. For periodic B-splines, things are even simpler, since
we don't need to deal with end conditions. Figure 4 shows two cubic periodic B-splines labelled with knot
P0
P1
P2
P4 P3
d0= 1
d1= 1
d2= 1
d3= 1
d4= 1
P0
P1
P2
P4 P3
d0= 2
d1= 3
d2= 2
d3= 1
d4= 1
Figure 4: Periodic B-splines labelled with knot intervals
intervals. In this example, note that as knot interval d1 changes from 1 to 3, the length of the corresponding
curve segment increases.
Figure 5 shows two periodic B-splines with a double knot (imposed by setting d0 = 0) and a triple knot
(set d0 = d1 = 0).
3
P0
P1
P2
P4 P3
d0= 0 d1= 1
d2= 1
d3= 1
d4= 1
P0
P1
P2
P4 P3
d0= 0 d1= 0
d2= 1
d3= 1
d4= 1
Figure 5: Periodic B-splines with double and triple knots.
In order to determine formulae for operations such as knot insertion in terms of knot intervals, it is
helpful to infer polar labels for the control points. Polar algebra [5] can then be used to create the desired
formula. The arguments of the polar labels are sums of knot intervals. We are free to choose any knot
P0
P1
P2
P4 P3
d0 d1
d2
d3
d4
a.
f(-d4,0,d0)
f(0,d0,d0+d1)
f(d0,d0+d1,d0+d1+d2)
P4 f(d0+d1,d0+d1+d2,d0+d1+d2+d3)
d0 d1
d2
d3
d4
b.
Figure 6: Inferring polar labels from knot intervals.
origin. For the example in Figure 6, we choose the knot origin to coincide with control points P0. Then the
polar values are as shown in Figure 6.b.
The following subsections show how to perform knot insertion and interval halving, and how to compute
hodographs using knot intervals. These formulae can be verified using polar labels. The expressions for these
operations written in terms of knot vectors can be found, for example, in [3].
2.1 Knot Insertion
Knot intervals provide an easy-to-remember method for performing knot insertion. For a cubic B-spline,
begin by splitting each edge Pi{Pi+1 of the control polygon into three segments whose lengths are proportional
to di??1, di, and di+1 as shown in Figure 7a. (for periodic B-splines, the subscript values are all
modulo the number of edges in the control polygon). For a B-spline of even degree 2n, each edge is split
into 2n segments whose lengths are proportional to di??n; : : : ; di+n??1 and for a B-spline of odd degree 2n+1,
each edge is split into 2n + 1 segments whose lengths are proportional to di??n; : : : ; di+n. Knot insertion in
terms of knot intervals can be thought of as splitting a knot interval at some fraction t 2 [0; 1]. For example,
suppose we wish to split knot interval d1 in Figure 7a at t = 1
3 . We simply find each occurrence of d1 on the
control polygon edges, insert a control point 1
3 of the way along each segment labelled d1, and replace the
control points P1 and P2 with A, B and C as shown in Figure 7.b.
Knot removal is the inverse of knot insertion. Thus, given the control polygon in Figure 7.b, knot removal
would produce the control polygon in Figure 7.a. Knot removal is possible only when two adjacent curve
segments are Cr with r > n ?? m where n is the degree and m is the multiplicity of the knot; thus it is not
generally possible to perform knot removal. We will say that a control polygon which cannot undergo knot
4
P0
P1
P2
P4 P3
d4
d0
d1
d0
d1
d2
d1
d2
d3
d4 d3 d2
d3
d4
d0
a.
P0
P1
P2
P4 P3
A B
C
d4
d0
d1
d0
d1
d2
d1
d2
d3
b.
Figure 7: Knot insertion on a cubic B-spline.
removal is in minimal form, and the minimal form of a B-spline control polygon results when all knots have
been removed that can be.
2.2 Interval Halving
Subdivision surfaces such as the Catmull-Clark scheme are based on the notion of inserting a knot half way
between each existing pair of knots in a knot vector. These methods are typically restricted to uniform knot
vectors. Knot intervals help to generalize this technique to non-uniform B-splines. Using knot intervals, we
can think of this process as cutting in half each knot interval. For a quadratic non-uniform B-spline, the
interval halving procedure is a generalization of Chaikin's algorithm, but the placement of the new control
points becomes a function of the knot interval values. If each knot interval is cut in halve, the resulting
control polygon has twice as many control points, and their coordinates Qk are:
Q2i =
(di + 2di+1)Pi + diPi+1
2(di + di+1)
Q2i+1 =
di+1Pi + (2di + di+1)Pi+1
2(di + di+1)
(1)
as illustrated in Figure 8.
Pi-1
Pi
Pi+1
di-1
di-1
di di
di+1
di+1
di/2 di/2
di+1/2
Q2i-1 Q2i
Q2i+1
Figure 8: Interval halving for a non-uniform quadratic B-spline curve.
For non-uniform cubic periodic B-spline curves, interval halving produces a new control point corresponding
to each edge, and a new control point corresponding to each original control point. The equations for
the new control points Qk generated by interval halving are:
Q2i+1 =
(di + 2di+1)Pi + (di + 2di??1)Pi+1
2(di??1 + di + di+1)
(2)
Q2i =
diQ2i??1 + (di??1 + di)Pi + di??1Q2i+1
2(di??1 + di)
(3)
as shown in Figure 9.
Note that each new knot interval is half as large as its parent.
5
Pi-1
Pi
Pi+1
Q2i-1
Q2i
Q2i+1
di-1
di
di-2 di+1
di-1/2 di/2
Figure 9: Interval halving for a non-uniform cubic B-spline curve.
2.3 Hodographs
The derivative P0(t) of a B-spline is called its hodograph. The hodograph of a degree n B-spline P(t) with
knot intervals di and control points Pi is a B-spline of degree n??1 with the same knot intervals di and with
control points Qi where
Qi = ci(Pi+1 ?? Pi): (4)
The scale factor ci is the inverse of the average value of n neighboring knot intervals. Specifically, if the
curve is even-degree n = 2m, then
ci =
n
di??m+1 + : : : + di+m
and if the curve is odd degree n = 2m+ 1
ci =
n
di??m + : : : + di+m
2.4 Degree elevation
Ramshaw [5] presented an elegant insight into degree elevation using polar form. The symmetry property of
polar labels demands that
g2(a; b) =
f1(a) + f1(b)
2
; g3(a; b; c) =
f2(a; b) + f2(a; c) + f2(b; c)
3
; (5)
g4(a; b; c; d) =
f3(a; b; c) + f3(a; b; d) + f3(a; c; d) + f3(b; c; d)
4
; etc. (6)
where fi refers to the i-polar form that results from a univariate polynomial of degree not greater than
i, and gi+1 means the (i + 1)-polar form from the same polynomial.
The procedure of degree elevation on a periodic B-spline that is labeled using knot intervals results in two
effects. First, an additional control point is introduced for each curve segment. Second, if the sequence of
knot intervals is initially d1; d2; d3; : : :, the sequence of knot intervals on the degree elevated control polygon
will be d1; 0; d2; 0; d3; 0; : : :. The zeroes must be added because degree elevation raises the degree of each
curve segment without raising the continuity between curve segments,
Degree elevation of a degree one B-spline is simple: merely insert a new control point on the midpoint of
each edge of the control polygon. The knot intervals are as shown in Figures 10.a and b.
Degree elevation for a degree two B-spline is illustrated in Figures 10.c and d. The new control points
are:
Pi;j =
(2di + 3dj )Pi + diPj
3di + 3dj
: (7)
Figure 11 illustrates degree elevation from degree three to four. The equations for the new control points
are:
Pi;i+1 =
(di + 2di+1)Pi + (2di??1 + di)Pi+1
2(di??1 + di + di+1)
Qi =
di
4(di??2 + di??1 + di)
Pi??1+
Pi+
di??1
4(di??1 + di + di+1)
Pi+1
6
.
P0
P1
P2
P3
d0
d1
d2
d3
a. Degree one B-spline
P0
P1
P2
P3
P01
P12
P23
0
0
0
0
d0
d1
d2
d3
b. Degree elevation of (a.)
P0
P1
P2
P3
d0
d1
d2
d3
c. Degree two B-spline
P01
P10
P12
P21
P23
P32
P30 P03
0
0
0
0
d0
d1
d2
d3
b. Degree elevation of (c.)
Figure 10: Degree elevating a degree one and degree two B-spline.
d0
d1
d2
d3
P0
P1
P2 P3
P4
a. Cubic B-spline.
d0
d1
d2
d3
0
0 0
P01
Q1
P12
Q2 P23 Q3
P34
b. Degree elevated.
Figure 11: Degree elevating a degree three B-spline.
3 Split-Interval Notation
A useful variation of knot interval notation is split-knot-interval notation in which a knot interval is split
into a sequence of two or more non-negative knot intervals which sum to the original interval. Figure 12.a
shows a periodic cubic B-spline whose top edge has a knot interval of 3. In Figure 12.b, that knot interval is
divided and the edge is labeled with two knot intervals 1,2. Figure 12.c shows an equivalent representation
in which the knot interval has actually been split by performing knot insertion, as discussed in Section 2.1.
We will refer to this as the expanded form of the split-interval notation
1
3
1
1
a. Original knot intervals
1
1,2
1
1
b. Split interval
1
1
2
1
1
c. Expanded form.
Figure 12: Cubic B-spline with two knot intervals on one edge.
A degree n B-spline is comprised of curve segments that meet with continuity Cn??r where r is the
multiplicity of the knot. Curve segments mapped to in split-interval notation are C1.
7
2
2
2
2
a. Original knot intervals
2
1,0,0,1
2
2
b. Split interval
2
1
0 0
1
2
2
c. Expanded form.
Figure 13: Four knot intervals on one edge of a cubic B-spline, expressing the de Boor algorithm.
A second example is presented in Figure 13. Here, the knot interval on the top edge is split into four
intervals in Figure 13.b. The expanded form contains a triple knot. This is actually a way of denoting the
de Boor algorithm using split interval notation. Using the terminology in Section 2.1, the control polygon
in Figure 13.a is the minimal form of the control polygon in Figure 13.c.
4 MD-splines
In MD-splines, curve segments are not required to all have the same degree and so each knot interval carries
a superscript which specifies the degree of its corresponding curve segment. As in conventional B-splines,
knot intervals of even degree are assigned to vertices and of odd degree to edges of the control polygon.
Similar to split-interval notation (Section 3), every MD-spline has an equivalent representation as an
\expanded-form" control polygon, which is a conventional B-spline. In our discussion, we will denote the
MD-spline control polygon by P and the expanded-form control polygon as Q. Thus, each knot interval in
Q will have a superscript of n. Since Q is a conventional B-spline control polygon, it is labeled with knot
intervals of only one degree, and each vertex (for even degree) or edge (for odd degree) has exactly one knot
interval. MD-splines are thus defined in terms of a set of rules for constructing a unique Q from a given P,
subject to some constraints. Those rules will define a mapping E which takes an MD-spline control polygon
and creates a B-spline control polygon; we will write Q = E(P).
Before stating the constraints, we define some terminology. A control polygon is said to be in B-spline
form if each vertex (for even degree) or edge (for odd degree) has exactly one knot interval and the degrees
of all knot intervals are the same. A B-spline control polygon is said to be in minimal form if knot removal
is impossible. A control polygon Q that is not in minimal form can be converted to minimal form through
(possibly repeated) knot removal which will produce the minimal form of Q. We will denote by M(Q) the
minimal form of Q. The minimal-expanded form M(E(P)) of an MD-spline control polygon P is produced
by taking its expanded form and performing all possible knot removals.
We now present the constraints for devising the transformation Q = E(P).
1. The degree of Q is the largest degree of any knot interval in P (n will denote that largest degree) and
Q is in B-spline form.
2. The sequence of knot interval values in P is a subsequence of the sequence of knot interval values in
Q, although the superscripts may differ since all knot interval superscripts in Q are n. The only knot
intervals in Q that are not in P have a value of zero and are used to impose the required continuity.
3. The support for a curve segment whose knot interval is dk consists of k +1 control points. If k is even
and knot interval dk is assigned to Pi, those control points are Pi??k=2; : : : ;Pi+k=2. If k is odd and
knot interval dk is assigned to edge Pi{Pi+1, the support consists of Pi??k=2 : : :Pi+k=2+1.
8
4. Since a B-spline control polygon Q is a special case of an MD-spline control polygon, M(Q) =
M(E(Q)).
5. If an MD-spline control polygon P is created by taking an even/odd degree n B-spline control polygon
Q and assigning odd/even degree 6= n knot intervals with values of zero to one or more edge/vertex,
then M(Q) = M(E(P)).
6. The continuity between curve segments is as high as possible while maintaining properties 1|5.
In the knot interval notation dj
i , the value (curve segment parameter length) of the knot interval is
conveyed by di, and the superscript j indicates that the interval represents a degree j curve segment. The
curve segment degrees are specified only in the knot intervals for P, because all knot intervals in Q have the
same superscript (since Q is in B-spline form). The mapping E assures that a curve segment corresponding
to knot interval dj
i in P is indeed degree j in power basis, although it is degree-elevated to be degree n in
the B-spline basis. Also, if a knot interval dj
i on P is converted to a knot interval dk
i (k 6= j) on Q, the value
(parameter length) of those knot intervals are the same,
We will now examine three special cases of MD-splines: the case where one or more curve segments are
degree 1 and the other curve segments are all of the same degree n > 1 (Section 4.1), the case where all
curve segments are degree 2 or 3 (Section 4.2). and the case where all curve segments are degree 1, 2, or 3
(Section 4.3). We will refer to these as the degree (1; n) case, the degree (2; 3) case, and the degree (1; 2; 3)
case respectively. In the (1; n) and (1; 2; 3) cases, each degree-one curve segment is Cn=2 with its degree
n neighbors. In the (2; 3) and (1; 2; 3) cases, quadratic segments are C1 with their neighbors and pairs of
adjacent cubic segments are C2. These continuities assume that there are no zero knot intervals in P.
The mappings E(P) presented in the following sections require that, for an odd/even value of n, all
edges/vertices of the control polygon be labeled with a knot interval, but if a knot interval on an edge/vertex
is not specified, we will assume it to be zero. Knot intervals on vertices/edges are optional.
4.1 Degree (1; n) MD-splines
In this section we consider MD-splines that have knot intervals of degree 1 along with knot intervals of one
other degree n > 1. The control polygon for a (1; n) MD-spline is defined as follows. If n is even, then every
vertex of P is labeled with a knot interval of degree n and one or more edges are labeled with a knot interval
of degree one. If n is odd, then every edge of P is labeled with a knot interval that is either of degree 1 or
of degree n.
For the (1; n) case, it is straightforward to devise a transformation Q = E(P) for creating an expanded
form Q from the MD-spline control polygon P, subject to the conditions enumerated in Section 4. Recall
that for a degree n B-spline curve, necessary and sufficient conditions for one of the curve segments to be
a line is for n + 1 adjacent control points to be collinear. In order for that line segment to be a degree-one
curve (i.e., properly parametrized) we also require that the second hodograph for the curve segment must
vanish. With that in mind, we can devise a transformation E(P) as follows. To begin with, every control
point in P is also a control point in Q. In addition, if an edge of P is labeled d1
i , that edge is split into n
collinear line segments in Q by inserting n ?? 1 control points. If n is even/odd, the middle of those new
control points/edges is labeled dn
i and all other of those control points/edges is labeled with a zero knot
interval. We must next space those new control points such that the second hodograph of that curve segment
is identically zero. Denote by l1; : : : ; ln the lengths of the new edges into which the edge on P is partitioned.
Denote the knot intervals on Q in the neighborhood of the edge by
di??n
2 ; di??n
2
n??1
2
; di; 0|; :{:z: ; 0}
n??1
2
; di+1; : : : ; di+n
2 (8)
= e1; e2; : : : ; e2n??1: (9)
Then the second hodograph will vanish if
9
21
12 11
12 12
22
a. (1,2) MD-spline.
22
12 12
12 12
22
b. Expanded form.
Figure 14: Degree (1; 2) MD-spline.
where L(i; j) =
Pj
k=i ek. This choice for E(P) will satisfy all of the conditions in Section 4. Since there are
n??1
2 adjacent zero knot intervals, the continuity is Cn??1??
n??1
2 = C n
2 .
13
13
13
21
a. (1,3) MD-spline.
13
13
13
03 23 03
b. Expanded form.
Figure 15: Degree (1; 3) MD-spline.
MD-splines of degree (1; 2) and (1; 3) are shown in Figures 14 and 15.
4.2 Degree (2; 3) MD-splines
In this section we consider MD-splines that have knot intervals of degree 2 or 3. Our goal is to devise a
transformation Q = E(P) for creating an expanded form Q from the MD-spline control polygon P, subject
to the conditions enumerated in Section 4.
We first must resolve the continuity question, stated in condition 6. Our analysis revealed that C1
between segments of degree 2 and 3 is the highest continuity which allows for conditions 1{5; C2 is possible
only if we relinquish condition 3. The C1 condition means that every knot interval d2 in P maps to a knot
interval d3 in Q that has a knot interval 03 on each of its two neighboring edges. Topologically, each vertex in
P that is labeled with d2
i will be replaced by four control points Q0, Q1, Q2, and Q3, as shown in Figure 16.
The coordinates for the control points Q0, Q1, Q2, and Q3 that replace P1 are:
Q0 =
(d4 + d5)P0 + (d1 + d2 + d3)P1
d1 + d2 + d3 + d4 + d5
; Q3 =
(d5 + d6 + d7)P1 + (d3 + d4)P2
d3 + d4 + d5 + d6 + d7
(11)
Q1 = c1Q0 + c2P1 + c3Q3; Q2 = c4Q0 + c5P1 + c6Q3 (12)
where
c1 =
(d3 + d4)(d4 + 2d5)
(2d3 + 3d4)(d3 + d4 + d5)
c2 =
d4(d3 + 2d4 + d5)
(d4 + d5)(2d3 + 3d4)
c3 =
d3(d3 + d4)(d4 + 2d5)
(d4 + d5)(2d3 + 3d4)(d3 + d4 + d5)
(13)
10
d3
3
d2
4
d3
5
d2
2
d3
1
d3
7
d2
6
P0
P1
P2
a. Degree (2,3) MD-spline.
03 03
Q0
Q1Q2
d3 Q3
3 d3
5
d3
4
b. Expanded form.
Figure 16: Expanded form of a degree (2; 3) MD-spline .
c4 =
d5(d4 + d5)(2d3 + d4)
(d3 + d4)(3d4 + 2d5)(d3 + d4 + d5)
c5 =
d4(d3 + 2d4 + d5)
(d3 + d4)(3d4 + 2d5)
c6 =
(d4 + d5)(2d3 + d4)
(3d4 + 2d5)(d3 + d4 + d5)
: (14)
The superscripts of the knot intervals are ignored in these equations, since we are only interested in the
values of the knot intervals. If d2 or d6 are not specified on the control polygon, they are taken to be zero.
4.3 Degree (1; 2; 3) MD-splines
The (1; 2; 3) case can be dealt with by first preprocessing all degree 1 segments by inserting two temporary
control points A and B into each degree 1 edge in P as discussed below, then applying the transformation
rules for the (2; 3) case, and finally removing each A and B. The preprocess, illustrated in Figure 17, turns
the degree one edge into a degree three edge that has double knots on each end.
d1
3
d2
4
d3
5
d2
2
d3
1
d3
7
d2
6
P0
P1
P2
a. Degree (1,2,3) MD-spline.
03
03
d1
3
d2
4
d3
5
d2
2
d3
1
d3
7
d2
6
P0
P1
P2
A
B
b. Preprocess step.
Figure 17: Preprocessing a degree (1; 2; 3) MD-spline .
11
The new control points A and B are found as follows:
where
=
(d2 + d3)
2
3(d4
4 + d2
2 + d3(
2 +
4 +
2
4))
; =
(d3 + d4)
4
1(d4
4 + d2
2 + d3(
2 +
4 +
2
4)
(16)
with
1 =
d4 + d5
d3 + d4 + d5
;
2 =
2d4 + d5
3(d4 + d5)
;
3 =
d1 + d2
d1 + d2 + d3
;
4 =
d1 + 2d2
3(d1 + d2)
: (17)
The positions for A and B given by these equations are uniquely chosen so that, after the transformation
rules for the (2; 3) case are applied and each A and B are removed, the resulting linear segments will be C1
with their neighbors plus they will satisfy all of the conditions in Section 4.
A (1; 2; 3) MD-spline is shown in Figure 18.
11
22
12
12
13
23
P0 13
P1 P2
P3
a. Degree (1,2,3) MD-spline.
03
03
13
22
12
12
13
23
13
A
B
b. Preprocess step.
03
03
13
23
03
13
03 13
23
13 03
13
03
c. Expanded form.
Figure 18: A degree (1; 2; 3) MD-spline.
5 Discussion
This paper introduces the notion of MD-splines and explores two cases: degree (1; n), and degree (1; 2; 3).
It is clear that these MD-splines obey the convex hull property because the control points of Q lie within
the convex hull of P. It is also straightforward to prove that these MD-splines are variation diminishing,
because the map Q = E(P) will not allow a generic line to intersect Q more times than it intersects P.
Several interesting questions remain for subsequent study. For example,
1. Can MD-splines be extended to higher degrees, and do general expressions exist for the transformation
Q = E(P)?
2. Is there some way that MD-splines can be understood in terms of polar form, such that polar algebra
would lead directly to computing the expanded forms?
3. How can knot insertion, degree elevation, and differentiation be performed directly on MD-splines?
4. What are the basis functions for MD-splines? Can they be generated using recurrence relations?
With insights that polar form might provide, the answers to most other questions would be more straightforward.
12
References
[1] P. Costantini. Variable degree polynomial splines. In C. Rabut A. Le Mehaute and L. L. Schumaker,
editors, Curves and Surfaces with Applications in CAGD, pages 85{94. Vanderbilt University Press,
Nashville, 1997.
[2] P. Costantini. Curve and surface construction using variable degree polynomial splines. Computer Aided
Geometric Design, 17(5):419{446, 2000. ISSN 0167-8396.
[3] J Hoschek and D Lasser. Fundamentals of Computer Aided Geometric Design. A K Peters, 1993.
[4] P.D. Kaklis and D.G. Pandelis. Convexity-preserving polynomial splines of non-uniform degree. IMA
Journal of Numerical Analysis, 10:223{234, 1990.
[5] L Ramshaw. Blossoms are polar forms. Computer Aided Geometric Design, 6:323{358, 1989.
[6] TWSederberg, J Zheng, D Sewell, and M Sabin. Non-uniform recursive subdivision surfaces. Proceedings
of SIGGRAPH 98, pages 387{394, July 1998. ISBN 0-89791-999-8.
13