Bézier Extraction

Perhaps the most important concept to understand in smooth-spline FEA is called Bézier Extraction – extraction of the piecewise Bézier elements (composed of Bernstein polynomials) that constitute a basis-spline (aka B-spline). One can actually extract any arbitrary family of piecewise elements (e.g. Lagrange), but we’ll cover that in a future post.

The Bézier extraction process effectively is a process through which the continuity across the element boundaries is systematically reduced, which creates a new degree of freedom (i.e. node / control point), and a corresponding basis function, that had previously been linearly dependent on its neighboring degrees of freedom. A single iteration in this process is often referred to as knot insertion, while the complete process that results in a global \mathcal{C}^0 spline (or in some implementations, a global \mathcal{C}^{-1} spline) is called Bézier decomposition. Neither knot insertion nor Bézier decomposition change the resultant spline – each knot insertion step creates a new spline-space that produces an exactly equivalent spline (albeit with different parameterization).

Because of the prior linear dependence of the new node and of the exactness of this process, a linear transformation exists that relates the new basis function to the original spline basis functions. This linear transformation is can be trivially generated during the Bézier decomposition process – this constructed transformation is called the Bézier extraction operator.


Question: How is it that you can trivially generate the extraction operator through the decomposition process?

Figure 1 below demonstrates the general idea of constructing a transformation operator during a decomposition process. Let’s pretend that we want to decompose a line segment into two equivalent line segments. As shown in figure 1 we can insert a node at the midpoint of the line segment. While the midpoint could be trivially identified via averaging the two end-points, note that we can encode this subdivision via a 3\times2 matrix operating on a 2\times1 column vector of the two endpoints.

Figure 1: The Bisection Operator.
Whenever we arbitrarily select a location on a line segment, we are applying the action of sectioning operator – even though we may not ever explicitly construct the operator.

Ironically, the importance of Bézier extraction is not due to the extraction of individual Bézier components, but rather the use of the extraction operator to transform the extracted \mathcal{C}^0 basis functions back into the smooth-spline basis functions. This relationship is described in the equation below.

\mathbf{N} = \mathbf{C}^\textrm{g} \mathbf{B}


It’s dangerous to go alone; Let’s use an example to guide us

First we define the spline space to be a partitioning of the domain x\in [0, 1], into four \mathcal{P}^3 elements where all internal element interfaces are \mathcal{C}^2 continuous. The basis spline for this spline space is shown in figure 2 below. A challenge with implementing a general, smooth-spline finite element method on this spline-space is that, unlike a \mathcal{C}^0 basis functions or certain classes of \mathcal{C}^1 basis functions[1], we would need to define two reference elements that the finite element code could reference.

Figure 2: The basis spline for a four-element, \mathcal{P}^3 \mathcal{C}^2 partitioning of the unit-domain. the element boundaries are denoted by vertical dashed lines. Note that some basis functions, N_i, are supported (non-zero) in multiple elements. The portions of the basis functions that are supported by a given element are colored by a unique color assigned to each element.

Next we construct the global extraction operator by decomposing the \mathcal{P}^3 \mathcal{C}^2 spline into a \mathcal{P}^3 \mathcal{C}^0 spline, the latter of which is shown in figure 3 below.

Figure 3: The basis spline for a four-element, \mathcal{P}^3 \mathcal{C}^0 partitioning of the unit-domain. the element boundaries are denoted by vertical dashed lines. Note that some basis functions, N_i, are supported (non-zero) in multiple elements. The portions of the basis functions that are supported by a given element are colored by a unique color assigned to each element.

And here is the global extraction operator for this example

Global extraction operator for this example

And plugging this into the smoothness equation defined above we can more readily see how this operator reconstructs the \mathcal{P}^3 \mathcal{C}^2 spline basis functions from the \mathcal{P}^3 \mathcal{C}^0 spline basis functions.

Evaluating the matrix multiplication function:
\mathbf{N} = \mathbf{C}^\textrm{g} \mathbf{B}

A key insight that we can discern from figures 2 and 3 is that the amount of basis functions supported by each element in the \mathcal{P}^3 \mathcal{C}^k splines is invariant of the continuity, k. Thus, as shown in figure 4 below, we can identify square sections of the global extraction operator that operate on just the basis functions for a given element. We call these sub-matrices local extraction operators or element extraction operators and denote these as \mathbf{C}^\textrm{e}

Figure 4: Identifying the local extraction operators within the global extraction operator

So how does this relate to the finite element method?

The value of these local extraction operators is made clear in figure 5 below where we show a single reference Bézier element can be linearly transformed into a smooth-spline element. Not only does the local extraction operator define the transformation of the Bézier basis functions into the smooth-spline basis functions, but it can also be used to compute the transformation of the Bézier element’s nodes into the nodes of the smooth-spline element’s nodes.[2]

Figure 5: Using the local extraction operator to transform a reference element into an arbitrary smooth spline function

The overall effect of these local extraction operators is that we can easily adapt the traditional \mathcal{C}^0 finite element method into a smooth-spline finite element method. For example, below are two algorithms for computing the local element stiffness matrices, first for a \mathcal{C}^0 FEA code and then for a \mathcal{C}^k FEA code.

  • For e \in [1, \textrm{Number of Elements}]
    • For n_1 \in  [1, \textrm{Number of Basis Functions in Current Element}]
      • For n_2 \in  [1, \textrm{Number of Basis Functions in Current Element}]
        • k^{e}_{n_1, n_2} = \int_{\Omega_e} B^{e}_{n_1} B^{e}_{n_2} \ d\Omega_e
  • For e \in [1, \textrm{Number of Elements}]
    • For n_1 \in  [1, \textrm{Number of Basis Functions in Current Element}]
      • For n_2 \in  [1, \textrm{Number of Basis Functions in Current Element}]
        • k^{e}_{n_1, n_2} = \int_{\Omega_e} \left(C^{e} B^{e}_{n_1}\right) \left(C^{e} B^{e}_{n_2}\right) \ d\Omega_e

There you have it, a simple change is all it takes! And note that if \mathcal{C}^\textrm{e} was the identity matrix in the second example that it would be functionally equivalent to the first example. The construction of a smooth-spline finite element’s local stiffness matrix is a generalization the local stiffness matrix calculations found in the traditional \mathcal{C}^0 finite element method! In a future post we’ll dive deeper into global assembly operators in smooth-spline FEA, but for now I think this is a good place to stop.


Glossary of Symbols

\mathcal{P}^d: Polynomial of degree d
\mathcal{C}^k: k-Continuous
\mathcal{P}^d \mathcal{C}^k: Depending on the context this may refer to an entire spline-space, or a single spline-element, having these properties.
\mathbf{N} : The smooth (i.e. \mathcal{C}^{>0}) spline basis functions
\mathbf{B} : The \mathcal{C}^0 basis functions
\mathbf{C}^\textrm{g}: The global Bézier extraction operator
\mathbf{C}^\textrm{e}: The local or element Bézier extraction operator
\Omega_e: Domain of a finite element

Footnotes
[1] For example, the \mathcal{P}^3\mathcal{C}^1 Hermite basis functions
[2] These smooth-spline nodes are almost universally called spline control-points in literature, but hopefully this makes it clear why I prefer to call these smooth-spline nodes instead.

References
Borden, M.J., Scott, M.A., Evans, J.A. and Hughes, T.J.R. (2011), Isogeometric finite element data structures based on Bézier extraction of NURBS. Int. J. Numer. Meth. Engng., 87: 15-47. doi:10.1002/nme.2968

Scott, M.A., Borden, M.J., Verhoosel, C.V., Sederberg, T.W. and Hughes, T.J.R. (2011), Isogeometric finite element data structures based on Bézier extraction of T‐splines. Int. J. Numer. Meth. Engng., 88: 126-156. doi:10.1002/nme.3167

Cottrell, J. Austen., Yuri Bazilevs, and Thomas J.R. Hughes. Isogeometric Analysis: toward Integration of CAD and FEA. Wiley, 2009.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: