Search

New geometric methods for fast evaluation of derivatives of polynomial and rational B\'{e}zier curves are proposed. They apply an algorithm for evaluating polynomial or rational B\'{e}zier curves, which was recently given by the authors. Numerical tests show that the new approach is more efficient than the methods which use the famous de Casteljau algorithm. The algorithms work well even for high-order derivatives of rational B\'{e}zier curves of high degrees.

A new differential-recurrence relation for the B-spline functions of the same degree is proved. From this relation, a recursive method of computing the coefficients of B-spline functions of degree $m$ in the Bernstein-B\'{e}zier form is derived. Its complexity is proportional to the number of coefficients in the case of coincident boundary knots. This means that, asymptotically, the algorithm is optimal. In other cases, the complexity is increased by at most $O(m^3)$. When the Bernstein-B\'{e}zier coefficients of B-spline basis functions are known, it is possible to compute any B-spline function in linear time with respect to its degree by performing the geometric algorithm proposed recently by the authors. This algorithm scales well when evaluating the B-spline curve at multiple points, e.g., in order to render it, since one only needs to find the coefficients for each knot span once. When evaluating many B-spline curves at multiple points (as is the case when rendering tensor product B-spline surfaces), such approach has lower computational complexity than using the de Boor-Cox algorithm. The numerical tests show that the new method is efficient. The problem of finding the coefficients of the B-spline functions in the power basis can be solved similarly.

A new algorithm for computing a point on a polynomial or rational curve in B\'{e}zier form is proposed. The method has a geometric interpretation and uses only convex combinations of control points. The new algorithm's computational complexity is linear with respect to the number of control points and its memory complexity is $O(1)$. Some remarks on similar methods for surfaces in rectangular and triangular B\'{e}zier form are also given.

Dual Bernstein polynomials of one or two variables have proved to be very useful in obtaining B\'{e}zier form of the $L^2$-solution of the problem of best polynomial approximation of B\'{e}zier curve or surface. In this connection, the B\'{e}zier coefficients of dual Bernstein polynomials are to be evaluated at a reasonable cost. In this paper, a set of recurrence relations satisfied by the B\'{e}zier coefficients of dual bivariate Bernstein polynomials is derived and an efficient algorithm for evaluation of these coefficients is proposed. Applications of this result to some approximation problems of Computer Aided Geometric Design (CAGD) are discussed., Comment: arXiv admin note: text overlap with arXiv:1504.03557

We propose a novel approach to the problem of polynomial approximation of rational B\'ezier triangular patches with prescribed boundary control points. The method is very efficient thanks to using recursive properties of the bivariate dual Bernstein polynomials and applying a smart algorithm for evaluating a collection of two-dimensional integrals. Some illustrative examples are given.

We present an efficient method to solve the problem of the constrained least squares approximation of the rational B\'{e}zier curve by the B\'{e}zier curve. The presented algorithm uses the dual constrained Bernstein basis polynomials, associated with the Jacobi scalar product, and exploits their recursive properties. Examples are given, showing the effectiveness of the algorithm.

This paper deals with the merging problem of segments of a composite B\'ezier curve, with the endpoints continuity constraints. We present a novel method which is based on the idea of using constrained dual Bernstein polynomial basis (P. Wo\'zny, S. Lewanowicz, Comput. Aided Geom. Design 26 (2009), 566--579) to compute the control points of the merged curve. Thanks to using fast schemes of evaluation of certain connections involving Bernstein and dual Bernstein polynomials, the complexity of our algorithm is significantly less than complexity of other merging methods.