Basis conversion among Bézier, Tchebyshev and Legendre

Abstract

Bézier representation of curves and surfaces has been a standard in most CAD/CAM systems. The conversion between Bézier, Tchebyshev, and Legendre representation of polynomial curves and surfaces is often desired when an approximation procedure is involved. In this paper, we present a simple and numerically stable method for basis conversion of Bézier, Tchebyshev, and Legendre polynomials.

1  Introduction

B-spline and Bézier (a special case of B-spline) representations of curves and surfaces are the standard in CAD systems. However, polynomial curves and surfaces in Tchebyshev and Legendre basis (Davis, 1975) have found their applications in many geometric operations such as intersecting and offsetting where approximation approaches are involved. For example, we have seen the use of Tchebyshev polynomials in degree reduction schemes (Watkins and Worsey, 1988; Eck, 1993) and the use of Legendre polynomials in parametrising algebraic curves of genus not equal to zero (Malosse, 1994) Recently, we developed a curve offsetting algorithm in which a Legendre series is used (Li and Hsu, 1997). Due to the importance of Tchebyshev and Legendre polynomials in CAD applications, we are concerned with how to convert a curve in Bézier basis into the one in Tchebyshev or Legendre basis.

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

A polynomial in the Bézier form may be given by (Farin, 1988):

r(t)= n

i=0 
pi Bi,n(t)        (t [0,1])
where, Bi,n(t)=Cni(1-t)n-iti. 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 bi such that

r(x)= n

i=0 
pi Bi,n(x)= n

i=0 
bi Ti(x),
where Ti(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 xn, 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 bn=[(an)/(2n-1)]=[2/(4n)]i=0n(-1)n-iCnipi. 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 pin-1 denote the control points of this lower degree Bézier polynomial. Then, pin-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, ai=n/i (i=n,n-1,,n/2+1). It is noted that f is of degree n-1 and hence f(n)(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 pin, we present the pseudo-code of our algorithm as follows:

       l0 = 2.0
       do k=1, n
             lk = 0.25lk-1
       enddo
       do k=n, 1, -1
             bk = 0.0
             do i=k, 0,  -2
                   bk = bk + Cki pik
             enddo
             do i=k-1, 0, -2
                   bk = bk - Cki pik
             enddo
             bk = lk bk
             do i=k, 0,  -1
                   ri=pik+bk C2k2i/ Cki
                   bk = -bk
             enddo
             p0k-1=p0k
             pk-1k- 1=pkk
             m=k/2 + 1
             do i=k-1, m, -1
                   ai=n/i
                   pk-ik- 1=ai(rk- i-pk-i -1k-1 )+ pk-i-1k -1
                   pi-1k-1=a i(ri-pik- 1) +pik-1
             enddo
       enddo

In most CAD systems, the binomial coefficients Cni 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 n2 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

Tchebyshev and Legendre polynomials are special cases of Jacobi polynomial (Davis, 1975) Therefore, converting a polynomial in Bézier basis to Legendre basis is very similar to that from Bézier to Tchebyshev. In this section, we briefly describe the method.

 

We want to compute ci such that

r(x)= n

i=0 
pi Bi,n(x)= n

i=0 
ci li(x)
where, li(x) are Legendre polynomials of degree i. For any given xn, 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 an=[(2n)/(C2nn)]. Let cn=anan, where an 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 ci.

4  Conclusions and remarks

We presented a simple and numerically stable method for basis conversion from Bézier to Tchebyshev or Legendre. Although the conversion from Tchebyshev or Legendre to Bézier is not specifically discussed in this short communication, one can achieve this by using equation (3) or (6) respectively in cooperation with the Bézier degree elevation scheme.

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.

RETURN