Basis conversion among Bézier, Tchebyshev and Legendre

Abstract

1  Introduction

A simple approach suggested by Watkins and Worsey (1988) is to convert a Bézier curve first into the power basis, then to the Tchebyshev basis. Since any basis conversion is a linear transformation, the conversion from Bézier to Tchebyshev may be represented as matrices and performed as a matrix multiplication. The advantage of their approach is that the conversion can be carried out efficiently if the transformation matrices are computed and saved in advance. However, there is a severe disadvantage with respect to their approach: the conversion from Bézier to the power basis is numerically unstable when the degree of polynomial is high. Therefore, their algorithm will generate very poor results when the degree of curve is above 20. Another disadvantage is that the transformation matrices vary depending on the degree of Bézier curves. Hence, a large table of transformation matrices for different degrees has to be created in order to achieve efficiency. In this short communication, we shall present stable and efficient methods to convert a curve in Bézier basis into the one in Tchebyshev or Legendre basis.

2  Bézier to Tchebyshev

r(t)= n å i=0  pi Bi,n(t)        (t Î [0,1])

where, B_i,n(t)=C_nⁱ(1-t)^n-itⁱ. We reparametrise r(t) by x=2t-1 so as to obtain

r(x)= n å i=0  pi Bi,n(x)        (x Î [-1,1])

where,

Bi,n(x)=Cni æ ç è 1-x 2 ö ÷ ø n-i   æ ç è 1+x 2 ö ÷ ø i   .

We want to compute b_i such that

r(x)= n å i=0  pi Bi,n(x)= n å i=0  bi Ti(x),

where T_i(x) are Tchebyshev polynomials of degree i. If r(x) is represented in the power basis, the coefficient of the highest degree term is

an= 1 2n n å i=0  (-1)n-iCni pi

(1)

For any given xⁿ, we can express it as a combination of Tchebyshev polynomials, i.e.,

xn= 1 2n-1 n/2 å i=0  CniTn-2i(x)   (n ³ 1).

Accordingly,

anxn= an 2n-1 Tn(x)+ an 2n-1 n/2 å i=1  CniTn-2i(x).

Let b_n=[(a_n)/(2^n-1)]=[2/(4ⁿ)]å_i=0ⁿ(-1)^n-iC_nⁱp_i. Then,

f(x)= n å i=0  piBi,n(x)-bnTn(x)

(2)

is a polynomial of degree n-1. Representing a Tchebyshev polynomial in the Bézier form gives

Tn(x)= n å i=0  (-1)n-i C2n2i Cni Bi,n(x).

(3)

Consequently, we can express (2) as

f(x)= n å i=0  æ ç è pi-bn(-1)n-i C2n2i Cni ö ÷ ø Bi,n(x)= n å i=0  ri Bi,n(x),

which is a Bézier polynomial of degree n-1. Let p_i^n-1 denote the control points of this lower degree Bézier polynomial. Then, p_i^n-1 may be computed using the following degree reduction formulas (Farin, 1988):

pn-in-1=ai(rn-i-pn-i-1n-1) +pn-i-1n-1,    pi-1n-1=ai(ri-pin-1)+pin-1

(4)

where, a_i=ⁿ/_i (i=n,n-1,¼,ⁿ/₂+1). It is noted that f is of degree n-1 and hence f⁽ⁿ⁾(t) º 0. In this case, the above degree reduction scheme is numerically stable (Eck, 1993). Denoting the original control points of a Bézier curve by p_iⁿ, we present the pseudo-code of our algorithm as follows:

       l₀ = 2.0
       do k=1, n
             l_k = 0.25l_k-1
       enddo
       do k=n, 1, -1
             b_k = 0.0
             do i=k, 0,  -2
                   b_k = b_k + C_kⁱ p_i^k
             enddo
             do i=k-1, 0, -2
                   b_k = b_k - C_kⁱ p_i^k
             enddo
             b_k = l_k b_k
             do i=k, 0,  -1
                   r_i=p_i^k+b_k C_2k²ⁱ/ C_kⁱ
                   b_k = -b_k
             enddo
             p₀^k-1=p₀^k
             p_k-1^{k- 1}=p_k^k
             m=^k/₂ + 1
             do i=k-1, m, -1
                   a_i=ⁿ/_i
                   p_k-i^{k- 1}=a_i(r_{k- i}-p_{k-i -1}^k-1 )+ p_k-i-1^{k -1}
                   p_i-1^k-1=a _i(r_i-p_i^{k- 1}) +p_i^k-1
             enddo
       enddo

In most CAD systems, the binomial coefficients C_nⁱ are tabulated (Otherwise, one can obtain them efficiently by the construction of the Pascal's triangle). If this is the case, our algorithm requires, in total, 3n(n+1)/2 multiplications and 3n(n+1)/4 divisions (ignoring the O(n) multiplications and divisions). In Watkins and Worsey's method, the conversion requires n² multiplications when transformation matrices for any degree are available. Otherwise, their algorithm would require much more computations than ours.

We now look at an example: Converting a Bézier polynomial of degree 25 into Tchebyshev form. The coefficients of the Bézier polynomial are

    0.000000000000000e+00    2.600000000000000e+01    -4.160000000000001e+02
    3.915599999999999e+03    -2.516800000000000e+04    1.202500000000000e+05
    -4.482021818181818e+05    1.344608545454545e+06    -3.316699345454546e+06
    6.828500181818184e+06    -1.186002526315789e+07    1.750765757894737e+07
    -2.207487146910755e+07    2.384086222663616e+07    -2.207487146910755e+07
    1.750765757894737e+07    -1.186002526315790e+07    6.828500181818183e+06
    -3.316699345454545e+06    1.344608545454546e+06    -4.482021818181818e+05
    1.202500000000000e+05    -2.516800000000000e+04    3.915600000000000e+03
    -4.160000000000000e+02    2.600000000000000e+01

The coefficients of the expecting Tchebyshev polynomial are all equal to 1. Using our method the result converges with the precision of 10^-9. However, the result obtained by Watkins and Worsey's method diverges (the maximum absolute difference is 16.911635467789309). If this data is run 100 times for both implementations in the absence of any pre-computed table, the total CPU time for ours and Watkins and Worsey's is respectively 0.183 and 0.883 seconds.

3  Bézier to Legendre

We want to compute c_i such that

r(x)= n å i=0  pi Bi,n(x)= n å i=0  ci li(x)

where, l_i(x) are Legendre polynomials of degree i. For any given xⁿ, we can express it as a combination of Legendre polynomials, i.e.,

xn=an ln(x)+an-1ln-1(x)+¼

The coefficient of the leading term is a_n=[(2ⁿ)/(C_2nⁿ)]. Let c_n=a_na_n, where a_n is given in (1). Then,

cn= 1 C2nn n å i=0  (-1)n-iCnipi.

It is readily seen that

n å i=0  piBi,n(x)-cnln(x)

(5)

is a polynomial of degree n-1. Representing a Legendre polynomial in the Bézier form gives

ln(x)= n å i=0  (-1)n-iCni Bi,n(x).

(6)

Consequently, we can express (5) as

n å i=0  piBi,n(x)-cnln(x)= n å i=0  (pi-cn(-1)n-iCni) Bi,n(x)

which is a Bézier polynomial of degree n-1. The control points of this lower degree Bézier polynomial can be obtained using (4). Repeating this process until we obtain all c_i.

4  Conclusions and remarks

References

P.J. Davis (1975), Interpolation and Approximation, Dover Publications, Inc.

M. Eck (1993), Degree reduction of Bézier curves, Computer Aided Geometric Design 10, 237-251.

G. Farin (1988), Curves and Surfaces for Computer Aided Geometric Design, Academic Press, Inc.

Y.M. Li and Vivian Y. Hsu, Curve offsetting based on Legendre series, Computer Aided Geometric Design 15(7), pp. 711-720.

J-J Malosse (1994), Parametrisation of implicit elliptic curves by rational functions, in R.B. Fisher ed. Design and Application of Curves and Surfaces: The Mathematics of Surfaces V, Oxford Univ. Press.

M.A. Watkins and A.J. Worsey (1988), Degree reduction of Bézier curves, Computer-Aided Design 20, 398-405.