One of the
simplest procedural geometry forms that everyone should be familiar with
are lines. Given the two end points of a line segment, any desired number
of intermediate points can be generated using the line equation. It is
possible to store a large number of points that are located on the line
instead, but we all know that would be silly. However, it does illustrate
some of the problems of static geometry. Instead of storing just two points,
a large number of points would need to be stored. Also, these points would
be targeted for a specific resolution. If the resolution is reduced, redundant
points exist, and if the resolution is increased, gaps in the line will
appear. It is apparent that the procedural form is preferred.
Let's examine
lines to help us develop a notation that will be useful to us later. The
equation below shows the parametric form of the line equation.
t
is the parameterized value ranging between 0 and 1 inclusive and P_{0}
and P_{1} are the line's endpoints. When t is 0,
the equation returns P_{0} and when t is 1, the
equation returns P_{1}. This equation can be rewritten
as follows.
Where:
We will
call B_{0}(t)and B_{1}(t) the basis functions
of the parametric line equation. They are sometimes also called blending
functions, because they define how the two endpoints are blended to get
the value for the line at t. The line equation can be further rewritten
compactly as:
This is
the analytical version of the parametric line equation. Most descriptions
of parametric curves will be presented using this form. Yes, lines are
curves, just very straight ones.
Developing
Bézier Curves
How might
we come up with a parametric form for a curve using notation similar to
above? We would like to describe a curve that passes through its endpoints
and curves towards a third point. Figure
2 shows a possible setup where P_{0} and P_{2}
are the endpoints of the curve and P_{1} is the point to
approach. A line segment can be defined where one endpoint, P_{a}(t),
is interpolated from P_{0} to P_{1} and
its other endpoint, P_{b}(t), is interpolated from P_{1}
to P_{2}. This is shown in Figure
3. The desired point on the curve can then be found by interpolating
between P_{a}(t) and P_{b}(t). This formulation
is developed in the equations below.
Figure
4 shows the curve that is generated when t goes from 0 to 1.
Using the
notation we developed for the line, this becomes:
Where B_{0},
B_{1}, and B_{2} are the basis functions
shown below:
Some features
to note about this curve formulation: the curve passes through the endpoints,
the line segment from P_{0} to P_{1} is
tangent to the curve at P_{0}, and the line segment from
P_{1} to P_{2} is tangent to the curve at
P_{2}. This leads to a very intuitive description of a
curve and is easy for artists to manipulate. Another aspect of this curve
is that it is contained in the convex hull of its control points. The
convex hull can be thought of as the polygon that would be formed by stretching
a rubber band around the control points. This property can be used for
rough hit detection or similar things.
Well, what
we have done is develop the definition of a quadratic Bézier curve.
This geometric interpretation of the Bézier curve is attributed
to de Casteljau. It can be thought of as a generalization of the parametric
line equation. If we would like to develop a Bézier curve of a
higher degree, the process used above of interpolating new line segments
can be applied recursively. When this is done, the basis functions can
be defined as follows, where n is the degree and i is which
basis function from 0 to n :
These are
known as the Bernstein polynomials. If n is 2, this generates the
basis functions for the quadratic Bézier curve that we discovered
earlier. Interestingly, when n is 1, this generates the blending
functions for the parametric line equation, further reinforcing that the
Bézier curve can be thought of as the generalization of a line
to higher orders. Typically, quadratic (n = 2) or cubic (n = 3) curves
are used. Quadratic curves are easier to calculate and require fewer control
points while cubic curves allow for a wider variety of curves at a higher
computational cost. Figure 5 shows an example
of each type of curve. For the rest of this article, I am going to restrict
the discussion to the quadratic forms, but everything can be extended
to higher degree curves, though cubic is the highest order ever used in
practice.

Figure
5: Quadratic and cubic curves. Quadratics are easier to calculate
(i.e. faster to render). 