Algorithms for polynomials in Bernstein form

doi:10.1016/0167-8396(88)90016-7

Computer Aided Geometric Design

Volume 5, Issue 1, June 1988, Pages 1-26

https://doi.org/10.1016/0167-8396(88)90016-7 Get rights and content

Abstract

Aspects of the formulation and numerical stability of geometric modeling algorithms in the Bernstein polynomial basis are further explored. Bernstein forms for various basic polynomial procedures (the arithmetic operations, substitution of polynomials, elimination of variables, determination of greatest common divisors, etc.) required in such algorithms are developed, and are found to be of similar complexity to their customary power forms. This establishes the viability of systematic computation with the Bernstein form, avoiding the need for (numerically unstable) basis conversions.

Procedures which nominally improve root condition numbers—the power-to-Bernstein conversion and Bernstein degree elevation and subdivision techniques—are examined in greater detail. These procedures are found to have a relatively poor inherent conditioning, which essentially cancels the expected improvement, and their explicit use does not therefore provide a means of enhancing numerical stability.

We also examine the condition of computation in floating point arithmetic of the power and Bernstein formulations for the basic polynomial procedures. However, the detailed dependence of the computational errors on the input parameters, the algorithm structure, and the floating point system preclude comparisons as definitive and general as those pertaining to the root condition numbers in the power and Bernstein bases. Empirical evaluation of carefully selected test cases may provide firmer conclusions in this regard.

References (40)

P. Bézier
Procédé de définition numérique des courbes et surfaces non mathématiques; Système UNISURF
Automatisme
(1968)
P. Bézier
Numerical Control—Mathematics and Applications
(1972)
P. Bézier
Essai de définition numérique des courbes et des surfaces expérimentales
W. Boehm et al.
A survey of curve and surface methods in CAGD
Computer Aided Geometric Design
(1984)
P.J. Davis
Interpolation and Approximation
(1963)
P. de Casteljau
Courbes et surfaces à pôles
(1963)
Y. de Montaudouin et al.
The Cayley method in computer aided geometric design
Computer Aided Geometric Design
(1984)
A.D. De Rose
Composing Bézier simplices
G. Farin
Konstruktion und Eigenschaften von Bézier-Kurven und Bézier-Flächen, Diplom-Arbeit
(1977)
G. Farin
Algorithms for rational Bézier curves
Computer Aided Design
(1983)

R.T. Farouki

The characterization of parametric surface sections

Computer Vision, Graphics, and Image Processing

(1986)

R.T. Farouki et al.

On the numerical condition of polynomials in Bernstein form

Computer Aided Geometric Design

(1987)

C.T. Fike

Computer Evaluation of Mathematical Functions

(1968)

A.R. Forrest

Interactive interpolation and approximation by Bézier polynomials

The Computer Journal

(1972)

G.E. Forsythe

Pitfalls in computation, or why a math book isn't enough

American Mathematical Monthly

(1970)

W. Gautschi

On the condition of algebraic equations

Numerische Mathematik

(1973)

W. Gautschi

Questions of numerical condition related to polynomials

P. Goetgheluck

Computing binomial coefficients

American Mathematical Monthly

(1987)

R.N. Goldman et al.

Vector elimination: a technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves

Computer Aided Geometric Design

(1984)

W.J. Gordon et al.

Bernstein-Bézier methods for the computer aided design of free-form curves and surfaces

J. ACM

(1974)

Cited by (266)

Geometric Hermite interpolation by rational curves of constant width
2024, Journal of Computational and Applied Mathematics
A constructive characterization of the support function for a rationally parameterized curve of constant width is given. In addition, a Hermite interpolation problem for such kind of curves is solved, which yields a method to determine a rational curve of constant width that passes through a set of free points with the corresponding tangent directions. Finally, the case of piecewise rational support functions is considered, which increases the design freedom. The procedure is presented in the general case of hedgehogs of constant width taking the advantage of projective hedgehogs, so that some constraints must be taken to ensure convexity of the desired curve.
Accurate Detection and Smoothness-Oriented Avoidance Method of Singularity in 5-Axis CNC Machining
2024, CAD Computer Aided Design
As an inherent flaw in the kinematic chain mechanism of 5-axis machine tools, singularity can induce dramatic changes in machine axes motion and unfavorable fluctuations in feedrate. For effective singularity avoidance, it is desirable to first achieve accurate and efficient singularity detection and then eliminate the singularity without impairing tool orientation smoothness. This paper presents a novel approach for accurately detecting and smoothly avoiding the singularity in 5-axis CNC machining. In the detection method, two exclusion criteria are presented to efficiently exclude most non-singular segments of the tool orientation spline, and a curve intersection-based algorithm is thus developed to accurately identify the singular segments. In the singularity avoidance method, a concept of admissible tool orientation annulus (ATOA) is introduced, which serves to confine the range and magnitude of the tool orientation spline’s adjustments, and a local adjustment algorithm is then developed to enable the escape of the tool orientation from the singular region with controllable direction and deviation, while maintaining its continuity and smoothness. The effectiveness of singularity avoidance and the kinematic performance of the tool orientation modified by our method, are comparable to a state-of-the-art singularity avoidance algorithm. Finally, the conducted experiments validate the proposed method.
On the accuracy of de Casteljau-type algorithms and Bernstein representations
2023, Computer Aided Geometric Design
This paper summarizes interesting results on systematic backward and forward error analyses performed for corner cutting algorithms providing evaluation of univariate and multivariate functions defined in terms of Bernstein and Bernstein related bases. Relevant results on the conditioning of the bases are also recalled. Finally, the paper surveys important advances, lately obtained, for the design of algorithms adapted to the structure of totally positive matrices, allowing the resolution of interpolation and approximation problems with Bernstein-type bases achieving computations to high relative accuracy.
A New Framework for Joint Trajectory Planning Based on Time-Parameterized B-Splines
2023, CAD Computer Aided Design
This paper discusses a new, highly effective trajectory planning paradigm for robotics and manufacturing systems. The proposed approach offers a more flexible solution to a problem classically solved in closed-form, defining a generalization of the existing methods by providing a common data structure based on time-parameterized curves to represent exactly or approximately the joint trajectories. In the framework, the most generic approach to constrain or optimize a trajectory is to set up an iterative loop and act on the parameters through computer-aided design concepts, such as shape modeling, symbolic calculation, derivation and integration. The iso-parametric representation allows to define these procedures as macro-instructions to develop scalable and reusable solutions. A benchmark is proposed to confirm the advantages of the new approach over an established solution. Finally, an experimental case study of a single axis motion control is provided to illustrate and clarify the method.
An approximate characterisation of the set of feasible trajectories for constrained flat systems
2022, Automatica
We study differentially flat systems, subject to constraints on the input, the state and their derivatives. We are interested in providing an approximate characterisation of the set of trajectories satisfying both the equations of the system and the constraints. The flatness property and the choice of a polynomial parametrisation in terms of Bézier functions enable a finite dimension formulation of the problem in the parameter space of the Bézier control points. Such formulation provides a unified method to express a large variety of relevant constraint types in the state and the inputs. We present a simple and effective inner approximation of the aforementioned set of trajectories obtained by simple algebraic manipulations of the original constraints formulation. The symbolic nature of the proposed approximation allows a certain degree of adaptation to changes in the constraints without the need for a complete re-computation.
The general Bernstein function: Application to χ-fractional differential equations
2024, Mathematical Methods in the Applied Sciences

View all citing articles on Scopus

View full text

Algorithms for polynomials in Bernstein form

Abstract

Procédé de définition numérique des courbes et surfaces non mathématiques; Système UNISURF

Automatisme

Numerical Control—Mathematics and Applications

Essai de définition numérique des courbes et des surfaces expérimentales

A survey of curve and surface methods in CAGD

Computer Aided Geometric Design

Interpolation and Approximation

Courbes et surfaces à pôles

The Cayley method in computer aided geometric design

Computer Aided Geometric Design

Composing Bézier simplices

Konstruktion und Eigenschaften von Bézier-Kurven und Bézier-Flächen, Diplom-Arbeit

Algorithms for rational Bézier curves

Computer Aided Design

The characterization of parametric surface sections

Computer Vision, Graphics, and Image Processing

On the numerical condition of polynomials in Bernstein form

Computer Aided Geometric Design

Computer Evaluation of Mathematical Functions

Interactive interpolation and approximation by Bézier polynomials

The Computer Journal

Pitfalls in computation, or why a math book isn't enough

American Mathematical Monthly

On the condition of algebraic equations

Numerische Mathematik

Questions of numerical condition related to polynomials

Computing binomial coefficients

American Mathematical Monthly

Vector elimination: a technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves

Computer Aided Geometric Design

Bernstein-Bézier methods for the computer aided design of free-form curves and surfaces

J. ACM