A universal approach to blossoming with applications to Bernstein bases and Bézier curves for arbitrary function spaces

Bézier and B-spline curves and surfaces are fundamental tools in many branches of computational science and engineering: computer graphics and scientific visualization, computer aided design and manufacture, medical and biomedical imaging, computer art and architecture, computer games and animated movies all rely on Bézier and B-spline curves and surfaces. Blossoming is an elegant and potent tool for analyzing polynomial and piecewise polynomial curves and surfaces, and for developing the theory and applications of the corresponding Bézier and B-spline curves and surfaces. The blossom is particularly powerful for constructing recursive algorithms to evaluate, subdivide, differentiate, degree elevate, and change bases for Bézier and B-spline curves and surfaces.

The classical polynomial blossom is easy to define and is uniquely characterized by three simple properties: symmetry, multiaffinity, and a diagonal property. Thus the classical blossom of a degree \(n\) polynomial \(P(t)\) is the unique function \(p(u_1,\ldots ,u_n)\) that satisfies the following three axioms [7]: Standard properties, formulas, computations, and algorithms for Bézier and B-spline curves and surfaces, including affine invariance, the de Casteljau evaluation and subdivision algorithms for Bézier curves and surfaces, the de Boor recursive evaluation algorithm for B-splines, knot insertion and subdivision algorithms for B-splines, Marsden’s identity, all follow readily from blossoming.

Over the years blossoming has been extended in many directions: to quantum splines, to Müntz spaces, to \(Q\)-splines, to trigonometric splines, and to Chebyshev splines. These generalizations facilitate extending the Bernstein-Bézier and B-spline bases along with their standard properties, formulas, computations, and algorithms from polynomial spaces to these special function spaces. In each case a novel approach has been introduced to extend blossoming to the desired space of functions by altering either the multiaffine property or the diagonal property of the blossom.

The main goal of this paper is to finally understand at a fundamental level the general mathematical principles underlying blossoming and to provide a single unified approach that extends blossoming to all finite dimensional spaces of univariate functions without the need to reinvent blossoming for each new space of functions. The key observation is that elementary symmetric functions appear both in the blossoms of monomials and in the coefficients of polynomials. The coefficients of polynomials are elementary symmetric functions of the roots. The blossoms of monomials are elementary symmetric functions in the blossom parameters. To extend blossoming to arbitrary function spaces, we will link these two seemingly disparate manifestations of elementary symmetric functions.

We will also show that the analogues of the Bernstein-Bézier bases exist for all finite dimensional spaces of univariate functions and that as a consequence of blossoming the basic properties, formulas, computations, and algorithms listed above hold for all finite dimensional spaces of univariate functions. (Extensions to B-splines will be treated in a separate paper.) Moreover the analysis is not complicated and the computations are straightforward. Our investigation shows that the blossom depends not only on the function space, but also on the basis of the function space. Thus there are many different blossoms and consequently many different Bernstein bases for the same function space, a fact already evident from our investigation of quantum blossoms for polynomial spaces [10].

The blossom is central in the study of Bézier and B-spline curves and surfaces because the blossom provides the dual functionals for these bases. The dual functional property asserts that the coefficients \(\{P_k\}\) of any degree \(n\) polynomial \(P(t)\) relative to the Bernstein basis of degree \(n\) over the interval \([a,b]\) are given by the blossom \(p(u_1,\ldots ,u_n)\) evaluated at the end points of the parameter interval–that is, \(P_k=p(a^{\langle n-k\rangle },b^{\langle k\rangle })\), where \(c^{\langle k\rangle }\) denotes the \(k\)-tuple \((c,\ldots ,c)\). A similar dual functional property holds for B-splines: the coefficients of a spline \(S(t)\) relative to the corresponding B-spline basis are given by the blossom of \(S(t)\) evaluated at the knots.

Blossoms are polar forms, which are a classical topic in mathematics, but the incarnation of polar forms as blossoms and their application to Bézier and B-spline curves and surfaces emerged only in the 1980s in the work of Ramshaw [24‐26] and de Casteljau [4, 5]. Only recently (since the 1990s) have researchers become interested in generalizing and extending the classical notion of blossoming to certain finite dimensional function spaces, such as Müntz spaces [2], Chebyshev spaces [14], spaces of trigonometric polynomials [16], and other more general function spaces [6]. This new development came with the initial realization that by modifying only the multiaffine property, the polynomial blossom can be extended to Chebyshev spaces [14, 19‐22].

One important consequence of the classical blossom is the existence of a Bernstein basis over a finite interval. For the degree \(n\) polynomials on an interval \([a,b]\) this basis consists of \(n+1\) polynomials of exact degree \(n\): \(\{B_k^n(t;[a,b])\}_{k=0}^n\), where \(B_k^n\) vanishes \(k\) times at \(a\) and \(n-k\) times at \(b\), \(k=0,\ldots ,n\). The dual functional property relates this Bernstein basis to the blossom in the following way: For every degree \(n\) polynomial \(P(t)\) we have \(P(t)=\sum _{k=0}^n p(a^{\langle n-k\rangle },b^{\langle k\rangle })B_k^n(t;[a,b])\), where \(p(u_1,\ldots ,u_n)\) is the blossom of \(P(t)\). That is, the blossom gives the coefficients in the representation of a polynomial in the Bernstein basis. One direct consequence of this dual functional property is the Marsden identity, which can itself be used as a starting point to construct more general blossoms as outlined in Sect. 2 of this paper. Natural questions then to ask were if such Bernstein bases can be constructed in any finite dimensional Chebyshev space, and then whether a certain type of blossom can be constructed in that Chebyshev space. These questions were answered affirmatively in [21] for extended Chebyshev systems.

Ramshaw [24‐26] observed that the classical blossom can be viewed as the intersection of tangent hyperplanes or oscillating flats. This definition was later extended by Pottman to Chebyshev spaces in [23] and used by Goodman and Mazure to study Chebyshev spaces in [14]. The blossom \(f(u_1,\ldots ,u_n)\) of a function \(F\) in a Chebyshev space is defined as the intersection of the oscillating flats to the curve \(F\) at the distinct values \(\{u_i\}_{i=1}^n\). This Chebyshev blossom is symmetric and satisfies the usual diagonal property, but it is not multiaffine. Rather this Chebyshev blossom is pseudo-affine in the sense that this blossom is monotone in each variable. The blossom for Chebyshev spaces can be used to develop a full Chebyshev–Bernstein theory with the corresponding dual functional property and de Casteljau type evaluation and subdivision algorithms as well as a corresponding theory of B-splines. Very recently, using this general framework, Chebyshev–Bernstein bases and a Chebyshev blossom for Müntz spaces were constructed in [1, 2].

Blossoming for trigonometric polynomials was first introduced in [13]. Trigonometric splines first appeared in [15] and were studied extensively in many later works: see [17, 18], and [16] for a survey.

Yet another approach to blossoming, Bernstein polynomials, Bézier curves, B-splines, and many other applications emerged in 2010, when new type of polynomial blossoms, quantum blossoms, were introduced and studied in [10, 11, 28‐30]. The main idea of this approach is to keep the symmetry and multiaffine properties, but to change the diagonal property by replacing the diagonal vector \((t,\ldots ,t)\) by either \((t,qt,\ldots ,q^{n-1}t)\) (\(q\)-blossom), or \((t,t-h,\ldots ,t-(n-1)h)\) (\(h\)-blossom), or \((t,g(t),\ldots ,g^{[n-1]}(t))\) with \(g^{[k]}(t)=q^kt+(q^k-1)h/(q-1)\) (\((q,h)\)-blossom). In addition to fully investigating these quantum blossoms, the corresponding Bernstein-Bézier and B-spline theories have also been thoroughly investigated in [3, 10‐12, 27, 29, 30]. These new types of quantum blossom can be used to construct and to recursively evaluate not only the corresponding quantum Bézier curves, but also their quantum derivatives, thus replicating one of the most important properties of the classical blossom which is crucial as well for constructing quantum B-splines, where the classical derivative is replaced by the quantum derivative.

Hence there are several different ways to extend the blossom in order to investigate either more general function spaces or more general derivatives for polynomial spaces.

Thus recent research in splines for finite dimensional univariate function spaces has diverged into a variety of special cases. Understanding why blossoming is a general property of all finite dimensional univariate function spaces and their associated bases and simplifying and unifying blossoming for all finite dimensional univariate function spaces under one simple rubric is one of the main goals of this paper.

Blossoming is one of the most powerful and ubiquitous methods for developing the theory and applications of Bézier and B-spline curves and surfaces not only for polynomial and piecewise polynomial spaces but also for non-polynomial and piecewise non-polynomial spaces such as trigonometric splines and Chebyshev splines. Here we will build a blossoming theory for arbitrary finite dimensional univariate function spaces.

The classical blossom satisfies three axioms: symmetry, multi-affinity, and a simple diagonal property. Variants of the blossom can be constructed by altering one of these three properties. Over the past few decades, researchers have constructed blossoms for Müntz spaces [1, 2], trigonometric spaces [13, 17], and Chebyshev spaces [14, 19‐22], by keeping the symmetry and diagonal properties of the blossom and replacing the multiaffine property by a pseudo-affine property. In contrast, to blossom quantum splines, the authors keep the symmetry and multiaffine properties and change instead the diagonal property [10, 12, 28‐30]. The advantage of keeping the multiaffine property is that the computations and proofs remain simple and stay similar to the classical polynomial case because the blossom is still a multiaffine polynomial, even if the functions to be blossomed are no longer polynomials. Indeed we shall see in Sects. 3.1–3.4 that standard properties, formulas, computations, and algorithms for Bernstein bases and Bézier curves and surfaces, including the dual functional property, partition of unity, affine invariance, Marsden’s identity, and the de Casteljau evaluation and subdivision algorithms for Bézier curves and surfaces all generalize readily to arbitrary finite dimensional function spaces using the symmetry and multiaffine properties of the blossom. Therefore to extend blossoming from polynomials to arbitrary finite dimensional function spaces, we shall keep the symmetry and multiaffine properties and change only the diagonal property of the blossom.

By the multiaffine property, the \(R\)-blossom \(f(u_1,\ldots ,u_n)\) is a multivariate polynomial of degree at most one in each variable. Thus all the complexity of the \(R\)-blossom is consigned to the \(R\)-diagonal property and to the functions \(R=(r_1(t),\ldots ,r_n(t))\). Hence for a given function space \({{\mathcal {F}}}=\textrm{span}\{F_k(t)\}_{k=0}^n\), we need to know: (i) what are the functions \(R=(r_1(t),\ldots ,r_n(t))\), and (ii) how do we compute these functions?

Recall that for classical splines and for quantum \(q\)-splines, we have the following contrasting formulas for the diagonal property [7, 27]: \(f(t,\ldots ,t)=F(t)\) for the classical blossom and \(f(t,qt,\ldots ,q^{n-1}t)=F(t)\) for the quantum \(q\)-blossom. Can these diagonal properties give us any clues into the \(R\)-diagonal property for an arbitrary function space \({{\mathcal {F}}}=\textrm{span}\{F_k(t)\}_{k=0}^n\)?

The key insight comes from the Marsden identity. The left-hand side of Marsden’s identity is [7, 27]: \((x-t)^n=x^n-ntx^{n-1}+\cdots +(-1)^nt^n\) with roots \(x=t,\ldots ,t\) and coefficients \(1,-nt,\ldots ,(-1)^nt^n\) for classical splines, and \((x-t)(x-qt)\cdots (x-q^{n-1}t)=x^n-(1+q+\cdots +q^{n-1})t x^{n-1}+\cdots +(-1)^n q^{n\atopwithdelims ()2}t^n\) with roots \(x=t,qt,\ldots ,q^{n-1}t\) and coefficients \(1,-(1+q+\cdots +q^{n-1})t,\ldots ,(-1)^n q^{n\atopwithdelims ()2}t^n\) for quantum \(q\)-splines.

Thus the roots of the left-hand side of Marsden’s identity are where we evaluate the blossom for the diagonal property and the coefficients of \(x^n,x^{n-1},\ldots ,1\) on the right-hand side form the corresponding polynomial basis.

We can now turn these observations around. Set \(F_0(t)=1\) so that \({{\mathcal {F}}}\) contains the constants and consider the polynomialThe roots \(r_1(t),\ldots ,r_n(t)\) on the right-hand side are where we evaluate the \(R\)-blossom for the diagonal property and the coefficients of \(x^n,x^{n-1},\ldots ,1\) on the left-hand side are our basis for the space \({{\mathcal {F}}}=\textrm{span}\{F_k(t)\}_{k=0}^n\). Notice that the functions \(r_1(t),\ldots ,r_n(t)\) need not be in the space \({{\mathcal {F}}}\). Moreover, these roots may even take on complex values, but if the functions \(F_0(t),\ldots ,F_n(t)\) are real-valued, the values of the \(R\)-blossom evaluated along the \(R\)-diagonal are also real.

We shall now establish the existence and the uniqueness of this \(R\)-blossom.

Notice that the \(R\)-blossom of \(F(t)\in {{\mathcal {F}}}\) depends not only on the function space \({{\mathcal {F}}}\) but also on the choice of the basis functions \(F_0(t),\ldots ,F_n(t)\) for the space \({{\mathcal {F}}}\). A different basis for \({{\mathcal {F}}}\) would give a different left-hand side in (1) and therefore different roots \(R=(r_1(t),\ldots ,r_n(t))\) on the right-hand side of (1). Even a simple change of basis such as multiplying one or more of the basis functions \(F_0(t),\ldots ,F_n(t)\) by non-zero constants will result in different roots \(R=(r_1(t),\ldots ,r_n(t))\) on the right-hand side of (1). This should not be surprising, since exactly the same phenomenon occurs with polynomial spaces: for polynomials we get different diagonal properties for classical splines and for quantum splines, but locally both spaces are polynomial spaces and the polynomial basis functions differ only by distinct constant factors. So we already have different notions of blossoming for polynomials, depending on our choice of polynomial basis. Other choices are indeed possible. For example for cubic polynomials if we choose the monomial basis \(1,t,t^2,t^3\), then (1) becomes \(x^3-tx^2+t^2x-t^3=(x-t)(x-it)(x+it)\), so in this case the diagonal property of the blossom would be \(f(t,it,-it)=F(t)\).

To actually compute the functions \(R=(r_1(t),\ldots ,r_n(t))\) at any particular value \(t=t^*\), we need to find the roots \(r_1(t^*),\ldots ,r_n(t^*)\) of the polynomial \(P(x)=x^n-F_1(t^*)x^{n-1}+\cdots +(-1)^nF_n(t^*)\). For \(n\le 4\) there are explicit formulas for these roots; for \(n\ge 5\) numerical methods may be required.

Having built a blossom for arbitrary finite dimensional univariate function spaces, in this section we will show how we can use this new blossom to develop the analogues of Bernstein bases and Bézier curves and surfaces for these function spaces. Since the surfaces we have in mind are tensor product surfaces, we concentrate our exposition on curves, since the results for curves easily extend to tensor product surfaces. We will also use the \(R\)-blossom to extend standard properties, formulas, computations, and algorithms for classical Bernstein bases and Bézier curves, including the de Casteljau evaluation and subdivision algorithms, the dual functional property of the blossom, partition of unity, affine invariance, interpolation of end points, a change of basis formula, and Marsden’s identity to arbitrary finite dimensional function spaces.

Here we briefly reexamine some well-known function spaces, including trigonometric polynomials, and their blossoms in light of the general theory of \(R\)-blossoming.

We begin with two linearly independent functions \(\gamma _1(t)\) and \(\gamma _2(t)\). Define the functions \(F_k(t)={n\atopwithdelims ()k}\gamma _1(t)^{n-k}\gamma _2(t)^k\), \(k=0,\ldots ,n\), and set \({{\mathcal {F}}}=\textrm{span}\{F_k(t)\}_{k=0}^n\). Following our approach in Sect. 2, we find that the left-hand side of Marsden’s identity isReplacing \(x\) by \(\gamma _2(x)/\gamma _1(x)\) in (20) and multiplying both sides by \(\gamma _1(x)^n\) yieldsThere are several well-known interesting examples: Additional interesting examples can be found in [6].

We can now apply the \(R\)-blossoming technique to develop a blossoming theory for the space \({{\mathcal {F}}}=\textrm{span}\{F_k(t)\}_{k=0}^n\); the only difference is that we use the homogeneous (multi-linear) variant of the standard polynomial blossom in place of the multiaffine blossom in case \(F_0(t)\ne 1\). In general, the roots of the left-hand side of Marsden’s identity (20) are \(x=\gamma _2(t)/\gamma _1(t)\). To avoid rational functions and to avert possible zeros in the denominator, we adopt the usual strategy and use the homogeneous multilinear blossom in place of the standard multiaffine blossom. Thus the \(\gamma \)-blossom of a function \(F(t)\in {{\mathcal {F}}}\) is the unique symmetric multi-linear function \(f((u_1,v_1),\ldots ,(u_n,v_n))\) such thatThe existence and uniqueness of this \(\gamma \)-blossom is a special case of Theorem 1.

We can also define \(\gamma \)-Bernstein bases and \(\gamma \)-Bézier curves just as in Sect. 3, and we can extend standard formulas and algorithms for classical Bernstein bases and Bézier curves for arbitrary function spaces generated from two linearly independent functions \(\gamma _1(t)\) and \(\gamma _2(t)\). All these results are essentially just special cases of the general theory of \(R\)-blossoming.