Efficient Local Refinement near Parametric Boundaries Using kd-Tree Data Structure and Algebraic Level Sets

Abstract

In analysis of problems with parametric spline boundaries that are immersed or inserted into an underlying domain, the discretization on the underlying domain usually does not conform to the inserted boundaries. While the fixed underlying discretization is of great convenience as the immersed boundaries evolve, the field approximations near the inserted boundaries require refinement in the underlying domain, as do the quadrature cells. In this paper, a kd-tree data structure together with a sign-based and/or distance-based refinement strategy is proposed for local refinement near the inserted boundaries as well as for adaptive quadrature near the boundaries. The developed algorithms construct and utilize implicit forms of parametric Non-Uniform Rational B-Spline (NURBS) surfaces to algebraically (and non-iteratively) estimate distance as well as sign relative to the inserted boundary. The kd-tree local refinement is demonstrated to produce fewer sub-cells for the same accuracy of solution as compared to the classical quad/oct tree-based subdivision. Consistent with the kd-tree data structure, we describe a new a priori refinement algorithm based on the signed and unsigned distance from the inserted boundary. We first demonstrate the local refinement strategy coupled with the the kd-tree data structure by constructing Truncated Hierarchical B-spline (THB-spline) “meshes”. We next demonstrate the accuracy and efficiency of the developed local refinement strategy through adaptive quadrature near NURBS boundaries inserted within volumetric three-dimensional NURBS discretizations.

Keywords

• immersed boundary analysis
• Non-Uniform Rational B-splines
• kd-tree data structure
• adaptive quadrature
• algebraic level sets