Partially Nested Hierarchical Refinement of Bivariate Tensor-Product Splines with Highest Order Smoothness

Abstract

The established construction of hierarchical B-splines starts from a given sequence of nested spline spaces. In this paper we generalize this approach to sequences formed by spaces that are only partially nested. This enables us to choose from a greater variety of refinement options while constructing the underlying grid. We identify assumptions that allow to define a hierarchical spline basis, to establish a truncation mechanism, and to derive a completeness result. Finally, we present an application to surface approximation that demonstrates the potential of the proposed generalization.

1 Introduction

Hierarchical tensor-product B-splines are one of the major approaches to perform local refinement in geometric modeling and isogeometric analysis, besides splines defined by control meshes with T-junctions (T-splines), locally refined (LR) splines and polynomial splines over hierarchical T-meshes (PHT-splines). See [3, 16,17,18] and the references therein for more information on the latter three.

Hierarchical spline refinement can be traced back to the work of Forsey and Bartels [6] on surface design using locally defined control meshes. Based on a selection mechanism, a system of basis functions spanning the resulting hierarchical spline space was established by Kraft in his PhD thesis [14]. Another basis, which consists of truncated hierarchical B-splines, possesses improved properties (increased locality, partition of unity and strong stability) and has been established more recently [8]. Its properties regarding stability, completeness and approximation power have been analyzed in greater detail [9, 19, 22].

Hierarchical B-splines have found numerous applications due to their good mathematical properties. They were used for surface reconstruction in Computer-Aided Design [10, 12]. Additionally, they were employed for performing numerical simulations using the powerful framework of isogeometric analysis [1, 2, 15, 20]. The recent article [7] discusses the potential of the truncated basis for geometric design and isogeometric analysis.

In addition to the work on applications, several authors proposed various extensions and generalizations of the hierarchical construction. These include extensions to Powell-Sabin splines [21], box splines and doubly hierarchical splines as instances of more general generating systems [24], B-splines on triangulations [11], hierarchical T-splines [5], and functions defined by subdivision algorithms [23, 25].

The established construction of hierarchical B-splines starts from a given sequence of nested spline spaces. As a consequence, if the refinement process inserts knot lines at some level, then they will automatically be present at all higher levels, even if they are not needed in all parts of the domain. This may lead to an unnecessary increase of the number of degrees of freedom. It should be noted that this limitation is not present when using alternative constructions such as T-splines, LR splines or PHT-splines.

In order to overcome the limitation caused by the sequential nature of hierarchical B-spline refinement, while maintaining their good mathematical properties, we extend the construction to sequences formed by spaces that are only partially nested. The proposed generalization enables us to choose from a greater variety of refinement options while constructing the underlying grid. This additional flexibility is potentially useful when designing surfaces that possess creases or similar features, and a related technique has been developed in the context of subdivision surface modeling [13]. It might also open new perspectives for adaptivity in isogeometric analysis by providing the opportunity to use different refinement techniques (such as h- versus p-refinement) in different parts of the computational domain.

In order to keep the presentation simple, in this paper we limit ourselves to the discussion of partially nested refinement for bivariate spline spaces of uniform degrees. We identify a number of assumptions that enable the definition of a hierarchical spline basis, of a truncation operation to obtain the partition of unity property, and the derivation of a completeness result.

The remainder of the paper consists of seven sections. We describe the framework of our construction in the next section and establish a hierarchical spline basis in Sect. 3. We then derive a characterization of the space spanned by the basis and adapt the definition of the truncation operation to the non-nested setting in the next two sections. The completeness properties of the basis are analyzed in Sect. 6. We then present an application to least-squares approximation that demonstrates the power of the new construction before concluding the paper with suggestions for future work.

2 Preliminaries

We consider a finite sequence of bivariate tensor-product spline spaces

$$\begin{aligned} V^\ell = \mathrm {span}B^\ell , \quad \ell =1,\ldots ,N, \end{aligned}$$

which are spanned by spline bases $B^\ell$. The upper index $\ell$ will be called the level. Each of the spline spaces is defined on the open unit square $(0,1)^2$.

The spline bases $B^\ell$ consist of tensor-product B-splines that are defined by two open knot vectors with boundary knots 0 and 1. We consider a uniform polynomial degree $\mathbf {p}=(p_x,p_y)$ and use only single knots except for the boundary knots that have multiplicity $p_x+1$ and $p_y+1$, respectively. The supports of the basis functions are axis-aligned boxes in $(0,1)^2$.

We use the subspace relation to restrict the natural ordering of the levels to a partial ordering. We say that level k precedes level $\ell$, denoted by $k\prec \ell$, if k is less than $\ell$ and $V^k$ is a subspace of $V^\ell$, i.e.

$$\begin{aligned} k\prec \ell \quad \Leftrightarrow \quad k<\ell \; \text{ and } \; V^k\subseteq V^\ell . \end{aligned}$$

(1)

The spaces are not necessarily nested. If they are, however, then the finer space is assumed to have the higher level, i.e.

$$\begin{aligned} V^k \subset V^\ell \; \Rightarrow \; k \prec \ell . \end{aligned}$$

(2)

Any finite sequence of spline spaces can be re-ordered such that this condition is satisfied.

We present an example that will be used throughout the paper to illustrate the discussion of notions and results.

Example

We consider $\mathcal C^1$-smooth biquadratic tensor-product spline spaces ($p_x=p_y=2$) on dyadically refined knots,

$$\begin{aligned} D^{r,s} = \mathcal S^2(0,0,0,\frac{1}{2^r},\ldots ,\frac{2^r-1}{2^r},1,1,1)\otimes \mathcal S^2(0,0,0,\frac{1}{2^s},\ldots ,\frac{2^s-1}{2^s},1,1,1), \end{aligned}$$

where $\mathcal S^2$ denotes the univariate spline space defined by a given knot sequence, with positive integers r, s. Among them we use the spaces

$$\begin{aligned}&V^1=D^{3,3}, \; V^2=D^{4,3}, \; V^3=D^{3,4}, \nonumber \\&V^4=V^5=D^{4,4}, \; V^6=D^{5,4}, \; V^7=D^{4,6}, \end{aligned}$$

(3)

which define the partial ordering

(4)

of the seven levels.       $\Diamond$

The functions in all spline spaces $V^\ell$ are $\mathcal C^{\mathbf s}$-smooth on $(0,1)^2$, where the order of smoothness is given by

$$\begin{aligned} \mathbf s=(p_x-1,p_y-1). \end{aligned}$$

(5)

More precisely, they possess continuous partial derivatives of order $p_x-1$ and $p_y-1$ with respect to x and y, respectively. We shall denote the set of all functions on an open subset $X\subseteq (0,1)^2$ with this smoothness as $\mathcal C^{\mathbf s}(X)$.

Fig. 1.

The subdivision of the domain into patches (a). The numbers (r, s) in each patch specify the dyadically refined knot sequences that define the associated spline spaces. The corresponding partially nested hierarchical mesh (b).

In addition to the spline spaces we consider an associated sequence of open sets

$$\begin{aligned} \pi ^\ell \subseteq (0,1)^2, \quad \ell =1,\ldots ,N, \end{aligned}$$

which will be called patches. We assume that these are mutually disjoint,

$$\begin{aligned} \pi ^\ell \cap \pi ^k\ne \emptyset \; \Rightarrow \; \ell =k. \end{aligned}$$

We use the closures $\overline{\pi ^\ell }$ of the patches to define the domain

$$\begin{aligned} \varOmega = \text{ int }\bigg (\bigcup _{\ell =1}^N \overline{\pi ^\ell }\bigg ) \subseteq (0,1)^2. \end{aligned}$$

The part of the boundary of each patch that is shared with patches of a lower level,

$$\begin{aligned} \varGamma ^\ell = \bigcup _{k=1}^{\ell -1}\overline{\pi ^k} \cap \overline{\pi ^\ell }, \end{aligned}$$

is called the constraining boundary of the patch $\pi ^\ell$. Note that the constraining boundary may be empty. In particular we have $\varGamma ^1=\emptyset$.

Example

We consider again the spaces (3), which are defined by the dyadically refined knot vectors. Figure 1a visualizes an associated sequence of patches, which defines a subdivision of the domain $\varOmega$. In this case, the domain is also the unit square. Additionally, Fig. 1b shows the knot lines of the spline spaces within each patch.

      $\Diamond$

We conclude this section by defining the partially nested hierarchical spline space

$$\begin{aligned} H = \{ s\in \mathcal C^{\mathbf s}(\varOmega ) \; \text{: }\; s|_{\pi ^\ell }\in V^\ell |_{\pi ^\ell } \; \forall \ell =1,\ldots ,N\}. \end{aligned}$$

(6)

It consists of all the $\mathcal C^{\mathbf s}$-smooth functions with the property that their restrictions $s|_{\pi ^\ell }$ to the patches are contained in the associated spline spaces $V^\ell |_{\pi ^\ell }$. In particular, the space of tensor-product polynomials of degree $\mathbf {p}$, restricted to the domain $\varOmega$, is a subspace of H.

3 Basis Functions

We define the basis by a selection procedure, which generalizes the definition of Kraft’s basis for hierarchical B-splines. This procedure selects elements of each spline basis $B^\ell$. Among all B-splines that do not vanish on the patch $\pi ^\ell$, we select the ones that take zero values on the constraining boundary $\varGamma ^\ell$ of that patch, i.e.,

$$\begin{aligned} K^\ell = \{\beta ^\ell \in B^\ell \; \text{: }\; \beta ^\ell |_{\pi ^\ell }\ne 0 \quad \mathrm {and} \quad \beta ^\ell |_{\varGamma ^\ell } = 0\}. \end{aligned}$$

Each set $K^\ell$ of selected functions defines the shadow of the associated patch $\pi ^\ell$,

$$\begin{aligned} \hat{\pi }^\ell = \mathrm {supp}K^\ell = \bigcup _{\beta ^\ell \in K^\ell } \mathrm {supp}\beta ^\ell . \end{aligned}$$

We collect the selected B-splines of all levels into the set

$$\begin{aligned} K = \bigcup _{\ell =1}^N K^\ell . \end{aligned}$$

(7)

We will denote this set of functions as PNHB-splines, since it consists of hierarchical B-splines defined by a partially nested sequence of spline spaces.

Example

We consider the PNHB-splines on the subdivision of the domain which was shown in Fig. 1a. The selected functions for the levels 2 and 6 are visualized in Fig. 2a and b.

The constraining boundary of $\pi ^2$ consists of the line segment on the border with $\pi ^1$. The set $K^2$ consists of 30 tensor-product B-splines (note the Greville points on the domain boundary). The shadow defined by them extends into the patches $\pi ^4$ and $\pi ^7$, covering $\pi ^4$ fully and $\pi ^7$ partially.

The constraining boundary of $\pi ^6$ consists of three line segments. The set $K^6$ contains 144 tensor-product B-splines. The shadow defined by them is equal to the patch, since the only non-constraining patch boundary is located on the boundary of the domain $\varOmega$.       $\Diamond$

Fig. 2.

Constraining boundaries (dark blue line segments), shadows (blue and light blue) and selected basis functions (represented by their Greville points, which are shown as red dots) of the patches (shown in blue) $\pi ^2$ (a) and $\pi ^6$ (b) for the domain subdivision shown in Fig. 1. Patches of lower levels are shown in green. For the latter patch, the shadow is equal to the patch itself. (Color figure online)

The following condition is essential for proving the linear independence of the PNHB-splines:

Assumption

If the shadow $\hat{\pi }^\ell$ of the patch of level $\ell$ intersects another patch $\pi ^k$ of a different level k, then the first level is lower than the second one,

$$\begin{aligned} \hat{\pi }^\ell \cap \pi ^k \ne \emptyset \quad \Rightarrow \quad \ell \le k. \end{aligned}$$

(SOA)

This will be called the Shadow Ordering Assumption (SOA).

We will use this assumption in the remainder of the paper. Since we will make several further assumptions throughout the paper, we provide Table 1 containing their names and acronyms, in order to guide the reader.

Table 1. Assumptions and acronyms.

SOA enables us to obtain our first result:

Theorem 1

The PNHB-splines are linearly independent on $\varOmega$ if SOA holds.

Proof

The proof of linear independence follows an idea originally formulated in [14], see also [8]. However, we will repeat it here in order to keep this paper self-contained and in order to adapt it to the current setting. We need to prove the implication

$$\begin{aligned} \sum _{\ell =1}^N \sum _{\beta ^\ell \in K^\ell }d_{\beta ^\ell }\beta ^\ell =0 \;\; \Rightarrow \;\; d_{\beta ^\ell }=0\;\; \forall \beta ^\ell \in K^\ell \; \forall \ell =1,\ldots ,N. \end{aligned}$$

(8)

We first restrict the sum in (8) to $\pi ^{1}$. Due to SOA only functions $\beta ^1\in K^1$ are non-zero on $\pi ^{1}$. The local linear independence of the B-splines $B^1$ gives $d_{\beta ^1}=0$ for all $\beta ^1\in K^1$. This implies that the sum in (8) involves only functions with $\ell >1$.

We now consider the restriction of the sum to $\pi ^{2}$. Again, according to SOA only the functions $\beta ^2\in K^2$ take non-zero values there. As the B-splines in $B^2$ are locally linearly independent, we conclude that $d_{\beta ^2}=0$ for all $\beta ^2\in K^2$. By repeatedly using the above argument, we eventually exhaust all the terms in (8), which concludes the proof of linear independence.       $\square$

While the selection mechanism and SOA guarantee linear independence, they do not ensure that the spline space spanned by PNHB-splines contains a class of functions that guarantees certain approximation properties, such as tensor-product polynomials of degree $\mathbf {p}$. This is shown in the following example:

Example

We consider the two biquadratic spline spaces

$$\begin{aligned} V^1=D^{3,0},\; V^2=D^{1,1} \end{aligned}$$

(9)

and the two patches

$$\begin{aligned} \pi ^1=(0,\frac{1}{2})\times (0,1), \quad \pi ^2=(\frac{1}{2},1)\times (0,1). \end{aligned}$$

(10)

The first set $K^1$ of selected functions consists of 18 tensor-product B-splines and defines the shadow $\hat{\pi }^1=(0,\frac{3}{4})\times (0,1)$. The second set $K^2$ of selected functions contains only 4 functions. The functions in $K^1\cup K^2$ are linearly independent but cannot represent any biquadratic function on $\varOmega$. This can be seen easily by analyzing the space which is spanned by the 4 functions in $K^2$ and noting that only these functions take non-zero values on $(\frac{3}{4},1)\times (0,1)$.       $\Diamond$

4 The Spline Space

Consequently, we need to introduce further assumptions. We replace SOA by a stronger condition, which will be used in the remainder of this paper.

Assumption

If the shadow $\hat{\pi }^\ell$ of the patch of level $\ell$ intersects another patch $\pi ^k$ of a different level k, then the first level precedes the second one,

$$\begin{aligned} \hat{\pi }^\ell \cap \pi ^k \ne \emptyset \quad \Rightarrow \quad \ell =k \quad \text{ or } \quad \ell \prec k. \end{aligned}$$

(SCA)

This will be called the Shadow Compatibility Assumption (SCA).

In other words, the shadow $\hat{\pi }^\ell$ intersects only patches that correspond to spaces containing $V^\ell$ as a subspace.

Example

We consider again the situation shown in Figs. 1 and 2. The shadow $\hat{\pi }^2$ intersects $\pi ^4$ and $\pi ^7$. SCA is satisfied since $2\prec 4$ and $2\prec 7$, see (4).       $\Diamond$

This condition obviously implies (SOA). However, it turns out that SCA does not yet suffice to prove that the space spanned by the PNHB-splines contains a class of functions, which would guarantee certain approximation properties (e.g. polynomials). We need to impose a condition on the location of the constraining boundaries.

Assumption

For each level $\ell$, the constraining boundary $\varGamma ^\ell$ of the patch $\pi ^\ell$ is aligned with the knot lines of the spline space $V^\ell$. This will be called the Constraining Boundary Alignment (CBA) condition.

More precisely, the constraining boundary $\varGamma ^\ell$ is either empty or is formed by horizontal segments, vertical segments and isolated vertices, where not all these features need to be present. We assume that the segments are all located on knot lines of $V^\ell$ and that the vertices are intersections of knot lines.

We will use both assumptions CBA and SCA in the remainder of the paper. Under these assumptions we can characterize the spline space that is generated by the PNHB-splines:

Theorem 2

The PNHB-splines span the partially nested hierarchical spline space H if both SCA and CBA are satisfied.

We will need a technical lemma to prove this result. This lemma uses the notion of homogeneous boundary conditions of order $\mathbf {s}$. A function f is said to satisfy these conditions at a point (x, y) if $(\vartheta f)(x,y)=0$, where the operator

$$\begin{aligned} \vartheta = \Big (\frac{\partial ^i}{\partial x^i}\frac{\partial ^j}{\partial y^j}\Big )_{i=0,\ldots ,s_x; j=0,\ldots ,s_y} \end{aligned}$$

transforms a function into a matrix of dimension $\mathbf {p}$ that contains all the partial derivatives up to order $\mathbf {s}$. (Note here that 0 denotes the null matrix of dimension $\mathbf {p}$, not a scalar.) In particular, this operator contains the evaluation of its argument as its first element.

Lemma 1

The selected functions of level $\ell$ span the subspace

$$\begin{aligned} \mathrm {span}K^\ell |_{\pi ^\ell } = \{f\in V^\ell \; \text{: }\; (\vartheta f)|_{\varGamma ^\ell }=0\}|_{\pi ^\ell } \end{aligned}$$

of the associated spline space $V^\ell |_{\pi ^\ell }$ on the patch $\pi ^\ell$, which consists of the restrictions $f|_{\pi ^\ell }$ of all functions $f \in V^\ell$ that satisfy homogeneous boundary conditions of order $\mathbf {s}$ on the constraining boundary $\varGamma ^\ell$, provided that CBA holds.

Proof

First, we show that all selected functions of level $\ell$ satisfy the homogeneous boundary conditions of order $\mathbf {s}$ on the constraining boundary $\varGamma ^\ell$.

Consider a selected tensor-product B-spline $\beta ^\ell \in K^\ell$. None of the points $(x,y)\in \varGamma ^\ell$ of the constraining boundary belongs to the interior of the support $\mathrm {supp}\beta ^\ell$. This point thus either belongs to the support’s boundary, or it is even farther away. The tensor-product B-spline $\beta ^\ell$ satisfies homogeneous boundary conditions of order $\mathbf {s}$ at (x, y) in both cases, since it is $\mathcal C^{\mathbf {s}}$-smooth.

Second, we show that the restriction $f|_{\pi ^\ell }$ of any function $f\in V^\ell$, which satisfies the homogeneous boundary conditions of order $\mathbf {s}$ on the constraining boundary $\varGamma ^\ell$, can be represented as a linear combination of the selected functions $K^\ell$. Obviously, the restriction possesses a representation of the form

$$\begin{aligned} f(\mathbf x) = \sum _{\begin{array}{c} \beta ^\ell \in B^\ell \\ \mathrm {supp}\beta ^\ell \cap \pi ^\ell \ne \emptyset \end{array}} c_{\beta ^\ell } \beta ^\ell (\mathbf x), \quad \mathbf x\in \pi ^\ell . \end{aligned}$$

(11)

We consider a function $\beta ^\ell \in B^\ell \setminus K^\ell$ that does not vanish on $\pi ^\ell$. There exists an isolated vertex $\mathbf {v}$ or a (horizontal or vertical) segment L of the constraining boundary such that $\beta ^\ell$ takes non-zero values there.

In the case of an isolated vertex, the matrix $(\vartheta f)(\mathbf {v})$ depends on $p_x\times p_y$ spline coefficients due to CBA, and one of them is $c_{\beta ^\ell }$. The matrix has the same dimensions, cf. (5), and the linear mapping that transforms the spline coefficients into the matrix elements has full rank, simply because the spline function can take any values of $(\vartheta f)(\mathbf {v})$. Thus we conclude that $c_{\beta ^\ell }=0$ if $(\vartheta f)(\mathbf {v})=0$.

In the case of a segment L we choose a (sub-) segment $L'$ which is contained in only one knot span, and consider the tensor-product Bernstein–Bézier (BB) representation of f with respect to a sufficiently small axis-aligned box in $\pi ^\ell$ with this segment on its boundary. More precisely, this box is chosen such that it is simultaneously located within $\pi ^\ell$ and in one of the tensor-product knot spans of $V^\ell$.

The elements of the matrix $(\vartheta f)|_{L'}$ depend on the $p_x+1$ columns (each of height $p_y$) of adjacent BB coefficients for a horizontal segment, and on the $p_y+1$ rows (each of width $p_x$) of adjacent BB coefficients for a vertical segment. The matrix is equal to the null matrix on $L'$ if and only if all these BB coefficients are equal to zero.

Due to CBA, these BB coefficients depend on the same number of spline coefficients, and $c_{\beta ^\ell }$ is one of them. The linear mapping that transforms the spline coefficients into the considered BB coefficients has full rank, since any tensor-product polynomial of degree $\mathbf {p}$ is contained in the spline space $V^\ell$. Thus we conclude that $c_{\beta ^\ell }=0$ if $(\vartheta f)|_{L'}=0$.       $\square$

We now proceed with the proof of the Theorem:

Proof

(Theorem 2 ). Given a function $f\in H$, we consider its restriction to the patch of level 1 and find a representation

$$\begin{aligned} f(\mathbf x)= \sum _{\beta ^1\in K^1} c_{\beta ^1}\beta ^1(\mathbf x), \quad \mathbf x\in \pi ^1. \end{aligned}$$

(12)

It exists since $f|_{\pi ^1}\in V|_{\pi ^1}$ according to the definition of H and because the associated constraining boundary is empty. We use this local representation to derive the globally defined level 1 representation

$$\begin{aligned} f^1(\mathbf x)= \sum _{\beta ^1\in K^1} c_{\beta ^1}\beta ^1(\mathbf x), \quad \mathbf x\in \varOmega . \end{aligned}$$

We now proceed by iterating over the remaining levels $\ell =2,\ldots ,N$. In each level, we consider the restriction of

$$\begin{aligned} f-\sum _{k=1}^{\ell -1} f^k \end{aligned}$$

to the patch $\pi ^\ell$ and its local representation

$$\begin{aligned} f(\mathbf x)-\sum _{k=1}^{\ell -1} f^k(\mathbf x)= \sum _{\beta ^\ell \in K^\ell } c_{\beta ^\ell }\beta ^\ell (\mathbf x), \quad \mathbf x\in \pi ^\ell , \end{aligned}$$

(13)

which leads to the globally defined level $\ell$ representation

$$\begin{aligned} f^\ell (\mathbf x)= \sum _{\beta ^\ell \in K^\ell } c_{\beta ^\ell }\beta ^\ell (\mathbf x), \quad \mathbf x\in \varOmega . \end{aligned}$$

(14)

The existence of a local representation (13) with respect to the full basis $B^\ell$ is guaranteed by $f|_{\pi ^\ell }\in V|_{\pi ^\ell }$ according to the definition of H, and by using SCA. This confirms that the function on the left-hand side of (13) is contained in $V^\ell |_{\pi ^\ell }$. Additionally, we use the fact that

$$\begin{aligned} f(\mathbf {x})-\sum _{j=1}^{\ell -1} f^j(\mathbf {x}) = 0, \quad \mathbf x\in \pi ^k,\; k < \ell , \end{aligned}$$

(15)

which follows immediately from the definition of $f^j$. Combining this observation with the $\mathcal C^\mathbf{s}$-smoothness of f gives the homogeneous boundary conditions of order $\mathbf {s}$ on the constraining boundary $\varGamma ^\ell$. Finally, these conditions enable us to apply Lemma 1, which confirms that only the selected functions $K^\ell \subseteq B^\ell$ are needed in (13).

We conclude the proof by noting that (15) is satisfied since Eqs. (13) and (14) imply

$$\begin{aligned} f(\mathbf x)-\sum _{k=1}^{\ell -1} f^k(\mathbf x) = f^\ell (\mathbf x), \quad \mathbf x\in \pi ^\ell , \end{aligned}$$

while SOA (which is implied by SCA) means that increasing the level $\ell$ does not affect the values on patches of lower levels. Thus, we finally choose $\ell =N+1$ in (15) and arrive at

$$\begin{aligned} f(\mathbf x) = \sum _{k=1}^{N} f^k(\mathbf x), \quad \mathbf x\in \varOmega . \end{aligned}$$

      $\square$

In particular, this proves that every tensor-product polynomial of degree $\mathbf {p}$ can be represented as a linear combination of PNHB-splines, since these polynomials belong to the partially nested hierarchical spline space.

5 Truncation

We define the truncated PNHB-splines by suitably generalizing the truncation mechanism, which has been established in [8]. These functions are linearly independent, form a partition of unity, and span the partially nested hierarchical spline space H.

We consider a fixed level $\ell >1$ and a function

$$\begin{aligned} f \in \mathrm {span}\bigcup _{k=1}^{\ell -1} K^k, \end{aligned}$$

(16)

which is a linear combination of all tensor-product B-splines that have been selected at lower levels. SCA then implies that

$$\begin{aligned} f|_{\pi ^k}\in V^k|_{\pi ^k}, \quad k=1,\ldots ,\ell , \end{aligned}$$

for all levels that do not exceed $\ell$. When restricted to the patch $\pi ^\ell$, this function possesses a unique local representation

$$\begin{aligned} f (\mathbf x) = \sum _{\begin{array}{c} \beta ^\ell \in B^\ell \\ \mathrm {supp}\beta ^\ell \cap \pi ^\ell \ne \emptyset \end{array}} c_{\beta ^\ell } \beta ^\ell (\mathbf x), \quad \mathbf x\in \pi ^\ell , \end{aligned}$$

(17)

as a linear combination of tensor-product B-splines in $B^\ell$. We now define the truncation of f with respect to $K^\ell$ as the globally defined function

$$\begin{aligned} (\mathrm {trunc}^{\ell }f)(\mathbf x) = f(\mathbf x) - \sum _{\beta ^\ell \in K^\ell } c_{\beta ^\ell } \beta ^\ell (\mathbf x), \quad \mathbf x\in \varOmega , \end{aligned}$$

(18)

where the coefficients $c^\ell _\beta$ are taken from the representation (17). Combining this definition with (16) implies that

$$\begin{aligned} \mathrm {trunc}^{\ell }f \in \mathrm {span}\bigcup _{k=1}^{\ell } K^k. \end{aligned}$$

Consequently, we are now able to apply truncation of the next higher level $\ell +1$ to $\mathrm {trunc}^{\ell }f$.

For future reference we note that the trunction with respect to level $\ell$ does not change the value of the function on patches of previous levels,

$$\begin{aligned} f|_{\pi ^k} = (\mathrm {trunc}^{\ell }f) |_{\pi ^k} \quad \text{ if } \quad k<\ell . \end{aligned}$$

(19)

This is a direct consequence of SOA. We also note that

$$\begin{aligned} (\mathrm {trunc}^{\ell }f)|_{\pi ^\ell }\in \mathrm {span}(B^\ell \setminus K^\ell )|_{\pi ^\ell }. \end{aligned}$$

(20)

This can be confirmed by combining the local representation (17) with the definition (18) of the truncation.

We define truncated PNHB-splines of level $\ell$ by applying the truncation repeatedly to the selected tensor-product splines in $K^\ell$,

$$\begin{aligned} T^\ell = \mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1} K^\ell = \{ \; \mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell \; \text{: }\; \beta ^\ell \in K^\ell \; \}. \end{aligned}$$

(21)

Collecting the contributions from all levels gives the set of truncated PNHB-splines

$$\begin{aligned} T = \bigcup _{\ell =1}^N T^\ell . \end{aligned}$$

(22)

Lemma 2

We assume SCA and consider a selected B-spline $\beta ^\ell \in K^\ell$ of level $\ell$ and a lower level $k\le \ell$. Then

$$\begin{aligned} (\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )|_{\pi ^k} = {\left\{ \begin{array}{ll} 0 &{} \text { if } k<\ell \\ \beta ^\ell |_{\pi ^k} &{} \text { if } k=\ell . \end{array}\right. } \end{aligned}$$

(23)

Moreover, for larger levels $k>\ell$ we have

$$\begin{aligned} (\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )|_{\pi ^k} \in \mathrm {span}(B^k\setminus K^k)|_{\pi ^k}. \end{aligned}$$

(24)

Proof

Due to SCA we have that

$$\begin{aligned} \beta ^\ell |_{\pi ^k} = {\left\{ \begin{array}{ll} 0 &{} \text { if } k<\ell \\ \beta ^\ell |_{\pi ^k} &{} \text { if } k=\ell . \end{array}\right. } \end{aligned}$$

This implies (23) since the truncations with respect to the levels $\ell +1,\ldots ,N$ do not change the values on $\pi ^k$ according to (19).

To prove (24) we first observe that (20) gives

$$\begin{aligned} (\mathrm {trunc}^{k}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )|_{\pi ^k} \in \mathrm {span}(B^k\setminus K^k)|_{\pi ^k}, \end{aligned}$$

and note that the remaining truncations with respect to the levels $k+1,\ldots ,N$ do not change the values on $\pi ^k$ according to (19).       $\square$

Proposition 1

The truncated PNHB-splines are linearly independent if SCA is satisfied.

Proof

We use Eq. (23) and proceed as in the proof of Theorem 1.       $\square$

Proposition 2

The truncated PNHB-splines span the partially nested hierarchical spline space H if both SCA and CBA hold.

Proof

The definition of truncation implies that every function in T can be represented with respect to K. Indeed, a function $\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell$ for $\beta ^\ell \in K^\ell$ is obtained by subtracting contributions of functions included in $K^k$ for $k=\ell +1,\dots ,N$. Hence, it can be written as a linear combination of functions in K, and consequently, $\mathop {\text {span}}T\subseteq \mathop {\text {span}}K$. Since both T and K are linearly independent, and since $|T|=|K|$, we conclude that $\mathop {\text {span}}T=\mathop {\text {span}}K$. Finally, we use Theorem 2 to complete the proof.       $\square$

Similar to [9] we show that the functions in T preserve the coefficients of the corresponding selected functions in $K^\ell$.

Theorem 3

(Preservation of coefficients). Any function $f\in H$ possesses local representations

$$\begin{aligned} f(\mathbf x) = \sum _{\begin{array}{c} \beta ^k\in B^k\\ \mathrm {supp}\beta ^k\cap \pi ^k \ne \emptyset \end{array}} c_{\beta ^k} \beta ^k(\mathbf x), \quad \mathbf x\in \pi ^k, \end{aligned}$$

(25)

on the patches. The representation with respect to the truncated PNHB-splines inherits the coefficients $c_{\beta ^k}$ from these local representations,

$$\begin{aligned} f(\mathbf x) = \sum _{\ell =1}^N\sum _{\beta ^\ell \in K^\ell } c_{\beta ^\ell } (\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )(\mathbf x), \quad \mathbf x\in \varOmega , \end{aligned}$$

provided that SCA and CBA are valid.

Proof

Proposition 2 guarantees that there exists a representation of $f\in H$ with respect to T,

$$\begin{aligned} f(\mathbf x) = \sum _{\ell =1}^N\sum _{\beta ^\ell \in K^\ell } d_{\beta ^\ell } (\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )(\mathbf x), \quad \mathbf x\in \varOmega , \end{aligned}$$

with certain coefficients $d_{\beta ^\ell }$. We consider the restriction of this representation to the patch $\pi ^k$ of level k. None of the terms obtained for $\ell >k$ contributes to this restriction, according to (23). This also implies that the PNHB-splines of level k are simply tensor-product splines on $\pi ^k$. Using these two observations we obtain

$$\begin{aligned} f(\mathbf x) = \sum _{\ell =1}^{k-1}\sum _{\beta ^\ell \in K^\ell } d_{\beta ^\ell } (\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{\ell +1}\beta ^\ell )(\mathbf x) + \sum _{\beta ^k\in K^k} d_{\beta ^k}\beta ^k(\mathbf x), \quad \mathbf x\in \pi ^k. \end{aligned}$$

(26)

We note that the first sum is contained in $(B^k\setminus K^k)|_{\pi ^k}$, due to (24). Consequently we may use the linear inpendence of the tensor-product B-splines $(B^k)|_{\pi ^k}$ on the patch of level k to conclude

$$\begin{aligned} d_{\beta ^k} = c_{\beta ^k}, \quad \forall \beta ^k\in K^k, \end{aligned}$$

by comparing the coefficients of (25) and (26).       $\square$

The property of preservation of coefficients implies that the functions in T form a partition of unity:

Corollary 1

The sum of the truncated PNHB-splines is the constant function with value 1 if both SCA and CBA are valid.

Proof

Since the constant function with value 1 is contained in H, we may consider its representations (25) on all patches $\pi ^k$, with the coefficients $c_{\beta ^k} = 1$. Theorem 3 confirms the partition of unity property of truncated PNHB-splines.       $\square$

Similarly, the function $\mathrm {trunc}^{N}\cdots \mathrm {trunc}^{k+1}\beta ^k$ has the same Greville abscissa as its corresponding function $\beta ^k\in K^k$ from which it was derived by using truncation.

6 Completeness

The knot lines of each spline space $V^\ell$ define a subdivision of the unit square $(0,1)^2$ into the mesh $M^\ell$ of level $\ell$. More precisely, the elements of $M^\ell$ are axis-aligned boxes, which are the Cartesian product of two closed intervals that represent knot spans of $V^\ell$ in x- and y-direction. These elements will be denoted as cells of level $\ell$

Another assumption, which is stronger than CBA, is required to investigate the completeness of the PNHB-splines:

Assumption

The boundaries of the patches $\pi ^\ell$ are aligned with the mesh of level $\ell$. More precisely, each patch $\pi ^\ell$ is obtained as the interior

$$\begin{aligned} \pi ^\ell = \text{ int }\bigcup _{c\in C^\ell } c \end{aligned}$$

(FBA)

of the union of a cell set $C^\ell \subseteq M^\ell$. This condition will be called the Full Boundary Alignment (FBA) condition.

The union of the cell sets $C^\ell$ over all levels forms the partially nested hierarchical mesh.

Example

We consider again the partially nested hierarchical spline space, which is defined by the patches and spaces shown in Fig. 1a. The partially nested hierarchical mesh $\bigcup _{\ell =1}^N C^\ell$ is shown in Fig. 1b.       $\Diamond$

In this section we are interested in the full spline space F of degree $\mathbf {p}$ and maximal smoothness $\mathbf s=\mathbf {p}-(1,1)$,

$$\begin{aligned} F = \{ f \in \mathcal C^{\mathbf s}(\varOmega )\; \text{: }\; f|_{c}\in \varPi _{\mathbf {p}}\; \forall c\in C^\ell \; \forall \ell =1,\ldots ,N \}, \end{aligned}$$

(27)

where $\varPi _{\mathbf {p}}$ denotes the space of tensor-product polynomials of degree $\mathbf {p}$. This space contains the partially nested hierarchical spline space H, but it is generally larger. A simple condition implies that both spaces are equal:

Assumption

The support intersections of the basis functions of level $\ell$ with the associated patches $\pi ^\ell$ are all connected,

$$\begin{aligned} \mathrm {supp}\beta ^\ell \cap \pi ^\ell \quad \text{ is } \text{ connected } \quad \forall \beta ^\ell \in B^\ell , \; \ell =1,\ldots ,N. \end{aligned}$$

(SIC)

This will be denoted as the Support Intersection Condition (SIC).

If this assumption is satisfied in addition to all previous ones, then PNHB-splines are complete.

Theorem 4

The PNHB-splines span the full spline space F if FBA, SIC and SCA are satisfied.

Proof

Given a function $f\in F$, we proceed exactly as in the proof of Theorem 2. There is one modification, however, since we need to use a different argument to confirm the existence of the local representations (12) and (13).

This is achieved with the help of a result from [19]: Each patch $\pi ^\ell$ is a multi-cell domain due to FBA. Theorem 2.12 of that paper implies that we obtain local representations as linear combinations of tensor-product B-splines $\beta ^\ell$ if one uses several copies for functions with more than one support intersection. More precisely, when considering the function in (13) we obtain

$$\begin{aligned} f(\mathbf {x})-\sum _{k=1}^{\ell -1} f^k(\mathbf {x}) = \sum _{\beta ^\ell \in B^\ell } \sum _{\begin{array}{c} \sigma \\ \sigma \; \mathrm {is}\, \mathrm {connected}\; \\ \mathrm {component} \; \mathrm {of} \\ \mathrm {supp}\beta ^\ell \cap \pi ^\ell \end{array}} c_{\beta ^\ell \!,\sigma } \; \beta ^\ell (\mathbf x) \; \chi _\sigma (\mathbf x),\quad \mathbf x\in \pi ^\ell , \end{aligned}$$

where $\chi _\sigma (\mathbf x)$ is the characteristic function of the connected component $\sigma$.

SIC implies that only one instance of each B-spline $\beta ^\ell$ is required, as the support intersections with $\pi ^\ell$ possess at most one connected component $\sigma$. Lemma 1 can be applied again and confirms that only functions $\beta ^\ell \in K^\ell$ need to be considered. Consequently, we can find a representation of the form (13) (and also (12) for the first level).

The remainder of the proof applies without any modifications.       $\square$

Since PNHB-splines span the partially nested hierarchical spline space H, we also proved that the full spline space is equal to the partially nested hierarchical spline space under the assumptions of the theorem. All these results apply to truncated PNHB-splines as well.

7 An Example: Least-Squares Fitting

We consider a surface approximation problem to compare PNHB-splines with classical tensor-product B-splines and hierarchical B-splines. We choose the function

$$\begin{aligned} f(x,y)=0.6\bigg (\sum _{i=0}^{10}\sum _{j=0}^{10}d_{ij}b_i(x)b_j(y)+(x-0.5)^2\bigg ), \end{aligned}$$

which is constructed by multiplying the elements of the tensor-product basis constructed from the univariate Bernstein polynomials

$$\begin{aligned} b_k(t)=\left( {\begin{array}{c}10\\ k\end{array}}\right) t^k(1-t)^{10-k}, \text{ for } k=0,\dots ,10, \end{aligned}$$

of degree 10 with the function-valued coefficients

$$\begin{aligned} D=[d_{ij}]=\begin{bmatrix} 1+\sin (60x) \;&1&\cdots&1&1 \\ 1&1&\dots&1&1 \\ \vdots&\vdots&\vdots&\vdots \\ 1&1&\dots&1&1 \\ 1&1&\cdots&1&\; 1+\sin (60y) \end{bmatrix}, \end{aligned}$$

see Fig. 3. Its domain is the unit square $(0,1)^2$. This function is fairly flat in most parts of the domain, but has distinctive vertical and horizontal features in the southwest and the northeast corners of the domain, which motivates us to use partially nested spline refinement.

Fig. 3.

The function considered in the fitting example.

We use a simple least-squares approximation to project this function into spline spaces spanned by

• 1. biquadratic tensor-product B-splines defined on the mesh shown in Fig. 4a,

• 2. hierarchical B-splines defined on the mesh shown in Fig. 4b, and

• 3. partially nested hierarchical B-splines defined on the mesh shown in Fig. 4c.

For tensor-product splines we consider a vertical and horizontal refinement in the southwest and northeast corner. These knot lines propagate to the northwest corner since tensor-product splines do not support local refinement. This is not the case for HB-splines, where we can perform local refinement. Nevertheless, one still needs to use nested splines spaces, which enforces the simultaneous refinement in both directions. Therefore, we add knot lines in x- and y-direction in both considered corners. Finally, we show the mesh used for PNHB-spline approximation. It seems to be perfectly suited for this task as the knot line segments are aligned with the features of the function.

Fig. 4.

The meshes used for defining the approximating spline functions. Left: tensor-product B-splines, middle: HB-splines, right: PNHB-splines.

Table 2. Numerical results of the least-squares approximation.

The numerical results are reported in Table 2, which presents information about the number of degrees of freedom, the percentage of degrees of freedom (with respect to the tensor-product case), the maximum error between the original function and the fitting result and the average error.

The tensor-product splines provide the baseline for these tests. The number of control points is equal to 2304 and this is sufficient to obtain a reasonable result. By using hierarchical B-splines we saved some degrees of freedom and obtained a similar result. We used spline spaces $D^{i,i}$ for $i\le 6$. Further refinement in the corners would substantially increase the number of degrees of freedom. Finally, the use of PNHB-splines leads to an additional improvement: a better approximation is obtained by using an even smaller number of degrees of freedom.

So far we constructed the meshes manually. Our current work is devoted to the use of error estimators for automating this process.

8 Conclusion

We proposed the new construction of partially nested hierarchical B-splines in order to overcome the limitations of the existing hierarchical spline constructions, which are based on sequences of fully nested spline spaces. Suitable assumptions enabled us to define a hierarchical spline basis, to establish a truncation mechanism, and to derive a completeness result. The application potential of the proposed generalization has been demonstrated by a first experimental result on least-squares approximation.

Future work will be devoted to extensions of this construction to the full multivariate case and to refinement strategies that can guide the process of local mesh refinement. Further, we will study alternative formulations of the generalized truncation mechanism, in order to analyze the non-negativity of the resulting spline basis. Also, we will investigate algorithms for assigning spaces to patches which ensure that the various assumptions are satisfied. Finally, we will continue to explore the application potential of our new construction. Some results on these topics will be presented in a forthcoming paper [4].