Bezier curves is one of the simplest instances of a spline curve. The
general idea of a spline is that given n basis functions
Pi:R→R and n control points
vi∈R2, we define a parametric curve
x:[0,1]→R2 by letting x(t) =
ΣviPi(t). In order for the curve to interact
nicely with affine transforms, we usually want the basis functions to sum to
unity, that is Σ Pi(t) = 1 for all t∈[0,1].
The typical use is in CAD/CAM or vector-based illustration programs, where
the user will use a point-and click interface to place the control points,
and then interactively drag and drop them until the resulting curve looks
as it should.
Bezier curves where developed by Pierre Bezier at Renault in the late
1960s to be used in their early CAD/CAM software. In car design, there is an
obvious interest in having a simple way to specify smoothly bending curves.
(Interestingly, Paul de Casteljau at Citroen had already developed exactly
the same curves, but he was not allowed to publish by his company so the they
now bear Bezier's name).
The basis functions in Bezier curves are based of the formula in the
binomial theorem: (t+(1-t))n = Σ C(n,i)ti(1-t)n-i. The n-degree Bezier basis
functions are defined by Pn,i(t) =
C(n,i)ti(1-t)i (We will use the convention that C(n,i)=0
if i<0 or i>n). Thus the n-degree basis functions are a set of n+1 polynomials
of degree n. For example any four points can be used to specify a cubic
Bezier curve.
We can immediately see that the basis functions sum to one:
Pn,0(t) + Pn,1(t) + ... + Pn,n(t) =
((1-t)+t)n = 1n = 1. When t=0, Pn,1(t)=1 and
all the other functions are 0, so x(0) = v0. Likewise
x(1)=vn, so the defined curve begins at the first
control point and ends at the last one. Since the functions always sum to one,
the curve will be contained inside the convex hull of the control points. (In
more graphical terms, if you snap a rubber band around the control points, the
Bezier curve they define will be contained inside it).
We can also say something about the derivative. Differentiating term-wise, we
find x'(t) = -n(1-t)n-1v0 +
Σ{ C(n,i)(iti-1(1-t)n-i -
ti(n-i)(1-t)n-i-1)vi} +
ntn-1vn (where the summation ranges from i=1 to
i=n-1). In particular, x'(0) = n(v1 -
v0) and x'(1) = n(vn -
vn-1). So the direction and speed with which the curve leaves
the first control point is directly proportional to the vector from the first
to the second control point, and similarly it arrives at the last control point
with a direction and speed proportional to the vector between the next-to-last
and the last control point.
A cubic polynomial is specified completely by giving its value and derivate
at two points, so the four control points of a cubic Bezier curve provides a
very intuitive user interface: you specify the endpoints and the initial and
final direction of the curve, and the curve will smoothly interpolate between
them. At the same time, cubics are sufficiently rich to describe many curves
that are useful in practice (in particular, they can have a point of
inflexion) so degree-3 Beziers are a good compromise between usability and
expressivity, and are what are usually used.
To specify more complicated shapes, several cubic Beziers can be put after
each other. As long as the last control point of each curve coincides with the
first point of the following curve, the sequence will trace out a continuous
path. Furthermore, if the vector from the third to the forth point of one curve
is equal to the vector from the first to the second point of the next, the path
will as we have seen have a continuous derivative so it will look smooth. The
user interface of a design program will hide these details from the user.
Typically, one can enter a string of points that the path will interpolate
between, and then adjust the tangent of the curve at each of the points. By
designating a point as a "corner point", the program will drop the restriction
on the derivative, so one can make paths with e.g. sharp 90-degree corners.
Unfortunately there is no simple condition that ensures a continuous second
derivative, so for applications that require that, some more complicated kind of
spline is needed (e.g. NURBS or subdivision surfaces).
Yet another way of describing Bezier curves can be got by noting that the
basis functions satisfy the recurrence Pn,i(t) = t
Pn,i-1(t) + (1-t) Pn-1,i(t). (This follows from the
identity C(n,i) = C(n-1,i-1)+C(n-1,i)). So the n-degree basis functions are in
a sense linear interpolations of the (n-1)-degree ones. Given
control points v0, ..., vn, we can
construct the n-degree interpolating curve z(t) by first forming the
(n-1)-degree curves x(t) between v1 and
vn, and the (n-1)-degree curve y(t) between
v0 and vn-1, and then setting z(t) =
t x(t) + (1-t) y(t). Paul Cox[1] describes a nice
illustration of this idea. Consider drawing the quadratic Bezier between three
control points v0, v1,
v2. The linear Beziers x(t) and y(t) are of
course straight lines from v1 to v2 and
from v0 to v1. Now we can construct the
quadratic by first connecting the midpoints of x and y by a
straight line and marking the midpoint on it, then drawing a line between the
point a quarter along the way of x and a quarter along the way of
y and marking the point a quarter along the way of that line, etc. If
you look at the picture thus constructed, it looks very much like the pictures
we all drew in school using a ruler during boring art classes, or the
"sculptures" you get by tying strings between equidistant nails on a wooden
frame. Bezier curves are the mathematics of string art!
The same principle has a more directly useful application: it gives a way to
split Bezier curves. Consider a cubic Bezier curve x(t) between the
points q0, q1, q2,
q3 (drawing this with pen and paper will help). Now let
r0 = (q0+q1)/2, the point
halfway between q0 and q1, and similarly let
r1 = (q1+q2)/2,
r2 = (q2+q3)/2. Continue
this way and let
s0 = (r0+r1)/2,
s1 = (r1+r2)/2,
and finally let t = (s0+s1)/2.
The point t we have constructed in this way will lie on the curve; in
fact from the discussion in the previous paragraph it is clear than t =
x(1/2). Of course, had we instead split each line segment in thirds, we
would have obtained the point at x(1/3), etc. While not as obvious, it
is in fact the case that the cubic Bezier curve defined by the four points
q0, r0, s0, t will
coincide exactly with x([0, 0.5]). So we have taken our original
cubic Bezier curve, and split it into two segments with independent control
points. This is exactly what is needed in an interactive design program: the
user can first sketch out the rough shape of an object using a few curves, then
introduce extra control points on the curve where more detail is needed and
make adjustments without disturbing the rest of the shape.
Another use for this subdivision scheme is as an efficient algorithm for
rendering Bezier curves using line segments. As we split the curve, the control
points get closer and closer to the curve proper. Eventually they will be less
than a pixel away from it, which means that we can safely approximate the curve
with a single line segment from the first to the last control point. So to
render a curve we can use the following procedure: first check if it is flat
enough, if so draw a single line segment, otherwise split it in two and
recursively render those. This is known as de Casteljau's algorithm.
Of course, when designing cars what we really want is smooth surfaces rather
than just curves. Fortunately splines generalise nicely. Given (n+1)*(n+1)
control points vi,j∈R3 we define a
parametric Bezier patch
x:[0,1]×[0,1]→R3 by
x(t,u) =
Σ vi,jPn,i(t)Pn,j(u) (where
the summation ranges over both i and j). This deforms the unit square into a
curved patch with sides given by the one-dimensional Bezier curves
between the "border" control points. Bezier patches can also be rendered using
subdivision, although one must take some care with the "topology" of the
subdivided mesh to avoid creating a surface with small gaps in it.
Currently, the main application of Bezier curves is in vector-based 2D
illustration programs like Adobe Illustrator, and in describing scalable
fonts. Both TrueType and PostScript fonts are specified in terms of
Bezier curves. In CAD/CAM applications they have been replaced with the more
general NURBS (which give Bezier curves as a special case), and 3D-graphics
programs that only generate pretty pictures have generally moved to
subdivision surfaces.
References:
Paul Cox. "The Mathematics of String Art: A Tribute to Pierre Bezier
(1910-1999)". http://members.cox.net/mathmistakes/bezier.htm