Evaluation and approximate evaluation of the multivariate Bernstein-Bézier form on a regularly partitioned simplex

ABSTRACT

Polynomials of the total degree d in m variables have a geometrically intuitive representation in the Bernstein-Be´zier form defined over an m-dimensional simplex. The two algorithms given in this article evaluate the Bernstein-Be´zier form on a large number of points corresponding to a regular partition of the simplicial domain. The first algorithm is an adaptation of isoparametric evaluation. The second is a subdivision algorithm. In contrast to de Casteljau's algorithm, both algorithms have a cost of evaluation per point that is linear in the degree regardless of the number of variables. To demonstrate practicality, implementations of both algorithms on a triangular domain are compared with generic implementations of six algorithms in the literature.

REFERENCES

• 1: BOE~M, W. 1983. Subdividing multivariato splinog. Comput. Aided Des_ 15, 6 (Nov. L 345-352.
• 2: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 3: DE BOOR, C. 1987. B-form basics In Geometrzc Modehng: Appl~catzons and New Trends, G Farin, Ed. SIAM, Philadelphia, Pa.
• 4: DE BooR, C. 1978. A Practical Guide to Spl~nes. Applied Mathematical Sciences. Vol. 27. Springer, New York.
• 5: DE BOOR, C. AND RON, A. 1990. Computational aspects of polynomial interpolation m several variables. Comput. Sci. Tech. Rep. 924, Univ. of Wisconsin, Madison, Wisc
• 6: DE CASTELJAU, F. 1959. Courbes et surfaces ~ p61es. Andr~ Cztroen Automobzles. Paris 1963. CONTE, S. D. AND DE BOOR, C. 1980. Elementary Numerzcal Analyszs. 3rd ed. McGraw-Hill, New York
• 7: W. Dahmen, Subdivision algorithms—recent results, some extensions and further developments, Algorithms for approximation, Clarendon Press, New York, NY, 1987
• 8: W Dahmen, Subdivision algorithms converge quadratically, Journal of Computational and Applied Mathematics, v.16 n.2, p.145-158, Oct. 1986 [doi>10.1016/0377-0427(86)90088-9]
• 9: DAHMEN, W. 1986b. Bernstein-B~zmr representation of polynomial surfaces In SIGGRAPH '86. Lecture notes. ACM, New York.
• 10: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 11: FARIN, G. 1983. Smooth interpolation to scattered 3D-data In Surfaces tn CAGD, R E. Barnhfil and W. Boehm, Eds.
• 12: 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]
• 13: 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]
• 14: GOLDMAN, R.N. 1983. Subdivision algorithms for B~zmr triangles. Comput. A~ded Des. 15, 3 (May), 159-166.
• 15: GOLUB, G. H. AND VAN LOAN, C. F 1989 Matrix Computatzons 2nd ed. Johns Hopkins University Press, London.
• 16: T. N. T. Goodman, Variation diminishing properties of Bernstein polynomials on triangles, Journal of Approximation Theory, v.50 n.2, p.111-126, June 1987 [doi>10.1016/0021-9045(87)90002-5]
• 17: LANE, J. AND RIESENFELD, R.F. 1980. A theoretmal development for the computer generation and display of plecewise polynomial surfaces IEEE Trans. Part Anal. Mach. Intell. 2, 1, 35-46
• 18: Sheue-Ling Lien , Michael Shantz , Vaughan Pratt, Adaptive forward differencing for rendering curves and surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.111-118, July 1987
• 19: LYCHE, T., COHEN, E., AND RIESENFELD, R. 1980. Discrete B-sphnes and subdivision techniques in computer aided geometric design and computer graphics. Comput. Graph. Image Process. 14, 2, 87-111
• 20: PETERS, g. 1990a. Evaluation of multivariate Bernstem polynomials CMS Tech. Rep No 91-1, Univ. of Wisconsin, Madison, Wisc.
• 21: J. Peters, Smooth mesh interpolation with cubic patches, Computer-Aided Design, v.22 n.2, p.109-120, Mar. 1990 [doi>10.1016/0010-4485(90)90005-W]
• 22: L L Shumaker , W Volk, Efficient evaluation of multivariate polynomials, Computer Aided Geometric Design, v.3 n.2, p.149-154, August 1986 [doi>10.1016/0167-8396(86)90018-X]
• 23: SCHONBERG, I.J. 1959. On variation dimimshmg approximation methods. In On Numerical Approxzmatzon, R. E. Langer, Ed. Univ. of Wisconsin Press, Madison, Wisc., 249-274
• 24: STUMMEL, F AND HAINEI~. K. 1992. Pratetzsclze Mathem~tzl~. Teubnar, ~tuttgart
• 25: W. Volk, Making the difference interpolation method for splines more stable, Journal of Computational and Applied Mathematics, v.33 n.1, p.53-59, Dec. 1990 [doi>10.1016/0377-0427(90)90255-X]
• 26: Wolfgang Volk, An efficient Raster evaluation method for univariate polynomials, Computing, v.40 n.2, p.163-173, May 1988 [doi>10.1007/BF02247944]
• 27: Wolfgang Volk, Die Auswertung von Polznomen mehrerer Veränderlicher auf Punktrastern, Austrographics '88, Aktuelle Entwicklungen in der Graphischen Datenverarbeitung, p.237-251, September 28-30, 1988

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance, Theory

Keywords:
Bernstein-Be´zier form, multivariate, powerform, subdivision