A shape sensitive, variational approach for the matching of surfaces considered as thin elastic shells is investigated. The elasticity functional to be minimized takes into account two different types of nonlinear energies: a membrane energy measuring the rate of tangential distortion when deforming the reference shell into the template shell, and a bending energy measuring the bending under the deformation in terms of the change of the shape operators from the undeformed into the deformed configuration. The variational method applies to surfaces described as level sets. It is mathematically well-posed, and an existence proof of an optimal matching deformation is given. The variational model is implemented using a finite element discretization combined with a narrow band approach on an efficient hierarchical grid structure. For the optimization, a regularized nonlinear conjugate gradient scheme and a cascadic multilevel strategy are used. The features of the proposed approach are studied for synthetic test cases and a collection of geometry processing examples.
Notes
Communicated by Philippe G. CIARLET.
1 Introduction
We present a variational model for the matching of surfaces implicitly represented as level sets. The approach is inspired by the mathematical theory of nonlinear elasticity of thin shells. The model consists in an energy functional, which is to be minimized among deformations of a computational domain in which two given surfaces are embedded. A minimizer of this functional is a deformation that closely maps one (reference) surface onto the other (template) surface. As the underlying model we consider the reference surface as a thin elastic shell, i.e., a layer of an elastic material embedded in a volume of another several orders of magnitude softer isotropic elastic material. Subject to matching forces the volume is deformed in such a way that the thin shell is mapped onto the template surface. The functional reflects desired phenomena like resistance to compression and expansion of the surface, resistance to bending, and rotational invariance, while solely involving the deformation and the Jacobian of the deformation. The model is formulated in terms of projected derivatives from the tangent space of the reference surface onto the expected tangent space of the template surface. Taking into account a suitable factorization of the natural pullback under a deformation of shape operators enables us to formulate a model with appropriate convexity properties. The actual surface matching constraint is handled through a penalty, allowing for efficient numerical computation.
Through arguments of compensated compactness, we are able to show weak lower semicontinuity of the energy and consequently existence of minimizing deformations. We present a numerical approach based on a multilinear finite element ansatz for the deformation implemented on adaptive octree grids. The resulting discrete energy is minimized in a multiscale fashion applying a regularized gradient descent.
Advertisement
In the conference article [32], a preliminary version of this approach was presented. For the functional in that paper, lower semicontinuity could not be ensured for either the membrane or bending energies. This lack of lower semicontinuity manifests itself in applications, where compression of the surface is expected, and leads to undesired oscillations in almost-minimizing deformations, which we explore in the present work through explicit examples and computations. Additionally, to increase the efficiency the computational meshes are in the present paper adapted to the surfaces. Consequently, the number of degrees of freedom scales asymptotically almost like that of a surface problem.
The main pillar of our modeling is the use of polyconvex energy densities, first introduced in [3]. Energies of this type allow for geometric consistency properties like rotation invariance and the ability to measure area and volume changes. The core insight of this theory is that integrands consisting of convex functions of subdeterminants of the Jacobian give rise to integral functionals that are weakly lower semicontinuous in suitable Sobolev spaces. Indeed, this can be seen as an instance of compensated compactness [50]. A generic polyconvex isotropic energy density of the type used in this work is
for \({\text {Cof}}\,A := \det A\, A^{-T}\) the cofactor matrix of A. Here, the coefficients and the function \(\Gamma \) are such that (1.1) attains a local minimum for \(A \in \text {SO}(n)\), that is, for rigid motions. Such an example is provided in (3.8). Often in the modeling of nonlinear elasticity the condition
is added, to reflect the noninterpenetration of matter [4]. In our model, we make use of densities both with and without this property.
Related work Linear elasticity has been extensively used in computer vision and in graphics. Prominent applications are image registration [33, 34, 38, 48, 55], optical flow extraction [35], and shape modeling [29]. Recently, theories of nonlinear elasticity have been applied in many computer vision and graphics problems such as mesh deformation [13], shape averaging [56], registration of medical images [12]. The advantage of nonlinear models is that they allow for intuitive deformations when the displacements are large.
In this paper, we present a model for nonlinear elastic matching of thin shells. A finite element method for the discretization of bending energies of biological membranes has been introduced in [5]. Their approach uses quadratic isoparametric finite elements to approximate the interface on which the gradient flow of an elastic energy of Helfrich type is considered. The papers [9, 10] discuss accurate convex relaxation of higher-order variational problems on curves described as jump sets of functions of bounded variation. In particular, it enables the numerical treatment of elastic energies on such curves.
Advertisement
One challenge in polyhedral surface processing is to provide consistent notions of curvatures and second fundamental forms, i.e., notions that converge (in an appropriate topology or in a measure theoretic sense) to their smooth counterparts, given a smooth limit surface. One computationally popular model for discretizing the second fundamental form is Grinspun’s et al. [30] discrete shells model. Another efficient and robust method for nonlinear surface deformation and shape matching is PriMo [6]. This approach is based on replacing the triangles of a polyhedral surfaces by thin prisms. During a deformation, these prisms are required to stay rigid, while nonlinear elastic forces are acting between neighboring prisms to account for bending, twisting, and stretching of the surface. We refer to Botsch and Sorkine [7] for a discussion of pros and cons for various such methods. In comparison with methods based on polyhedral surfaces, level set approaches like ours are not dependent on specific triangulations of the shapes.
The matching of surfaces with elastic energies has recently been studied in [61]. Their energy contains a membrane energy depending on the Cauchy–Green strain tensor and a bending-type energy comparing the mean curvatures on the surfaces. The matching problem is formulated in terms of a binary linear program in the product space of sets of surface patches. For computations, a relaxation approach is used.
A different direction is the use of parametric approaches to reduce shape matching problems to the matching of functions on a fixed domain. For example, the methods presented in [60, 62] are based on conformal maps from the unit disk. A more general variant using conformal maps on surfaces with arbitrary topology is presented in [42]. Within the family of parametric methods, a surface matching approach related to ours is presented in [44], where nonlinear elastic energies are used for matching parametrized surface patches. In comparison with all these methods, our level set approach is nonparametric and allows surfaces of any topology, which does not need to be fixed in advance.
In [59], face matching based on a matching of corresponding level set curves on the facial surfaces is investigated. To match pairs of curves an optimal deformation between them is computed using an elastic shape analysis of curves. Compared to our approach, this model does not take into account bending dissipation of the curves.
A different direction in shape recognition and matching is exploiting the intrinsic geometry of the surfaces only, thereby producing isometry-invariant methods based on the first fundamental form, like those in [11, 24]. In comparison, bending is penalized in our model and we use all curvatures of the surfaces and their directions to be able to better match regions of edges and creases correctly.
A method for matching and blending of curves represented by level sets has been presented in [49]. Thereby, a level set evolution generates an interpolating family of curves, where the associated propagation speed of the level sets depends on differences of level set curvatures. In this class of approaches, geometric evolution problems are formulated, whereas here we focus on variational models for matching deformations. Variational registration of implicit surfaces was also considered in [40], but only through volume elasticity, in contrast to our shell terms.
To summarize, the main novelty of our contribution is the combination of independence of mesh topologies arising from the use of level sets, penalization of tangential distortion in a rotationally invariant framework, and awareness both of curvatures and curvature directions of the surfaces in the matching. We are not aware of any other methods possessing all of these features simultaneously.
Our approach is inspired by the articles [21, 22] in which surface PDE models are derived in terms of the signed distance function. Shape warping based on the framework of [21] has been discussed from a geometric perspective in [14].
Outline The paper is organized as follows. In Sect. 2, we review the required preliminaries about distance functions and formulate the geometric nondistortion and matching conditions that inspire our model. In Sect. 3, we present the different contributions to our energy. Section 4 is devoted to proving the existence of minimizing deformations under suitable Dirichlet and Neumann boundary conditions. Furthermore, the strong convergence of solutions for vanishing matching penalty parameter is discussed and counterexamples showing the lack of lower semicontinuity of related simpler models are given. In Sect. 5, a numerical strategy for minimizing the energy on adaptive octree grids is presented. Finally, Sect. 6 contains a range of numerical examples demonstrating the behavior of solutions corresponding to our design criteria and presents several potential applications.
Some useful notation For later usage and the purpose of reference, let us collect some useful notation, mostly introduced in detail in later sections:
|B| stands for the Lebesgue measure of \(B \subset \mathbb {R}^n\), and \({\text {diam}}\,B = \sup _{x,y \in B}|x-y|\) for its diameter.
Generic matrices are denoted by A, B, M, N. We use \({\mathbb {1}}\) for the identity matrix. The set of rotations is denoted by \(\text {O}(n)\), and \(\text {SO}(n)\) is the set of orientation-preserving rotations. The set of all symmetric and positive definite matrices is \(\text {SPD}(n)\).
Components of vectors are denoted with subindices. For \(v\in \mathbb {R}^n\), |v| denotes its Euclidean norm. The \((n-1)\)-dimensional sphere is \(\mathbb {S}^{n-1}\). For a matrix M, |M| is the Frobenius norm.
For two column vectors \(v,w \in \mathbb {R}^n\), \(v \otimes w\) is the tensor product of v and w, that is, the square matrix \(v w^T\). In particular, if \(|w|=1\) we have the identity \((v \otimes w) w = v\).
\(\text {P}(e)={\mathbb {1}}- e \otimes e\) is the projection onto vectors orthogonal to \(e \in \mathbb {S}^{n-1}\).
Deformations on \(\mathbb {R}^n\) are denoted by \(\phi \), and deformations defined on a hypersurface \(\mathcal {M}\subset \mathbb {R}^n\) by \(\varphi \). The identity deformation is denoted by \({\text {id}}\).
\(\Omega \subset \mathbb {R}^n\) denotes the computational domain. Every relevant deformation \(\phi \) maps \(\Omega \) into \(\mathbb {R}^n\). \(\Omega \) has to contain all computationally relevant manifolds \(\mathcal {M}\). \(\Omega \) has Lipschitz boundary, is open and bounded.
We use the notation \(\partial _i\) for partial derivatives, \(\nabla \) for the gradient of a scalar function, \(\mathcal {D}\) for the Jacobian matrix of a vector function and \(\mathcal {D}^2\) for the Hessian matrix of a scalar function.
\(\mathcal {M}_1, \mathcal {M}_2 \subset \Omega \) are \(C^{2,1}\) compact hypersurfaces. The inside and outside components of \(\Omega \setminus \mathcal {M}_i\) are well defined by the Jordan–Brouwer separation theorem ([31], Chapter 2, Section 5).
The signed distance function to \(\mathcal {M}_1, \mathcal {M}_2\) is denoted by \(\mathbf{{d}}_1, \mathbf{{d}}_2\). The sign convention is that \(\mathbf{{d}}_i\) is negative on the inside of \(\mathcal {M}_i\), so that \(\mathbf{{d}}_i(x)=-{\text {dist}}(x, \mathcal {M}_i)\) if x is in the inside component of \(\Omega \setminus \mathcal {M}_i\) and \(\mathbf{{d}}_i(x)={\text {dist}}(x, \mathcal {M}_i)\) otherwise, where the distance functions \({\text {dist}}(\cdot , \mathcal {M}_i)\), \(i=1,2\) are the unique viscosity solutions of \(1-|\nabla {\text {dist}}(\cdot , \mathcal {M}_i)|=0\) and \({\text {dist}}(\cdot , \mathcal {M}_i)=0\) on \(\mathcal {M}_i\). The normal fields to the offsets of \(\mathcal {M}_i\) at a point x are denoted by \(\mathbf{{n}}_i(x):=\nabla \mathbf{{d}}_i(x)\). A superscript next to \(\mathcal {M}_i\) (\(i=1,2\)), as in \(\mathcal {M}_i^c\), denotes that we are talking about a level set of \(\mathbf{{d}}_i\) with value different from zero, so that \(\mathcal {M}_i^c := \mathbf{{d}}_i^{-1}(c)\).
\(T_x\mathcal {M}_i^{\mathbf{{d}}_i(x)}\) denotes the tangent space to \(\mathcal {M}_i^{\mathbf{{d}}_i(x)}\) at x. The outwards normal to \(\mathcal {M}_i^{\mathbf{{d}}_i(x)}\) is given by \(\mathbf{{n}}_i(x)\), and the set of points where \(\mathbf{{d}}_i\) is not differentiable is denoted by \({\text {sing}}\,\mathbf{{d}}_i\).
We use \({\mathcal {S}}_i = \mathcal {D}^2 \mathbf{{d}}_i\) for the Hessian of \(\mathbf{{d}}_i\), which coincides with an extended shape operator of \(\mathcal {M}_i\).
\(\lambda , \mu \) are the Lamé coefficients of an isotropic material in linearized elasticity.
\(C^0(\Omega ;\mathbb {R}^n)\) is the space of continuous functions from the domain \(\Omega \) to the range \(\mathbb {R}^n\), \(C^{k,\alpha }\) the Hölder spaces in which the k-th derivative is \(\alpha \)-Hölder continuous, including the Lipschitz case \(\alpha =1\). The range of the spaces is specified unless it is \(\mathbb {R}\). Sobolev spaces are denoted by \(W^{1,p}\) and the closure of compactly supported smooth functions in them by \(W_0^{1,p}\).
The letter C is reserved for a generic positive constant that may have different values in each appearance. Sequence indexing is usually denoted by a superscript k, and limits by an overline, e.g., \(\phi ^k \rightarrow \overline{\phi }\).
2 Deformation and Matching of Level Set Hypersurfaces
We are given two compact, connected embedded hypersurfaces \(\mathcal {M}_1,\mathcal {M}_2\) of class \(C^{2,1}\), which are diffeomorphic to each other, and both of which are contained in a bounded Lipschitz domain \(\Omega \subset \mathbb {R}^{n}\). In this section, we deal with the tangential distortion and the change of the shape operator under a deformation \(\phi : \Omega \rightarrow \mathbb {R}^n\).
For any \(c \in \mathbb {R}\), we denote the c-offsets to the hypersurface \(\mathcal {M}_i\) by \(\mathcal {M}_i^c := \{ x \in \Omega \,|\, \mathbf{{d}}_i(x) = c \}\,\). Furthermore, we define the singularity set \({\text {sing}}\,\mathbf{{d}}_i\) as the set of points where \(\mathbf{{d}}_i\) is not differentiable. With the regularity of \(\mathcal {M}_i\) that we have assumed, it is well known (e.g., Theorem 1.1, Corollary 1.3 and Remark 1.4 of [43]) that \({\text {sing}}\,\mathbf{{d}}_i\) has Lebesgue measure zero and \({\text {dist}}(\mathcal {M}_i, {\text {sing}}\,\mathbf{{d}}_i) > 0\). Furthermore, combining [21, Theorem 5.6] and [45, Proposition 4.6, 7.] we see that \(\mathbf{{d}}_i \in C^2(\overline{\Omega } \setminus \overline{{\text {sing}}\,\mathbf{{d}}_i})\).
The gradient of the signed distance function \(\nabla \mathbf{{d}}_i(x)\) is the outward-pointing unit normal \(\mathbf{{n}}_i(x)\) to \(\mathcal {M}_i^{\mathbf{{d}}_i(x)}\) at a point x. The tangent space to \(\mathcal {M}^{\mathbf{{d}}_i(x)}_i\) at x, denoted by \(T_x \mathcal {M}^{\mathbf{{d}}_i(x)}_i\), consists of all vectors orthogonal to \(\mathbf{{n}}_i(x)\). Then, the corresponding projection matrices onto the tangent spaces are defined by
Note that \({\mathcal {S}}_i(x):=\mathcal {D}^2 \mathbf{{d}}_i(x)=\mathcal {D}\mathbf{{n}}_i(x) \text {P}_i(x)\) is the shape operator of the immersed hypersurface \(\mathcal {M}^{\mathbf{{d}}_i(x)}_i\) at a point x. In fact, from \(|\mathbf{{n}}_i(x)|^2=1\) we deduce by differentiation that \(\mathbf{{n}}_i^T(x){\mathcal {S}}_i(x)=0\). This, together with the fact that \(\mathbf{{n}}_i \otimes \mathbf{{n}}_i\) is the projection onto the normal of the hypersurface \({\mathcal {S}}_i\) shows that
With our choice of signs for \(\mathbf{{d}}_i\), the symmetric matrices \({\mathcal {S}}_i\) are positive semidefinite for convex hypersurfaces \(\mathcal {M}_i\). Further information on tangential calculus for level set functions may be found in Chapter 9 of [23].
2.1 Tangential Derivative and Area and Length Distortion
First, let us assume that \(\phi \) exactly maps \(\mathcal {M}_1^c\) onto \(\mathcal {M}_2^c\), for all \(c>0\). Then, \(T_x \mathcal {M}_1^{\mathbf{{d}}_1(x)}={\text {im}}\text {P}_1(x)\) and \(T_{\phi (x)}\phi (\mathcal {M}_1^{\mathbf{{d}}_1(x)})=T_{\phi (x)}\mathcal {M}_2^{\mathbf{{d}}_2(\phi (x))}={\text {im}}\text {P}_2 ( \phi (x) )\) and we define the tangential derivative induced by the deformation \(\phi \) as
capturing the tangential variation of \(\phi (x)\) on \(\mathcal {M}_2\) along tangential directions on \(\mathcal {M}_1\). In the variational model, we consider below an energy term depending on \(\mathcal {D}_{\text {tg}}\phi (x)\) will reflect the tangential distortion of the deformation in the context of a matching of the two hypersurfaces \(\mathcal {M}_1\) and \(\mathcal {M}_2\) even though \(\phi (\mathcal {M}_1)\) does not necessarily equal \(\mathcal {M}_2\). Indeed, in the case \(\mathcal {M}_2 \ne \phi (\mathcal {M}_1)\) the variation along a tangent direction on \(\mathcal {M}_1\) is still projected via \(\mathcal {D}_{\text {tg}}\phi (x)\) onto the tangent space \(T_{\phi (x)}\mathcal {M}_2^{\mathbf{{d}}_2(\phi (x))}\) and not onto the tangent space of the deformed hypersurface \(\phi (\mathcal {M}_1)\) (cf. Fig. 1). Therefore, there may exist tangential directions \(v \in T_x \mathcal {M}_1^{\mathbf{{d}}_1(x)}\), such that \(\mathcal {D}_{\text {tg}}\phi (x) v =0\) even though \(\mathcal {D}\phi v \ne 0\). Thus \(\mathcal {D}_{\text {tg}}\phi (x)\) can only be considered a measure of tangential distortion if \(\phi (\mathcal {M}_1)\) is sufficiently close to \(\mathcal {M}_2\) in the sense of closeness of tangent bundles.
×
For a general deformation \(\psi :\mathbb {R}^n\rightarrow \mathbb {R}^n\) the Cauchy–Green strain tensor \(\mathcal {D}\psi ^T \mathcal {D}\psi \) describes (up to first order) the deformation in a frame invariant (with respect to rigid body motions) way. Since we are interested in the effect of such a deformation between two hypersurfaces, for a suitably extended tangential gradient \(\mathcal {D}_{\text {tg}}\phi + \mathbf{{n}}_2\circ \phi \otimes \mathbf{{n}}_1\) we define the extended tangential part of the Cauchy–Green strain tensor, measuring only tangential distortion:
The term \(\mathbf{{n}}_2(\phi (x)) \otimes \mathbf{{n}}_1(x)\) is used to complement directions that are removed by the projections in the definition of the tangential distortion \(\mathcal {D}_{\text {tg}}\phi \) and can be seen to realize a nonlinear Kirchhoff–Love assumption [18, Page 336], which postulates that lines normal to the middle surface of a shell remain normal after the deformation, without stretching.
Next, we investigate the area and length distortion due to the tangential derivative \(\mathcal {D}_{\text {tg}}\phi \). For a given vector \(e \in \mathbb {R}^n\) we denote by \(\text {Q}(e)\) any proper rotation such that \(\text {Q}(e) e_n = e\), where \(e_n\) denotes the n-th element of the canonical basis of \(\mathbb {R}^n\). Note that this condition does not specify a unique \(\text {Q}(e)\). Then, for every \(B \in \mathbb {R}^{n \times n}\) satisfying \(w \in \ker B\) and \({\text {im}}B \subseteq v^\perp \) for some unit vectors \(v,w \in \mathbb {S}^{n-1}\), we have
$$\begin{aligned} \begin{gathered} \text {Q}(v)^T ( B + v \otimes w ) \text {Q}(w) = \text {Q}(v)^T B \text {Q}(w) + e_n \otimes e_n=\left( \begin{array}{c|c} \tilde{B} &{} 0 \\ \hline 0 &{} 1 \end{array} \right) , \end{gathered} \end{aligned}$$
(2.3)
where \(\tilde{B}\) is the upper left \((n-1)\times (n-1)\) submatrix of \(\text {Q}(v)^T B \text {Q}(w)\). Obviously, (2.3) implies
Hence, for \(\phi (\mathcal {M}_1)=\mathcal {M}_2\) and \(v=n_2(\phi (x))\), \(w=n_1(x)\) the area distortion under the hypersurface matching deformation \(\phi \) at some position x is described by \(\det (\mathcal {D}_{\text {tg}}\phi (x) + \mathbf{{n}}_2(\phi (x)) \otimes \mathbf{{n}}_1(x))\), which equals the positive square root of the determinant of the above Cauchy–Green strain tensor \(\mathcal {D}_{\text {tg}}\phi ^T \mathcal {D}_{\text {tg}}\phi + \mathbf{{n}}_1 \otimes \mathbf{{n}}_1\). The squared tangential length distortion (in the sense of summing all squared distortions with respect to an orthogonal basis) is described by \(|\mathcal {D}_{\text {tg}}\phi (x) + \mathbf{{n}}_2(\phi (x)) \otimes \mathbf{{n}}_1(x))|^2\) and equals the trace of the Cauchy–Green strain tensor.
2.2 Bending and Curvature Mismatch
Now, we quantify the change of curvature directions and magnitudes under the deformation \(\phi \). Our approach is motivated by models describing bending of elastic shells, because in our application the hypersurfaces are considered as thin shells.
In order to quantify the changes of curvature, we first assume that \(\phi (\mathcal {M}_1)=\mathcal {M}_2\), and compute the difference of the pull back of the shape operator \({\mathcal {S}}_2\) on \(\mathcal {M}_2\) onto \(\mathcal {M}_1\) under the deformation \(\phi \) and the shape operator \({\mathcal {S}}_1\) on \(\mathcal {M}_1\), which, for two arbitrary directions \(v,\,w\in \mathbb {R}^n\), is given by
$$\begin{aligned}&{\mathcal {S}}_2(\phi (x)) \mathcal {D}\phi (x) v \cdot \mathcal {D}\phi (x) w - {\mathcal {S}}_1(x) v \cdot w \\&\quad = \left( \mathcal {D}\phi (x)^T {\mathcal {S}}_2(\phi (x)) \mathcal {D}\phi (x) - {\mathcal {S}}_1(x)\right) v\cdot w\;. \end{aligned}$$
If \(v,\,w\) are tangent vectors in \(T_x \mathcal {M}_1\), this difference describes the relative shape operator.
For \(n=3\) and when \(\phi \) is an isometric deformation between \(\mathcal {M}_1\) and \(\mathcal {M}_2\) (that is, \(\mathcal {D}\phi (x)\) is an orthogonal mapping on \(T_x \mathcal {M}_1\) for all \(x\in \mathcal {M}_1\)), \({\mathcal {S}}_{rel}\) appears in physical models for thin elastic shells in the context of the \(\Gamma -\)limit of \(\mathrm {3D}\) hyperelasticity [28]. Even though we do not necessarily expect our deformations to be tangentially isometric, we use this ansatz to compare curvatures of level sets in deformed and undeformed configuration, respectively. The following calculations shed some light on the properties of \({\mathcal {S}}_{rel}\):
The assumption that \(\phi (\mathcal {M}_1)=\mathcal {M}_2\) can be rewritten as \(\mathbf{{d}}_2 \circ \phi (x) = 0\) for \(x \in \mathcal {M}_1\). Let us assume that in addition \(\mathbf{{d}}_2 \circ \phi \) is a distance function (that is \(|\nabla ( \mathbf{{d}}_2 \circ \phi )|=1\)), then \(\mathbf{{d}}_2 \circ \phi \) is again a distance function, and since \(\mathbf{{d}}_2 \circ \phi = 0\) it follows that the left-hand side of (2.5) is the shape operator of the hypersurface \(\mathcal {M}_1\). The first term in the right-hand side is the pullback of \({\mathcal {S}}_2\).
Let us remark that the appearance of a second fundamental form is consistent with Koiter’s nonlinear thin shell theory [36], [18, Section 11.1]. Regardless of whether \(\mathbf{{d}}_2 \circ \phi \) is a distance function or not, (2.5) implies that
in case \(\mathbf{{d}}_2 \circ \phi = \mathbf{{d}}_1\). In the next section, we use the extended relative shape operator to derive a variational model for the mismatch of curvatures.
3 Energy Functional
Given two hypersurfaces \(\mathcal {M}_1\) and \(\mathcal {M}_2\) our ultimate goal is to describe best matching deformations \(\phi \), which map \(\mathcal {M}_1\) onto \(\mathcal {M}_2\) as the minimizer of a suitable energy. Thereby, different energy terms will reflect a set of matching conditions for a volumetric deformation \(\phi :\Omega \rightarrow \mathbb {R}^{n}\) and without a hard constraint \(\phi (\mathcal {M}_1) = \mathcal {M}_2\):
A membrane deformation energy \(E_{\text {mem}}\) penalizes the tangential distortion measured through \(\mathcal {D}_{\text {tg}}\phi \).
A bending energy \(E_{\text {bend}}\) penalizes bending as reflected by the relative shape operator.
A matching penalty \(E_{\text {match}}\) ensures a proper matching of the two hypersurfaces \(\mathcal {M}_1\) onto \(\mathcal {M}_2\) via a narrow band approach.
A volume energy \(E_{\text {vol}}\) enforces a regular deformation on the whole computational domain \(\Omega \).
Our approach is based on level sets. Hence, we replace the integration over a single hypersurface, i.e., \(\mathcal {M}_1\), for the first three energies by a weighted integration over a narrow band of width \(\sigma \) with \(0< \sigma < {\text {dist}}(\mathcal {M}_1, {\text {sing}}\,\mathbf{{d}}_1)\). To this end, we will make use of a cutoff function \(\eta _\sigma \in C^\infty _0(\mathbb {R})\) with \(\int _\mathbb {R}\eta _\sigma (t) {{\text {d}}}t =1\) and \({\text {supp}}\,\eta _\sigma = [-\sigma , \sigma ]\). Additionally, \(\eta _\sigma \) is assumed to be even and strictly decreasing in \([0,+\infty )\).
In what follows we introduce the four energy contributions separately.
3.1 Tangential Distortion Energy
Picking up the insight gained in Sect. 2.1, we formulate the membrane energy in terms of the length and area change associated with the tangential distortion \(\mathcal {D}_{\text {tg}}\phi \):
where \(W\) is a nonnegative polyconvex energy density vanishing at \(\text {SO}(n)\). The weight \(\delta \) reflects the proper scaling of the tangential distortion energy in case of a thin shell model with shell thickness \(\delta \).
The energy (3.1) vanishes only on deformations \(\phi \) whose Jacobian matrix \(\mathcal {D}\phi (x)\) maps \(T\mathcal {M}_1^{\mathbf{{d}}_1(x)}\) isometrically onto \(T\mathcal {M}_2^{\mathbf{{d}}_2(\phi (x))}\) for every point \(x \in {\text {supp}}\,{\eta _\sigma \circ \mathbf{{d}}_1}\). In consequence, both tangential expansion and compression are penalized.
Let us remark, that the extension \(\mathcal {D}_{\text {tg}}\phi + \mathbf{{n}}_2(\phi (x)) \otimes \mathbf{{n}}_1(x)\) of the tangential derivative \(\mathcal {D}_{\text {tg}}\phi \) defined in (2.1) with rank \(n-1\) can degenerate or be orientation-reversing depending on the local configuration of \(\mathcal {M}_1\) and \(\mathcal {M}_2\) at x (cf. Fig. 2 for examples).
×
Furthermore, the energy density W should not satisfy \(W(B) \rightarrow \infty \) for \(\det B \rightarrow 0\). A straightforward modification of the arguments of Ciarlet and Geymonat ([16, 17] Theorem 4.10-2) leads to a smooth integrand \(W\) which has isometries as local minimizers, with the correct invariance properties, and with a Hessian for \(B={\mathbb {1}}\) which matches the quadratic energy integrand of the Lamé-Navier model of linearized elasticity. With given Lamé coefficients \(\lambda , \mu > 0\), we select the energy
This density fits into the notation of (1.1), if we choose \(p=q=2\) and \(\Gamma (t)=c t^2 + d e^{- (t-1) }\;.\)
3.2 Bending Energy
Now, we discuss a variational formulation of the curvature matching condition \(\mathcal {D}\phi (x)^T {\mathcal {S}}_2(\phi (x)) \mathcal {D}\phi (x) = {\mathcal {S}}_1(x)\), which is equivalent to a vanishing relative shape operator [cf. (2.4)], where \({\mathcal {S}}_i = \mathcal {D}\mathbf{{n}}_i \text {P}_i = \text {P}_i \mathcal {D}^2 \mathbf{{d}}_i \text {P}_i\) for \(i=1,2\) are the shape operators on the hypersurfaces \(\mathcal {M}_1\) and \(\mathcal {M}_2\), respectively. At first sight, it appears natural to formulate a quadratic penalization and to define a bending energy
The weight \(\delta ^3\) reflects the scaling of the bending energy for thin shells of thickness \(\delta \). However, this energy is in general not weakly lower semicontinuous. Indeed, consider a situation in which \({\mathcal {S}}_1(x) = {\mathcal {S}}_2(\phi (x)) = P(e_n)\). A short computation shows that the corresponding density is not convex in its matrix variable along the rank-one segment joining \({\mathbb {1}}-\frac{3}{4}e_1 \otimes e_1\) and \({\mathbb {1}}-\frac{1}{2}e_1 \otimes e_1\), which precludes lower semicontinuity (cf. also Example 4.8 on the lack of rank-one convexity). In fact, this kind of density is closely related to the Saint Venant–Kirchhoff energy, whose quasiconvex envelope is computed in [39].
Thus, we are asking for an alternative lower semicontinuous energy functional which gives preference to deformations \(\phi \) for which \(\mathcal {D}\phi ^T ( {\mathcal {S}}_2\circ \phi ) \mathcal {D}\phi \) is close to \({\mathcal {S}}_1\). We show that this can be achieved with the extended shape operators \({\mathcal {S}}^{ext}_i = \text {P}_i \mathcal {D}^2 \mathbf{{d}}_i \text {P}_i + \mathbf{{n}}_i \otimes \mathbf{{n}}_i\) for \(i=1,2\) and factorization. For proving this, we make use of the following lemma.
Lemma 3.1
(Modified curvature matching condition) Assume that M, N are two symmetric, positive definite matrices satisfying
$$\begin{aligned} M = \text {P}_1 M \text {P}_1 + \mathbf{{n}}_1 \otimes \mathbf{{n}}_1 \text { and } N = \text {P}_2 N \text {P}_2 + \mathbf{{n}}_2\otimes \mathbf{{n}}_2\;. \end{aligned}$$
Moreover, assume that \(A\in \mathbb {R}^{n \times n}\) satisfies
$$\begin{aligned} A \text {P}_1 = \text {P}_2 A\,, \end{aligned}$$
then the following statements are equivalent:
$$\begin{aligned} A^T \text {P}_2 N \text {P}_2 A = \text {P}_1 M \text {P}_1 \end{aligned}$$
If we multiply this equation from left and right by \(\text {P}_1 M^{\frac{1}{2}} \text {P}_1\) and take into account that \((\text {P}_2 N^{\frac{1}{2}} \text {P}_2)^2 = \text {P}_2 N \text {P}_2\) and \((\text {P}_1 M^{\frac{1}{2}} \text {P}_1)^2 = \text {P}_1 M \text {P}_1\) we see that this is equivalent to
$$\begin{aligned} \text {P}_1 A^T \text {P}_2 N \text {P}_2 A \text {P}_1 = \text {P}_1 M \text {P}_1\,. \end{aligned}$$
Applying that \(A \text {P}_1 = \text {P}_2 A\) we finally achieve at the equivalent condition
$$\begin{aligned} A^T \text {P}_2 N \text {P}_2 A = \text {P}_1 M \text {P}_1\,. \end{aligned}$$
The proof of the converse follows the same steps in opposite direction. \(\square \)
If the assumptions of this lemma apply to \(M={\mathcal {S}}^{ext}_1(x)\), \(N={\mathcal {S}}^{ext}_2(y)\), and \(A= \mathcal {D}\phi (x)\) with \(y=\phi (x)\), then the curvature matching condition
is equivalent to \(\Lambda ({\mathcal {S}}^{ext}_1(x),{\mathcal {S}}^{ext}_2(\phi (x)) ,\mathcal {D}\phi (x)) \in \text {O}(n)\) and a lower semicontinuous energy functional penalizing deviations of \(\Lambda ({\mathcal {S}}^{ext}_1(x),{\mathcal {S}}^{ext}_2(\phi (x)) ,\mathcal {D}\phi (x))\) from \(\text {O}(n)\) would be a proper choice for realizing curvature matching. Unfortunately, the positive definiteness assumption of Lemma 3.1 is not fulfilled if principal curvatures of \(\mathcal {M}_1\) or \(\mathcal {M}_2\) are negative. Hence, we are replacing the extended shape operator matrices \({\mathcal {S}}_i^{ext}\) by symmetric and positive definite curvature classification matrices \(C_i = {\mathcal {C}}({\mathcal {S}}_i^{ext})\), \(i=1,2\), respectively.
We have experimented with two different choices for \({\mathcal {C}}\):
A simple choice is \({\mathcal {C}}({\mathcal {S}}_i^{ext})= {\mathcal {S}}_i^{ext} + \mu {\mathbb {1}}\), where \(-\mu \) is a strict lower bound of the principal curvatures. But in applications surfaces are frequently characterized by strong creases or rather sharp edges, leading to very large \(\mu \). As a consequence, the relative difference of the eigenvalues is significantly reduced when dealing with the resulting curvature classification matrices. Thus, the variational approach is less sensitive to different principal curvatures of the input hypersurfaces.
Another option is to use a truncation of the absolute value function for the eigenvalues of symmetric matrices. For a symmetric matrix \(B\in \mathbb {R}^{n,n}\) with eigenvalues \(\lambda _1,\ldots , \lambda _n\) and a diagonalization \(B=Q^T \mathrm {diag}(\lambda _1,\ldots , \lambda _n) Q\) we use the classification operator
where \(|\lambda |_\tau = \max \{|\lambda |, \tau \}\) for some \(\tau >0\). This approach properly represents the exact shape operator matching objective in case of principal curvatures of equal sign and absolute value larger than \(\tau \). A disadvantage of this construction is that it is not able to force the deformation to correctly match curvature directions on the hypersurface with the same absolute value of the principal curvatures but with different signs. That is, locally a saddle point of the hypersurface may be mistaken for an elliptical point. However, this effect is usually compensated globally, and in applications the ansatz performs well, in particular in matching regions of edges and creases (see Sect. 6).
Like for the membrane energy (3.1), if \(\mathcal {D}\phi (x)\) is ensured to be orientation-preserving (\(\det \mathcal {D}\phi >0\)) and \(\mathbf{{n}}_1 \cdot ( \mathbf{{n}}_2 \circ \phi ) > 0\) (cf. Fig. 2), the curvature matching condition is equivalent to
where \(W\) can be chosen as the same polyconvex density already used for \(E_{\text {mem}}\).
3.3 Mismatch Penalty and Volumetric Regularization Energies
So far, we have defined tangential membrane and bending energies which quantify the appropriateness of deformations \(\phi :\Omega \rightarrow \mathbb {R}^n\) in a narrow band around the hypersurface \(\mathcal {M}_1\). In the derivation of these energies, we assumed the constraint \(\phi (\mathcal {M}_1)=\mathcal {M}_2\). However, such a constraint would be very hard to enforce numerically. Thus, we use a weaker mismatch penalty instead:
Moreover, we aim for a regular deformation on the whole computational domain \(\Omega \) which is globally injective. This, in particular, prevents from self-intersections of the deformed hypersurface \(\phi (\mathcal {M}_1)\). To achieve this, we introduce the following volume regularization term based on a polyconvex density \(\hat{W}\) that enforces orientation preservation
with \(p>n\), \(q>n\), \(s>(n-1)q/(q-n)\), and with \(\alpha _p, \beta _q, \gamma _s >0\) ensuring that the density \(\hat{W}\) attains a local minimum when \(\mathcal {D}\phi ^T \mathcal {D}\phi = {\mathbb {1}}\). As mentioned in the introduction, such an energy is weakly lower semicontinuous in \(W^{1,p}(\Omega ; \mathbb {R}^n)\) when restricted to deformations whose Jacobian determinant is positive almost everywhere, and this condition is closed under weak convergence.
Choosing \(p=q=n+1\), \(s=n^2\) and using that because of its symmetries \(\hat{W}\) can be expressed in terms of singular values [20, Proposition 5.31], elementary but lengthy computations yield the stationarity condition at \({\mathbb {1}}\)
and that the corresponding Hessian is positive definite. For \(n=3\) an adequate example is then \(p=q=4\), \(s=9\), \(\alpha _p=1, \beta _q=1\), and \(\gamma _s=4\). For \(n=2\), one can use \(p=q=3\), \(s=4\), \(\alpha _p=\beta _q=2\) and \(\gamma _s=3 \sqrt{2}\). Notice that in this case, \(|\mathcal {D}\phi |=|{\text {Cof}}\,\mathcal {D}\phi |\).
3.4 Total Energy
Summing the above terms, our energy for shape-aware level set matching reads
where the different terms depend on the fixed input geometries \(\mathcal {M}_1\) and \(\mathcal {M}_2\) through \(\mathbf{{d}}_1\) and \(\mathbf{{d}}_2\).
4 Existence of Optimal Matching Deformations
First, we prove the following weak continuity lemma, which is a generalization of the classical result given in [50, Theorem 4.1]. Here, the coefficients may depend on the deformed configuration.
Lemma 4.1
Let \(\phi ^k \rightharpoonup \phi \in W^{1,p}(\Omega ; \mathbb {R}^n)\) and \(p>n\). Moreover, let \(V_i \in C^0(\overline{\Omega } \times \mathbb {R}^{n}; \mathbb {S}^{n-1})\), \(i=1,2\) and we denote
By the Rellich–Kondrakov embedding theorem ([1], Theorem 6.3 III), there exist subsequences of \(\mathbf{{v}}_i^k\), \(i=1,2\), which for simplicity of notation are again denoted by \(\mathbf{{v}}_i^k\), \(i=1,2\), that converge uniformly to \(\mathbf{{v}}_i\), \(i=1,2\), respectively. Taking into account the Lipschitz continuity estimate
$$\begin{aligned} |\text {P}(e)-\text {P}(f)|=|(e-f)\otimes e + f \otimes (e-f)| \le 2 \sqrt{n}|e - f| \end{aligned}$$
and that \(\mathbf{{v}}_i^k \rightarrow \mathbf{{v}}_i\), \(i=1,2\) in \(L^\infty \) we obtain \(| I^k - \overline{I}^k | \rightarrow 0\) for \(k\rightarrow \infty \).
Next, we replace \(\mathbf{{v}}_i\), \(i=1,2\) in \(\bar{I}^k\) by a piecewise constant approximation on a grid superimposed to the computational domain \(\Omega \). Explicitly, we consider the finitely many nonempty intersection \(\omega _\delta ^z = \delta (z+ [0,1]^n) \cap \Omega \) of cubical cells with \(\Omega \) for \(z \in \mathbb {Z}^n\) and define
where \(\mathbf{{v}}_{1,\delta }\) and \(\mathbf{{v}}_{2,\delta }\) are piecewise constant functions in \(L^\infty \) with \(\mathbf{{v}}_{1,\delta }|_{\omega _\delta ^z} = \mathbf{{v}}_1(z_\delta )\) and \(\mathbf{{v}}_{2,\delta }|_{\omega _\delta ^z} = \mathbf{{v}}_2(z_\delta )\), respectively.
Using the uniform continuity of \(\mathbf{{v}}_2\) and \(\mathbf{{v}}_1\) on \(\overline{\Omega }\), we obtain that \(\left| \overline{I}^k_\delta - \overline{I}^k \right| \le \beta (\delta )\) for a monotonically increasing continuous function \(\beta : \mathbb {R}^+_0 \rightarrow \mathbb {R}\) with \(\beta (0) =0\). In particular, the convergence is uniform with respect to k. The same argument applies for the difference of I and
Thus \( \det ( \text {P}(\mathbf{{v}}_2(z_\delta )) A \text {P}(\mathbf{{v}}_1(z_\delta )) + \mathbf{{v}}_2(z_\delta ) \otimes \mathbf{{v}}_1(z_\delta )) = \det (\tilde{A})\) represents an \((n-1)\times (n-1)\) minor of the linear mapping corresponding to the matrix A with respect to different orthogonal basis in preimage space (associated with \(\text {P}(\mathbf{{v}}_1(z_\delta ))\) and \(\mathbf{{v}}_1(z_\delta )\)) and the image space (associated with \(\text {P}(\mathbf{{v}}_2(z_\delta ))\) and \(\mathbf{{v}}_2(z_\delta )\)). Indeed, denoting \(Q_i:=Q(\mathbf{{v}}_i(z_\delta ))\) we have
where we have used the orthogonal change of variables \(y = Q_1^T x\) and \({{\text {Cof}}}_{nn}\) denotes the minor obtained by erasing the last column and the last row. This change of orthogonal coordinates is fixed on each cell \(\omega _\delta ^z\). Since for each \(\delta \) the domain \(\Omega \) is covered by finitely many cells \(\omega _\delta ^z\), using the above computation and standard weak continuity results [20, Theorem 8.20] for determinants of minors of the Jacobian we obtain that \(\bar{I}^k_\delta \rightarrow \bar{I}_\delta \) for \(k\rightarrow \infty \). Finally, for given \(\epsilon \) we first choose \(\delta \) small enough to ensure that \(\left| \bar{I}_\delta - I \right| + \left| \bar{I}^k_\delta - \bar{I}^k \right| \le \tfrac{\epsilon }{2}\). Then, we choose k large enough to ensure that \(\left| I^k - \bar{I}^k \right| + \left| \bar{I}^k_\delta - \bar{I}_\delta \right| \le \tfrac{\epsilon }{2}\). This proves that a subsequence of \(I^k\) converges to I for \(k\rightarrow \infty \). Since the limit does not depend on the subsequence, we finally obtain weak convergence for the whole sequence.
To prove (4.2), consider the three sequences of matrix functions
The determinant of the second expression above converges weakly as \(k \rightarrow \infty \) by the first part of the lemma, while the determinants of the first and third can be assumed to converge uniformly. Moreover, the matrices in (4.3) have the block structure shown in (2.3), so multiplying the three together and taking into account that \(\text {P}\) is a projection (depending on the argument) recovers the matrix
appearing in the statement. Multiplicativity of the determinant and the fact that a product of strongly converging and one weakly converging sequence converges weakly then finishes the proof. \(\square \)
We are now in a position to prove existence of a minimizing deformation for the hypersurface matching energy E in a suitable set of admissible deformations. Of particular difficulty is that derivatives of \(\mathbf{{d}}_2\) are not defined in the whole of \(\Omega \) and that in the functional these derivatives are evaluated at deformed positions. We handle this by ensuring that the involved deformations are such that terms involving these derivatives are not evaluated near the singularities. We obtain the following theorem:
Theorem 4.2
(Existence of minimizing deformations) Let \(\mathcal {M}_1,\mathcal {M}_2\) be \(C^{2,1}\) compact embedded hypersurfaces in \(\mathbb {R}^n\) such that a \(C^1\) diffeomorphism \(\varphi : \mathcal {M}_1 \rightarrow \mathcal {M}_2\) exists between them.
where \({\text {sing}}\,\mathbf{{d}}_i\) is the set of points where \(\mathbf{{d}}_i\) is not differentiable, and that \({\mathcal {C}}:\mathbb {R}^{n \times n} \rightarrow \text {SPD}(n)\) is continuous. Then there exists a constant \(0 < \nu _0 := \nu _0(\Omega , \mathcal {M}_1, \mathcal {M}_2, \sigma , p, \alpha _p)\) such that for \(0 < \nu \le \nu _0\), the functional \(E_\nu \) has at least one minimizer \(\phi \) among deformations in the space \(W^{1,p}_0(\Omega ; \mathbb {R}^{n})+{\text {id}}\). Moreover, \(\phi \) is a homeomorphism of \(\Omega \) into \(\Omega \), and \(\phi ^{-1}\in W^{1,\theta }(\Omega ; \mathbb {R}^{n})\), where \(\theta \) is given by \(\theta =q(1+s)/(q+s)\).
Proof
We proceed in several steps.
Step 1 Coercivity First, we point out the coercivity enjoyed by our functional. Using the Poincaré and Morrey inequalities ([41], Theorem 12.30 and 11.34), and the Dirichlet boundary conditions we have
for any \(\phi \in W^{1,p}_0(\Omega )+{\text {id}}\) and \(\alpha =1-n/p\).
Step 2 Lower semicontinuity along sequences of constrained deformations For the remainder of the proof, a deformation \(\phi \in W^{1,p}_0(\Omega ; \mathbb {R}^n) + {\text {id}}\), \(p>n\) is termed \(\rho \)-admissible for \(\rho > 0 \), if
\(E_{\text {vol}}[\phi ]< +\infty \),
\(\det \mathcal {D}\phi (x) > 0\) for a.e. \(x \in \Omega \), and
for all \(x \in {\text {supp}}\,\big ( \eta _\sigma \circ \mathbf{{d}}_1 \big )\) and every \(y \in {\text {sing}}\,(\mathbf{{d}}_2)\), we have \(\left| \phi (x) - y \right| \ge \rho \).
Notice that since \(p>n\), \(\phi \) has a unique continuous representative, so the third property is well defined.
First, notice that with the assumption (4.4) we have
Let \(\phi ^k\) be a sequence of \(\rho \)-admissible deformations with \(E_{\text {vol}}[\phi ^k]\le C\). By (4.5) and using the Banach–Alaoglu and Rellich–Kondrakov theorems, a subsequence (again denoted by \((\phi ^k)\)) converges to a deformation \(\phi \), both in the \(W^{1,p}\)-weak and uniform topologies.
Additionally, since (4.7) holds and because \(E_\nu [\phi _k]\) is bounded, \(\int _\Omega (\det \mathcal {D}\phi _k)^{-s} d x\) is bounded by the definition of \(\hat{W}\) and \(\det \mathcal {D}\phi _k \ge 0\) a.e. Together with (4.7), we have
Notice also that by a.e. positivity of the determinants, (4.7) and a standard lower semicontinuity result for convex integrands (see, e.g., [20, Theorem 3.23]) implies
with \(\chi _{\{|\mathbf{{d}}_1|\le \sigma \}}\) denoting the indicator function. Combining (4.11) with the polyconvexity of W, defining the function \(E_{\text {mem}}\), both introduced in (3.1) we find the assertion (4.9).
Furthermore, by our assumptions on \(\mathcal {M}_i\) (see Sect. 2), we have that
Since \({\mathcal {C}}\) produces uniformly positive matrices, we have \(\chi _{\{|\mathbf{{d}}_1|\le \sigma \}}({\mathcal {C}}({\mathcal {S}}^{ext}_1))^{-1}\in C^0(\overline{\Omega }; \mathbb {R}^{n \times n})\). We can then use a continuity result for square roots of nonnegative definite matrix-valued functions defined on \(\Omega \) [15, Theorem 1.1] to see that
The second part of Lemma 4.1 implies the weak convergence
from which (4.10) follows by using the polyconvexity of W.
Step 3 Existence of minimizers restricted to admissible deformations Since we have already seen that the set of \(\rho \)-admissible deformations is weakly closed and weakly compact, and that every term of E is weakly lower semicontinuous on this set, we just need to check that for all fixed \(\nu > 0\), the set of \(\rho \)-admissible deformations, with adequate \(\rho \), is not empty.
For some given \(\sigma \) satisfying \({\text {dist}}( \mathcal {M}_2, {\text {sing}}\,\mathbf{{d}}_2 ) - \sigma > 0\) let \(\rho \) satisfy
We construct a deformation \(\hat{\varphi }\), which is \(\rho \)-admissible and satisfies \(E_\nu [\hat{\varphi }] < \infty \). By assumption, there exists a diffeomorphism \(\varphi :\mathcal {M}_1\rightarrow \mathcal {M}_2\). Thus, we construct an extension of this diffeomorphism to \(\{|\mathbf{{d}}_1|\le \sigma \}\) along the normal directions using
We can then extend \(\hat{\varphi }\) to the inside and outside components \(\Omega _i, \Omega _o\) of \(\Omega \setminus \{|\mathbf{{d}}_1|\le \sigma \}\) by solving the minimization problems for \(E_{{\text {vol}}}\) with Dirichlet boundary conditions given by (4.13) on \(\partial \Omega _i\) and \(\partial \Omega _o \setminus \partial \Omega \), and by \(\hat{\varphi }(x)=x\) on \(\partial \Omega \). For the resulting \(\hat{\varphi }\), we have
where the first two statements follow by construction, and the last two by virtue of \(\varphi \) being a diffeomorphism and the choice of \(\sigma \). Moreover, we note that since \(\hat{\varphi }\) has finite energy and the growth conditions assumed for \(\hat{W}\) [see (3.7)], the condition \(\det \mathcal {D}\hat{\varphi }(x) > 0\) for a.e. x is also satisfied [4].
Step 4 A priori estimate to remove the constraint Next, we show that for any \(\rho \) satisfying (4.12) there exists a parameter \(\nu _0 > 0\) such that for all \(0< \nu < \nu _0\) the constrained minimizers of \(E_\nu \) subject to (4.4) solves the unconstrained optimization problem, consisting in minimizing \(E_\nu \) on \(W_0^{1,p}+{\text {id}}\).
To this end, we verify that every \(\phi \) that satisfies
is \(\rho \)-admissible. It is immediate from (4.14) that \(E_{\text {vol}}(\phi ) < + \infty \), and from the definition of \(\hat{W}\) in (3.7) it follows with the same arguments as in (4.8) that \(\det \phi > 0\) a.e.
We prove now that for all deformations \(\phi \) satisfying (4.14) also satisfy
By the monotonicity of \(\eta _\sigma \) and the fact that the signed distance functions \(\mathbf{{d}}_i\) are Lipschitz continuous with constant 1 we have, for each \(\hat{\sigma } \in (0, \sigma )\) that
Now we can apply Ehrling’s lemma [54, Theorem 7.30] for the embeddings \( W^{1,p}(\Omega ) \subset \subset L^\infty (\Omega ) \subset L^2(\Omega )\) to control the last term in (4.19). Taking into account, the Poincaré inequality and Dirichlet boundary conditions, we obtain for any \(\epsilon > 0\) a constant \(C(\epsilon ) > 0\) such that
where we have applied the product rule, the definition of \(E_{\text {match}}\), \(\eta _\sigma \in C^\infty _0\), \(\eta _\sigma \le C\), that \(| \nabla \mathbf{{d}}_i | = 1\) a.e., \(i=1,2\), the chain rule, and (4.14). The use of the chain rule is justified by [46, Theorem 2.2], since \(\mathbf{{d}}_2\) has Lipschitz constant 1.
In light of (4.19) and (4.23), and since \(E_\nu [\hat{\varphi }]\) is independent of \(\nu \), we can now choose first \(\hat{\sigma }\), then \(\epsilon \) and finally \(\nu \) small enough to obtain
Step 5 Injectivity The injectivity and regularity of the inverse follow by the growth conditions satisfied by \(E_\text {vol}\) and classical results of Ball [4, Theorems 2 and 3]. Note that Theorem 3 in [4] is stated in the mechanical application context in dimension \(n=3\), but it holds also in \(\mathbb {R}^n\) following the same proof and using the condition \(s>(n-1)q/(q-n)\). \(\square \)
We have particularized the statement of Theorem 4.2 to the case of Dirichlet boundary conditions to ensure global invertibility. In fact, we also have existence of minimizing deformations for the case of Neumann boundary conditions.
Corollary 4.3
(Natural boundary conditions) Under the assumptions of Theorem 4.2, there exists a constant
such that for \(0 < \nu \le \nu _N\), the functional \(E_\nu \) possesses at least one minimizer among deformations in the space \(W^{1,p}(\Omega ; \mathbb {R}^{n})\).
Proof
The proof follows the same arguments used for Theorem 4.2, so we only point out the necessary modifications. We need a replacement for the coercivity estimate (4.5) and claim
To verify this let us consider \(\omega :=\{|\mathbf{{d}}_1| \le \sigma /2 \}\). An adequate Poincaré inequality (see, e.g., [41, Theorem 12.23]) implies that
where Hölder’s inequality has been used to compare \(L^1\) and \(L^2\) norms. Therefore, (4.24) follows.
The proof of the estimate for \(\Vert \mathbf{{d}}_2 \circ \phi \Vert _{L^\infty (\{|\mathbf{{d}}_1| \le \sigma \})}\) (to ensure that deformations stay away from the singularities of \(\mathbf{{d}}_2\)) is still valid with minor modifications, since \(\nu \) appears in (4.24) multiplicatively. \(\square \)
We conclude this section with the following proposition, which explores the penalization limit in which the parameter \(\nu \) tends to zero.
Proposition 4.4
Let \(\{\nu _k\}_{k \in \mathbb {N}}\), be a sequence of penalty matching parameters such that \(\nu _k \rightarrow 0\) as \(k \rightarrow \infty \), and \(\phi ^k\) be solutions of the Dirichlet minimization problem for \(E_{\nu _k}\). Then, up to a choice of subsequence, the \(\phi ^k\) converge strongly in \(W^{1,p}\) to a minimizer of
in \(W_0^{1,p}(\Omega ;\mathbb {R}^n)+{\mathbb {1}}\) under the constraint \(\phi (\mathcal {M}_1^{c}) = \mathcal {M}_2^{c}\) for all \(c \in (-\sigma , \sigma )\).
where \(H:\mathbb {R}^+ \times \mathbb {R}^{n \times n} \times \mathbb {R}^{n \times n} \times \mathbb {R}\times \mathbb {R}^{n \times n} \times \mathbb {R}\rightarrow \mathbb {R}^+\) is smooth and convex.
Denote by \(\hat{\varphi }\) the extension of a diffeomorphism between \(\mathcal {M}_1\) and \(\mathcal {M}_2\) used in the proof of Theorem 4.2. Since \(E_{\text {match}}[\hat{\varphi }]=0\), we have that \(E_{\nu _k}[\phi ^k] \le E_1[\hat{\varphi }]\). By the coercivity estimate (4.5), the \(\phi ^k\) are then bounded in \(W^{1,p}\) and we may extract a (not relabeled) subsequence converging uniformly and weakly in \(W^{1,p}\) to some limit \(\phi \). Since \(\{E_{\nu _k}[\phi ^k]\}\) is bounded and \(\nu _k \rightarrow 0\), the uniform convergence of \(\phi ^k\) implies that
In consequence, \(\phi (\mathcal {M}_1^c)\subseteq \mathcal {M}_2^c\). Since \({ \left. \phi \phantom {\big |} \right| _{\mathcal {M}_1^c} }\) is the uniform limit of the maps \({ \left. \phi ^k \phantom {\big |} \right| _{\mathcal {M}_1^c} }\) which are surjective onto \(\mathcal {M}_2^c\) and \(\mathcal {M}_1^c\) is compact, we conclude that \(\phi (\mathcal {M}_1^c)=\mathcal {M}_2^c\) for all \(c \in (-\sigma , \sigma )\). Therefore, \(\phi \) is admissible for all \(\nu _k\) and \(E_{\nu _k}[\phi ^k] \le E_{1}[\phi ]\). Combined with lower semicontinuity and (4.25), the above implies
From this identity, the fact that H is convex and differentiable, and \(\mathcal {D}\phi ^k \rightharpoonup \mathcal {D}\phi \) in \(L^p\) it follows that
Because \(L^p(\Omega )\) has the Radon-Riesz property ([47, 2.5.26]), weak convergence and convergence of the norm guarantee strong convergence. Since \(\phi _k\) was assumed to converge uniformly, we have also \(\phi _k \rightarrow \phi \) in \(L^p\), and this shows that \(\phi _k \rightarrow \phi \) in \(W^{1,p}(\Omega ; \mathbb {R}^{n})\).
That \(\phi \) is a minimizer of the constrained problem follows directly ([8], Theorem 1.21) from the fact that the \(E_{\nu _k}\) are an equicoercive family of functionals, \(\Gamma \)-converging in the weak topology of \(W^{1,p}\). Indeed, equicoercivity follows easily from the above, while \(\Gamma \)-convergence is implied by the fact that \(E_{\nu _k}\) is an increasing sequence ([8], Remark 1.40), because \(\nu _k \rightarrow 0\) appears as a denominator in \(E_{\text {match}}\). \(\square \)
Remark 4.5
By the coercivity estimate (4.24) of Corollary 4.3, an entirely analogous result holds for minimizers with Neumann boundary conditions.
Remark 4.6
Contrary to what might be expected, the limit problem we have obtained is not a surface problem, since all the level sets are still coupled through the volume energy \(E_{\text {vol}}\). The line of reasoning above depends heavily on the fact that the coefficients of the volume term are held fixed, since the equicoercivity and uniform strict quasiconvexity (in the language of [25]) both require the presence of \(\Vert \mathcal {D}\phi \Vert ^p_{L^p(\Omega )}\) in the functional.
4.1 Oscillations and Lack of Rank-One Convexity for the Naive Approach
To model the tangential distortion energy we have considered a frame indifferent energy density with the argument \(\mathcal {D}_{\text {tg}}\phi +(\mathbf{{n}}_2 \circ \phi ) \otimes \mathbf{{n}}_1\). Let us now consider the case \(n=2\) and a simpler version of the membrane energy (3.6), where we use as an argument of the energy density directly the tangential Cauchy–Green strain tensor [cf (2.2)] \(({{{\tilde{\mathcal {D}}}}}_{tg}\phi (x))^T ({{{\tilde{\mathcal {D}}}}}_{tg}\phi (x)) + \mathbf{{n}}_1(x) \otimes \mathbf{{n}}_1(x)\), and define the membrane energy
with \({{{\tilde{\mathcal {D}}}}}_{tg}\phi := \mathcal {D}\phi \text {P}_1\) defined as the tangential part of the derivative along \(T_x \mathcal {M}_1^{\mathbf{{d}}_1(x)}\), and \(W:\mathbb {R}^{2 \times 2}\rightarrow \mathbb {R}\) a frame indifferent energy density that has a strict minimum at \(\text {SO}(2)\). In fact, this energy is no longer lower semicontinuous and we will present counterexamples.
Example 4.7
(Oscillation patterns) We construct an explicit sequence for which lower semicontinuity of the membrane energy \({\tilde{E}}_\text {mem}\) fails. Fix \(0<R<1\) and \(\mathcal {M}_1 = \mathbb {S}^1\) with the parametrization \(\xi \rightarrow e^{i \xi }\). Consider a sequence of deformations \(\varphi _k: \mathbb {S}^1 \rightarrow \mathbb {R}^2\) defined in polar coordinates of \((r, \theta )\) by the condition
where \(e_r=(\cos \theta , \sin \theta )^T, e_\theta =(-\sin \theta , \cos \theta )^T\) for given \(\phi _k(0)\). Note that for any k and \(\theta \) that \(|\partial _\theta \varphi _k(\theta )|=1\), so that the transformations are tangentially isometric. We define \(\varphi _k(0)\) via two integration constants \(r_0\) and \(\theta _0\) for the initialization of r and \(\theta \) at \(\xi =0\). We set \(\theta _0=0\) and choose \(r_0\) such that the curve \(\varphi _k\) is closed and simple, which imposes \(r_0=r(\varphi _k(0))=r(\varphi _k(2\pi ))\) since the first term in (4.29) has zero average. From the second term, taking into account that \(e_\theta (r, \theta )\) is independent of r, we get the condition
where we have applied the change of variables \(\zeta = k \xi \). By periodicity the right-hand side (an incomplete elliptic integral of the second kind with modulus R) is independent of k and thus determines \(r_0\). The resulting \(\varphi _k\) for several values of k are depicted in Fig. 3.
We observe that \(\partial _\theta \varphi _k(\theta ) \rightharpoonup r_0 e_\theta \text { in }L^p,\) for any \(1 \le p < \infty \) (and also weak-* in \(L^\infty \)). Therefore, the weak \(W^{1,p}\)-limit \(\varphi \) of the \(\varphi _k\) is the function defined by \(\varphi (\theta )=r_0 e_r\) and obviously not an isometry. Assuming \(0< \sigma < 1\) and extending \(\varphi _k, \varphi \) along the radial direction \(e_r\) to the annulus \(\{1-\sigma \le r \le 1+\sigma \}\), we obtain corresponding deformations given by
where \(Q_{\frac{\pi }{2}}\) stands for clockwise rotation by \(\pi /2\), so that \(Q_{\frac{\pi }{2}}\partial _\theta \varphi _k(\theta )\) is the unit outward normal to \(\varphi _k(\mathbb {S}^1)\). Clearly also \(\phi ^k \rightharpoonup \phi \) in \(W^{1,p}\) on the annulus. We observe that \({\tilde{E}}_{\text {mem}}[\phi ^k]=0\), but \({\tilde{E}}_{\text {mem}}[\phi ]>0\). Hence, \({\tilde{E}}_\text {mem}\) is not weakly lower semicontinuous.
×
The celebrated Nash–Kuiper theorem [37, 51] states that it is possible to uniformly approximate any short \(C^\infty \) immersion by \(C^1\) isometric ones. Our explicit oscillations around \(r_0 \mathbb {S}^1\) is just one example of this phenomenon. Notice that a bending term of the type \(E_{\text {bend}}\) introduced in our model only compares the curvatures of \(\mathcal {M}_1^{\mathbf{{d}}_1(x)}\) and \(\mathcal {M}_2^{\mathbf{{d}}_2(\phi (x))}\). It therefore does not penalize oscillations, since it does not detect the curvature of \(\phi (\mathcal {M}_1)\) at all.
Example 4.8
(Lack of rank-one convexity) We present an additional example of a configuration for which the integrand of an energy of the type \({\tilde{E}}_{\text {mem}}\) is not rank-one convex. Rank-one convexity of the complete energy density, i.e., , convexity in \(t \in \mathbb {R}\) when composed with the function \(A+tB\) for any matrix A and any rank-one matrix B, is known to be a necessary condition for quasiconvexity ([20], Theorem 5.3). Quasiconvexity, in turn, is necessary for weak lower semicontinuity of integral functionals in Sobolev spaces ([20], Theorem 8.1 and Remark 8.2).
Let \(\Omega =(-2,2)^2\), and \(\mathcal {M}_1\) be a closed \(C^2\) curve such that \(\mathcal {M}_1 \cap (-1,1)\times (0,2)=(-1,1)\times \left\{ 1\right\} \). At any point \(x_0 \in (-1,1)\times \left\{ 1\right\} \), the tangential derivatives are just partial derivatives along the first coordinate, yielding
has a pointwise minimum, with value zero, whenever \(\mathcal {D}\phi \) is such that \(\left( \partial _1 \phi _1\right) ^2 + \left( \partial _1 \phi _2\right) ^2=1\).
Consider now, for \(0\le \lambda \le 1\), the family of matrices
Clearly \(B(\lambda )\) is rank one. But we have \(W_F(B(\lambda ))=\lambda ^2+(1-\lambda )^2+\frac{1}{\lambda ^2+(1-\lambda )^2}-2\) and therefore
$$\begin{aligned} W_F(B(0))=F(B(1))=0, \text { but }W_F( B(1/2))=\frac{1}{2}, \end{aligned}$$
which demonstrates that \(W_F\) is not rank-one convex.
5 Finite Element Discretization Based on Adaptive Octrees
We adopt a ‘discretize, then optimize’ approach and consider a finite element approximation and optimize for the coefficients of the solution. Since the energy \(E_\nu \) is highly nonlinear and nonconvex, we use a cascadic multilevel minimization scheme in which the solution for one grid level is used as the initial data for the minimization on the next finer grid. We use adaptive refinement of the underlying meshes around the surfaces \(\mathcal {M}_1, \mathcal {M}_2 \subset (0,1)^n\) for \(n=2,3\) (Algorithm 1).
One of the main characteristics of our functional is the pervasive presence of coefficients depending on the deformed position \(\phi (x)\). Indeed, this is how the functional takes into account the geometry of target surface, through the projection \(\text {P}_2\) and shape operator \({\mathcal {S}}_2\). From an implementation perspective, however, this means that frequently discrete functions have to evaluated at deformed positions. Therefore, the ability to efficiently search the index of an element containing a given position is of paramount importance, so a hierarchical data structure that allows for efficient searching is needed. The model only contains first derivatives of the unknown deformation. Hence, multilinear finite elements already allow a conforming discretization. For these reasons we use multilinear FEM on octree grids. The grids used are such that all of the elements are either squares or cubes of side length \(h=2^{-\ell }\), for an integer \(\ell \) to which we refer as grid level of the element. In what follows let us detail the different ingredients of the algorithm.
×
Multilinear Finite Elements on Octrees We assume \(n=3\) for the presentation here. Using an adaptive octree grid based on cubic cells leads to hanging nodes (see Fig. 4), nodes which are on the facet of a cell without being one of its vertices. Enforcing continuity of the finite element functions leads to constraints for function values on hanging nodes and these hanging nodes are not degrees of freedom. Additionally, to minimize the complexity of the required interpolation rules, the subdivision is propagated in such a way that the grid level of neighboring elements sharing a cell facet differs at most by one.
×
Octrees and the access to degrees of freedom via hashtables Even though the tree structure gives a natural hierarchical structure to the elements of the mesh, maintaining consistent linear indices for degrees of freedom, hanging nodes, and elements can be delicate. Consistent rules could be devised to maintain consistency with the element octree for a given mesh, but these would not be easy to update when the grid is refined. In order to keep track of vertex indices in a simple manner without sacrificing efficiency, hash maps ([19], Chapter 11) are maintained to keep track of the indices of degrees of freedom, hanging nodes, and cells. The keys used in the hashmap are a combination of a level value \(\ell \) and point coordinates as integer multiples of \(h=2^{-\ell }\). These keys uniquely identify nodes or elements, with the convention that an element is identified with its lower-left-back corner. Whenever a query for a node or cell is made, there are two possible outcomes. If it is already contained in the corresponding hash table, a linear index for it can be retrieved. Otherwise, a new entry of the hash table is created and the node or cell is given the next unused index. Since we do not require coarsening of the mesh, this scheme guarantees a consistent linear set of indices with a computational cost for insertions and queries that is, on average, independent of the mesh size.
Computing distance functions on octrees In our model, we have assumed that the distance functions to our surfaces are given. In practice, especially when using adaptive grids, we need to compute signed distance functions on such grids. This has been accomplished by a straightforward adaptation of the Fast Marching Method on cartesian grids [57] exploiting the fact that our grids still are subgrids of a regular cartesian grid. In the implemented variant hanging nodes are not taken into account for the propagation, their values being linearly interpolated to accommodate the constraints needed for conformality. The initialization for the distance computation has been performed starting from triangular meshes of the surfaces (for \(n=3\); for \(n=2\) two-bit segmentation of interior and exterior of the curves has been used). The signs of the distance functions have to be computed separately, by detecting which points of the grid are inside (resp. outside) the initial surface data. In our case, they have been computed with the provably correct algorithm given in [2].
Computation of the coefficients The discretization for the unknown deformation \(\phi \), as already mentioned, is done by multilinear finite elements. However, the coefficients of our model include first and second derivatives of the signed distance functions \(\mathbf{{d}}_i\), for the normal vectors \(\mathbf{{n}}_i\) and shape operators \({\mathcal {S}}_i\) (\(i=1,2\)), respectively. The approximations are required to be robust, since they appear in the highest order terms of the model. For the normal vectors \(\mathbf{{n}}_i\), we compute the \(L^2\) projection of the finite element derivative of \(\mathbf{{d}}_i\) to recover the nodal values of a piecewise multilinear function, followed by a orthogonal projection to the unit sphere to restore the constraint \(| \mathbf{{n}}_i | = 1\).
In the case of the shape operators, our approach is to approximate the distance functions \(\mathbf{{d}}_i\) by a quadratic polynomial supported on a neighborhood of each point. Given a fixed integer neighborhood size r, for each nonhanging node \(x_k\) (i.e., the neighborhood \(B_r(x_k)\) contains the r closest other degrees of freedom of the adaptive grid) the local quadratic polynomial \(p_k\) is defined as the one minimizing the least-squares error
which can be easily computed by inverting a small matrix. The Hessian of \(\mathbf{{d}}_i\) at the node \(x_k\) is then approximated by the Hessian of \(p_k\).
For the computation of matrix square roots and their inverses, we have used the method described in [26], taking appropriate care to truncate almost-singular matrices, since the resulting square roots also appear inverted.
Minimization strategy For the minimization at each level, we have opted for a Fletcher-Reeves nonlinear conjugate gradient method ([52], Section 5.2). The \(L^2\) gradient of \(E_\nu \), whose computation is involved but elementary, was implemented directly. The parameter \(\alpha \) is progressively reduced when a further feasible descent step is not found, according to an Armijo line search ([52], Section 3.1).
6 Numerical Results
All of our results have been computed on the unit cube \(\Omega =[0,1]^3\) for the matching of surfaces in 3D, and the unit square \([0,1]^2\) for the matching of contour curves in 2D. In practice, we have used homogeneous Neumann boundary conditions, since this allows to have relatively large shapes \(\mathcal {M}_i\) in comparison with the size of the domain \(\Omega \) without creating excessive volume energies near the boundary (for the justification we refer to Corollary 4.3). However, if the boundary is not fixed, the deformed domain \(\phi (\Omega )\) is not necessarily contained in \(\Omega \), so evaluation of coefficients on deformed positions has to be appropriately handled numerically. We use a projection of outside position onto the boundary of \(\Omega \) for sufficient large \({\text {dist}}(\mathcal {M}_2, \partial \Omega )\).
For the membrane and the bending energy we use the material parameters \(\lambda =\mu =1\), corresponding to the density
$$\begin{aligned} W(A)=\frac{1}{2}| A |^2 + \frac{1}{4} (\det A)^2 + \frac{3}{2}e^{- ( \det A - 1 ) } - \frac{13}{4}. \end{aligned}$$
In the bending term, the shape operators have been regularized through the truncated absolute value function with \(\tau =1\). Since we work on the unit cube, this corresponds to a comparatively large curvature radius. For the volume term, given that enforcing orientation preservation in a finite element framework is a far from straightforward, it is advantageous to work with the simplified version
We have run the minimization scheme of Algorithm 1 beginning from a uniform grid of level \(\ell _{\text {min}}=2\) or \(\ell _{\text {min}}=3\) with \(9^3=729\) nodes, and refined up to \(\ell _{\text {max}}=8\) for 3D examples. For 2D cases, a reasonable range turned out to be \(\ell _{\text {min}}=4, \ell _{\text {max}}=10\). The finest grids used for two of the examples below are depicted in Fig. 4. The width of the narrow band was chosen proportional the finest resolution of the mesh (\(\sigma =2h\)) since a small value of \(\sigma \) clearly produces inaccurate results when \(\eta _\sigma \) is evaluated on coarse grids. However, the constraint \(\int _\Omega \eta _\sigma = 1\) ensures that the overall strength of the surface terms \(E_{\text {match}}\), \(E_{\text {mem}}\) and \(E_{\text {bend}}\) is not affected. The value of the penalty constraint \(\nu \) was divided by 10 for each grid refinement, which is justified by Proposition 4.4. Furthermore, the volume weight \(c_{\text {vol}}\) was also halved per level to allow for simultaneously higher initial regularization and close final matches. Note that this reduction is much slower than that of the matching parameter.
In all examples, we have used the identity as the initial deformation. It should be noted that although the energy is geometric by design, we are using a first-order descent method for its minimization. In consequence, an adequate rigid pre-alignment can be beneficial for intricate shapes. Figure 8 shows results for the matching of two different dolphin shapes. Our variational approach is highly nonlinear and nonconvex. Thus, the numerical approximation of the globally optimal deformation depends on the initialization of the deformation. Figure 9 shows that the identity deformation as the initial deformation is advisable only if the expected optimal deformation is not too large. This is demonstrated by applying different rigid body motions to \(\mathcal {M}_1\).
×
×
×
×
All figures have been produced by deforming the input data (polygonal curve or triangulated surface) via the resulting deformation \(\phi \). This is in contrast to deforming the grid and plotting the resulting extracted level sets (which effectively visualizes the inverse deformation), as commonly done in the registration literature, and also in [32].
Test case First, we present a simple test case to underline the qualitative properties of our model. Figure 5 shows a configuration in which a high amount of compression, combined with rotation, is required. Our model finds the intuitively correct deformation, but oscillations typical for the lack of lower semicontinuity of the underlying energy are induced when \(\text {P}_2\) is not used in the membrane and bending terms. The bending term assists in matching the curvatures even if the deformation is not rigid. Note, however, that for the optimal match the curvature energy \(E_{\text {bend}}\) is not expected to vanish, as can easily be seen from (2.6), (3.4) and the related discussion in Sect. 3.
×
×
×
Shape matching applications We now turn our attention to high-resolution examples with real data. Figure 6 demonstrates the effect of the multilevel descent scheme, in which details are added progressively to avoid spurious local minima. In Fig. 11, a high-resolution 2D example is presented. Figures 7, 8, 9 and 10 show 3D examples in which the influence of the curvature matching is indispensable to obtain shape sensitive matching deformations. For these examples, the shell parameter \(\delta \) was chosen quite high, since the curvature matching term \(E_{\text {bend}}\) is a major driving force to obtain correct matching of geometric features. Table 1 lists the parameter values used, and run times for our implementation. We have split the timings between the highest resolution level and the combined previous ones, since in many applications a very high level of detail might not be necessary, thereby significantly reducing the required computational effort.
Table 1
Parameters and running times on a workstation with a single Intel Xeon E5-1650 CPU (6 cores, 3.2 Ghz)
Figs.
\(\ell _{\text {min}}, \ell _{\text {max}}\)
\(\delta \)
\(c_{\text {vol}}, \nu \) at \(\ell _{\text {min}}\)
Our implementation splits the computation of the different terms of the energy and the corresponding derivatives in different threads (obtaining a speedup factor \(\approx 2\)), but no further parallelization is used
Acknowledgements
Open access funding provided by University of Vienna. This research was supported by the Austrian Science Fund (FWF) through the National Research Network ‘Geometry+Simulation’ (NFN S117) and Doctoral Program ‘Dissipation and Dispersion in Nonlinear PDEs’ (W1245). Furthermore, the authors acknowledge support of the Hausdorff Center for Mathematics at the University of Bonn. We would like to thank the anonymous reviewers for comments that have led to substantial improvements in this paper. The shapes for Fig. 8 are originally from the McGill 3D Shape Benchmark [58]. The scanned faces of Fig. 6 are part of the 3D Basel Face Model dataset [53]. The laser-scanned sugar beets of Fig. 10 and the original shapes for Fig. 7 were kindly provided by Behrend Heeren.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.