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
Bspline and Bézier (a special case of Bspline) 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

p_{i} B_{i,n}(t) (t Î [0,1]) 

where, B_{i,n}(t)=C_{n}^{i}(1t)^{ni}t^{i}. We reparametrise r(t) by x=2t1
so as to obtain
r(x)= 
n å
i=0

p_{i} B_{i,n}(x) (x Î [1,1]) 

where,
B_{i,n}(x)=C_{n}^{i} 
æ ç
è

1x 2

ö ÷
ø

ni


æ ç
è

1+x 2

ö ÷
ø

i

. 

We want to compute b_{i} such that
r(x)= 
n å
i=0

p_{i} B_{i,n}(x)= 
n å
i=0

b_{i} T_{i}(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
a_{n}= 
1 2^{n}


n å
i=0

(1)^{ni}C_{n}^{i} p_{i} 
 (1) 
For any given x^{n}, we can express it as a combination of Tchebyshev
polynomials, i.e.,
x^{n}= 
1 2^{n1}


^{n}/_{2} å
i=0

C_{n}^{i}T_{n2i}(x) (n ³ 1). 

Accordingly,
a_{n}x^{n}= 
a_{n} 2^{n1}

T_{n}(x)+ 
a_{n} 2^{n1}


^{n}/_{2} å
i=1

C_{n}^{i}T_{n2i}(x). 

Let b_{n}=[(a_{n})/(2^{n1})]=[2/(4^{n})]å_{i=0}^{n}(1)^{ni}C_{n}^{i}p_{i}.
Then,
f(x)= 
n å
i=0

p_{i}B_{i,n}(x)b_{n}T_{n}(x) 
 (2) 
is a polynomial of degree n1. Representing a Tchebyshev polynomial in the
Bézier form gives
T_{n}(x)= 
n å
i=0

(1)^{ni} 
C_{2n}^{2i} C_{n}^{i}

B_{i,n}(x). 
 (3) 
Consequently, we can express (2) as
f(x)= 
n å
i=0


æ ç
è

p_{i}b_{n}(1)^{ni} 
C_{2n}^{2i} C_{n}^{i}

ö ÷
ø

B_{i,n}(x)= 
n å
i=0

r_{i} B_{i,n}(x), 

which is a Bézier polynomial of degree n1. Let p_{i}^{n1} denote the
control points of this lower degree Bézier polynomial. Then, p_{i}^{n1}
may be computed using the following degree reduction formulas (Farin, 1988):
p_{ni}^{n1}=a_{i}(r_{ni}p_{ni1}^{n1}) +p_{ni1}^{n1}, p_{i1}^{n1}=a_{i}(r_{i}p_{i}^{n1})+p_{i}^{n1} 
 (4) 
where, a_{i}=^{n}/_{i} (i=n,n1,¼,^{n}/_{2}+1). It is
noted that f is of degree n1 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 p_{i}^{n}, we present the
pseudocode of our algorithm as follows:
l_{0} = 2.0
do k=1, n
l_{k} = 0.25l_{k1}
enddo
do k=n, 1, 1
b_{k} = 0.0
do i=k, 0,
2
b_{k} = b_{k} + C_{k}^{i} p_{i}^{k}
enddo
do i=k1, 0, 2
b_{k} = b_{k}  C_{k}^{i} p_{i}^{k}
enddo
b_{k} = l_{k} b_{k}
do i=k, 0,
1
r_{i}=p_{i}^{k}+b_{k} C_{2k}^{2i}/ C_{k}^{i}
b_{k} =
b_{k}
enddo
p_{0}^{k1}=p_{0}^{k}
p_{k1}^{k
1}=p_{k}^{k}
m=^{k}/_{2} + 1
do i=k1, m, 1
a_{i}=^{n}/_{i}
p_{ki}^{k
1}=a_{i}(r_{k
i}p_{ki
1}^{k1} )+
p_{ki1}^{k
1}
p_{i1}^{k1}=a
_{i}(r_{i}p_{i}^{k
1}) +p_{i}^{k1}
enddo
enddo
In most CAD systems, the binomial coefficients C_{n}^{i} 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^{2}
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 precomputed
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 c_{i} such that
r(x)= 
n å
i=0

p_{i} B_{i,n}(x)= 
n å
i=0

c_{i} l_{i}(x) 

where, l_{i}(x) are Legendre polynomials of degree i. For any given x^{n},
we can express it as a combination of Legendre polynomials, i.e.,
x^{n}=a_{n} l_{n}(x)+a_{n1}l_{n1}(x)+¼ 

The coefficient of the leading term is a_{n}=[(2^{n})/(C_{2n}^{n})]. Let
c_{n}=a_{n}a_{n}, where a_{n} is given in (1). Then,
c_{n}= 
1 C_{2n}^{n}


n å
i=0

(1)^{ni}C_{n}^{i}p_{i}. 

It is readily seen that

n å
i=0

p_{i}B_{i,n}(x)c_{n}l_{n}(x) 
 (5) 
is a polynomial of degree n1. Representing a Legendre polynomial in the
Bézier form gives
l_{n}(x)= 
n å
i=0

(1)^{ni}C_{n}^{i} B_{i,n}(x). 
 (6) 
Consequently, we can express (5) as

n å
i=0

p_{i}B_{i,n}(x)c_{n}l_{n}(x)= 
n å
i=0

(p_{i}c_{n}(1)^{ni}C_{n}^{i}) B_{i,n}(x) 

which is a Bézier polynomial of degree n1. 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
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, 237251.
 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. 711720.
 JJ 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,
ComputerAided Design 20, 398405.
RETURN