CS-460/560, Week 10
Spring, 1998
R. Eckert


The parametric equations for a 2-D cubic polynomial curve are:

x = ax*t^3 + bx*t^2 + cx*t + dx
                                   0 <= t <= 1
y = ay*t^3 + by*t^2 + cy*t + dy

The shape of the curve is determined by the polynomial coefficients:
(ax,bx,cx,dx, ay,by,cy,dy).

The extension to 3-D is given by adding a third parametric equation:

z = az*t^3 + bz*t^2 + cz*t + dz

We would like to be able to determine the shape of the curve by giving
four control points-- P0(x0,y0,z0), P1(x1,y1,z1), P2(x2,y2,z2), and

One method would be to use interpolating polynomials, in which the curve
is forced to pass through all of the control points. More useful is an
approximating polynomial, in which the curve may interpolate only some or
none of the control points. There are many possible ways to do the
approximating. An important kind of approximating polynomial is the
uniform cubic Bezier polynomial. We assume a generic parametric cubic

P = a*t^3 + b*t^2 + c*t + d,    0 <= t <= 1

determined by the control points P0, P1, P2, and P3

Here P could be x, y, or z; a could be ax, ay, or az; P0 could be x0, y0,
or z0; etc.

For a uniform cubic Bezier polynomial we take the control points to be
uniformly separated in t-space (P0 at t=0, P1 at t=1/3, P2 at t=2/3, and
P3 at t=1). The uniform cubic Bezier boundary conditions are:

1. The curve must interpolate control point P0 when t = 0

   ==> P0 = d

2. The curve must interpolate control point P3 when t = 1

   ==> P3 = a + b + c + d

3. The slope of the curve at t=0 must be equal to that of the line that
joins control points P0 and P1.

   ==> dP/dt(at t=0) = slope of P0-P1

       dP/dt = 3*a*t^2 + 2*b*t + c

       c = (P1-P0)/(1/3 - 0)

       c = 3+(P1-P0)

4. The slope of the curve at t=1 must be equal to that of the line that
joins control points P2 and P3.

   ==> dP/dt(at t=1) = slope of P2-P3

       3*a + 2*b + c = (P3-P2)/(1 - 2/3)

       3*a + 2*b + c = 3*(P3-P2)

If we solve the four equations that result from these boundary conditions
for the polynomial coefficients (a,b,c,d), and express the result a matrix
equation, we get:

  |a|    |-1   3  -3   1|   |P0|
  |b| =  | 3  -6   3   0| * |P1|
  |c|    |-3   3   0   0|   |P2|
  |d|    | 1   0   0   0|   |P3|

Note that this is a constant 4 X 4 matrix multiplied by a vector whose
components are the control points. In the case of uniform cubic Bezier
polynomials, the 4 X 4 matrix is called the Bezier geometry matrix. Other
kinds of polynomial curves will have their polynomial coefficients given
by a similar equation--only the matrix elements of the constant 4 X 4
geometry matrix will change. Since points P on the curve are given by:

P = a*t^3 + b*t^2 + c*t + d,    0 <= t <= 1

we can write this in a more compact form:

P = T * Bg * Pc

where T is a row vector of powers of the parameter = |t^3  t^2  t  1|,
Bg is the constant 4 X 4 Bezier Geometry matrix given above, and Pc is the
column vector of the control points:

Pc = |P1|

If we multiply out this matrix equation and rearrange terms, we can write
the Bezier polynomial equations in a different form--called the Blending
function form. The result is:

P = SUM ( Pi * Bi(t) )

where Pi are the control points (P0, P1, P2, P3)

and the Bi(t) are the "Bernstein Blending Functions"

Note that this is just a weighted sum of the control points. The weighting
factors are the Bernstein Blending Functions. The value of the Blending
function gives the magnitude of the "pull" that the corresponding control
point exerts on the curve at any given point t on the curve.

The blending functions are given by:

Bi(t) = C(3,i) * t^i * (1-t)^(3-i)

Here C(3,i) is the number of combinations of 3 things taken i at a time:

C(3,i) = 3! / (i! * (3-i)!)

For the cubic Bezier polynomial:

B0(t) = (1-t)^3
B1(t) = 3 * t * (1-t)^2
B2(t) = 3 * t^2 * (1-t)
B3(t) = t^3

It turns out the B0 has its maximum value of 1 (100%) at t=0, and all the
other blending functions give 0 there. This means that control point pulls
with 100% "force" at t=0, and that none of the other control points pulls
at all--i.e., the curve must go through P0 (as we know).

At t=1, B3 is 1 (100%) and all the others are zero. So that means P3
uniquely determines the point on the curve at t=1.

B1 has its maximum value at t=1/3, but that value is less than 1. Also the
other blending functions are non-zero at that point but have values less
than that of B1. This means that control point P1 pulls hardest on that
point, but the other control points also pull--so the curve cannot go
through P1.

Similarly at t=2/3, P2 pulls hardest.

Plotting Bezier Curves--Brute Force Method:

1. Get the control points P0=(x0,y0), P1=(x1,y1), P2=(x2,y2), P3=(x3,y3).
   (This could be done using an interactive locator device like a mouse.)

2. Computer the values of a, b, c, d (really ax,bx,cx,dx and ay,by,cy,dy)
   from the control points using the matrix equations.

3. for (t=0; t<=1; t+=delta)
       compute P (x and y) from the polynomial equations
       if (t==0)

Here delta would be some small increment, perhaps 0.05. (This would give an
approximation to the curve consisting of 20 straight-line segments.)

But this is much too much work. Looking at the polynomial,

P = a*t^3 + b*t^2 + c*t + d

we see that on each iteration we would have to do 5 floating point
multiplies [c*t, t*t, b*(c*t), t*(t*t), a*(t*(t*t))] and 3 floating point
adds. Using Horner's rule for polynomial evaluation improves the situation
to 3 multiplies and 3 adds:

P = ((a*t+b)*t+c)*t

But we can do much better. We need to use the technique of Forward
Differences. This will improve things so that we only need to perform 3
floating point adds during each iteration!