Bill Casselman's home page

Bezier curves

Bezier curves are used in computer graphics to produce curves which appear reasonably smooth at all scales (as opposed to polygonal lines, which will not scale nicely). Mathematically, they are a special case of cubic Hermite interpolation (whereas polygonal lines use linear interpolation). What this means is that curves are constructed as a sequence of cubic segments, rather than linear ones. But whereas Hermite interpolating polynomials are constructed in terms of derivatives at endpoints, Bezier curves use a construction due to Sergei Bernstein, in which the interpolating polynomials depend on certain control points. The mathematics of these curves is classical, but it was a French automobile engineer Pierre Bezier who introduced their use in computer graphics.

Roughly speaking, to each set of four points P0, P1, P2, P3 we associate a curve with the following properties:

* It starts at p0 and ends at p3.

* When it starts from p0 it heads directly towards p1, and when it arrives at p3 it is coming from the direction of p2.

* The entire curve is contained in the quadrilateral whose corners are the four given points (their convex hull).

One reason these curves are used so much in computer graphics is that they are very efficient to construct, since a simple recursion process means that the basic arithmetic operation needed to build the points along one is just division by two. For this reason, also, the most efficient implementations use scaled integers instead of floating point numbers as basic numerical data.

Bezier curves are discussed in a lot of places in the computer graphics literature, but as far as I know the most detailed discussion of practical implementation is in D. E. Knuth's book Metafont: the Program, pp. 123-131. My own program follows Knuth's quite closely, except that it doesn't include refinements to get that extra smoothness that makes Knuth's own curves so beautiful. Knuth's entire book is available as a WEB file in the standard TEX distribution (it is in fact the source code for METAFONT.

I make available here my own Java source code for Bezier curves, and notes on Bezier curves from my UBC geometry course. And in addition some personal notes. Finally, a complete package can be found in the file bezier.zip. Note that this package can be compiled with version 1.0.2 of Java (or later).

The main difference between Knuth's program and mine is that Knuth is concerned with writing all the pixels, whereas I am concerned with building up a polygon of straight line segments. For him it is necessary to smooth out the pixelization as much as possible, and this causes him a lot of work. Most of his code is concerned with the octant subdivision, necessary in order to maintain the symmetry of square pixelization.

A good reference on cubic interpolation is Henrici's book Essentials of numerical analysis (with pocket calculator demonstrations). Bernstein polynomials of all degrees are discussed in the book Infinitesimal Calculus by Jean Dieudonne.

The program for building Bezier curves needs also two classes for dealing with real numbers and real points.