i
i
i
i
i
i
i
i
15.6. Approximating Curves 369
Figure 15.12. The
variation diminishing
property of Bézier curves means that the curve
does not cross a line more than its control polygon does. Therefore, if the control polygon
has no “wiggles,” the curve will not have them either. B-splines (Section 15.6.2) also have
this property.
When B´ezier segments are connected together to make a spline, connectivity be-
tween the segments is created by sharing the endpoints. However, continuity
of the derivatives must be created by positioning the other control points. This
provides the user of a B´ezier spline with control over the smoothness. For G
1
continuity, the second-to-last point of the first curve and the second point of the
Figure 15.13. Two B ézier
segments connect to form
a
C
1
spline, because the
vector between the last two
points of the first segment
is equal to the vector be-
tween the first two points of
the second segment.
second curve must be collinear with the equated endpoints. For C
1
continu-
ity, the distances between the points must be equal as well. This is illustrated
in Figure 15.13. Higher degrees of continuity can be created by properly posi-
tioning more points.
Geometric Intuition for Bezier Curves
B´ezier curves can be derived from geometric principles, as well as from the alge-
braic methods described above. We outline the geometric principles because they
provides intuition on how B´ezier curves work.
Imagine that we have a set of control points from which we want to create
a smooth curve. Simply connecting the points with lines (to form the control
polygon)will lead to something that is non-smooth. It will have sharp corners. We
could imagine “smoothing” this polygon by cutting off the sharp corners, yielding
a new polygon that is smoother, but still not “smooth” in the mathematical sense
(since the curve is still a polygon, and therefore only C
1
. We can repeat this
process, each time yielding a smoother polygon, as shown in Figure 15.14. In the
limit, that is if we repeated the process infinitely many times, we would obtain a
C
1
smooth curve.
What we have done with corner cutting is defining a subdivision scheme. That
is, we have defined curves by a process for breaking a simpler curve into smaller
pieces (e.g., subdividing it). The resulting curve is the limit curve that is achieved
i
i
i
i
i
i
i
i
370 15. Curves
Figure 15.14. Subdivision procedure for quadratic Béziers. Each line segment is divided in
half and these midpoints are connected (gray points and lines). The interior control point is
moved to the midpoint of the new line segment (white circle).
by applying the process infinitely many times. If the subdivision scheme is de-
fined correctly, the result will be a smooth curve, and it will have a parametric
form.
Let us consider applying corner cutting to a single corner. Given three points
(p
0
, p
1
, p
2
), we repeatedly “cut off the corners” as shown in Figure 15.15. At
each step, we divide each line segment in half, connect the midpoints, and then
move the corner point to the midpoint of the new line segment. Note that in this
process, new points are introduced, moved once, and then remain in this position
for any remaining iterations. The endpoints never move.
If we compute the “new” position for p
2
as the midpoint of the midpoints, we
get the expression
p
2
=
1
2
(
1
2
p
0
+
1
2
p
1
)+
1
2
(
1
2
p
1
+
1
2
p
2
).
The construction actually works for other proportions of distance along each
segment. If we let u be the distance between the beginning and the end of each
cut
Figure 15.15. By repeatedly cutting the corners off a polygon, we approach a smooth curve.
i
i
i
i
i
i
i
i
15.6. Approximating Curves 371
segment where we place the middle point, we can re-write this expression as
p(u)=(1− u)((1 −u)p
0
+ up
1
)+u((1 − u)p
1
+ up
2
).
Regrouping terms gives the quadratic B´ezier function:
B
2
(u)=(1− u)
2
p
0
+2u(1 − u)p
1
+ u
2
p
2
.
The De Casteljau Algorithm
OnenicefeatureofB´ezier curves is that there is a very simple and general method
for computing and subdividing them. The method, called the de Casteljau algo-
rithm, uses a sequence of linear interpolations to compute the positions along the
B´ezier curve of arbitrary order. It is the generalization of the subdivision scheme
described in the previous section.
The de Casteljau algorithm begins by connecting every adjacent set of points
with lines, and finding the point on these lines that is the u interpolation, giving a
set of n−1 points. These points are then connected with straight lines, those lines
are interpolated (again by u), giving a set of n −2 points. This process is repeated
until there is one point. An illustration of this process is shown in Figure 15.16.
The process of computing a point on a B´ezier segment also provides a method
for dividing the segment at the point. The intermediate points computed during
the de Casteljau algorithm form the new control points of the new, smaller seg-
ments, as shown in Figure 15.17.
The existence of a good algorithm for dividing B´ezier curves makes divide-
and-conquer algorithms possible. For example, when drawing a B´ezier curve
segment, it is easy to check if the curve is close to being a straight line because it is
bounded by its convex hull. If the control points of the curve are all close to being
co-linear, the curve can be drawn as a straight line. Otherwise, the curve can be
1
23
4 1
23
4
Figure 15.16. An illustration of the de Casteljau algorithm for a cubic Bézier. The left-hand
image shows the construction for
u
=0.5. The right-hand image shows the construction for
0.25, 0.5, and 0.75.
i
i
i
i
i
i
i
i
372 15. Curves
A
BC
D
CDAB
BC
AC BDAD
Figure 15.17. The de Casteljau algorithm is used to subdivide a cubic Bézier segment.
The initial points (black diamonds A, B, C, and D) are linearly interpolated to yield gray circles
(AB, BC, CD), which are linearly interpolated to yield white circles (AC, BD), which are linearly
interpolated to give the point on the cubic AD. This process also has subdivided the Bézier
segment with control points A,B,C,D into two Bézier segments with control points A, AB, AC,
AD and AD, BD, CD, D.
divided into smaller pieces, and the process can be repeated. Similar algorithms
can be used for determining the intersection between two curves. Because of the
existence of such algorithms, other curve representations are often converted to
B´ezier form for processing.
15.6.2 B-splines
B-splines provide a method for approximating a set of n points with a curve made
up of polynomials of degree d that gives C
(d−1)
continuity. Unlike the B´ezier
splines of the previous section, B-splines allow curves to be generated for any
desired degree of continuity (almost up to the number of points). Because of
this, B-splines are a preferred way to specify very smooth curves (high degrees
of continuity) in computer graphics. If we want a C
2
or higher curve through an
arbitrary number of points, B-splines are probably the right method.
We can represent a curve using a linear combination of B-spline basis func-
tions. Since these basis functions are themselves splines, we call them basis
splines or B-splines for short. Each B-spline or basis function is made up of a
set of d +1polynomials each of degree d. The methods of B-splines provide
general procedures for defining these functions.
The term B-spline specifically refers to one of the basis functions, not the
function created by the linear combination of a set of B-splines. However, there
is inconsistency in how the term is used in computer graphics. Commonly, a “B-
spline curve” is used to mean a curve represented by the linear combination of
B-splines.
The idea of representing a polynomial as the linear combination of other poly-
nomials has been discussed in Section 15.3.1 and 15.3.5. Representing a spline
i
i
i
i
i
i
i
i
15.6. Approximating Curves 373
as a linear combination of other splines was shown in Section 15.4.1. In fact, the
example given is a simple case of a B-spline.
The general notation for representing a function as a linear combination of
other functions is
f(t)=
n
i=1
p
i
b
i
(t), (15.15)
where the p
i
are the coefficients and the b
i
are the basis functions. If the coeffi-
cients are points (e.g. 2 or 3 vectors), we refer to them as control points. The key
to making such a method work is to define the b
i
appropriately. B-splines provide
a very general way to do this.
A set of B-splines can be defined for a number of coefficients n and a param-
eter value k.
3
The value of k is one more than the degree of the polynomials used
to make the B-splines (k = d +1.)
B-splines are important because they provide a very general method for cre-
ating functions (that will be useful for representing curves) that have a number
of useful properties. A curve with n points made with B-splines with parameter
value k:
• is C
(k−2)
continuous;
• is made of polynomials of degree k − 1;
• has local control—any site on the curve only depends on k of the control
points;
• is bounded by the convex hull of the points;
• exhibits the variation diminishing property illustrated in Figure 15.12.
A curve created using B-splines does not necessarily interpolate its control points.
We will introduce B-splines by first looking at a specific, simple case to in-
troduce the concepts. We will then generalize the methods and show why they
are interesting. Because the method for computing B-splines is very general, we
delay introducing it until we have shown what these generalizations are.
3
The B-spline parameter is actually the order of the polynomials used in the B-splines. While this
terminology is not uniform in the literature, the use of the B-spline parameter k as a value one greater
than the polynomial degree is widely used, although some texts (see the chapter notes) write all of the
equations in terms of polynomial degree.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.