Linear-Time Algorithm for Computing the Bernstein–Bézier Coefficients of B-spline Basis Functions. (January 2023)

• Record Type: Journal Article
• Authors: Chudy, Filip; Woźny, Paweł
• Is Part Of: Computer aided design. Volume 154(2023)
• Publication Date: 2023-01
• Subjects: B-spline functions -- Bernstein–Bézier form -- Recurrence relations -- Bézier curves -- B-spline curves and surfaces -- De Boor–Cox algorithm; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103434
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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é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é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. Graphical abstract: Highlights: A new differential-recurrence relation for the B-spline functions of the same degree A fast method of finding the Bernstein–Bézier coefficients of B-spline functions The evaluation of B-spline curves and tensor product surfaces is accelerated The method is numerically stable A simplified case of uniform B-splines is included