 The magazine of the Melbourne PC User Group Behind Bézier Robin Blair |
In April and May 1999, PC Update carried an article by Ken Holmes, "Build a Bézier Boat" (http://www.melbpc.org.au/pcupdate/9904/9904article7.htm and http://www.melbpc.org.au/pcupdate/9905/9905article11.htm ), and in November 2000, another by Myles Straus, "Spline Fever" (http://www.melbpc.org.au/pcupdate/2011/2011article16.htm). Both referred to Bézier curves - mysterious objects, but obviously capable of generating graphics of great beauty, and possibly very useful to those of us who write our own home-brewed graphics programs for various purposes. The mathematics behind these curves would surely be totally opaque to mere mortals, but maybe not, and inspired by Ken and Myles' applications, I set out on a little research. In the spirit of "members helping members" here's a summary of what I found. The maths is really quite simple, I promise.
The Inventor
Pierre Bézier invented the curves while working for the Renault motor company in early 1970. He is said to have used the curves to design body panels, and in particular, exhaust systems for Renault cars. Anyone who has owned a Renault 16 would doubtlessly attest to their probable usefulness in this latter application. This story may be true, but what Pierre had found was really a new tool to add to an existing toolbox which already contained quite a few methods for drawing smooth curves.
Bézier curves fall into a larger class of techniques known as "splines" and are accordingly often referred to as Bézier splines. In days not too long ago, when a draftsman had to draw a smooth curve through a series of points he used a drawing accessory known as a spline.
A spline was something like a flexible ruler. It usually consisted of a metal backbone enclosed in a plastic sheath. The backbone would comprise a rod of lead, or a stack of copper or aluminium strips, such that it could be bent fairly easily and would then retain the bent shape. The plastic sheath incorporated a drawing edge to guide a pen or pencil in drawing the curve defined by the bent shape of the spline. Nowadays, mechanical splines have gone the way of the slide-rule in the face of advancing computerisation.
Like their mechanical predecessors, mathematical splines are used to draw smooth curves through a series of disparate points in a process generally known as "curve fitting". The simplest process has usually been to fit these points to a polynomial equation of a form like the following:
y = ax3 +bx2+cx +d
where x and y are the screen coordinates of all the points on the line, and only a few are known beforehand. It is the job of the programmer to provide a means of calculating the values of a, b, c, and d from the coordinates of the few known points. A simple line drawing algorithm then draws what looks like a continuous curve by drawing straight line segments between closely spaced pairs of (x,y) values.
As we shall see, this method has very limited application in practice. However, it does allow the simple illustration of two features that we will need to refer to later. The first is that these equations can become very complex if we try to fit them to too many points. Notice that the equation above has only four variables, a, b, c, and d. A fundamental theory of algebra says that we can fit that equation to no more than four points - this sounds plausible in that it should take more information to define a set of points as the number of points in the set increases. Hence, attempting to fit a curve to more points requires more unknowns (and, evidently, greater powers of x in the equation). In addition to some other problems, this leads to great complexity, and it is usual to confine the curves to fit only small, or short, groups of points. Longer curves are drawn by joining these shorter curves end to end.
This joining end to end of shorter curves raises the second feature we must consider - that of continuity through the joins. Effectively, we want the join to be smooth, not discontinuous or cusped. If one thinks of a point travelling along the curve, this requirement means that the direction in which the point is travelling when it leaves one curve must be the same as it should be when the point enters the next curve. Thus, in two dimensional graphics, the slopes at the end of one curve must match that at the beginning of the next. In three dimensions, the tangents at the ends of the curves must match.
In summary, good mathematical splines fit segments to a limited number of points in each segment, and match the slopes at the ends of segments.}
Despite their simplicity, the polynomial equations just described find little application in engineering or general graphics programming. Principally, this is because one can have only one value of y for each value of x. Rather, curve fitting relies on what are called parametric equations, where both x and y are defined as functions of some third parameter, say u.
To avoid circumlocution about generalities, I will write these as they would appear for Bézier splines, and then explain the particular features.
The equations are:
p = p1(1-u)3 +h1(1-u) 2u+h2(1-u)u2+p2u3
for the four point spline, and
p = p1(1-u)2+h(1-u)u+p2u2
for the three point spline.
Here, p1 and p2 are the two end points of the spline and h1, h2, and h are other points commonly called the handles. Collectively, the "p"s and "h"s together are called "control points." Each point comprises an x and a y value (they are vectors in mathematical parlance). Hence, x or y can be found for any value of u by substituting into the above equations the values of x or y at each p and h.
Notice that in the above, if u = 0, p lies on p1, and if u =1, p lies on p2. Thus, by varying u in small increments from 0 to 1, and calculating x and y at each increment, a simple line drawing algorithm can draw a seemingly continuous curve from p1 to p2. The direction in which our putative moving point would be travelling as it enters the curve is directed from p1 to h1, and as it leaves, from h2 to p2, for the four point spline. These directions are from p1 to h and from h to p2 for the three point spline.
|
To see the end points and handles at work, draw a short curve in your favourite drawing (not painting) program with a "pen" or "freehand" tool. Now open up the curve for editing. You will probably have to use a menu item labelled "edit freeform" or similar. What you see should look something like Figure 1, where the little filled circles are the end points and the rectangles are the handles.
Figure 1 shows a shape made up of two Bézier spline segments joined end to end. For the first segment the end points are p1 and p2, and the handles are h1 and h2. For the second segment, the end points are p2 and p3, and the handles are h3 and h4. Note that where segments join smoothly, the two dashed lines joining end points and handles meet at an angle of zero degrees. Hence, the slopes, (or tangents) of the two segments coincide at these points. Drawing programs usually allow the user to manipulate the ends and the slopes by dragging the end points and the handles respectively with a mouse. There is a fast algorithm for drawing Bézier splines, known as the deCasteljau dividing formula. Figure 2 shows how this works for three point and four splines, and I will use the latter for illustration. The algorithm first finds point A, the mid-point between the two handles, and points B1 and B2, the mid-points between the end points and their associated handles. C1 and C2 come next, and the mid-point D between them is plotted as one point on the spline. The algorithm then divides the curve in two and repeats itself on the left and right hand sections. On the left, it takes P1 and D as the end points, and B1 and C1 as the handles, to plot a second point for the spline. Then, it finds a mirror point on the right using D, C2, B2 and P2 This subdividing of the curve may continue recursively until the points so plotted are no more than one pixel apart, giving a continuous line. Alternatively, a general straight line drawing algorithm might be called once a sufficient number of points are found to give an apparently smooth curve. |
|
Finding the mid-points is easy. The mid point (x3,y3) between two other points with co-ordinates (x1,y1) and (x2,y2) is simply given by
x3=(x1+x2)/2
and
y3=(y1+y2)/2
Most programming languages have a facility whereby this process can be handled as integer divisions, rather than a floating point operation. Hence, the algorithm tends to be quite fast in practice and because of its recursive nature, it is fairly easy to program.
Thus what's behind Bézier curves is really quite simple. They are very useful in artistic drawing, and less so for mathematical or engineering applications, since finding the handles in not always simple - although it can often be done with some cunning and ingenuity. In this context, formulae for Bézier curves are available for those having more than the three or four control points discussed here. The formulae generally take the form of the parametric equations described above, in (u) and(1-u). Again, however, the curves pass through only the end points, and the other points appear off the curve as handles - so they are not easy to fit through a series of points.
Reprinted from the September 2001 issue of PC Update, the magazine of Melbourne PC User Group, Australia
