Blossoming

From CGAFaq

Blossoming is the term coined by Lyle Ramshaw (1987) for the process of converting a polynomial of degree $n$ in one variable to its blossom, a symmetric polynomial in $n$ variables each of degree one such that the original polynomial is recovered by substituting the same value for each variable. This poetic name has gained wide acceptance in computer graphics (Farin, 2001), though it soon emerged that the idea has a longer pedigree as polarization (Ramshaw, 1989). For example, polarizing the Pythagorean distance

$x^2 + y^2 + z^2$

gives the dot product,

$x_1 x_2 + y_1 y_2 + z_1 z_2 .$

This example also shows that blossoming is not limited to univariate polynomials. The motivating use for computer graphics is B-spline theory, where blossoming is an elegant and powerful tool.

A polynomial is symmetric in $n$ variables $t_1,\ldots,t_n$ if it is unchanged by any permutation of the variables. For example, elementary symmetric polynomials in three variables can be created by the substitutions

$\begin{align} 1 &\mapsto &1 \\ t &\mapsto &(t_1 + t_2 + t_3)/3 \\ t^2 &\mapsto &(t_1 t_2 + t_2 t_3 + t_3 t_1)/3 \\ t^3 &\mapsto &t_1 t_2 t_3 . \end{align}$

Consider the special case of a cubic Bézier curve parameterized over the interval $[0..1]$ . The curve is a polynomial function

$\bold{p}(t) = \bold{x}_0 + \bold{x}_1 t + \bold{x}_2 t^2 + \bold{x}_3 t^3 .$

If $\bold{P}$ is the blossom of $\bold{p}$ , the Bézier control points are

$\begin{align} \bold{p}_0 &= \bold{c}_{03} &= \bold{P}(0,0,0) ,\\ \bold{p}_1 &= \bold{c}_{12} &= \bold{P}(0,0,1) ,\\ \bold{p}_2 &= \bold{c}_{21} &= \bold{P}(0,1,1) ,\\ \bold{p}_3 &= \bold{c}_{30} &= \bold{P}(1,1,1) . \end{align}$

The de Casteljau algorithm can then be deduced as a simple consequence of blossom properties, as can curve splitting.

By definition, the blossom value $\bold{P}(t,t,t)$ equals the curve point $\bold{p}(t)$ , so this is what evaluation must compute. The first two control points are the blossom values $\bold{P}(0,0,0)$ and $\bold{P}(0,0,1)$ ; and since $\bold{P}$ is linear in its last argument we deduce that linear interpolation of these points will produce