The symmetric analogue of the polynomial power basis

ABSTRACT

A new polynomial basis over the unit interval t∈0,1 is proposed. The work is motivation by the fact that the monomial (power) form is not suitable in CAGD, as it suffers from serious numerical problems, and the monomial coefficients have no geometric meaning. The new form is the symmetric analogue of the power form, because it can be regarded as an “Hermite two-point expansion” instead of a Taylor expansion. This form enjoys good numerical properties and admits a Horner-like evaluation algorithm that is almost as fast as that of the power form. In a ddition, the symmetric power coeddicients convey a geometric meaning, and therefore they can be used as shape handles. A polynomial expressed in the symmetric power basis is decomposed into linear, cubic, quintic, and successive components. In consequence, this basis is better suited to handle polynomials of different degrees than the Bernstein basis, and those algorithms involving degree operations have extremely simple formulations. The minimum degree of a polynomial is immediately obtained by inspecting its coefficients. Degree reduction of a curve or surface reduces to drooping the desired high degree terms.

REFERENCES

• 1: BARNHILL, R.E., ed. 1992. Geometry Processing for Design and Manufacturing. SIAM, Philadelphia, PA.
• 2: BOWYER, A. AND WOODWARK, g. 1993. Introduction to Computing with Geometry. Information Geometers, Winchester, UK.
• 3: BRUNET, P. 1985. Increasing the smoothness of bicubic spline surfaces. Comput. Aided Geom. Des. 2, 157-164.
• 4: CLARIS 1994. Claris Draw, User's Guide. Claris Corporation, Santa Clara, CA.
• 5: COMPUTER ASSOCIATES 1991. CA-Cricket Draw III, User's Guide. Computer Associates International, Inc., Garden City, NY.
• 6: M. Daniel , J. C. Daubisse, The numerical problem of using Be´zier curves and surfaces in the power basis, Computer Aided Geometric Design, v.6 n.2, p.121-128, May 1989 [doi>10.1016/0167-8396(89)90015-0]
• 7: Matthias Eck, Degree reduction of Be´zier curves, Computer Aided Geometric Design, v.10 n.3-4, p.237-251, Aug. 1993
• 8: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 9: R. T. Farouki, On the stability of transformations between power and Bernstein polynomial forms, Computer Aided Geometric Design, v.8 n.1, p.29-36, Feb. 1991 [doi>10.1016/0167-8396(91)90047-F]
• 10: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 11: R. T. Farouki , V. T. Rajan, Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design, v.5 n.1, p.1-26, June 1988 [doi>10.1016/0167-8396(88)90016-7]
• 12: FORREST, A.R. 1972. Interactive interpolation and approximation by B~zier curves. Cornput. J. 15, 71-79.
• 13: T. N. T. Goodman , H. B. Said, Shape preserving properties of the generalised Ball basis, Computer Aided Geometric Design, v.8 n.2, p.115-121, May 1991 [doi>10.1016/0167-8396(91)90037-C]
• 14: GOODMAN, T. N. T. AND SAID, H.B. 1991b. Properties of generalized Ball curves and surfaces. Comput. Aided Geom. Des. 23, 8 (Oct.), 554-560.
• 15: Josef Hoschek , Dieter Lasser , Larry L. Schumaker, Fundamentals of computer aided geometric design, A. K. Peters, Ltd., Natick, MA, 1993
• 16: Michael A. Lachance, Chebyshev economization for parametric surfaces, Computer Aided Geometric Design, v.5 n.3, p.195-208, Sept. 1988 [doi>10.1016/0167-8396(88)90003-9]
• 17: MILLER, R. 1986. Sculptured surfaces in solid models: Issues and alternative approaches. IEEE Comput. Graph Appl. 6, 12 (Dec.), 37-48.
• 18: PIEGL, L. AND TILLER, W. 1995. Algorithm for degree reduction of B-spline curves. Comput. Aided Des. 27, 2, 101-110.
• 19: H. B. Said, A generalized Ball curve and its recursive algorithm, ACM Transactions on Graphics (TOG), v.8 n.4, p.360-371, Oct. 1989 [doi>10.1145/77269.77275]
• 20: Thomas W. Sederberg, Point and tangent computation of tensor product rational Be´zier surfaces, Computer Aided Geometric Design, v.12 n.1, p.103-106, Feb. 1995 [doi>10.1016/0167-8396(94)00029-R]
• 21: M. A. Watkins , A. J. Worsey, Degree reduction of Be´zier curves, Computer-Aided Design, v.20 n.7, p.398-405, Sept. 1988 [doi>10.1016/0010-4485(88)90216-3]
• 22: Stephen Wolfram, Mathematica: a system for doing mathematics by computer (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis
      G.1.1 Interpolation
          Subjects: Interpolation formulas

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms

Keywords:
Ball basis, Bernstein-Be´zier basis, Hermite interpolation, degree reduction, monomial form, power basis, symmetric power