Algorithms and data structures for truncated hierarchical B-splines

Tensor–product B–spline surfaces are commonly used as standard modeling tool in Computer Aided Geometric Design and for numerical simulation in Isogeometric Analysis. However, when considering tensor–product grids, there is no possibility of a localized mesh refinement without propagation of the refinement outside the region of interest. The recently introduced truncated hierarchical B–splines (THB–splines) [5] provide the possibility of a local and adaptive refinement procedure, while simultaneously preserving the partition of unity property. We present an effective implementation of the fundamental algorithms needed for the manipulation of THB–spline representations based on standard data structures. By combining a quadtree data structure — which is used to represent the nested sequence of subdomains — with a suitable data structure for sparse matrices, we obtain an efficient technique for the construction and evaluation of THB–splines.