i
i
i
i
i
i
i
i
374 15. Curves
b
1,2
(t) b
2,2
(t)
012
3
4
0
1
012
3
4
0
1
Figure 15.18. B-splines with
d
=1or
k
=2.
Uniform Linear B-splines
Consider a set of basis functions of the following form:
b
i,2
(t)=
⎧
⎪
⎨
⎪
⎩
t − i if i ≤ t<i+1,
2 − t + i if i +1≤ t ≤ i +2,
0otherwise.
(15.16)
Each of these functions looks like a little triangular “hat” between i and i +2with
its peak at i +1. Each is a piecewise polynomial, with knots at i, i +1,andi +2.
Two of them are graphed in Figure 15.18.
Each of these functions b
i,2
is a first degree (linear) B-spline. Because we will
consider B-splines of other parameter values later, we denote these with the 2 in
the subscript.
Notice that we have chosen to put the lower edge of the B-spline (its first knot)
at i. Therefore the first knot of the first B-spline (i =1)isat1. Iteration over the
B-splines or elements of the coefficient vector is from 1 to n (see Equation 15.15).
When B-splines are implemented, as well as in many other discussions of them,
they often are numbered from 0 to n − 1.
We can create a function from a set of n control points using Equation 15.15,
with these functions used for the b
i
to create an “overall function” that was influ-
enced by the coefficients. If we were to use these (k =2) B-splines to define the
overall function, we would define a piecewise polynomial function that linearly
interpolates the coefficients p
i
between t = k and t = n +1. Note that while
(k =2) B-splines interpolate all of their coefficients, B-splines of higher degree
do this under some specific conditions that we will discuss in Section 15.6.3.
Some properties of B-splines can be seen in this simple case. We will write
these in the general form using k, the parameter, and n for the number of coeffi-
cients or control points.
• Each B-spline has k +1knots.
• Each B-spline is zero before its first knot and after its last knot.
i
i
i
i
i
i
i
i
15.6. Approximating Curves 375
• The overall spline has local control because each coefficient is only mul-
tiplied by one B-spline, and this B-spline is non-zero only between k +1
knots.
• The overall spline has n + k knots.
• Each B-spline is C
(k−2)
continuous, therefore the overall spline is C
(k−2)
continuous.
• The set of B-splines sums to 1 for all parameter values between knots k
and n +1. This range is where there are k B-splines that are non-zero.
Summing to 1 is important because it means that the B-splines are shift
invariant: translating the control points will translate the entire curve.
• Between each of its knots, the B-spline is a single polynomial of degree
d = k − 1. Therefore, the overall curve (that sums these together) can also
be expressed as a single, degree d polynomial between any adjacent knots.
In this example, we have chosen the knots to be uniformly spaced. We will con-
sider B-splines with non-uniformspacing later. When the knot spacing is uniform,
each of the B-splines are identical except for being shifted. B-splines with uni-
form knot spacing are sometimes called uniform B-splines or periodic B-splines.
Uniform Quadratic B-splines
The properties of B-splines listed in the previous section were intentionally writ-
ten for arbitrary n and k. A general procedure for constructing the B-splines will
be provided later, but first, lets consider another specific case with k =3.
The B-spline b
2,3
is shown in Figure 15.19. It is made of quadratic pieces
(degree 2), and has 3 of them. It is C
1
continuous and is non-zero only within
the 4 knots that it spans. Notice that a quadratic B-spline is made of 3 pieces,
one between knot 1 and 2, one between knot 2 and 3, and one between knot 3
0
1
012345
Figure 15.19. The B-spline
b
2,3
with uniform knot spacing.
i
i
i
i
i
i
i
i
376 15. Curves
0
1
012345678910
Figure 15.20. The set of seven B-splines with
k
= 3 and uniform knot spacing
[1,2,3,4,5,6,7,8,10].
and 4. In Section 15.6.3 we will see a general procedure for building these func-
tions. For now, we simply examine these functions:
b
i,3
(t)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
1
2
u
2
if i ≤ t<i+1 u = t − i,
−u
2
+ u +
1
2
if i +1≤ t<i+2 u = t − (i +1),
1
2
(1 − u)
2
if i +2≤ t<i+3 u = t − (i +2),
0otherwise.
(15.17)
In order to make the expressions simpler, we wrote the function for each part as
if it applied over the range 0 to 1.
If we evaluate the overall function made from summing together the B-splines,
at any time only k (3 in this case) of them are non-zero. One of them will be in
the first part of Equation 15.17, one will be in the second part, and one will be
in the third part. Therefore, we can think of any piece of the overall function as
being made up of a degree d = k − 1 polynomial that depends on k coefficients.
For the k =3case, we can write
f(u)=
1
2
(1 − u)
2
p
i
+(−u
2
+ u +
1
2
)p
i+1
+
1
2
u
2
p
i+2
where u = t−i. This defines the piece of the overall function when i ≤ t<i+1.
If we have a set of n points, we can use the B-splines to create a curve. If we
have seven points, we will need a set of seven B-splines. A set of seven B-splines
1
2
3
4
5
6
7
Figure 15.21. Curve made from seven quadratic (
k
=3) B-splines, using seven control
points.
i
i
i
i
i
i
i
i
15.6. Approximating Curves 377
for k =3is shown in Figure 15.20. Notice that there are n + k (10) knots, that
the sum of the B-splines is 1 over the range k to n +1(knots 3 through 8). A
curve specified using these B-splines and a set of points is shown in Figure 15.21.
Uniform Cubic B-splines
Because cubic polynomials are so popular in computer graphics, the special case
of B-splines with k =4is sufficiently important that we consider it before dis-
cussing the general case. A B-spline of third degree is defined by 4 cubic poly-
nomial pieces. The general process by which these pieces are determined is de-
scribed later, but the result is
b
i,4
(t)=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
1
6
u
3
if i ≤ t<i+1 u = t − i,
1
6
(−3u
3
+3u
2
+3u +1) ifi +1≤ t<i+2 u = t −(i +1),
1
6
(3u
3
− 6u
2
+4) ifi +2≤ t<i+3 u = t −(i +2),
1
6
(−u
3
+3u
2
− 3u +1) ifi +3≤ t<i+4 u = t −(i +3),
0 otherwise.
(15.18)
This degree 3 B-spline is graphed for i =1in Figure 15.22.
We can write the function for the overall curve between knots i +3and i +4
as a function of the parameter u between 0 and 1 and the four control points that
influence it:
f(u)=
1
6
(−u
3
+3u
2
− 3u +1)p
i
+
1
6
(3u
3
− 6u
2
+4)p
i+1
+
1
6
(−3u
3
+3u
2
+3u +1)p
i+2
+
1
6
u
3
p
i+3
.
b
0
(t)
b
1
(t-1)
b
3
(t-3)
b
2
(t-2)
2
3
t=i
t=i+1
t=i+2
t=i+3
t=i+4
Figure 15.22. The cubic (
k
= 4) B-spline with uniform knots.
i
i
i
i
i
i
i
i
378 15. Curves
This can be re-written using the matrix notation of the previous sections, giv-
ing a basis matrix for cubic B-splines of
M
b
=
1
6
⎡
⎢
⎢
⎣
−13−31
3 −630
−3030
1410
⎤
⎥
⎥
⎦
.
Unlike the matrices that were derived from constraints in Section 15.5, this ma-
trix is created from the polynomials that are determined by the general B-spline
procedure defined in the next section.
15.6.3 Non-uniform B-splines
One nice feature of B-splines is that they can be defined for any k>1. So if we
need a smoother curve, we can simply increase the value of k. This is illustrated
in Figure 15.1.
So far, we have said that B-splines generalize to any k>1 and any n ≥ d.
There is one last generalization to introduce before we show how to actually com-
pute these B-splines. B-splines are defined for any non-decreasing knot vector.
For a given n and k, the set of B-splines (and the function created by their
linear combination) has n + k knots. We can write the value of these knots as
a vector, that we will denote as t. For the uniform B-splines, the knot vector is
[1, 2, 3,...,n+ k]. However, B-splines can be generated for any knot vector of
length n + k, providing the values are non-decreasing (e.g., t
i+1
≥ t
i
).
There are two main reasons why non-uniform knot spacing is useful: it gives
us control over what parameter range of the overall function each coefficient af-
k=3
k=2 k=4
k=5
Figure 15.1. B-spline curves using the same uniform set of knots and the same control
points, for various values of
k
. Note that as
k
increases, the valid parameter range for the
curve shrinks.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.