The Basis Refinement Method

Citation

Grinspun, Eitan (2003) The Basis Refinement Method. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/QH6Z-0276. https://resolver.caltech.edu/CaltechETD:etd-05312003-133558

Abstract

Finite element solvers are critical in computer graphics, engineering, medical and biological application areas. For large problems, the use of adaptive refinement methods can tame otherwise intractable computational costs. Current formulations of adaptive finite element mesh refinement seem straightforward, but their implementations prove to be a formidable task. We offer an alternative point of departure which yields equivalent adapted approximation spaces wherever the traditional mesh refinement is applicable, but proves to be significantly simpler to implement. At the same time it is much more powerful in that it is general (no special tricks are required for different types of finite elements), and applicable to novel discretizations where traditional mesh refinement concepts are not of much help, for instance on subdivision surfaces.

For classical finite-elements, adaptive refinement is typically carried out by splitting mesh elements in isolation. While so-called mesh refinement is well-understood, it is considered cumbersome to implement for unstructured three-dimensional meshes, among other settings, in particular because mesh compatibility must be explicitly maintained. Furthermore, element-splitting does not apply to problems that benefit from higher-order B-spline discretizations and their more general counterparts, so-called subdivision elements. We introduce a simple, general method for adaptive refinement which applies uniformly in all these settings and others. The basic principle of our approach is to refine basis functions, not elements. Our method is naturally compatible: unlike mesh refinement, basis refinement never creates incompatible meshes. Our contributions are (a) a minimal mathematical framework, with (b) associated algorithms for basis refinement; furthermore, we (c) describe the mapping of popular methods (finite-elements, wavelets, splines and subdivision) onto this framework, and (d) demonstrate working implementations of basis refinement with applications in graphics, engineering, and medicine.

Our approach is based on compactly supported refinable functions. We refine by augmenting the basis with narrowly-supported functions, not by splitting mesh elements in isolation. This removes a number of implementation headaches associated with element-splitting and is a general technique independent of domain dimension, element type (eg, triangle, quad, tetrahedron, hexahedron), and basis function order (piecewise linear, quadratic, cubic, etc.). The (un-)refinement algorithms are simple and require little in terms of data structure support. Many popular discretizations, including classical finite-elements, wavelets and multi-wavelets, splines and subdivision schemes may be viewed as refinable function spaces, thus they are encompassed by our approach.

Our first contribution is the specification of a minimal mathematical framework, at its heart a sequence of nested approximation spaces. By construction, the bases for these spaces consist of refinable functions. From an approximation theory point of view this is a rather trivial statement; however it has a number of very important and highly practical consequences. Our adaptive solver framework requires only that the basis functions used be refinable. It makes no assumptions as to (a) the dimension of the domain; (b) the tesselation of the domain, i.e., the domain elements be they triangles, quadrilaterals, tetrahedra, hexahedra, or more general domains; (c) the approximation smoothness or accuracy; and (d) the support diameter of the basis functions. The specification of the nested spaces structure is sufficiently weak to accomodate many practical settings, while strong enough to satisfy the necessary conditions of our theorems and algorithms.

Our second contribution is to show that basis refinement can be implemented by a small set of simple algorithms. Our method requires efficient data structures and algorithms to (a) keep track of interactions between basis functions (i.e., to find the non-zero entries in the stiffness matrix), and (b) manage a tesselation of the domain suitable for evaluation of the associated integrals (i.e., to evaluate the entries of the stiffness matrix). We provide a specification for these requirements, develop the relevant theorems and proofs, and invoke these theorems to produce concrete, provably-correct pseudo-code. The resulting algorithms, while capturing the full generality (in dimension, tesselation, smoothness, etc.) of our method, are surprisingly simple.

Our third contribution is the mapping of finite-elements, wavelets and multi-wavelets, splines and subdivision schemes onto our nested spaces framework. No single discretization fits all applications. In our survey of classical and recently-popularized discretizations we demonstrate that our unifying algorithms for basis refinement encompass a very broad range of problems.

Our fourth contribution is a set of concrete, compelling examples based on our implementation of basis refinement. Adaptive basis refinement may be profitably applied in solving partial differential equations (PDEs) useful in many application domains, including simulation, animation, modeling, rendering, surgery, biomechanics, and computer vision. Our examples span thin shells (fourth order elliptic PDE using a Loop subdivision discretization), volume deformation and stress analysis using linear elasticity (second order PDE using linear-tetrahedral and trilinear-hexahedral finite elements respectively) and a subproblem of electrocardiography (the generalized Laplace equation using linear tetrahedral finite elements).

Thesis Files