Curves and splines for fun and profit at Lessons taught; Lessons learnt

Curves and splines for fun and profit

Imagine you are given some points, and asked to join them together. Probably the easiest way to do this is to use straight lines:

What if we wanted the line joining these points together to be a curve, rather than a sequence of straight lines? Even better, to be a smooth curve (in other words, to not have any sharp changes in direction)? One of the simplest ways to do this is to move into the world of Bézier curves.

The geometry of Bézier curves

Beziér curves are a class of surprisingly easy to generate curves which can be specified completely by a small number of points. Here is how to geometrically construct the two most common types of Bézier curve:

First, a quadratic Bézier curve:

To see this Geogebra worksheet, please enable Java.

Second, a cubic Bézier curve:

To see this Geogebra worksheet, please enable Java.

(Both of these are interactive -- move the blue points around and see how the curve changes.)

It should be obvious that we could continue this process with more and more control points to get Bézier curves of even higher orders.

From curves to splines

These curves are very nice, but they only go through the first and last points, with the others acting like 'control points', influencing the direction of the curve. If we create a Bézier curve using all the points given earlier, for example, we get this:

To connect up the points we are going to need to join together several of these Bézier curves, to form a spline. The full theory of splines is very complicated, but we can make a good start by connecting together a bunch of cubic Bézier curves:

If you have ever used a vector graphics package (like Inkscape, Illustrator or Coreldraw), this is exactly how they create paths through specified points. They tend not to draw the line segment connecting the two control points together, which makes the path look like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

Playing with the path above, you soon notice that it is very easy to get kinks (cusps) at the points where the Bézier curves meet. We can avoid this by making sure that the control points before and after a curve point are on the same straight line. Drawing packages also usually make the control points the same distance away from the curve point, giving you something like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

There is still too much choice here, though -- remember that we have just been given the points for the curve to go through. We can get a fairly nice curve, which just depends on one parameter (the 'curviness', lambda), by setting the control points as follows:

Given points $X_0$ up to $X_n$ , for $i \in \{1, \ldots, n-1\}$ , set the control point to the left of $X_i$ to be $X_i - \lambda \overrightarrow{X_{i-1} X_{i+1}}$ , and the control point to the right of $X_i$ to be $X_i + \lambda \overrightarrow{X_{i-1} X_{i+1} }$ .

In other words, the line between the two control points is parallel to the line between the two neighbouring curve points, and the distance is proportional to the distance between the curve points.

We also need to decide what to do with the control points of the ends of the curve, $X_0$ and $X_n$ . Probably the simplest thing to do is to set the control points equal to the curve points themselves.

This gives us something like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

I call the parameter the 'curviness', because the spline becomes more and more like a collection of straight line segments the closer lambda is to 0. The higher the value of lambda, the more pronounced the curve is -- and interesting things happen if lambda becomes negative!

Solving our original problem

We can now solve our original problem, by connecting our collection of points together with an appropriately generated set of Bézier curves. We might decide to have an 'open' curve (with endpoints):

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

or indeed to create a 'closed' curve, treating all the points equally:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

Why not see what different types of shapes you can generate from these seven points? How close to a perfect circle can you get, for example?

Further notes

Without realising it, you have been looking at Bézier curves for years: every scalable Truetype font is defined using quadratic Bézier curves, and many other font systems use quadratic or cubic ones. The mass use of scalable fonts (first popularised in the Postscript printing system) was a major innovation, rendering the old bitmap system, where fonts came in one particular pixel-based size, almost entirely redundant.

Interestingly, Bézier was not the first person to discover, or to work with Bézier curves. One of the most common algorithms for drawing Bézier curves is due to de Casteljau, who was working with Bézier curves several years before Bézier!

Although probably the most common, Bézier curves are certainly not the only choice to use for splines. If you are interested, see this Wikipedia article for more information than you probably wanted on the deeper mathematics behind them.

A Geogebra postscript

All the interactive sections above were generated using Geogebra. Double-clicking on any of them will open the interactivity in its own window, where you can save it to your computer, or explore how it was generated. If the interactivities are not there, then the Geogebra website is probably down!

One of the features introduced in version 3 of Geogebra is custom tools. I have created one of these custom tools which will let you easily create cubic Bézier curves. Simply open the following file: cubic-bezier-tool.ggt, and you will see a cubic Bézier tool appear in the toolbar.

Appendix: The algebra of Bézier curves

The reason for the names 'quadratic' and 'cubic' becomes clearer when we try to figure out an algebraic way to generate Bézier curves. It is apparent from the geometric construction that the key to constructing these curves is to move a certain proportion of the way between pairs of points, and then repeat this process until we have only one point, which will trace out the Bézier curve.

We will build up the formulae from the simplest case:

Straight lines (linear Bézier curves): If $t$ is a parameter between $0$ and $1$ , then the point $t$ th of the way between $A$ and $B$ is $P_{AB} = (1-t)A + t B$ . As $t$ changes, $P_{AB}$ will trace out the line segment $AB$ . This is sometimes called linear interpolation.

Quadratic Bézier curves: We are given points $A$ , $B$ , and $C$ . From these we generate the two points $P_{AB} = (1-t)A + t B$ and $P_{BC} = (1-t)B + t C$ . Moving $t$ th of the way between these two points we generate $P_{ABC}$ :

Rearranging and simplifying, we get

$P_{ABC} = (1-t)^2 A + 2 (1-t) t B + t^2 C$ .

This will trace out our quadratic Bézier curve.

Cubic Bézier curves: We are now given four points, $A$ to $D$ . We can generate two quadratic points, $P_{ABC}$ and $P_{BCD}$ , with equations as above. Combining them, we get $P_{ABCD}$ , which will trace out our cubic Bézier curve. The simplified form of its equation is:

$P_{ABCD} = (1-t)^3 A + 3 (1-t)^2 t B + 3 (1-t) t^2 C + t^3 D$ .

We could continue this as far as we wanted, to get equations for higher order Bézier curves.

2 Responses to 'Curves and splines for fun and profit'

Subscribe to comments with RSS or TrackBack to 'Curves and splines for fun and profit'.

[...] Curves and splines for fun and profit [...]

Lessons taught; Lessons learnt » Blog Archive » Further reading on splines

4 Apr 09 at 1:50 pm
[...] Curves and splines for fun and profit [...]

Lessons taught; Lessons learnt » Blog Archive » Geogebra Miscellancies

11 Apr 09 at 3:32 pm

Lessons taught; Lessons learnt