CS-460/560, Week 10 Spring, 1998 R. Eckert BEZIER POLYNOMIAL CURVES 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 P3(x3,y3,z3). 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 polynomial: 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: |P0| Pc = |P1| |P2| |P3| 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: 3 P = SUM ( Pi * Bi(t) ) i=0 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) MoveTo(x,y) else LineTo(x,y) 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!