Polynomial Pieces

The most popular representations for curves in computer graphics are piecewise functions where each curve piece is represented by a polynomial. Piecewise linear representations (a line segment is a polynomial of order 1) are a special case of this. In this section, we look over the mathematics of the individual polynomial pieces. In the next section, we discuss how to put pieces of polynomials together.

Polynomials are functions of the form:

where the $a_i$ are the coefficients. The number of coefficients $n+1$ is called the order. Notice that the order is one more than the highest power of $t$ in the expression, since we have a coefficient for $n=0.$ If we write the coefficients of the polynomial as a vector (of length $n+1$), we can write Equation Equation 1 as:We refer to this form of writing a polynomial (e.g. as coefficients multiplied by the various powers of the parameter) as the canonical form.

The degree of a polynomial is the highest power of the parameter. A polynomial of order 4 may be of degree 3, but it may be of a lower degree if $a_n = 0.$

We can generalize the canonical form of Equation Equation 2 as:

where $\mathbf{c}$ is a vector of $n+1$ coefficients, and each $b_i(t)$ is a polynomial. The set of $n+1$ polynomials $b_i(t)$ are called basis functions, or blending functions. Notice that Equation Equation 2 is simply Equation Equation 3 with $b_i(t) = t^i.$ If the set of basis function is chosen correctly, any polynomial of order $n+1$ can be represented by an appropriate choice of $\mathbf{c}.$

While canonical form is sufficient for describing any polynomial, the coefficients are not necessarily convenient. Throughout this chapter, we will find sets of basis functions such that the coefficients are convenient ways to control the curves represented by the polynomial functions.

For specifying curves, we can either create a separate polynomial for each dimension of the curves’ embedding, or use a vector form of Equations like Equation Equation 3, where the coefficients are points. Note that even in such a case, the basis or blending functions still produce scalar values.

A Line Segment

To introduce the concepts of piecewise polynomial curve representations, we will discuss line segments. In practice, line segments are so simple that the mathematical derivations will seem excessive. However, by understanding this simple case, things will be easier when we move on to more complicated polynomials.

Consider a line segment that connects point $\mathbf{p_0}$ to $\mathbf{p_1}$. We could write the parametric function over the unit domain for this line segment as:

By writing this in vector form, we have hidden the dimensionality of the points, and the fact that we are dealing with each dimension separately. For example, were we working in 2D, we could have created separate equations:using the (admittedly ugly) notation $\mathbf{p}_{0x}$ to refer to the $x$ coordinate of point 0.

The line that we specify is determined by the two end points.

but from now on we’ll stick to vector notation since its cleaner. We will call the vector of control parameters $\mathbf{p}$ the control points, and each element of $\mathbf{p}$ a control point.

While describing a line segment by the positions of its endpoints is obvious and usually convenient, there are other ways to describe a line segment. For example:

1. the position of the center of the line segment, the orientation, and the length;
2. the position of one endpoint and the position of the second point relative to the first;
3. the position of the middle of the line segment and one end.

It should be fairly obvious that given one kind of a description of a line segment, we can switch to another.

A different way to describe a line segment is using the canonical form of the polynomial (as discussed in Section Polynomial Notation),

Any line segment can be represented either by specifying $\mathbf{a_0}$ and $\mathbf{a_1}$, or the endpoints ($\mathbf{p_0}$ and $\mathbf{p_1}$). It is usually more convenient to specify the endpoints, because we can compute the other parameters from the endpoints.

To write the canonical form in as a vector expression, we define a vector $\mathbf{u}$ that is a vector of the powers of $u$:

so that Equation Equation 2 can be written as:This vector notation will make transforming between different forms of the curves easier.

Equation Equation 8 describe a curve segment by the set of polynomial coefficients for the simple form of the polynomial. We call such a representation the canonical form. I will denote the parameters of the canonical form by $\mathbf{a}$.

While it is mathematically simple, canonical form is not always the most convenient way to specify curves. For example, we might prefer to specify a line segment by the positions of its endpoints. If we want to define $\mathbf{p_0}$ to be the beginning of the segment (where the segment is when $u=0$) and $\mathbf{p_1}$ to be the end of the line segment (where the line segment is at $u=1$), we can write:

We can solve these equations for $\mathbf{a_0}$ and $\mathbf{a_1}$:

Matrix Form for Polynomials

While this first example was easy easy enough to solve, for more complicated examples it will be easier to write Equation Equation 9 in the form:

Or, if we call this constraint matrix $\mathbf{C},$ we can writealthough, this is being a little sloppy with notation.¹ If having vectors of points bothers you, you can consider each dimension independently (so that $\mathbf{p}$ is $[{p_0}_x\ {p_1}_x]$ or $[{p_0}_y\ {p_1}_y]$) and $\mathbf{a}$ is handled correspondingly).

We can solve Equation Equation 12 for $\mathbf{a}$ by finding the inverse of $\mathbf{C}.$ This matrix we will call the basis matrix, and we will denote it by $\mathbf{B}.$ The basis matrix is very handy since it tells us how to convert between the convenient parameters $\mathbf{p}$ and the canonical form $\mathbf{a_,}$ and therefore gives us an easy way to evaluate the curve:

We can find a basis matrix for whatever form of the curves that we want, providing that there are no non-linearities in the definition of the parameters.

Another Example: Suppose we want to parameterize the line segment so that $\mathbf{p_0}$ is the half-way point ($u=.5$), and $\mathbf{p_1}$ is the ending point ($u=1$). To derive the basis matrix for this parameterization:

Soand, therefore

Beyond Line Segments

Line segments are simple enough that the effort of finding a basis matrix is silly. However, it was good practice for curves of higher degree. First, let’s consider quadratics (curves of degree 2). The advantage of the canonical form (Equation Equation 2) is that it works for these more complicated curves, just by letting $n$ be a larger number.

A quadratic (a degree 2 polynomial) has 3 coefficients (it has order 3), $\mathbf{a_0}$, $\mathbf{a_1}$, and $\mathbf{a_2}$. These coefficients are not convenient for describing the shape of the curve. However, we can use the same basis matrix method to devise more convenient parameters. If we know the value of $u,$ Equation Equation 2 becomes a linear equation in the parameters,and the linear algebra from the last section still works.

Suppose that we wanted to describe our curves by the position of the beginning ($u=0$), middle² ($u=.5$), and end ($u=1$). Filling the appropriate values into Equation Equation 2:

So the constraint matrix is:and the basis matrix is:

There is one additional type of constraint (or parameter) that is sometimes convenient to specify: the derivative of the curve (with respect to its free parameter) at a particular value. Intuitively, the derivatives tell us how the curve is changing, so that the first derivative tells us what direction the curve is going, the second derivative tells us how quickly the curve is changing direction, etc. We will see examples of why it is useful to specify derivatives later.

For the quadratic,

the derivatives are simple:andOr, more generally,

For example, consider a case where we want to specify a quadratic curve segment by the position, first, and second derivative at its middle ($u=.5$).

So the constraint matrix is:and the basis matrix is:

Basis Matrices for Cubics

Cubic polynomials are popular in graphics (See Section Cubics). One reason is that the basis matrix is a $4x4$ matrix, which is something graphics people work with a lot. The derivations for the various forms of cubics are just like the derivations we’ve seen already in this section. We will work through one more example, for practice.

A very useful form of a cubic polynomial is the Hermite form, where we specify the position and 1st derivative at the beginning and end. That is,

So the constraint matrix is:and the basis matrix is:We will discuss Hermite cubic splines in Section Hermite.

Blending Functions

If we know the basis matrix ($\mathbf{B}$) we can multiply it by the parameter vector ($\mathbf{u}$) to get a vector of functions

Notice that we denote this vector by $\mathbf{b}(u)$ to emphasize the fact that its value depends on the free parameter $u.$ We call the elements of $\mathbf{b}(u)$ the blending functions because they specify how to blend the values of the parameter vector together:It is important to note that for a chosen value of $u$, Equation Equation 31 is a linear equation, specifying a linear blend (or weighted average) of the control points. This is true no matter what degree polynomials are “hidden” inside of the $\mathbf{b_i}$ functions.

Blending functions provide a nice abstraction for describing curves. Any type of curve that can be represented as a weighted linear combination of its control points, where those weights are computed as some arbitrary functions of the free parameter.

Another common term for blending function is basis function.

Interpolating Polynomials

In general, a polynomial of order $m$ can interpolate a set of $m$ values. If we are given a vector $\mathbf{p}$ of values to interpolate, and a corresponding vector $\mathbf{t}$ of sites, we can use the methods described in the previous sections to determine an $m$ by $m$ basis matrix, that would give us a function $f(t)$ such that $f(t_i) = p_i.$ For any given vector $\mathbf{t}$ we would need to set up and solve an $m$ by $m$ linear system. This would provide us with a set of $m$ basis functions that would perform interpolation so the interpolating function is:

This requires that each element of $\mathbf{t}$ is distinct, since the curve can’t interpolate multiple values at a single site.

These interpolating basis functions can be derived in other ways. One particularly elegant way to define them is the Lagrange Form.

There are more computationally efficient ways to express the interpolating basis functions than the Lagrange Form. See (Source: deboor-splines-book) for details.

Interpolating polynomials provide a mechanism for defining curves that interpolate a set of points. Figure Figure (See below) shows some examples. While it is possible to create a single polynomial to interpolate any number of points, we rarely use high order polynomials to represent curves in computer graphics. Instead, interpolating splines (piecewise polynomial functions) are preferred. Some reasons for this are considered in Section Cardinal.

Exercises

For each of the following, find the constraint matrix, the basis matrix, and the blending functions. You should not invert matrices by hand - use a program such as MATLAB or OCTAVE (a free MATLAB-like system).

1. A Line Segment: Parameterized with $\mathbf{p_0}$ being 25% of the way along the segment ($u=.25$), and $\mathbf{p_1}$ being 75% of the way.
2. A Quadratic: Parameterized with $\mathbf{p_0}$ being the position of the beginning point ($u=0$), $\mathbf{p_1}$ being the 1st derivative at the beginning point, and $\mathbf{p_2}$ being the 2nd derivative at the beginning point.
3. A Cubic: With its control points being positions that are equally spaced ($\mathbf{p_0}$ has $u=0,$ $\mathbf{p_1}$ has $u=1/3$, $\mathbf{p_2}$ has $u=2/3$, and $\mathbf{p_3}$ has $u=1$).
4. A Quintic: (a degree 5 polynomial, so the matrices will be $6x6$) Where $\mathbf{p_0}$ is the beginning position, $\mathbf{p_1}$ is the beginning derivative, $\mathbf{p_2}$ is the middle ($u=.5$) position, $\mathbf{p_3}$ is the 1st derivative at the middle, $\mathbf{p_4}$ is the position at the end, and $\mathbf{p_5}$ is the 1st derivative at the end.
5. Lagrange Polynomials: The Lagrange Form (Equation Equation 33) can be used to represent the interpolating cubic of Excursive 3. Use it at several different parameter values to confirm that it does produce the same results as the basis functions derived in Excursive 3.