Browse Prior Art Database

Degree Reduction for Polynomial Curves And Surfaces

IP.com Disclosure Number: IPCOM000119394D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 3 page(s) / 101K

Publishing Venue

IBM

Related People

Luken, WL: AUTHOR

Abstract

Previous methods for degree reduction of high-order polynomials have been based on the use of Chebyshev polynomials and recursive subdivision of the parameter range spanned by the curve or surface. Such methods suffer from the large amount of computation required to transform each polynomial to lower-degree polynomials. The method described here reduces this effort to the multiplication of one n-component vector by one n x n matrix, where n is the order of the original polynomial. The matrix does not depend on the coefficients of the polynomial.

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

Degree Reduction for Polynomial Curves And Surfaces

      Previous methods for degree reduction of high-order
polynomials have been based on the use of Chebyshev polynomials and
recursive subdivision of the parameter range spanned by the curve or
surface.  Such methods suffer from the large amount of computation
required to transform each polynomial to lower-degree polynomials.
The method described here reduces this effort to the multiplication
of one n-component vector by one n x n matrix, where n is the order
of the original polynomial.  The matrix does not depend on the
coefficients of the polynomial.

      This method overcomes numerical instability problems associated
with high-order polynomials, thereby making it possible to evaluate
curves and surfaces defined by high-order polynomials using single
precision floating point arithmetic processors.

      This method is based on the numerical transformation described
below.  This transformation determines the control points DknNj, j=0
to n-1 of a kth order non-uniform b-spline curve SknN(t) from the
coefficients CNi, i=0 to N-1 of a power series polynomial function
FN(t) having a degree N greater than k.

      The polynomial function is defined as: FN(t) = sum of
CNi*(t**i) for i=0 to N-1, and 0<=t<=1.
      The non-uniform b-spline curve is defined as:

      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
defined by the know vector:
      0, 0, 0, ... 1, 2, 3, ...m, m, m.

      This know vector consists of m+1 sequential integers with the
first and last values being repeated k times each. The value of m is
given by m=n-k+1, and specifies the number of spans in the
non-uniform b-spline curve.

      The control points of the non-uniform b-spline curve are
determined by the transformation:

      DknNj = sum of AknNji*CNi for i=0 to N-1, where AknNji is an
element of the transformation matrix AknN determined by the matrix
product:

      AknN = Bkn(-1)&PnN. That is,
      AknNji = sum of Bkn(-1)j1*PnN1i for 1=0 to n-1.

      The matrix PnN is formed by evaluating the N power series basis
functions at n values of the parametric coordinate t:
 PnN1i = (t1)**i for i=0 to N-1, and t1 an element of t1, 1=0 to
n-1.

      The matrix Bkn(-1) is the inverse of the matrix Bkn formed by
evaluating the non-uniform b-spline basis functions at the same
values of the parametric coordinate t:

      Bknj1 = Bknj(t1) for j=0 to n-1, and t1 an element of t1, 1=0
to n-1.

      The set...