Applications of the polynomial s-power basis in geometry processing

ABSTRACT

We propose a unified methodology to tackle geometry processing operations admitting explicit algebraic expressions. This new approach is based on representing and manipulating polynomials algebraically in a recently basis, the symmetric analogue of the power form (s-power basis for brevity), so called because it is associated with a “Hermite two-point expansion” instead of a Taylor expansion. Given the expression of a polynomial in this basis over the unit interval u &egr;[0, 1], degree reduction is trivally obtained by truncation, which yields the He many terms as desired of the corresponding Hermite interpolant and build “s-power series,” akin to Taylor series. Applications include computing integral approximations of rational polynomials, or approximations of offset curves.

REFERENCES

• 1: BARNHILL, R. E., Ed. 1992. Geometry Processing for Design and Manufacturing. SIAM, Philadelphia, PA.
• 2: COURANT, C. AND JOHN, F. 1989. Introduction to Calculus and Analysis, Vol I. Springer-Verlag, New York, NY.
• 3: DAVIS, P.J. 1975. Interpolation and Approximation. Dover Publications, Inc., Mineola, NY.
• 4: Tony D. DeRose , Ronald N. Goldman , Hans Hagen , Stephen Mann, Functional composition algorithms via blossoming, ACM Transactions on Graphics (TOG), v.12 n.2, p.113-135, April 1993 [doi>10.1145/151280.151290]
• 5: Tony D. DeRose, Composing Bézier simplexes, ACM Transactions on Graphics (TOG), v.7 n.3, p.198-221, July 1988 [doi>10.1145/44479.44482]
• 6: Gershon Elber , In-Kwon Lee , Myung-Soo Kim, Comparing Offset Curve Approximation Methods, IEEE Computer Graphics and Applications, v.17 n.3, p.62-71, May 1997 [doi>10.1109/38.586019]
• 7: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 8: Gerald E. Farin, NURB curves and surfaces: from projective geometry to practical use, A. K. Peters, Ltd., Natick, MA, 1995
• 9: G. Farin, Trends in curve and surface design, Computer-Aided Design, v.21 n.5, p.293-296, June 1989 [doi>10.1016/0010-4485(89)90035-3]
• 10: Rida T. Farouki, The conformal map z→z2 of the hodograph plane, Computer Aided Geometric Design, v.11 n.4, p.363-390, Aug. 1994 [doi>10.1016/0167-8396(94)90204-6]
• 11: FAROUKI, R. T. 1992. Pythagorean-hodograph curves in practical use. In Geometry Processing for Design and Manufacturing, R. E. Barnhill, Ed. SIAM, Philadelphia, PA, 3-33.
• 12: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 13: Josef Hoschek , Dieter Lasser , Larry L. Schumaker, Fundamentals of computer aided geometric design, A. K. Peters, Ltd., Natick, MA, 1993
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: Wei Lü, Offset-rational parametric plane curves, Computer Aided Geometric Design, v.12 n.6, p.601-616, Sept. 1995 [doi>10.1016/0167-8396(94)00036-R]
• 16: PHAM, G. 1992. Offset curves and surfaces: A brief survey. Comput. Aided Des. 24, 4, 223-229.
• 17: L. Piegl, Key developments in computer-aided geometric design, Computer-Aided Design, v.21 n.5, p.262-273, June 1989 [doi>10.1016/0010-4485(89)90032-8]
• 18: Helmut Pottmann, Rational curves and surfaces with rational offsets, Computer Aided Geometric Design, v.12 n.2, p.175-192, March 1995 [doi>10.1016/0167-8396(94)00008-G]
• 19: J. Sánchez-Reyes, The symmetric analogue of the polynomial power basis, ACM Transactions on Graphics (TOG), v.16 n.3, p.319-357, July 1997 [doi>10.1145/256157.256162]
• 20: Thomas W. Sederberg , David B. Buehler, Offsets of polynomial Be´zier curves: Hermite approximation with error bounds, Mathematical methods in computer aided geometric design II, Academic Press Professional, Inc., San Diego, CA, 1992
• 21: SEDERBERG, T. W. AND KAKIMOTO, M. 1991. Approximating rational curves using polynomial curves. In NURBS for Curve and Surface Design, G. Farin, Ed. SIAM, Philadelphia, PA, 149-158.
• 22: SILVERMAN, R. A., DEBRAY, S. K., AND PETERSON, L. L. 1972. Introductory Complex Analysis. Dover Publications, Inc., Mineola, NY.
• 23: Guo-Zhao Wang , Jian-Min Zheng, Bounds on the moving control points of hybrid curves, Graphical Models and Image Processing, v.59 n.1, p.19-25, Jan. 1997 [doi>10.1006/gmip.1996.0411]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

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

General Terms:
Algorithms

Keywords:
Hermite interpolation, Taylor series, degree reduction, geometry processing, offset curves and surfaces, power basis, s-power basis