Browse Prior Art Database

# Error Bounds for Conversion of High Degree Polynomials to Lower Degree B-spline Curves and Surfaces

IP.com Disclosure Number: IPCOM000109771D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 3 page(s) / 115K

IBM

## Related People

Luken, WL: AUTHOR

## Abstract

A previous article, "Degree Reduction for Polynomial Curves and Surfaces," IBM Technical Disclosure Bulletin 33, 467 (January 1991), presented a method for converting a polynomial or order N (degree N-1), FN(t) = sum of CNi*(t**i) for i=0 to N-1 and 0<=t<=1, to a non-uniform b-spline function SknN(t) = sum of DknNj*Bknj(m*t) for j = 0 to N-1, where Bknj(s) is the (j+1) member of the non-uniform b-spline basis functions of order k<= defined by the knot vector (0, 0, 0, ..., 1, 2, 3, ..., m, m, m) in which the initial (0) and final (m=n=k+1) known values are each repeated k times. This conversion is accomplished by multiplying the vector of polynomial coefficients CN by a matrix AknN defined in the above-referenced article to obtain the vector of b-spline coefficients DknN. That is, DknN = AknN CN.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Error Bounds for Conversion of High Degree Polynomials to Lower Degree B-spline Curves and Surfaces

A previous article, "Degree Reduction for Polynomial
Curves and Surfaces," IBM Technical Disclosure Bulletin 33, 467
(January 1991), presented a method for converting a polynomial or
order N (degree N-1),
FN(t) = sum of CNi*(t**i) for i=0 to N-1 and 0<=t<=1,
to a non-uniform b-spline function
SknN(t) = sum of DknNj*Bknj(m*t) for j = 0 to N-1,
where Bknj(s) is the (j+1) member of the non-uniform b-spline basis
functions of order k<= defined by the knot vector
(0, 0, 0, ..., 1, 2, 3, ..., m, m, m)
in which the initial (0) and final (m=n=k+1) known values are each
repeated k times.  This conversion is accomplished by multiplying the
vector of polynomial coefficients CN by a matrix AknN defined in the
above-referenced article to obtain the vector of b-spline
coefficients DknN.  That is,
DknN = AknN CN.

If the order k of the b-spline functions is equal to the order
N of the polynomial function, then this conversion is exact.
Otherwise, if the order of the b-sline functions is less than that of
the polynomial function, then the conversion is an approximation and
there is an error given by the difference between these functions.
EknN(t) = SknN(t) - FN(t).

bounds Emax(k,n,N) on these errors,
Abs(EknN(ts)) <= Emax(k,n,N) for 0 <= t <= 1.

These methods make it possible to determine the size (n) of the
b-spline basis set required to convert a polynomial function to a
lower order b-spline function with a maximum error less than a
specified tolerance.

The first method for calculating an error bound for this
conversion is defined by representing the conversion error as a
b-spline function of order N,
EknN(t) = sum of eknNi*Bkn'i(m*t), for i=0 to n'-1.

This is accomplished by converting the polynomial and the
b-spline function to a common b-spline basis set.  In the case of the
b-spline function, this is achieved by using well-known degree
elevation techniques to determine the coefficients required to
represent the b-spline function with a b-spline basis set of order N.
The result is
SknN(t) = sum of dknNi*BNn'i(m*t), for i=0 to n'1-1.

The degree elevation process causes the size of the b-spline
basis set to be increased from n functions of order k to
n' = n + m*(N-k)
functions or order N.  This same basis set may be used to represent
the polynomial function exactly as
FN(t) = sum of DNn'Ni*BNn'i(m*t) for i = 0 to N-1.

The coefficient vectors dknN and DNn'N are related to the
polynomial coefficients CN by the matrix equations
d...