Sunday, January 25, 2015

Bezier Curves

In order to talk about Bezier curves, I first need to talk about polynomials.

A polynomial is a function y = a + b*x + c*x2 + d*x3 + … + p*xn. Such a polynomial is said to have a “degree” of n.

Polynomials are smooth functions, so it is impossible to represent the curve by simply listing all the points on the curve. A better way to represent a particular polynomial is with a coefficient vector, which is [a, b, c, d, …, p] in the above example. If someone wants to recreate the original curve, they can do so by multiplying each term in the coefficient vector by successive powers of x. This is important because, if you are trying to communicate a polynomial of degree n, you can do so by only transferring n coefficients (assuming that both ends have already agreed upon ahead of time the process of that multiplication with successive powers of x. This process is usually baked into code).

Another way to think of this operation is to perform a dot product between the coefficient vector and a basis vector. Therefore, the above polynomial could be represented by the dot product of [a, b, c, d, …, p] · [x0, x1, x2, x3, …, xn]. This is interesting because the values in the coefficient vector are simply scalars, while the values in the basis vector are functions themselves. In general, the communication of a polynomial of degree n can be communicated in n terms, assuming that both ends have previously agreed upon that basis vector ahead of time (and the basis functions form a basis over the vector space you are interested in).

However, there are alternative basis vectors. There are actually many different basis vectors that have been invented throughout history, but only one is relevant when discussing Bezier curves. The functions that Bezier curves use are called Bernstein polynomials. (For comparison, note that both the Fourier series and Taylor polynomials are different basis vectors.)

Before getting into Bernstein polynomials themselves, I want to discuss the fact that other basis vectors are useful in the first place (Naively, it seems like they just add more work to have to convert between different basis vectors). The reason is that each of the curves in a particular basis have some semantic meaning to them. In the Fourier series, each curve has a particular frequency. In the Taylor polynomial, each curve involves a particular derivative of a function.

The semantics behind the Bernstein polynomials is that each curve lies between y=0 and y=1, has a single hump, and the humps for all the functions are roughly equidistant across the interval from x=0 to x=1. In addition, as you move through the polynomials, the location of that function’s hump moves steadily to the right.

Here's a plot of all the Bernstein basis functions for degree 5 drawn on top of each other:

What this means is that a particular coefficient has an effect on the shape of the curve that is intuitive. Boosting a particular coefficient will have a local boosting effect on one part of the curve. This means that it is generally intuitive to figure out what values your coefficients should be if you have a particular shape in mind that you want your curve to hold. You can sculpt your coefficients and the resulting curve will have the same overall shape.

For comparison, this property definitely does not hold for the original basis vector [x0, x1, x2, x3, …, xn].

Usually when people talk about Bezier curves, they are actually talking about a sequence of Bezier curves that are connected tail-to-head, and they are talking about two-dimensional Bezier curves. A two dimensional Bezier is just two Bezier curves, where each curve represents one particular dimension’s output values. (Each of the two Bezier curves have different coefficient vectors). Because the coefficient vectors bear spatial resemblance to the output curve, the coefficient values and the output curve are usually plotted on the same surface.

In the two-dimensional case, a particular coefficient value is usually represented as a dot on the screen. That dot’s X position represents a coefficient in the X Bezier curve, and the dot’s Y position represents the coefficient in the Y Bezier curve. Once you have all the coefficients in the X Bezier curve, you can perform the dot product described above, which results in a description of all the X values that the resulting curve should hold when drawn. The same logic applies to the Y coordinates. Then, you can pair up the curve’s X and Y positions and plot them on the screen, eventually showing the entirety of the resultant curve.

Do this sequence for all of a path’s constituent Bezier curves, and viola! You’ve got a description for the outline of a glyph in a font. In TrueType, all the Bezier curves that describe a glyph are of order 2. In OpenType, all the Bezier curves that describe a glyph can be of order 3 (depending on .... details).

No comments:

Post a Comment