i
i
i
i
i
i
i
i
364 15. Curves
12
3
4
5
67
Figure 15.8. Cardinal splines through seven control points with varying values of tension
parameter
t
.
Cardinal splines are useful, because they provide an easy way to interpolate
a set of points with C
1
continuity and local control. They are only C
1
,sothey
sometimes get “kinks” in them. The tension parameter gives some control over
what happens between the interpolated points, as shown in Figure 15.8, where a
set of cardinal splines through a set of points is shown. The curves use the same
control points, but they use different values for the tension parameters. Note that
the first and last control points are not interpolated.
Given a set of n points to interpolate, you might wonder why we might prefer
to use a cardinal cubic spline (that is a set of n −2 cubic pieces) rather than a sin-
gle, order n polynomial as described in Section 15.3.6. Some of the disadvantages
of the interpolating polynomial are:
• The interpolating polynomial tends to overshoot the points, as seen in Fig-
ure 15.9. This overshooting gets worse as the number of points grows
larger. The cardinal splines tend to be well behaved in between the points.
• Control of the interpolating polynomial is not local. Changing a point at the
beginning of the spline affects the entire spline. Cardinal splines are local:
any place on the spline is affected by its four neighboring points at most.
• Evaluation of the interpolating polynomial is not local. Evaluating a point
on the polynomial requires access to all of its points. Evaluating a point
on the piecewise cubic requires a fixed small number of computations, no
matter how large the total number of points is.
There are a variety of other numerical and technical issues in using interpolating
splines as the number of points grows larger. See (De Boor, 2001) for more
information.
A cardinal spline has the disadvantage that it does not interpolate the first or
last point, which can be easily fixed by adding an extra point at either end of
i
i
i
i
i
i
i
i
15.6. Approximating Curves 365
Figure 15.9. Splines interpolating nine control points (marked with small crosses). The
thick gray line shows an interpolating polynomial. The thin, dark line shows a Catmull-Rom
spline. The latter is made of seven cubic segments, which are each shown in alternating
gray tones.
the sequence. The cardinal spline also is not as continuous—providing only C
1
continuity at the knots.
15.6 Approximating Curves
It might seem like the easiest way to control a curve is to specify a set of points
for it to interpolate. In practice, however, interpolation schemes often have unde-
sirable properties because they have less continuity and offer no control of what
happens between the points. Curve schemes that only approximate the points are
often preferred. With an approximating scheme, the control points influence the
shape of the curve, but do not specify it exactly. Although we give up the ability
to directly specify points for the curve to pass through, we gain better behavior
of the curve and local control. Should we need to interpolate a set of points, the
positions of the control points can be computed such that the curve passes through
these interpolation points.
The two most important types of approximating curves in computer graphics
are B´ezier curves and B-spline curves.
15.6.1 Bézier Curves
B´ezier curves are one of the most common representations for free-form curves
in computer graphics. The curves are named for Pierre B´ezier, one of the people
who was instrumental in their development. B´ezier curves have an interesting
history where they were concurrently developed by several independent groups.
AB´ezier curve is a polynomial curve that approximates its control points. The
curves can be a polynomial of any degree. A curve of degree d is controlled by
i
i
i
i
i
i
i
i
366 15. Curves
d +1control points. The curve interpolates its first and last control points, and
the shape is directly influenced by the other points.
Often, complex shapes are made by connecting a number of B´ezier curves of
low degree, and in computer graphics, cubic (d =3)B´ezier curves are commonly
used for this purpose. Many popular illustration programs, such as Adobe Illus-
trator, and font representation schemes, such as that used in Postscript, use cubic
B´ezier curves. B´ezier curves are extremely popular in computer graphics because
they are easy to control, have a number of useful properties, and there are very
efficient algorithms for working with them.
B´ezier curves are constructed such that:
• The curve interpolates the first and last control points, with u =0and 1,
respectively.
• The first derivative of the curve at its beginning (end) is determined by the
vector between the first and second (next to last and last) control points.
The derivatives are given by the vectors between these points scaled by the
degree of the curve.
• Higher derivatives at the beginning (end) of the curve depend on the points
at the beginning (end) of the curve. The n
th
derivative depends on the first
(last) n +1points.
For example, consider the B´ezier curve of degree 3 as in Figure 15.10. The
curve has four (d +1) control points. It begins at the first control point (p
0
)
and ends at the last (p
1
). The first derivative at the beginning is proportional to
the vector between the first and second control points (p
1
− p
0
). Specifically,
f
(0) = 3(p
1
− p
0
). Similarly, the first derivative at the end of the curve is given
p0
p1
p2
p3
p1-
p
0
p3
-p2
f’(0)=3(p1-p0)
f’(1)=3(p3-p2)
Figure 15.10. A cubic Bézier curve is controlled by four points. It interpolates the first and
last, and the beginning and final derivatives are three times the vectors between the first two
(or last two) points.
i
i
i
i
i
i
i
i
15.6. Approximating Curves 367
by f
(1) = 3(p
3
− p
2
). The second derivative at the beginning of the curve can
be determined from control points p
0
, p
1
and p
2
.
Using the facts about B´ezier cubics in the preceding paragraph, we can use the
methods of Section 15.5 to create a parametric function for them. The definitions
of the beginning and end interpolation and derivatives give
p
0
= f(0) = a
3
0
3
+ a
2
0
2
+ a
1
0+a
0
,
p
3
= f(1) = a
3
1
3
+ a
2
1
2
+ a
1
1+a
0
,
3(p
1
− p
0
)= f
(0) = 3a
3
0
2
+2a
2
0+a
1
,
3(p
3
− p
2
)= f
(1) = 3a
3
1
2
+2a
2
1+a
1
.
This can be solved for the basis matrix
B = C
−1
=
⎡
⎢
⎢
⎣
1000
−3300
3 −630
−13−31
⎤
⎥
⎥
⎦
,
and then written as
f(u)=(1−3u +3u
2
−u
3
)p
0
+(3u −6u
2
+3u
3
)p
1
+(3u
2
−3u
3
)p
2
+(u
3
)p
3
,
or
f(u)=
d
i=0
b
i,3
p
i
,
where the b
i,3
are the B´ezier blending functions of degree 3:
b
0,3
=(1− u)
3
,
b
1,3
=3u(1 − u)
2
,
b
2,3
=3u
2
(1 − u),
b
3,3
= u
3
.
Fortunately, the blending functions for B´ezier curves have a special form that
works for all degrees. These functions are known as the Bernstein basis polyno-
mials and have the general form
b
k,n
(u)=C(n, k) u
k
(1 − u)
(n−k)
,
where n is the order of the B´ezier curve, and k is the blending function number
between 0 and n (inclusive). C(n, k) are the binomial coefficients:
C(n, k)=
n!
k!(n − k)!
.
i
i
i
i
i
i
i
i
368 15. Curves
Figure 15.11. Various Bézier segments of degree 2–6. The control points are shown with
crosses, and the control polygons (line segments connecting the control points) are also
shown.
Given the positions of the control points p
k
, the function to evaluate the B´ezier
curve of order n (with n +1control points) is
p(u)=
n
k=0
p
k
C(n, k) u
k
(1 − u)
(n−k)
.
Some B´ezier segments are shown in Figure 15.11.
B´ezier segments have several useful properties:
• The curve is bounded by the convex hull of the control points.
• Any line intersects the curve no more times than it intersects the set of
line segments connecting the control points. This is called the variation
diminishing property. This property is illustrated in Figure 15.12.
• The curves are symmetric: reversing the order of the control points yields
the same curve, with a reversed parameterization.
• The curves are affine invariant. This means that translating, scaling, rotat-
ing, or skewing the control points is the same as performing those opera-
tions on the curve itself.
• There are good simple algorithms for evaluating and subdividing B´ezier
curves into pieces that are themselves B´ezier curves. Because subdivision
can be done effectively using the algorithm described later, a divide and
conquer approach can be used to create effective algorithms for important
tasks such as rendering B´ezier curves, approximating them with line seg-
ments, and determining the intersection between two curves.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.