Academic Articles & Supplements

Programming Tips: Bézier Curves

Stan Wagon

Author

Stan Wagon

Title

Programming Tips: Bézier Curves

Description

Creating curvy pointers and other objects where natural and easily modifiable curves are sought.

Programming Tips

Mathematica in Education and Research
Vol.4 No.1

Bezier Curves

Creating curvy pointers and other objects where natural and easily modifiable curves are sought.

by Stan Wagon, Macalester College wagon@macalstr.edu

Bezier Curves

While it is possible to move Mathematica graphics to a drawing program and perform various enhancements, life is much simpler if one can work entirely within Mathematica. In this column I will show how to make slinky curves of the sort that many of you will be familiar with from the Bezier curve tool in drawing programs.

While the traditional home of Bezier curves in the undergraduate curriculum is in computer graphics courses, I have always discussed them in numerical analysis, where it is illuminating to compare them to other methods of interpolation, such as splines or polynomial interpolation. These curves are essentially a type of efficient image compression (for example, laser printers use Bezier curves to form the shapes in each letter that they print) and I think that undergraduates not specializing in computer graphics should be exposed to them. Even if you are not a mathematician, they can be useful to you by allowing stylish annotations of diverse types of Mathematica graphics output. To explain what they are and why they work, we will focus first on the case of 4 control points, where the resulting curve is a BÎzier cubic. And let us first consider the one-dimensional problem. A BÎzier curve is simply a linear combination of Bernstein polynomials. The code that follows produces the Bernstein polynomials for the case at hand. Their general definition is Bin(t) = Binomial[n, i] (1 — t)n—i ti. We will use t throughout as the independent variable, so we do not list it as an argument to Bernstein[]. In the definition of Bernstein[n] that follows we define (1 — t)n and tn as special cases, thus avoiding 0^0 errors that would be generated later (if t is 0 or 1, as it will be in a plot).

In[1]:=

Clear[t];
Bernstein[i_, n_] := Binomial[n, i] t^i (1-t)^(n-i)

Bernstein[n_] := Append[Prepend[
Table[Bernstein[i, n], {i, n-1}], (1-t)^n], t^n]

Bernstein[n_] := Table[Bernstein[i, n], {i, 0, n}]
Bernstein[3]

Out[1]=

The folowing code, with n set to 3 and then 7, generates the graphs of the Bernstein polynomials shown in Figure 1.

In[2]:=

n = 3;
Plot[Evaluate[Bernstein[n]], {t, 0, 1},
Epilog -> {AbsolutePointSize[5],
Table[
Point[{i/n, Bernstein[i, n] /. t->i/n}],
{i, 0, n}]}];

Figure 1. The Bernstein polynomials (the n = 3 family at left, n = 7 at right) have the property that their maxima are uniformly distributed on the unit interval.

The main point to notice is that B03 dominates the scene around t = 0, B13 does the same around t = 1/3 (though to a lesser extent), B23 dominates the region around 2/3, and B33 dominates the region near t = 1. Analogous behavior holds for the higher-degree Bernstein polynomials. Now, suppose we have 4 numbers a, b, c, and d, which we call the control coefficients. A linear combination a B03(t) + b B13(t) + c B23(t) + d B33(t) will yield a function whose values at 0 and 1 are exactly a and d, respectively, and whose values at 1/3 and 2/3 are near b and c, respectively. For example:

In[3]:=

{0.7, 40, 200, -10} . Bernstein[3] /. t -> {0., 1/3, 2/3, 1}

Out[3]=

The two central values do not seem particularly close to the central control coefficients. But the important point about this construction is that if, say, c is made a little larger, the linear combination will become a little larger in the region where c has control (near 2/3). It is this behavior that is the key to the intuitive editing of BÎzier curves.

To turn this simple idea into a 2-dimensional drawing tool, we replace the control coefficients with four control points, Pi = (xi, yi), and consider the parametric curve P0 B03(t) + P1 B13(t) + P2 B23(t) + P3 B33(t). In other words, we use the linear combination idea in the x- and y-directions simultaneously. Then we get a parametric curve and changing the control points changes the shape of the curve in the direction of the change. It is this feature that makes editing a drawing program's BÎzier curve with a mouse so natural. If, say, Lagrange interpolation were used on the control points, the results of an editing change might be totally unpredictable.

Here is a function that produces the algebraic form of a BÎzier curve using n points. By remembering to use the dot product we save both computing time and programming effort.

In[4]:=

Bezier[pts_] := Bernstein[Length[pts] - 1] . pts

Bezier[{{1, 2}, {3, 4}, {5, 6}, {7, 8}}]

Out[4]=

Bezier returns a function of t and we can use ParametricPlot to see the curve. The BezierCurve code that follows defines a general routine (it requires Bezier and Bernstein) that allows us the option of seeing the control points, an important feature for editing. For by selecting the graphic and holding down the command key (or control key), we can choose new points and regenerate the curve with the new points until its shape is as desired. Figure 2 illustrates the central BÎzier property: moving the second control point up and left yields a more pronounced bump in the northwest direction. One small annoyance: the code as written will produce a plot range that stops at the centers of the points near the boundary, thus cutting off half of some of the points. Figure 2 was generated by a manual setting of the plot range.

In[5]:=

Options[BezierCurve] = {ShowPoints->False};

BezierCurve[pts_, opts___] := Module[{
showpoints = ShowPoints /. {opts} /. Options[BezierCurve]},
ParametricPlot[Evaluate[Bezier[pts]], {t, 0, 1},
PlotStyle->AbsolutePointSize[1], PlotRange->All,
Epilog->If[showpoints, {AbsolutePointSize[5], Point /@ pts}, {}] ]]

In[6]:=

BezierCurve[{{0, 0.2}, {2.6, 2.7}, {7, 0.2}, {10, 2}},
ShowPoints->True];

In[7]:=

BezierCurve[{{0, 0.2}, {-5, 4.7}, {7, 0.2}, {10, 2}},
ShowPoints->True];

Figure 2. Moving a control point drags the BÎzier curve in the direction of the motion; this is the key to the intuitive use of control points to fine-tune the shape of a curve.

It is clear from the construction that the BÎzier curve always passes right through the first and last control points. Less obvious, but equally useful to the computer artist, is the fact that for an n-point BÎzier curve the line from P0 to P1 is tangent to the curve at P0, and similarly for Pn-1 and Pn—2. (Exercise: Use Mathematica to prove this.) Also the curve lies in the convex hull of the control points. And most important, there is a recursive approach to the drawing of these curves that allow for very fast drawing, as opposed to the parametric plotting we use here; such speed is critical since this one wants real-time viewing when using editing in a drawing program, and also because these curves are used billions of time a day: each time a letter is printed on a laser printer, a BÎzier curve algorithm is called to form the shape of the letter.

The Ace of Spades

I recently wished to program a routine whose output involved cards from a standard deck. Bezier curves provide a quick way of generating the pip-shapes. To get a spade, we work on the left half only, and break it into two pieces, so as to easily get the sharp angle. The first piece is almost a straight line and requires only three control points. The second piece can be gotten with nine control points. The control points are obtained by generating a blank rectangle and clicking on it in the rough shape of the desired curve.

In[1]:=

SpadePlot1 = BezierCurve[
p1 = {{-0.144, -0.830}, {-0.069, -0.588}, {-0.037, -0.253}}];

SpadePlot2 = BezierCurve[
p2 = {{-0.060, -0.240}, {-0.233, -0.444},
{-0.498, -0.430}, {-0.712, -0.156}, {-0.637, 0.160},
{-0.423, 0.462}, {-0.149, 0.630}, {-0.056, 0.756},
{0, 0.853}}];

Show[SpadePlot1, SpadePlot2,
Graphics[{AbsolutePointSize[5], Point /@ Join[p1, p2]}],
AspectRatio->Automatic];

(a) (b)

Figure 3(a). The two pieces of the left-side of a spade, with the control points shown for ease of editing.
(b). Flipping and reversing the left side yields the full spade, which bears a passing resemblance to an actual card's spade pip. The fact that this smooth curve is generated from only about a dozen data points brings out the efficiency of using BÎzier curves.

We can now get at the actual points used in these two plots by using a trick described in my column on parametric plotting in the previous issue: if p is a plot or parametric plot then p[[1, -1, 1, 1]] contains the actual points that define the plot. For our spade we wish to get these points and then flip them around the y-axis and join the reverse of the flipped list to the original list. We do the flipping by multiplying each point by {—1, 1}. The result of the following code is Figure 3(b).

In[2]:=

SpadePoints = Module[{LeftSide},
LeftSide = Join[SpadePlot1[[1,-1,1,1]], SpadePlot2[[1,-1,1,1]]];
Join[LeftSide, Reverse[Map[{-1, 1} * # &, LeftSide]]]];

Show[Graphics[Polygon[SpadePoints]], AspectRatio->Automatic];

A 3-D Annotation Example

Our next application is the use of a BÎzier curve as a 2-dimensional pointer in a 3-dimensional graphic. The code that follows generates an image of a standard saddle (x2 — y2) together with some superimposed lines. To ensure that the lines are not partially hidden from view under the flat surface patches, they are raised by 0.04.

In[1]:=

surface = Plot3D[x^2 - y^2, {x, -2, 2}, {y, -2,2},
ColorOutput->GrayLevel, Boxed->False,
DisplayFunction->Identity, PlotPoints->11];

lines = Graphics3D[{AbsolutePointSize[8], AbsoluteThickness[2],
Point[{0,0,0}],
Line[Table[{x, 0, x^2 + 0.04}, {x, -2, 2, 4/11}]],
Line[Table[{0, y, -y^2 + 0.04}, {y, -2, 2, 4/11}]] }];

surfaceAndLines = Show[{surface, lines},
DisplayFunction->$DisplayFunction, AxesLabel->{"x", "y", None}];

In[2]:=

Show[surfaceAndLines]

(a)

(b)Figure 4(a). A surface with lines and a point added to highlight the saddle. (b). A label has been added using a 2-dimensional BÎzier curve.

Now, suppose our goal is the annotated surface as shown in Figure 4(b). We can use the 2-dimensional BÎzier tool we have defined to generate the curvy pointer. We choose 6 control points by selecting the surface graphic and clicking, which produces 2-dimensional coordinates.

In[3]:=

pointer = BezierCurve[{{0.665983, 0.761895}, {0.826821, 0.710372},
{0.706555, 0.653863}, {0.538472, 0.650539},
{0.490656, 0.555802}, {0.492105, 0.527548}}, ShowPoints->True];

Figure 5. The curve that will be used as a pointer, together with its six defining control points.

We can edit the curve until it is just right. To superimpose the curve and the surface, it is simplest to use the Epilog option, which causes a 2-dimensional graphics object to superimpose on a 3-dimensional image. Because Epilog wants graphics primitives, we must preprocess pointer. Since pointer looks like Graphics[graphics primitives, options], First[pointer] will produce the graphics primitives we need. Note that the control points lie in the Epilog option to pointer, and so they are removed by this process. It would be easy to add a little black arrow to the end of the pointer by adding a Polygon object to the Epilog list; we leave this as an exercise. And while for this example a user might be perfectly happy with a straight line pointer, which would avoid all the BÎzier machinery under discussion, there are times when more curviness is required; that will be where BezierCurve is most appropriate.

In[4]:=

Show[surfaceAndLines, Epilog->{
First[pointer], Text["Saddle point", {0.65, 0.76}, {+1,0}]},
DefaultFont->{"Courier", 9}];

The Sherlock Holmes Bicycle Problem

A second example of the use of Bezier curves arises from a fascinating, but troubling, Sherlock Holmes episode. Imagine a mud patch through which a bicycle has just passed, with its front and rear tires leaving distinct tracks (as in Figure 6). How can one determine the direction in which the bicyclist was travelling? Readers ought to stop now and ponder this question, because we will have to give away the solution in order to demonstrate the relevance of BÎzier curves. We point out that Sir Arthur Conan Doyle has let us down badly in this matter since the solution he attributes to Holmes in the detective's adventure at the Priory School is terribly wrong (the error was discovered by D. Thron of the Dartmouth Medical School); a fuller discussion of this problem will appear in the problem book, Which Way Did the Bicycle Go?, by J. Konhauser, D. Velleman, and S. Wagon (to be published by the MAA).

In order to get a realistic computer-generated image of the bicycle tracks, one must make the following key observation: the tangent to the rear wheel's path, in the direction of travel, strikes the front wheel's path so that the resulting segment has constant length. This solves the problem as posed (just check which of the possibilities yields constant-length tangent segments) and tells us how to construct the tracks: generate a curve to represent the rear track, and then use differentiation to generate the front track. BÎzier curves provide an easy way of generating the rear track; and since such curves are easily differentiated, the front track can be quickly defined from the rear track. More precisely, if g, an expression in t, generates the rear track, then
g + direction * 1.5 * unit[D[g, t]] gives the front track, where unit[] gives unit vectors, direction indicates the direction of travel (–1), and 1.5 is the constant length of the tangent segments. The beauty of using BÎzier curves is that one can generate and edit curves until one has one that looks realistic. It would be very difficult to guess at combinations of sines and/or polynomials to generate the desired curve. Here is the code that generates the tracks. Figure 6 shows the result, with the same rear track, but with the two front tracks corresponding to the two possible directions. Note the complexity of this computation: the expression g˚+ unit[D[g, t]] * 1.5 takes over 33 lines to display on a computer screen.

In[1]:=

pts = {{0.69, 3.93}, {1.4, 4.45}, {2.27, 4.76}, {2.8, 4.45}, {2.95, 3.87}, {3.64, 3.22}, {4.67, 2.87}, {5.73, 3.35}, {6.86, 4.21}, {8.06, 5.07}, {9.06, 4.93}, {10.16, 4.0}, {11.05, 3.18}, {11.7, 2.9}};g = Evaluate[Bezier[pts]];backPlot = BezierCurve[pts];unit[v_] := v/Sqrt[v.v]; (* Warning: v must not be {0, 0} *)frontPlot[direction_] := ParametricPlot[ Evaluate[g + direction unit[D[g, t]] * 1.5], {t, 0, 1}, DisplayFunction->Identity]; showTracks[direction_] := Show[backPlot, frontPlot[direction], AspectRatio->Automatic, Axes->None, Frame->True, FrameTicks->None, PlotRange->{{1.9, 10.3}, {2, 6}}, DisplayFunction->$DisplayFunction]Show[BezierCurve[pts, ShowPoints->True], AspectRatio->Automatic, Axes->None, Frame->True, FrameTicks->None, PlotRange->{{1.9, 10.3}, {2, 6}}];showTracks[+1];showTracks[-1];

Figure 6. Two examples of bicycle tracks. The top diagram shows the track of the rear wheel, along with the BÎzier control points. The other diagrams show both tracks, with the front track generated by left-to-right travel in the upper diagram, and right-to-left travel in the lower one.

Cite this as: Stan Wagon, "Programming Tips: Bézier Curves" from the Notebook Archive (2002), https://notebookarchive.org/2018-10-10nb4gk