Repeated line interpolation

deCastlejau Algorithm

 


Repeated line interpolation--

Example: Let F be an arbitrary polynomial F(x) = ax2 + bx + c, of degree < 2. We want to demonstrate how this curve is controlled by 3 points.

Step 1: Blossom of F. From F we can obtain a unique symmetric biaffine map f (x1, x2) = ax1x2 + b (x1+x2)/2 + c, such that F(x) = f(x, x), for all x in R. This process is called the blossom (or polar form) of F.

Step 2: Linear interpolation of f. Let ti = (1-li)r + lis, i=1,2. Let us compute f(t1, t2) = f( (1-l1)r + l1s, (1-l2)r + l2s) ....... (*) Note that f is symmetric and biaffine, so we can use the properties of such a map to expand (*) to get the following form, f( t1, t2) = (1-l1) (1-l2) f(r, r) + ((1-l1) l2 + l1 (1-l2)) f(r, s) + l1 l2 f(s,s) .......(**) Solving li in terms of ti we get
li = ( ti - r
s - r
)
Then (**) becomes

f( t1, t2 ) = ( s - t1
s - r
) ( s - t2
s - r
) f(r,r) + [( s - t1
s - r
) ( t2 - r
s - r
) +
( t1 - r
s - r
) ( s - t2
s - r
)] f(r,s) + ( t1 - r
s - r
) ( t2 - r
s - r
) f(s,s)

The points f(r, r), f(r, s) and f(s, s) are called the control points (or Bézier control points) of the curve F.

Step 3: Determination of a curve by control points Now let us see how to determine any point on the curve by the control points f(r,r), f(r,s), f(s,s). In practice we often choose r=0, s=1 in ti = (1-li)r + li s. Thus, ti = li . Now the polynomial function F corresponding to f(t1, t2) is F(t) = f(t, t) = (Please compare with (**)). The polynomials are known as Bernstein polynomials of degree 2. Thus, F(t) is determined by the control points f(0,0), f(0,1), f(1,1) and the Bernstein polynomials. In fact, we have written F(t) as a linear combination of Bernstein polynomials of degree 2. It is customary to call such a curve a Bézier Curve (in terms of Bernstein polynomials).

Remark: Clearly we can turn the above procedure into an algorithm. The obtained algorithm will be called deCastlejau algorithm.

deCastlejau Algorithm --

(for order n=2) Recall from the previous example what f(r,r), f(r,s) and f(s,s) are. The deCastlejau algorithm consists of two stages.

Stage1: We compute the 2 points f(r,t) = f(r, (1-l)r + l s) = (1-l)f(r,r) + lf(r,s) and f(t,s) = f((1-l)r + l s, s) = (1-l)f(r,s) + lf(s,s), by linear interpolation, where f(r,t) is computed from the two control points f(r,r) and f(r,s), and f(t,s) is computed from the two control points f(r,s) and f(s,s), the ratio of interpolation being .

Stage 2: Since by symmetry, f(r,t) = f(t,r), we compute the point f(t,t) = f(t, (1-l)r + l s) = (1-l)f(t,r) + lf(t,s), from the points f(t,r) and f(t,s) computed during the first stage, the ratio of interpolation being the same as before. Thus, by three linear interpolation steps, we obtain the point F(t) on the curve. Note that the two control points f(r,r) = F(r) and f(s,s) = F(s) are on the curve but f(r,s) is not.