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 P0 and P1 are the line's endpoints. When t is 0, the equation returns P0 and when t is 1, the equation returns P1. This equation can be rewritten as follows.
We will call B0(t)and B1(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 P0 and P2 are the endpoints of the curve and P1 is the point to approach. A line segment can be defined where one endpoint, Pa(t), is interpolated from P0 to P1 and its other endpoint, Pb(t), is interpolated from P1 to P2. This is shown in Figure 3. The desired point on the curve can then be found by interpolating between Pa(t) and Pb(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 B0, B1, and B2 are the basis functions shown below:
Some features to note about this curve formulation: the curve passes through the endpoints, the line segment from P0 to P1 is tangent to the curve at P0, and the line segment from P1 to P2 is tangent to the curve at P2. 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).|