Bruno Lévy
email: bruno.levy@inria.fr

Laplace-Beltrami Eigenfunctions Towards an algorithm that "understands" geometry

One of the challenges in geometry processing is to automatically reconstruct a higher-level representation from raw geometric data. For instance, computing a parameterization of an object helps attaching information to it and converting between various representations. More generally, this family of problems may be thought of in terms of constructing structured function bases attached to surfaces.

In this paper, we study a specific type of hierarchical function bases, defined by the eigenfunctions of the Laplace-Beltrami operator. When applied to a sphere, this function basis corresponds to the classical spherical harmonics. On more general objects, this defines a function basis well adapted to the geometry and the topology of the object.

Based on physical analogies (vibration modes), we first give an intuitive view before explaining the underlying theory. We then explain in practice how to compute an approximation of the eigenfunctions of a differential operator, and show possible applications in geometry processing.

Motivations

These last few years, mesh parameterization is a topic for which much time and effort has been devoted to. Floater in his recent survey [START_REF] Floater | Surface parameterization: a tutorial and survey[END_REF] reviews a large number of methods for objects with disc topology. More recently, the geometry processing community started to study methods that could be applied to objects of arbitrary topology, based for instance on holomorphic one-forms [START_REF] Gu | Global conformal parameterization[END_REF]. Such an interest for parameterization methods is justified by the fact that it facilitates attaching attributes to surfaces. For instance, such attributes may be physical properties simulated by a PDE solver. Adapting a finite-element method to this representation of surfaces is easy, and is often referred to as the master element method (see e.g. [START_REF] Lecot | Masterelement vector irradiance for large tessellated models[END_REF]). However, recent advances in PDE solving and in calculus suggest that a parameterization may not be the best representation of geometry and attributes attached to the geometry. For instance, to construct a hierarchical representation, the CHARMS method presented in [START_REF] Grinspun | Charms: A simple framework for adaptive simulation[END_REF] suggests to use function basis refinement instead of finite element refinement. This function-centric view leads to simpler computations. The external calculus and its discrete counterparts are also leading towards this direction (see e.g. Desbrun and Schroeder's course at Siggraph 2005).

For this reason, rather than seeking for a global parameterization of the objects, we will investigate algorithms that create a function basis over an object of arbitrary topology. Surprisingly, as shown further, the underlying basic principles (Laplace operator) are present in a wide variety of disciplines of computer graphics and geometry processing.

The remainder of this paper is organized as follows. Section 2 reviews spectral analysis used in the discrete setting. Section 3 explains the links with the continuous setting and the Laplace-Beltrami operator. Section 4 presents some possible applications in geometry processing.

The discrete setting: Graph Laplacians

Spectral graph theory was used for instance in [START_REF] Isenburg | Streaming meshes[END_REF] to compute an ordering of vertices in a mesh that facilitates out-of-core processing. Such a natural ordering can be derived from the Fiedler eigenvector of the Graph Laplacian. The Graph Laplacian L = (a i,j ) is a matrix defined by:

a i,j = w i,j > 0 if (i, j) is an edge a i,i = -w i,j ) a i,j = 0 otherwise
where the coefficients w i,j are weights associated to the edges of the graph. One may use the uniform weighting w i,j = 1 or more elaborate weightings, computed from the embedding of the graph. The first eigenvector of the Graph Laplacian is (1, 1 . . . 1) and its associated eigenvalue is 0. The second eigenvector is called the Fiedler vector and has interesting properties, making it a good permutation vector for numerical computations [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF][START_REF] Fiedler | A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory[END_REF]. It has many possible applications, such as finding natural vertices ordering for streaming meshes [START_REF] Isenburg | Streaming meshes[END_REF]. Figure 1 shows what it looks like for a snakelike mesh (it naturally follows the shape of the mesh).

More insight on the Fiedler vector is given by the following alternative definition. The Fiedler vector u = (u 1 . . . u n ) is the solution of the following constrained minimization problem:

Minimize: F (u) = u t Lu = i,j w i,j (u i -u j ) 2 Subject to: i u i = 0 and i u 2 i = 1 (1)
In other words, given a graph embedded in some space, and supposing that the edge weight w i,j corresponds to the lengths of the edges in that space, the Fielder vector (u 1 . . . u n ) defines a (1-dimensional) embedding of the graph on a line that tries to respect the edge lengths of the graph. This naturally leads to the question of whether embedding in higher-dimensional spaces can be computed (for instance, computing a 2-dimensional embedding of a surface corresponds the the classical surface parameterization problem). This general problem is well known by the automatic learning research community as a Manifold learning problem, also called dimension reduction, see for instance Martin Law's web page http://www.cse.msu.edu/ ∼ lawhiu/manifold/.

One of the problems in manifold learning is extracting from a set of input (e.g. a set of images of the same ob-ject) some meaningful parameters (e.g. camera orientation and lighting conditions), and sort these images with respect to these parameters. From an abstract point of view, the images leave in a high-dimensional space (the dimension corresponds to the number of pixels of the images), and one tries to parameterize this image space. The first step constructs a graph, by connecting each sample to its nearest neighbors, according to some distance function. Then, different classes of methods have been defined, we quickly review the most popular ones:

Local Linear Embedding [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] tries to create an embedding that best approximates the barycentric coordinates of each vertex relative to its neighbors. In a certain sense, Floater's Shape Preserving Parameterization (see [START_REF] Floater | Surface parameterization: a tutorial and survey[END_REF]) is a particular case of this approach.

Isomap [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF] computes the geodesic distances between each pair of vertex in the graph, and then uses MDS (multidimensional scaling) [START_REF] Young | Multidimensional scaling[END_REF] to compute an embedding that best approximates these distances. Multidimensional scaling simply minimizes an objective function that measures the deviation between the geodesic distances in the initial space and the Euclidean distances in the embedding space (GDD for Geodesic Distance Deviation), by computing the eigenvectors of the matrix D = (d i,j ) where d i,j denotes the geodesic distance between vertex i and vertex j. This is a multivariate version of Equation 1, that characterizes the Fiedler vector (in the univariate setting). Isomaps and Multidimensional scaling were used to define parameterization algorithms in [START_REF] Zigelman | Texture mapping using surface flattening via multidimensional scaling[END_REF], and more recently in the ISO-charts method [START_REF] Zhou | Iso-charts: Stretch-driven mesh parameterization using spectral analysis[END_REF], used in Microsoft's DirectX combined with our packing algorithm presented in [START_REF] Levy | Least squares conformal maps for automatic texture atlas generation[END_REF].

At that point, we understand that the eigenvectors play an important role in determining meaningful parameters. Just think about the simple linear case: in PCA (principal component analysis), the eigenvectors of the covariance matrix characterize the most appropriate hyperplane on which the data should be projected. In dimension reduction, we seek for eigenvectors that will fit non-linear features. For instance, in MDS, these eigenvectors are computed in a way that makes the embedding space mimic the global metric structure of the surface, captured by the matrix D = (d i,j ) of all geodesic distances between all pairs of vertices in the graph.

Instead of using the dense matrix D, methods based on the Graph Laplacian only use local neighborhoods (onering neighborhoods). As a consequence, the used matrix is sparse, and extracting its eigenvectors requires lighter computations. Note that since the Graph Laplacian is a symmetric matrix, its eigenvectors are orthogonal, and can be used as a vector basis to represent functions. This was used in [START_REF] Karni | Spectral compression of mesh geometry[END_REF] to define a compact encoding of mesh geometry. The basic idea consists in encoding the topology of the mesh together with the coefficients that define the geometry pro-jected onto the basis of eigenvectors. The decoder simply recomputes the basis of eigenvectors and multiplies them with the coefficients stored in the file. A survey of spectral geometry compression and its links with graph partitioning is given in [START_REF] Gotsman | On graph partitioning, spectral analysis, and digital mesh processing[END_REF]. Spectral graph theory also enables to exhibit ways of defining valid graph embeddings. For instance, Colin-de-verdière's number [START_REF] De Verdiere | Sur un nouvel invariant des graphes et un critere de planarite[END_REF] was used in [START_REF] Gotsman | Fundamentals of spherical parameterization for 3d meshes[END_REF] to construct valid spherical embeddings of genus 0 meshes. Other methods that use spectral graph theory to compute graph embeddings are reviewed in [START_REF] Koren | On spectral graph drawing[END_REF]. Spectral graph theory can also be used to compute topological invariants (e.g. Betti numbers), as explained in [START_REF] Feidman | Computing betti numbers via combinatorial laplacians[END_REF]. As can be seen from this short review of spectral graph theory, the eigenvectors and eigenvalues of the graph Laplacian contain both geometric and topological information.

However, as explained in [START_REF] Zhou | Iso-charts: Stretch-driven mesh parameterization using spectral analysis[END_REF], only using the connectivity of the graph may lead to highly distorted mappings. Methods based on MDS solve this issue by considering the matrix D of the geodesic distances between all possible pairs of vertices. However, we think that it is also possible to inject more geometry in the Graph Laplacian approach, and understand how the global geometry and topology of the shape may emerge from the interaction of local neighborhoods.

This typically refers to notions from the continuous setting, i.e. functional analysis and operators. The next section shows its link with the Laplace-Beltrami operator, that appears in the wave equation (Helmholtz's equation). We will also exhibit the link between the so-called stationary waves and spectral graph theory.

The Continuous Setting: Laplace Beltrami

Since we aim at constructing a function basis, we need some notions from functional analysis, quickly reviewed here. A similar review in the context of light simulation is given in [START_REF] Arvo | The Role of Functional Analysis in Global Illumination[END_REF].

Functional analysis

In a way similar to what is done for vector spaces, we need to introduce a dot product (or inner product) to be able to define function bases and project functions onto those bases. This corresponds to the notion of Hilbert space, outlined below.

Hilbert spaces

Given a surface S, let X denote the space of real-valued functions defined on S. Given a norm . , the function space X is said to be complete with respect to the norm if Cauchy sequences converge in X, where a Cauchy sequence is a sequence of functions f 1 , f 2 , . . . such that lim n,m->∞ f n -f m = 0. A complete vector space is called a Banach space.

The space X is called a Hilbert space in the specific case of the norm defined by f = √ < f, f >, where < ., . > denotes an inner product. A possible definition of an inner product is given by < f, g >= S f (x)g(x)dx, which yields the L 2 norm.

One of the interesting features provided by this additional level of structure is the ability to define function bases and project onto these bases using the inner product. Using a function basis (Φ i ), a function f will be defined by f = α i Φ i . Similarly to the definition in geometry, a function basis (Φ i ) is orthonormal if Φ i = 1 for all i and < Φ i , Φ j >= 0 for all i = j. Still following the analogy with geometry, given the function f , one can easily retrieve its coordinates α i with respect to an orthonormal basis (Φ i ) by projecting f onto the basis, i.e. α i =< f, Φ i >.

Operators

We now give the basic definitions related with operators. Simply put, an operator is a function of functions (i.e. from X to X). An operator L applied to a function f ∈ X is denoted by Lf , and results in another function in X. An operator L is said to be linear if L(λf ) = λLf for all f ∈ X, λ ∈ R. An eigenfunction of the operator L is a function f such that Lf = λf . The scalar λ is an eigenvalue of L. In other words, the effect of applying the operator to one of its eigenfunctions means simply scaling the function by the scalar λ.

A linear operator L is said to be Hermitian (or with Hermitian symmetry) 1 if < Lf, g >=< f, Lg > for each f, g ∈ X. An important property of Hermitian operators is that their eigenfunctions associated to different eigenvalues have real eigenvalues and are orthogonal. This latter property can be easily proven as follows, by considering two eigenfunctions f, g associated with the different eigenvalues λ, µ respectively:

< Lf, g > = < f, Lg > < λf, g > = < f, µg > λ < f, g > = µ < f, g > which gives the result (< f, g >= 0) since λ = µ.
As a consequence, considering the eigenfunctions of an Hermitian operator is a possible way of defining an orthonormal function basis associated to a given function space X. The next section shows this method applied to the Laplace-Beltrami operator. Before entering the heart of the matter, we will first consider the historical perspective.

Chladni plates

In 1787, the physicist Ernst Chladni published the book entitled "Discoveries Concerning the Theories of Music". In this book, he reports his observations obtained when putting a thin metal plate into vibration using a bow, and spreading sand over it. Sand accumulates in certain zones, forming surprisingly complex patterns (see Figure 2). This behavior can be explained by the theory of stationary waves. When the metal plate vibrates, some zones remain still, and sand naturally concentrates in these zones. This behavior can be modeled as follows, by the spatial component of Helmholtz's wave propagation equation:

∆f = λf (2)
In this equation, ∆ denotes the Laplace-Beltrami operator on the considered object. In Cartesian 2D space, ∆ = ∂ 2 /∂x 2 + ∂ 2 /∂y 2 . We are seeking for the eigenfunctions of this operator. To better understand the meaning of this equation, let us first consider a vibrating circle. This corresponds to the univariate case on the interval [0, 2π] with cyclic boundary conditions (i.e. f (0) = f (2π)). In this setting, the Laplace-Beltrami operator simply corresponds to the second order derivative. Recalling that sin(ωx) = ω 2 sin(ωx), our eigenfunctions are simply sin(N x), cos(N x) and the constant function, where N is an integer. Note that the so-constructed function basis is the one used in Fourier analysis.

From the spectrum of the Laplace-Beltrami operator, it is well known that one can extract the area of S, the length of its border and its genus. This leads to the question asked by Kac in 1966: Can we hear the shape of a drum ? [START_REF] Kac | Can you hear the shape of a drum?[END_REF]. The answer to this question is "no": one can find drums that have the same spectrum although they do not have the same shape [START_REF] Cipra | You can't always hear the shape of a drum[END_REF] (they are then referred to as isospectral shapes). However, the spectrum contains much information, which led to the idea of using it as a signature for shape matching and classification, as explained in the "shape DNA" approach [START_REF] Reuter | Laplace-beltrami spectra as "shape-dna" of surfaces and solids[END_REF]. Note that the term DNA is somewhat too strong since one may expect to be able to reconstruct the shape from its DNA. To be able to do so, one rather needs the eigenfunctions and the series of coefficients obtained by projecting the shape onto these eigenfunctions.

For this reason, we are going now to take a look at these eigenfunctions. Mathematicians mostly studied bounds and convergence of the spectrum. However, some results are known about the geometry of the eigenfunctions [START_REF] Jakobson | Geometric properties of eigenfunctions[END_REF]. More precisely, we are interested in the so-called nodal sets, defined to be the zero-set of an eigenfunction. Intuitively, they correspond to the locations that do not move on a Chladni plate, where sand accumulates (see Figure 2). A nodal set partitions the surface into a set of nodal domains of constant sign. The nodal sets and nodal domains are characterized by the following theorems:

1. the n-th eigenfunction has at most n nodal domains 2. the nodal sets are curves intersecting at constant angles Besides their orthogonality, these properties make eigenfunction an interesting choice for function bases. Theorem 1 exhibits their multi-resolution nature, and from theorem 2, one can suppose that they are strongly linked with the geometry of the shape. Note also that these theorems explain the appearance of Chladni plates. This may also explain the very interesting re-meshing results obtained by Dong et. al [START_REF] Dong | Quadrangulating a mesh using laplacian eigenvectors[END_REF], that use a Morse-smale decomposition of one of the eigenfunctions.

In the case of simple objects, a closed form of the eigenfunctions can be derived. This made it possible to retrieve the patterns observed by Chladni in the case of a square and a circle. For curved geometry, Chladni could not make the experiment, since sand would not remain in the nodal set. However, one can still study the eigenfunctions. For instance, on a sphere, the eigenfunction correspond to spherical harmonics (see e.g. [START_REF] Jakobson | Geometric properties of eigenfunctions[END_REF]), often used in computer graphics to represent functions defined on the sphere (such as radiance fields or Bidirectional Reflectance Distribution Functions). In other words, on a sphere, the eigenfunctions of the Laplace-Beltrami operator define an interesting hierarchical function basis. One can now wonder whether the same approach could be used to create function bases on more complex geometries. In the general case, a closed form cannot be derived, and one needs to use a numerical approach, as explained in the next section.

Numerical Solution Mechanism

Given a function basis (Φ i ), using the Galerkin method to solve a PDE means projecting the PDE onto the function basis. In our specific problem, we want to find an approximation of the eigenfunctions of Laplace-Beltrami (Equation 2). The projected equation is given by: ∀i, < ∆f, Φ i >= λ < f, Φ i > At this point, it is possible to use a high-order (Φ i ) function basis (e.g. polynomials), and use the divergence formula to transform the equation into a generalized eigenvalue problem, as done in [START_REF] Reuter | Laplace-beltrami spectra as "shape-dna" of surfaces and solids[END_REF].

In our context, to avoid the right-hand side matrix multiply in the generalized eigenvalue problem and the overhead in the computations, we use a discrete Laplacian operator (see e.g. [START_REF] Pinkall | Computing discrete minimal surfaces and conjugates[END_REF][START_REF] Desbrun | Applied geometry: Discrete differential calculus for graphics[END_REF][START_REF] Xu | Convergent discrete laplace-beltrami operators over triangular surfaces[END_REF] for possible definitions). We used Desbrun's formulation. However, special care needs to be taken: since these approaches define discrete rather than discretized Laplacians, they do not keep all the properties of their continuous counterparts. In our case, since we want to compute orthogonal function bases, we want to keep the Hermitian symmetry of the operator, that will be translated into a symmetric matrix. To ensure the symmetry of the matrix, we simply use 0.5(L + L t ), where L is the discrete Laplacian given in [START_REF] Desbrun | Applied geometry: Discrete differential calculus for graphics[END_REF]. The eigenvalues and eigenvectors of the sparse matrix 0.5(L + L t ) are found by the ARPACK solver (see http: //www.caam.rice.edu/software/ARPACK/).

Figure 3 shows the first eigenfunctions computed on a decimated version of the Armadillo model. The contours of the eigenfunctions nicely follow the protrusions of the object and respect the symmetries. Figure 4 shows the result obtained with a combinatorial Laplacian (left) and with a discrete Laplacian that takes the geometry into account (right). Note how the irregular mesh does not influence the result when the geometric terms are used.

Possible Applications

Signal processing on surfaces: Once the eigenfunction basis is computed, it can be used to represent various functions on the surface. Figure 5 shows how a signal (here the normal vector) can be compressed in this basis. The normal vector on the whole bunny is well approximated by 100 coefficients. This is similar to the way spherical harmonics can approximate functions on the sphere, with the difference that the function basis is adapted to the object on which functions need to be defined. This representation of the signal is interesting from a signal processing point of view (for instance, filtering can be done in real-time, since a convolution is replaced by a product in frequency space). However, this is not an efficient way of compressing a signal, since the representation also requires 100 coefficients per vertex to represent the function basis.

Geometry processing: If the geometry is also considered to be a signal, it can also be projected onto the eigenfunction basis (Figure 6). The figure shows the reconstructed geometry with an increasing number of coefficients. This is similar to Taubin's approach, described in his seminal paper [START_REF] Taubin | A signal processing approach to fair surface design[END_REF]. To completely implement Taubin's view of geometry processing, one can construct a hierarchical function space, defined over a chart-based parameterization of the surface (see e.g. [START_REF] Lee | MAPS: Multiresolution adaptive parameterization of surfaces[END_REF]). More recent work attempt to use a more natural function space, defined by spherical harmonics, mapped onto the surface thanks to a spherical parameterization [START_REF] Zhou | 3d surface filtering using spherical harmonics[END_REF]. Besides the limitation to genus 0 geometry, this may also introduce distortion and an uneven sampling of the function space near protrusion. In contrast, the eigenfunction basis is well adapted to the geometry of the object, and can be defined for objects of arbitrary topology. Figure 6 shows that non-shrinking filtering can be easily obtained, by simply selecting the components that correspond to low frequencies.

Registration and pose transfer: One may wonder what our parameter-space looks like. In a certain sense, we completely get rid of referencing any geometry, the parameterspace is an abstract manifold, that only know the neighborhoods. This characteristic is interesting when trying to define common parameterizations for two shapes that do not share the same discretization. Since the protrusions have an important influence on the low frequencies, they naturally define a common parameter space for the two shapes. As a consequence, the coefficients corresponding to geometry projected onto the eigenfunction basis are compatible. Figure 7 shows an example of this idea applied to pose transfer, performed as follows:

1. Compute the eigenfunction bases (Φ i ) of the Armadillo and (Φ i ) of Homer;

2. Project the geometry onto each eigenfunction Φ i and

Φ i α x i ← j x j Φ i (j) α y i ← j y j Φ i (j) α z i ← j z j Φ i (j) β x i ← j x j Φ i (j) β y i ← j y j Φ i (j) β z i ← j z j Φ i (j)
where p j = (x j , y j , z j ) denote the vertices of the Armadillo and q j = (x j , y j , z j ) denote the vertices of Homer;

3. Reconstruct the signal for each vertex j, using the α's for the low frequencies and the β's for the high frequencies:

x j ← 5 i=1 α x i Φ i (j) + n i=6 β x i Φ i (j) y j ← 5 i=1 α y i Φ i (j) + n i=6 β y i Φ i (j) z j ← 5 i=1 α z i Φ i (j) + n i=6 β z i Φ i (j)
As shown in the figure, this process successfully transfers small deformations. This method works provided that the eigenfunctions that correspond to the lower frequencies match, in other words, provided that the α's and the β's are expressed in the same "language". We think that deformations of larger scale may be transfered by a similar approach, by projecting local coordinates (e.g. Laplacian coordinates) onto the eigenfunctions rather than simply projecting the Cartesian coordinates (x, y, z) as we did.

Segmentation and parameterization: as suggested in [START_REF] Dong | Quadrangulating a mesh using laplacian eigenvectors[END_REF], it is possible to use the eigenfunctions to steer a re-meshing algorithm. Figure 8 shows how eigenfunctions can be used to segment a model, prior to parameterizing the charts. The model is segmented by cutting several zero-sets of eigenfunctions. The main difficulty will be to determine which eigenfunction should be used (eigenfunctions were manually selected in this example).

Finally, as suggested by Durand et. al in [START_REF] Durand | A frequency analysis of light transport[END_REF], light transport can be studied in frequency space. Based on Durand's remark, we think that one possible application of projecting the geometry and the lighting onto a basis of eigenfunctions may lead to define tools for combined geometry/lighting processing tools. In future works, we will study practical methods for computing the function basis for large models. Our current implementation is limited to a few thousand vertices. Multi-resolution methods may be an efficient way of overcoming this limit. About the theoretical aspects, we think that the eigenfunctions capture the interaction between the topology and the geometry at a fundamental level. Intuitively, the Laplace-Beltrami operator is a diffusion operator, that spreads the function it is applied to over small neighborhoods. The eigenfunctions make it possible to understand how these local neighborhoods interact and how global properties emerge from this interaction. We think that exterior calculus and co-homology may explain how these properties emerge. Another aspect we plan to study is the definition of hierarchical function bases with local supports, in order to support adaptive refinement.

Figure 1 .

 1 Figure 1. The Fiedler vector gives a natural ordering of the nodes of a graph. The displayed contours show that it naturally follows the shape of the dragon.

Figure 2 .

 2 Figure 2. Left: In the late 1700's, the physicist Ernst Chladni was amazed by the patterns formed by sand on vibrating metal plates. Right: numerical simulations obtained with our approach.

Figure 3 .

 3 Figure 3. Contours of the first eigenfunctions. Note how the protrusions and symmetries are captured. The eigenfunctions combine the geometric and topological information contained in the shape signal.

Figure 4 .

 4 Figure 4. Contours of the 4th eigenfunction, computed from the Graph Laplacian (left) and cotangent weights (right) on an irregular mesh.

Figure 6 .

 6 Figure 6. Geometric reconstructions obtained with increasing number of eigenfunctions.

Figure 5 .

 5 Figure 5. Reconstructing a signal (here the normal vector) using the eigenfunction basis. The variations of the normal vector over the bunny are well approximated by 100 coefficients.

Figure 7 .

 7 Figure 7. Pose transfer: the 5 first coefficients of the Armadillo (A) were copied to Homer (B) and adapted its pose to the Armadillo (C)

Figure 8 .

 8 Figure 8. Top: a genus 3 object; Center: three eigenfunctions; Bottom: computing a segmentation from the nodal sets of these eigenfunctions (thick black lines), and parameterizing the charts (thin lines). Non-square charts are then subdivided from their center, and Floater's Mean Values Coordinates parameterization is applied to all the charts.

the general definition of Hermitian operators concerns complexvalued functions, we only consider here real-valued functions.

Acknowledgment

We want to thank the AIM@Shape European network of excellence for funding this research, the SMI organizing committee for inviting this talk, Matthias Zwicker for his suggestion of studying diminution reduction and manifold learning, and Nicolas Ray for his intuition of "finding the natural vibrations" of shapes that did inspire the Chladni plate analogy.


Gilles-Philippe Paillé

Nicolas Ray

Pierre Poulin

Alla Sheffer

Bruno Lévy

Dihedral Angle-based Maps of Tetrahedral Meshes

Keywords: CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-Curve, surface, solid, and object representations Volume parameterization, interpolation, compression, optimization

We present a geometric representation of a tetrahedral mesh that is solely based on dihedral angles. We first show that the shape of a tetrahedral mesh is completely defined by its dihedral angles. This proof leads to a set of angular constraints that must be satisfied for an immersion to exist in R 3 . This formulation lets us easily specify conditions to avoid inverted tetrahedra and multiply-covered vertices, thus leading to locally injective maps. We then present a constrained optimization method that modifies input angles when they do not satisfy constraints. Additionally, we develop a fast spectral reconstruction method to robustly recover positions from dihedral angles. We demonstrate the applicability of our representation with examples of volume parameterization, shape interpolation, mesh optimization, connectivity shapes, and mesh compression.

Introduction

Geometry represention plays an important role in how we think about a problem and how we solve it. A careful choice of variables can simplify the expression of a solution and lead to a straightforward implementation. Such changes of variables have significantly improved efficiency and robustness of surface maps, such as methods based on angles [START_REF] Sheffer | Parameterization of faceted surfaces for meshing using angle-based flattening[END_REF], on metric [START_REF] Springborn | Conformal equivalence of triangle meshes[END_REF], and on curvature [START_REF] Crane | Spin transformations of discrete surfaces[END_REF][START_REF] Crane | Robust fairing via conformal curvature flow[END_REF]. Computer animation has also benefited from representions such as barycentric coordinates [START_REF] Ju | Mean value coordinates for closed triangular meshes[END_REF]] and modal analysis [START_REF] Pentland | Good vibrations: Modal dynamics for graphics and animation[END_REF] to reduce computational time. Based on these experiences for surfaces, it is only natural to look for similar approaches for volumes. While some deformation techniques using barycentric coordinates and modal analysis trivially generalize to volumes, the body of work in this field remains limited.

In this paper, we study dihedral angles, a geometric quantity wellknown to the volume mesh processing community. A dihedral angle is defined as the angle between two planes; each edge of a tetrahedron has a dihedral angle determined by its two incident triangles. It is commonly used to assess the quality of tetrahedral meshes [Labelle and [START_REF] Labelle | Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles[END_REF], and therefore, it seems natural to express an objective function that defines the quality of a mesh directly in terms of these angles, and to find a numerical solution mechanism to optimize them. We take a step in this direction by showing that the shape of a tetrahedral mesh is completely specified by its dihedral angles, up to a global rotation and isotropic scale. Basically, this implies that manipulating these angles indeed changes the geometry of the mesh. Our goal is to study the properties and the structure of this representation, and to gain some understanding about the intricate relations between vertex positions and dihedral angles.

Our first contribution is a proof that this change of variables is equivalent to an immersion of a mesh in R 3 , where an immersion is a locally injective simplicial map [START_REF] Cervone | Tight immersions of simplicial surfaces in three space[END_REF]], which guarantees that there are no inverted tetrahedra and no multiply-covered vertices. This proof leads to the construction of a set of variables along with a complete set of constraints required for the representation to be an immersion. Our second contribution is a numerical algorithm that optimizes arbitrary input dihedral angles in such a way that they satisfy the constraints that we have exhibited. We call this process flattening as a parallel to surface metric flattening techniques. Our third contribution is a robust spectral reconstruction that recovers vertex positions from dihedral angles.

Related Work

Our work is best interpreted as a volume equivalent of a series of angle-based surface parameterization techniques that were popularized over the last decades. The first angle-based technique was conceived by Di Battista and Vismara [1993] to draw graphs on 2D planes. This method has then been introduced to the computer graphics community for conformal parameterization of surfaces [START_REF] Sheffer | Parameterization of faceted surfaces for meshing using angle-based flattening[END_REF]. A considerable amount of work has been done toward improving its efficiency, including by [START_REF] Sheffer | ABF++: fast and robust angle based flattening[END_REF] who exploit the structure of constraints to significantly decrease solving time. Convergence rate has also been improved by reformulating nonlinear constraints [START_REF] Zayer | Variations on angle based flattening[END_REF]] and linearizing the problem [START_REF] Zayer | Linear angle based parameterization[END_REF]]. More relevant related work is given along its respective applications.

The success of these methods inspired us to search for an equivalent representation for tetrahedral meshes, which lead us to dihedral angles. It is known that the dihedral angles of a single tetrahedron determine its shape [START_REF] Luo | On a problem of Fenchel[END_REF]]. We generalize this observation to tetrahedral meshes and to build a complete framework to work with dihedral angles. While this generalization is nontrivial, we show that the same flattening-reconstruction workflow can be applied in a simple and intuitive way.

Overview Our goal is to prove that dihedral angles alone determine the shape of a tetrahedral mesh, and to show how to recover vertex positions from the sole dihedral angles (plus a global similarity transformation). We first proceed to show that the vertex positions of a tetrahedral mesh can be uniquely reconstructed from the sole dihedral angles, up to a global similarity transformation (Section 2). To prove this, we first demonstrate equivalence for a simple elementary mesh. Then, we consider a general mesh as a sequence of elementary combinatorial operations applied to a simple one, and prove the property by structural induction. In some application contexts, it may be desired that the angles match some prescribed values that do not necessarily satisfy the constraints. For these applications, we propose a constrained optimization problem that looks for the nearest set of angles that satisfy all constraints. We solve this problem using a nonlinear least-squares method (Section 3). Finally, we develop a fast spectral reconstruction method to robustly recover positions from dihedral angles (Section 4). We show some applications (Section 5) expressed with dihedral angles that range from volume parameterization, shape interpolation, mesh optimization, connectivity shapes, and mesh compression.

Dihedral Angle Variables

We now prove that dihedral angles completely determine the shape of a tetrahedral mesh, and exhibit the set of constraints that these dihedral angles need to satisfy. We suppose that the mesh is a topological ball. We can think of this change of representation as a change of variables. The key is to ensure that our new variables have the same representation power as position variables.

θ ij

Our variables are dihedral angles of all tetrahedra. Each tetrahedron has six dihedral angles θij ∈ [0, π], i.e., one for each pair of facets (i, j) (see inset). To simplify the expression of further equations, we say that θij = θji and θii = π. We note that an anglebased representation is unaware of global position (3 DOFs), rotation (3 DOFs), and scale (1 DOF) of the shape. Therefore, we must add 7 transformation variables to our representation for completeness. Note that for applications in this paper, this transformation is usually computed after reconstruction.

We rely on minimal geometric constructions to prove equivalence. For each construction, we use simple geometric arguments to discover constraints. We gain additional certification of the property by a counting argument, showing that the number of variables in the vertex-based representation coincides with the number of degrees of freedom in the angle-based representation, i.e., the number of variables minus the number of equality constraints. We stress that counting arguments are used only as additional validation and do not actually constitute part of the proof. We first show that the dihedral angles of a single tetrahedron are enough to describe its shape, but that they are not independent. The same conclusions are drawn for two tetrahedra sharing a triangle, and for tetrahedra surrounding an edge. During this process, we show that three types of structural constraints and some inequalities are needed to ensure representation equivalence. The conclusion is that these structural constraints are necessary and sufficient to guarantee that the mesh can be built in R 3 .

Cell Constraints

The simplest construction is composed of a single tetrahedron. [START_REF] Luo | On a problem of Fenchel[END_REF] gives necessary and sufficient conditions on dihedral angles to recover vertex positions, for which we give a simple proof here. It is sufficient to show that for a set of dihedral angles satisfying some constraints, there exists, up to a rotation, a unique set of unit normals spanning three dimensions and not lying in the same half-space. Such normals uniquely determine vertex positions of a tetrahedron, up to an isotropic scale and a translation, using plane intersections. We start from the identity i niai = 0, where ni and ai are the unit normal and area of the ith triangle of tetrahedron t. Taking the dot product with each of the four triangle normals nj keeps the identity and lets us writei cos(θij)ai = 0. We rewrite these four identities using Gram matrix Gt of triangle normals as

   1 -cos θ01 -cos θ02 -cos θ03 -cos θ01 1 -cos θ12 -cos θ13 -cos θ02 -cos θ12 1 -cos θ23 -cos θ03 -cos θ13 -cos θ23 1    G t    a0 a1 a2 a3    =    0 0 0 0    .
This shows how dihedral angles are determined from normals. We now show how to uniquely recover normals from Gt. First, we note that Gt is a Gram matrix of normals spanning three dimensions. Thus, Gt is rank deficient, which implies

|Gt| = 0. (1)
Additionally, Gt is constructed with normals that do not lie in the same half-space. Recalling that i niai = 0 and that ai are nonzero, this condition is satisfied if and only if ai have the same sign, which we enforce as follows. Let Ct be the cofactor matrix of Gt. It can be shown that entries (Ct)ij are proportional to aiaj [START_REF] Barrett | First order Regge calculus[END_REF]]. Thus, we could either constrain Ct to be positive or negative. However, Gt is a rank 3 positive semidefinite matrix, which forces diagonal entries of Ct to be positive, giving

Ct > 0, (2)
where the inequality is applied element-wise, and for which we give the complete expression in Appendix A. We do not need to further enforce positive semidefiniteness since the smallest unconstrained principal submatrices have determinants 1 and sin 2 θij. Positive determinants of all principal submatrices ensure that Gt is positive semidefinite.

We now show that Constraints (1) and ( 2) are sufficient to recover normals. Since Gt is a rank 3 positive semidefinite matrix, there exists a unique matrix N3×4, up to a rotation, such that Gt = N T N.

Columns of N are the desired normals. The unit diagonal and the rank of Gt ensure that normals have unit length and that they span three dimensions. The same sign property of the area eigenvector ensures that they do not lie in the same half-space.

As additional validation, we now count DOFs to ensure that they match the number of position variables. In terms of vertex positions, t has 12 DOFs (4 vertices × 3 coordinates). In terms of angles, t has 6 dihedral angle variables and 7 global transformation variables, for a total of 13 DOFs. Assuming that Constraints (1) and ( 2) are satisfied, there remain 12 DOFs, which supports the equivalence.

Each tetrahedron of the mesh should satisfy equality Constraint (1) and inequality Constraints (2). These constraints ensure the structural validity of each individual tetrahedron. However, the dihedral angles need to satisfy additional constraints that enforce the validity of the assembly of the tetrahedra, namely facet constraints and edge constraints detailed below.

Facet Constraints

The next construction is the assembly of two neighbor tetrahedra t0 and t1 sharing a triangle. We assume that cell constraints are satisfied by both tetrahedra. At this point, each tetrahedron can vary its shape independently. However, the assembly of t0 and t1 requires that the two glued triangles have the same shape, for which a necessary and sufficient condition is that all three pairs of corresponding corner angles are equal. Since cell constraints are satisfied, we know that corner angles are in [0, π]. Thus, we can equivalently ensure that the cosine of corner angles are equal. Noting φ 0 i and φ 1 i the ith corner angles of glued triangles of t0 and t1, we have the three constraints

cos φ 0 i = cos φ 1 i , (3)
φ θ 0 θ 1 θ 2
for which only two are independent by the identity

φ i 0 + φ i 1 + φ i 2 = π.
The cosine of a corner angle can be computed from dihedral angles incident to the corner vertex. Following the notations in the inset, we have [START_REF] Dittrich | Area-angle variables for general relativity[END_REF] cos φ = cos θ0 + cos θ1 cos θ2 sin θ1 sin θ2 .

We now count DOFs to ensure that they match the number of position variables. In terms of vertex positions, this construction has 15 DOFs (5 vertices × 3 coordinates). In terms of angles, this construction has 12 dihedral angle variables and 7 global transformation variables, for a total of 19 DOFs. Assuming that cell and facet constraints are satisfied by both tetrahedra, there remain 15 DOFs, which supports the equivalence.

Each pair of neighbor tetrahedra introduces three constraints (Equation 3). Intuitively, they ensure that strips of tetrahedra glued along common faces can be reconstructed. For a general topological ball, we need to examine another configuration that corresponds to a wheel of tetrahedra sharing a common edge.

Edge Constraints

The next construction is the assembly of tetrahedra looping around an edge. We assume that cell constraints are satisfied by all tetrahedra, and that facet constraints are satisfied by all pairs of neighbor tetrahedra. Even if all these constraints are satisfied, configurations exist where the wheel does not close. One can compare this phenomenon to angular defect around vertices of a curved surface. A necessary and sufficient condition for the wheel to close perfectly is to constrain the set Θe of dihedral angles around edge e with θ∈Θe θ = 2π, (4) which ensures that the edge is simply covered, and thus, that the local construction is injective.

In the 2D case (e.g., ABF), nothing constrains closing edges to be isometric, and thus, a wheel constraint is necessary. In our case, closing facets are similar due to facet constraints. However, these facets share an edge with other tetrahedra. The length of this edge being equal for all tetrahedra, the facets are not only similar, they are isometric. Thus, no wheel constraint is needed.

We now count DOFs to ensure that they match the number of position variables. We first consider the simple case of a wheel with only 3 tetrahedra. In terms of vertex positions, this construction has 15 DOFs (5 vertices × 3 coordinates). In terms of angles, this construction has 18 dihedral angle variables and 7 global transformation variables, for a total of 25 DOFs. Assuming that cell, facet, and edge constraints are satisfied for the 3 tetrahedra, 15 DOFs remain, which confirms the equivalence. For more general wheels, we proceed inductively. Adding a tetrahedron in the wheel adds one vertex. In terms of vertex positions, this adds 3 DOFs. In terms of angles, this adds 6 dihedral angle variables and 3 constraints, for a total of 3 DOFs. Thus, no more constraints are needed.

Each edge introduces one constraint (Equation 4), which lets us build topological balls. We now have a complete and valid representation of a volume immersed in R 3 given by a global similarity transformation and dihedral angle variables such that cell, facet, and edge constraints are satisfied.

Vertex Constraints

Local injectivity requires that each interior vertex is simply covered, i.e., that their solid angle is equal to 4π. However, the combined edge constraints around a vertex already enforce this equality [START_REF] Yin | Discrete curvature flow for hyperbolic 3-manifolds with complete geodesic boundaries[END_REF], and thus, no vertex constraint is needed.

We also note that counting DOFs of a local construction containing a single interior vertex requires some care. Indeed, closing a 1-ring creates redundant constraints. This is comparable to facet constraints where only two out of the three constraints are independent. We stress the fact that they are redundant but not contradictory, and thus, do not invalidate our method.

Flattening

We now tackle the case where given dihedral angles do not satisfy all constraints. It occurs when geometric constraints are not satisfied by the data (Section 5.1), or when the user gives an arbitrary set of dihedral angles (Section 5.2). A failure to satisfy constraints reflect the impossibility to recover positions without distorting input angles. We control this distortion by solving the following optimization problem,

min f (Θ) s.t. |Gt| = 0 ∧ Ct > 0 ∀t ∈ T Eqs. (1,2) cos φ 0 c = cos φ 1 c ∀c ∈ C Eq. (3) (5) θ∈Θe θ = 2π ∀e ∈ E Eq. (4) θ b ≤ θ ≤ π -θ b ∀θ ∈ Θ,
where Θ is the vector of all dihedral angles, Θe is the set of dihedral angles of an edge e, T is the set of tetrahedra, C is the set of corners, E is the set of edges, φ 0 c and φ 1 c are corner angles of glued triangles t0 and t1 associated to c, θ b is a positive parameter to bound dihedral angles, and f (Θ) is an objective function measuring distance to input dihedral angles.

ω θ 0 θ 1 θ 2
Objective Function We choose f to be a quadradic function of Θ that preserves the shape of tetrahedra defined by original dihedral angles Θ * . We use a combination of two sets of geometric properties that are linearly obtained from dihedral angles. The first set of properties is composed of the dihedral angles themselves. The second set of properties is composed of solid angles at each vertex of all tetrahedra. A solid angle ω is a linear function of dihedral angles incident to a vertex in a tetrahedron. Using notations in the inset, we have

ω = θ0 + θ1 + θ2 -π.
Noting Ω and Ω * the vectors of solid angles computed from Θ and Θ * , we define f as

f (Θ) = Θ -Θ * 2 + Ω -Ω * 2 .
The solid angle term tends to penalize elongated tetrahedra. The inset shows a connectivity shape (Section 5.3) flattened with (top) and without (bottom) the second term. Now that we have a complete formulation of the problem, we can solve it in practice in the following way.

Optimization To optimize the constrained nonlinear problem (5), we propose a multi-phase penalty method. Each phase minimizes an energy function that tries to balance between constraints satisfaction and objective function minimization in a nonlinear leastsquares sense. After each phase, we set initial dihedral angles Θ * to the current solution to let the next phase further satisfy the constraints. We repeat this procedure until the constraints are satisfied up to a given threshold. A solution is usually attained after two or three phases. Given initial dihedral angles Θ * , equality constraints c(Θ) = {ci(Θ)}, and inequality constraints d(Θ) = {dj(Θ)}, we define the function to be minimized as

E(Θ) = αf (Θ) + c(Θ) 2 + min(d(Θ), 0) 2 (6)
where constraints are expressed as ci(Θ) = 0 and dj(Θ) > 0, and α is a regularization factor. We set α = 10 -6 for all our examples. Constraint set c contains all constraints, including dependent ones, since we observed better convergence.

In this formulation, the objective function plays two roles. First, since the zero set of the constraint manifold contains every possible immersion of the mesh, it ensures that we do not stray too far from the input dihedral angles. Second, since some constraints are redundant, numerical errors due to the discretization can make simultaneous constraints impossible to satisfy exactly. In this case, the objective function regularizes the optimization and forces a compromise without ending up with degenerate solutions. The regularization factor is chosen to be very small so that the solver puts more efforts on satisfying the constraints.

We minimize E with a Quasi-Newton method called L-BFGS as implemented by [START_REF] Liu | On centroidal voronoi tessellation -energy smoothness and fast computation[END_REF] using a M1QN3 preconditioner, and a memory of eight iterations. This solver only requires first derivatives of each constraint. We refer the reader to Appendix B for more details on computing constraint derivatives.

Initial Solution

Since the optimization problem in Equation ( 5) is nonlinear and nonconvex, convergence to the global minimum is not guaranteed for arbitrary initial solutions using a local minimization method. We choose the initial solution to be the initial dihedral angles Θ * specific to each application since experience shows that it tends to improve convergence. As shown in Figure 1, choosing a jittered or random initial solution tends to slow convergence or can lead to a local minimum. The jittered initial solution experiment started with a larger error and needed 5× more iterations to converge.

Reconstruction

At this point, we have a set of dihedral angles satisfying all constraints. We can now proceed to recover positions. One could perform a greedy reconstruction of the entire mesh by laying out one tetrahedron at a time. However, this method is prone to numerical error accumulation and is only viable for small meshes (see Figure 2). Instead, we propose a robust linear spectral reconstruction method that distributes numerical errors uniformly across the mesh. To this end, we build a local construction for each tetrahedron. Then, we extract linear equations from pairs of neighboring tetrahedra relating their vertex positions using barycentric coordinates. We use these equations to build a linear system involving the entire mesh. Finally, we solve this linear system using eigendecomposition. The result is a set of vertex positions representing the immersion. Local Constructions The first step is to lay out each tetrahedron independently using its dihedral angles. While angles are theoretically sufficient for reconstruction, we observed that recovering edge lengths of a tetrahedron beforehand, and laying out using edgelength geometry is more stable. This stability has also been observed in greedy reconstructions of triangle meshes [START_REF] Springborn | Conformal equivalence of triangle meshes[END_REF].

To this end, we use the following identity [START_REF] Barrett | First order Regge calculus[END_REF]]

lij = bt ∂|Gt| ∂θij , θ ij l ij
where bt is a coefficient of proportionality, and lij is the length of the edge associated to θij as shown in the inset. Even though scale is not important at this time, we choose bt so that an arbitrary edge has unit length since it tends to make further computations more robust. Then, we perform a trilateration to recover local vertex positions as shown in Appendix C, which completes the construction.

Linear Relations

Local constructions offer a localized view of the mesh. We now need to position them globally. We do this by expressing relative positions of neighbor tetrahedra using barycentric coordinates. For all pairs of tetrahedra (t0, t1) sharing a triangle, we glue the two local constructions t0 and t1 along their associated two triangles by transforming the vertex positions of t0. We scale t0 so that the two triangles are congruent. There only remains to find the position of the vertex v opposite to the associated triangle f in t0. We compute local coordinates of v using two edges of f and its normal as basis. We compute a similar basis using the corresponding elements of t1 and use it to obtain the transformed v. -1 v4 1 .

We gather linear equations ( 7) from all pairs of tetrahedra into a linear system Ax = 0, where A is a matrix composed of barycentric coordinates, and x are the unknown global positions of all vertices.

We rewrite this overdetermined system into a least-squares formulation A T Ax = 0 to which we must find the kernel.

Spectral Solver We cannot solve for x directly since the kernel is not empty. This is due to barycentric coordinates being invariant to affine transformations. Fixing four vertices would remove this invariance, but this would also introduce distortions near anchors [START_REF] Mullen | Spectral conformal parameterization[END_REF]]. We instead use eigendecomposition to find the eigenvector associated to the smallest non-zero eigenvalue of A T A. This is efficiently computed using an inverse power method as described in Algorithm 1, where we use µ = 10 -8 and = 10 -12 . We solve the linear system using Cholesky decomposition, as implemented by CHOLMOD [START_REF] Chen | Algorithm 887: CHOLMOD, supernodal sparse cholesky factorization and update/downdate[END_REF]. Since the matrix is constant throughout iterations, we factorize B beforehand, and then solve using back-substitution.

Algorithm 1 Spectral Solver Input: a matrix A T A and an initial guess x Output:

vertex positions x B ← A T A + µI x ← RemoveAffineTransformation(x) while Bx -x T Bx x ∞ > do Solve By = x x ← RemoveAffineTransformation(y)
To avoid degenerate solutions, we remove the global affine transformation contained in x at each iteration as follows. First, we center vertices around the origin. Then, we remove shearing by comparing current solution to local constructions. Let Jt be the matrix transforming tetrahedron t, as defined by the current solution, to its local construction. We compute average shearing S of all tetrahedra in log-space [START_REF] Arsigny | Log-Euclidean metrics for fast and simple calculus on diffusion tensors[END_REF]] as

S = exp 1 2N t∈T ln J T t Jt ,
where the logarithm of a symmetric matrix M is computed using its diagonalization ln M = ln(QDQ T ) = Q ln(D)Q T , and the logarithm of a diagonal matrix is computed component-wise on diagonal elements only. We apply S to all vertices to remove shearing. Then, we remove rotation by aligning an arbitrary edge on the X-axis and one of its connected triangles on the XY -plane. Finally, we normalize x to remove global scale.

Solution x is the immersion in terms of vertex positions devoid of global scale, translation, and rotation. We choose the final rigid transformation to fulfill individual application needs.

Applications

We need to stress the fact that our motivation was mainly guided by scientific curiosity, and by the natural question of studying the structure of the space of admissible values for dihedral angles. We also studied potential applications based on this representation and on our constrained optimization procedure. We do not claim that our experiments perform better than the state of the art in volume parameterization, shape interpolation, and mesh compression in terms of computation time, but we think that besides our theoretical motivation, the experimental results below tend to confirm that our approach may have potential applications. In particular, we show that mesh optimization using our formulation manages to recover highly tangled meshes, which pose problems for many optimization methods. Moreover, we show that shape interpolation in terms of dihedral angles is well-behaved, even for large rotations.

We implemented the methods in C++ in the Graphite software [2015] and all tests were conducted on an Intel R Core TM i7 930 processor with 12GB of memory and without any GPU acceleration. We took advantage of the multi-threading capacity of the multi-core architecture using OpenMP. Computation times are shown in Table 2.

From Positions to Dihedral Angles Some applications rely on the initial dihedral angles of the mesh. Thus, we must be able to convert vertex positions to dihedral angles. While the process is straightforward, doing it robustly requires some care. Most programming languages offer a two-argument inverse tangent function that is generally more robust than an inverse cosine function. For this reason, we use the following formula [START_REF] Shewchuk | Lecture notes on geometric robustness[END_REF]]

θij = tan -1 - 3V lij 2ni • nj ,
where θij is a dihedral angle of tetrahedron t of volume V , lij is the length of the edge associated to θij, and ni is the area weighted normal of the ith triangle of t.

Geometric Constraints So far, we have looked at structural constraints that ensure that a mesh is well-formed. For some applications, we need to further constrain the shape of the mesh. For example, creating polycubes (Section 5.1) requires patches of the boundary of a mesh to be flat, and neighboring patches to be orthogonal. For mesh optimization (Section 5.4), we require the shape of the boundary of the mesh to remain unchanged. For both of these examples, we need geometric constraints to ensure that some geometric properties are satisfied by dihedral angles. We present two ways of constraining the shape of mesh M .

The first way is to reinterpret edge constraints (4) as follows. General immersions of volume geometries are described by their Riemann curvature tensor. An interesting property is that Riemann curvature is completely defined by sectional curvature. [START_REF] Regge | General relativity without coordinates[END_REF] shows that sectional curvature of a tetrahedral mesh is a discrete measure defined per edge e as 2π -θ∈Θe θ. To prescribe sectional curvature θe of e, we rewrite edge constraint (4) using the more general equation

θ∈Θe θ = θe,
where we sum over all dihedral angles incident to e. This curvature prescription lets us specify the flatness and orthogonality properties needed to create polycubes. The second way is to prescribe corner angles of boundary triangles of M . To do so, we add facet constraints as

cos φc = cos φc,
where φc is the angle of a corner c of M , and φi is its desired angle. This corner angle prescription lets us constrain the shape of the boundary needed for mesh optimization.

Note that these two methods are not mutually exclusive. One could use a combination of both if needed, but one must be careful to avoid contradictory constraints, in which case a solution will not exist. However, for the applications presented in this paper, it will be clear from the context that all constraints are compatible.

Volume Parameterization

Volume parameterization is the act of deforming the geometry of a volume so that it fits a simple regular domain. These simpler domains are quite popular for texturing and remeshing [START_REF] Li | All-hex meshing using singularity-restricted field[END_REF][START_REF] Livesu | Polycut: Monotone graph-cuts for polycube base-complex construction[END_REF]. A dihedral angle-based representation fits perfectly for this application. In our context, the geometry of domains is specified by adding geometric constraints. We present two types of domains. First, we consider polycube domains with their planar boundaries, and then domains defined by singularity graphs adding interior singularities. For polycube creation, the input is a surface triangle mesh for which every triangle has a label specifying the axis that its normal must be aligned to. From this surface, we create a tetrahedral mesh using TetGen [START_REF] Si | TetGen. A quality tetrahedral mesh generator and three-dimensional Delaunay triangulator[END_REF]]. We compute initial dihedral angles for all tetrahedra using the initial vertex positions. Then, we flatten the mesh (Section 3) using boundary geometric constraints that force polycube faces to be flat, and polycube edges to have angle turns matching the change in normal orientation. Finally, we recover positions using spectral reconstruction (Section 4). Results are shown in Figure 3 (left, center).

For this particular application, it is possible to stop the optimization before convergence and let the reconstruction absorb remaining errors. Stopping the flattening process may produce a curved polycube.

To fix this, we add the following equations to the linear system ( 7) during reconstruction to align each boundary triangle f ijk to its assigned axis n

(vj -vi) • n = 0 (v k -vj) • n = 0 (vi -v k ) • n = 0.
In addition to geometric boundary constraints, users can define edge constraints that do not sum up to 2π for interior edges. Such constraints are useful for introducing interior singularities for hexahedral meshing [START_REF] Li | All-hex meshing using singularity-restricted field[END_REF]]. We define a singularity graph as the set of such interior edges along with boundary edges such that their edge constraint does not sum up to π. An example with a handcrafted graph is shown in Figure 3 (right).

Our framework offers some advantages over position-based techniques for volume parameterization using singularity graphs. First, since dihedral angles are independent of global positioning, each tetrahedron can be spatially disconnected from its neighbors. This implies that dihedral angles naturally encode nontrivial domains without changing the combinatorics of the mesh. Second, this shows that a singular graph alone is enough to perform parameterization. Thus, our work opens the door for new algorithms that could directly create singularity graphs, instead of being by-products of frame fields [START_REF] Li | All-hex meshing using singularity-restricted field[END_REF]].

We note that two geometric informations are not encoded by singularity graphs (Figure 4). First, the length of each edge of the domain is not part of the formulation. Second, a singular graph with multiple components may have pairwise orientation ambiguities.

Combinatorial Considerations Given compatible geometric constraints, an immersion may not exist for a given mesh combinatorics. For example, two boundary triangles of a single tetrahedron cannot be coplanar without degenerating the tetrahedron. For the same reason, two edges of a single tetrahedron cannot be colinear. This observation has been made for polycube domains [START_REF] Aigerman | Injective and bounded distortion mappings in 3D[END_REF] and singularity graphs [START_REF] Jiang | Frame field singularity correction for automatic hexahedralization[END_REF]]. We rewrite these two constraints here for completeness.

The first constraint is that there should be a sufficient number of tetrahedra around edge e for given curvature prescription θe. Knowing that a single tetrahedron can support a dihedral angle up to π, we must have θe < |Te|π, where Te is the set of tetrahedra incident to e. If an edge does not satisfy the condition, we select an arbitrary tetrahedron t ∈ Te and split the edge opposite to e in t. The second constraint is related to singularity graphs. The constraint is that a triangle f should not be incident to two singular edges. In this eventuality, we split the third edge of f . These corrections only add tetrahedra around edges, so they cannot break other constraints.

Note that these combinatorics constraints are not only inherent to our method, but to every method that deforms tetrahedral meshes.

Method Scaling

We evaluate how our method scales with the number of tetrahedra by parameterizing a sphere to a cube for different resolutions. The inset log-log plot indicates that the computation time increases linearly with the number of tetrahedra. This behavior has been observed for most experiments. However, convergence rate also depends on geometric constraints complexity, hence the apparent nonlinear scaling between the Squirrel and the Buste models shown in Table 2.

Shape Interpolation

Shape interpolation is the creation of a smooth and natural transition between two different shapes. This application is inspired by the work of [START_REF] Chen | Planar shape interpolation with bounded distortion[END_REF], that proposes to interpolate planar shapes using squared edge lengths. The process of interpolating the metric, and then recovering positions using a robust conformal metric flattening method, creates a smooth deformation of bounded distortion. Unfortunately, current surface metric flattening methods do not trivially generalize to volumes, preventing direct application of this shape interpolation method to tetrahedral meshes. We propose to interpolate dihedral angles instead of squared edge lengths and to use our flattening-reconstruction procedure to recover the immersion.

The algorithm goes as follows. For two poses of a same tetrahedral mesh, we compute dihedral angles of each pose from vertex positions. Given a weight w ∈ [0, 1], we linearly interpolate corresponding dihedral angles (θ 0 j , θ 1 j ) as θ * j = (1 -w)θ 0 j + wθ 1 j , where θ i j is the jth dihedral angle of the ith mesh, and then we flatten resulting angles θ * j and recover vertex positions to obtain the interpolated mesh. One can also interpolate between n poses using n weights wi ≥ 0, i wi = 1. Finally, we fix the global similarity transformation by interpolating the center of gravity, cancelling global rotation, and preserving shape volume. Results are shown in Figure 5.

Our method is most similar to the second-order interpolation method of [START_REF] Kircher | Free-form motion processing[END_REF], which expresses changes in Jacobian matrices across the mesh. As ours, their formulation does not depend on global coordinates and thus, we achieve similar results. However, our method has the benefit of guaranteeing local injectivity (this guarantee comes at the cost of a longer computation time). We note that our method differs from techniques working in global coordinates, such as ARAP [START_REF] Alexa | As-rigidas-possible shape interpolation[END_REF], that may have problems with large rotations and require special care to minimize fold-overs [START_REF] Levi | Smooth rotation enhanced as-rigid-as-possible mesh animation[END_REF].

Connectivity Shapes

The connectivity shape concept, as introduced by [START_REF] Isenburg | Connectivity shapes[END_REF], shows that a lot of geometric information is encoded into its combinatorics. To prove their point, they start from a surface mesh, erase all vertex positions, and manage to recover an approximation of the original shape using an optimization procedure. This procedure simply tries to place vertices in space such that every edge has approximately the same length.

We extend this idea to volume mesh. Instead of using uniform edge length as the main criterion, we use uniform dihedral angles. We start from the combinatorics of a mesh, set dihedral angles of regular tetrahedra, i.e., cos -1 (1/3), and flatten the result without any geometric constraints. The result is a shape such that each tetrahedron is as close as possible to a regular tetrahedron, while maintaining coherency with its neighbors. A result is shown in Figure 6. This concept is not an application on its own. Nevertheless, it demonstrates the power of our representation, i.e., we do not need an initial immersion of the mesh. This property becomes useful when serving a more practical purpose, such as mesh optimization, as shown in the next section.

Mesh Optimization

We apply our method to mesh optimization. We focus on optimizing the shape of each tetrahedron without modifying the connectivity of the mesh. For this process, we use the flattening procedure as a mean to start from regular tetrahedron dihedral angles, and optimize them so they form a reconstructible set of angles. We include geometric constraints for boundary edges and triangle corners to preserve the original boundary shape. We fix boundary vertices to their original positions during reconstruction. We note that constraining both boundary dihedral angles and corner angles during flattening ensures that there are no DOFs left for the boundary to vary its shape. For this reason, this application supports higher genus meshes. This procedure ignores the original geometry of internal tetrahedra. This has the advantage of supporting tangled meshes having inverted and degenerate tetrahedra. By setting the initial angles to ideal angles, we ensure that the result will be as close as possible to regular tetrahedra. In Figure 7, we show initial meshes of a sphere and fertility model with jittered interior vertices with many inverted tetrahedra. The mesh optimization procedure improves the quality of initial meshes and remove all inverted or degenerated tetrahedra.

Our mesh optimization method resembles that of [START_REF] Aigerman | Injective and bounded distortion mappings in 3D[END_REF], which aims to improve the quality of each tetrahedron by bounding distortions relative to a regular tetrahedron. The key difference is that they measure distortions using the ratio of the maximum and minimum transformation matrix eigenvalue while we measure et al. [2013] (IBDM). We show the minimum and maximum dihedral angles (DA) of resulting meshes using IBDM and our method. differences in dihedral angles. As shown in Table 1, our method is able to improve extremal dihedral angles for all experiments using their models as a starting point. As noted by the authors, bounding dihedral angles does not bound aspect-ratio and could create elongated elements. However, the solid angle term contained in our objective function tends to minimize this kind of distortions.

Mesh Compression

Dihedral angles can be used as a way to compress the geometry of a mesh. Our idea is to quantize angles using a coarse approximation, for example, using only 2 bits per angle, and recover vertex positions from this information alone. One could quantize angles on a uniform sampling of [0, π]. However, a good sampling should take advantage of the fact that the dihedral angles of a good quality mesh are concentrated around cos -1 (1/3). To this end, we propose to guide the quantization using the histogram of all dihedral angles.

First, we compute dihedral angles of the initial geometry using vertex positions. Then, given a budget of n bits per angle, we build the histogram by creating a single bin containing all dihedral angles and recursively split it around its mean value until we have 2 n bins.

Our sampling is the mean value of each bin. Finally, we encode each angle using the index of its nearest sample. We also need to keep the table of mean values for decompression. Note, however, that the space used by this table is negligible for coarse approximations.

To recover the original geometry, we set initial dihedral angle θ * i to the mean value associated to its index. We flatten θ * i , and then we recover vertex positions using spectral reconstruction. Results are shown in Figures 8 and9.

For all examples, we are able to reduce to 2 bits per angle before dis- Figure 8: We compress the geometry of a cube mesh using its dihedral angles at different bit rates. Keeping 4 bits per angle creates no visible artifact, while some irregularities can be seen on edges (dashed) when keeping only 2 bits.

tortions start to be visually perceived. This high compression ratio is due to geometric redundancies in dihedral angle variables. Indeed, there is approximately 8× more angle variables than position variables, which means that we encode an average mesh using 48 bits per vertex. We do not compete with state-of-the-art methods that achieve an average of 8 to 16 bits per vertex [START_REF] Maglo | 3D mesh compression: Survey, comparisons, and emerging trends[END_REF]]. However, exploiting redundancies in angle variables to achieve higher compression ratios is subject to future work. Moreover, one could choose to keep more geometric information on the boundary, and little to no information for the interior. Since there is generally more interior variables than boundary ones, this strategy should improve compression ratios.

Discussion and Conclusion

We have shown that the shape of a tetrahedral mesh is completely determined by its dihedral angles, and have introduced constraints that must be satisfied to immerse the mesh in R 3 . This has lead us to an optimization procedure in the case where constraints are not readily satisfied. We then developed a robust spectral reconstruction method to recover positions. The result is an immersion of the mesh, which implies that there are no inverted tetrahedra and no multiply-covered vertices.

Furthermore, we demonstrated the applicability of our method in different contexts of volume geometry processing. In these applications, in terms of quality, our results are comparable to the state of the art, and we think that the additional robustness of locally injective maps guaranteed by our method may be a desirable property. However, this property comes at the expense of several limitations, which suggests future directions of research to overcome them.

Nonlinear Optimization Our formulation as a nonlinear, nonconvex optimization problem is reputably hard to solve numerically. As a consequence, the performance of our method does not match the state of the art. In addition, while experience shows that our nonlinear least-squares formulation is well-behaved for most experiments, we have experienced some failure cases where the solver got stuck in local minima (see Figure 1). Convexifying the problem would improve convergence rate and ensure a single global minimum.

Genus > 0 We remind the reader that this method applies only to topological balls, with an exception being the mesh optimization application. with constraints has always been a challenge for geometry algorithms working in local coordinates, and this work is no exception. Each additional handle needs global constraints to ensure that it closes perfectly. One way of solving this limitation is to let the spectral reconstruction deal with remaining errors introduced by the missing constraints. As shown in the inset, we successfully parameterized a torus to a polycube with a maximum difference of 0.4 • between flattened and reconstructed dihedral angles. Note, however, that the spectral reconstruction absorbs errors in the least-squares sense, and thus, does not guarantee injectivity. To remedy this, one could instead temporarily fill all tunnels before flattening, and remove them after reconstruction. Another possibility would be to study the structure of the constraints and feasible set. We think that the co-homology basis plays a central role in this structure, and that each generator adds a set of constraints.

Global Injectivity While our method ensures local injectivity for the mesh interior, we do not guarantee, similar to 2D methods, that the boundary does not self-intersect. We could potentially achieve global injectivity using techniques similar to those suggested by [START_REF] Sheffer | Parameterization of faceted surfaces for meshing using angle-based flattening[END_REF], i.e., by iteratively reconstructing the shape while adjusting boundary constraints to avoid self-intersection.

Figure 1 :

 1 Figure 1: Convergence plots visualized using log scale for shape interpolation of a twisted bar for different initial solutions: initial interpolated angles (left), jittered interpolated angles (center), and random angles (right). The random initial solution experiment converged to a local minimum and could not be reconstructed. Discontinuities in the plots are caused by a change of optimization phase.

Figure 2 :

 2 Figure 2: Comparison between greedy and spectral reconstructions of a sphere mesh with jittered dihedral angles. Our spectral method adds robustness by distributing the error over the entire mesh.

  the inset, for two glued tetrahedra composed of five vertices having positions vi, where (v0, v1, v2, v3) forms a tetrahedron, we express v4 by v4 = a0v0 + a1v1 + a2v2 + a3v3, (7) where ai are barycentric coordinates computed by

Figure 4 :

 4 Figure 4: Geometric ambiguities inherent to singularity graphs. We show two domains sharing the same singularity graph.

Figure 3 :

 3 Figure 3: Volume parameterization using polycube constraints (left and center) and a singularity graph (right). The boundary surface of all examples are constrained to be planar, but singularities are either on boundaries or inside the mesh.

Figure 5 :

 5 Figure 5: We linearly interpolate dihedral angles from a straight bar (left) to a curled bar (right). We show the condition number, normalized in [0, 1], of the map relative to the straight bar for the 100 most distorted tetrahedra.

Figure 6 :

 6 Figure 6: Connectivity shape illustrated with the foot model. The original immersion (left) has its vertex positions entirely removed. Using only the combinatorics, we can approximate them (right).

Figure 7 :

 7 Figure 7: Optimization of interior vertices of a sphere and fertility model. Interior vertices have been jittered (left) to introduce inversions. After optimization (right), the geometry of all tetrahedra was recovered without any inversion, as shown by the minimum and maximum dihedral angles.

Figure 9 :

 9 Figure 9: Angle distortion of the compressed cube (Figure 8), Bimba (left), and Buste (right) meshes at different bit rates. We show reconstruction of compressed meshes using only 2 bits per angle.

Table 1 :

 1 Model IBDM (min/max DA) Ours (min/max DA) Duck 16 • / 148 • 17 • / 146 • Elephant (v1) 16 • / 148 • 17 • / 146 • Elephant (v2) 18 • / 147 • 19 • / 146 • Hand 17 • / 148 • 18 • / 146 • Horse 16 • / 148 • 18 • / 146 • Max Plank 21 • / 148 • 22 • / 146 • Rocker 16 • / 148 • 18 • / 146 • Skull 14 • / 153 • 16 • / 151 • Results of mesh optimization using models from Aigerman

Table 2 :

 2 Statistics for all examples, where the number of iterations (iters) is the number of phases times the number of iterations per phase, and timings are in seconds.

	Application	Model	Tets	θ b	Iters	Time
		Squirrel 119k 0.20 2 × 2k	493
	Parameterization	Buste Sphere	160k 0.30 3 × 3k 1502 37k 0.10 2 × 2k 129
		Torus	6k 0.10 2 × 2k	21
	Interpolation	Bar	9k 0.10 2 × 2k	7
	Optimization	Sphere Fertility 364k 0.15 2 × 2k 1550 37k 0.20 2 × 2k 129
	Connectivity	Foot	158k 0.10 2 × 2k	684
		Cube	47k 0.10 2 × 2k	50
	Compression	Bimba	124k 0.10 2 × 2k	156
		Buste	214k 0.10 2 × 2k	274

Acknowledgements

We thank anonymous reviewers for their valuable comments. The work of the Canadian authors was supported by NSERC and GRAND NCE, and Bruno Lévy was supported by ANR BECASIM and ANR MORPHO. The Squirrel, Buste, Fertility, Foot, and Bimba models are provided courtesy of AIM@SHAPE Shape Repository.

A Cell Inequality Constraints

Cofactor matrix C of G is constrained to have positive entries. First, we note that C is symmetric, which eliminates six inequalities. Let (i, j, k, l) be a permutation of (0, 1, 2, 3), cij = cos θij and sij = sin θij. Off-diagonal entries of C can be written as

Diagonal inequalities can be simplified using the following observations. The minor matrix Mii of G is the Gram matrix of a triangle formed with corner angles (θ jk , θ kl , θ lj ), and a triangle is spherical if and only if its Gram matrix is positive definite [START_REF] Luo | On a problem of Fenchel[END_REF]]. However, inequality Cii = |Mii| > 0 and the fact that principal submatrices of Mii have positive determinants ensures that Mii is positive definite. Thus, we can replace Cii > 0 with

B Constraint Derivatives

Minimizing energy function (6) requires derivatives of constraints. Let (i, j, k, l) be a permutation of (0, 1, 2, 3), ∂ij = ∂/∂θij, ∂i = ∂/∂θi, cij = cos θij, and sij = sin θij. Following identities from The Matrix Cookbook [Petersen and Pedersen 2012], we have

where C is the cofactor matrix of G.

C Trilateration

Given the length of each edge of a tetrahedron t, we can recover vertex positions using trilateration. We compute positions using intersection points of circles and spheres. The process is intuitive, but computations can be tedious. We rewrite these equations here to ease implementation. Since lengths do not encode translation and rotation, we arbitrarily set a vertex at the origin, an edge on the X-axis, and a triangle on the XY -plane. Noting vi the position of the vertex opposed to the ith triangle of t, and lij the length of edge incident to the ith and jth triangle of t, we have


Simon Benacchio

Arnaud Malher

Stefania Lo Feudo

Jean Boisson

C Touzé

DYNAMIC BEHAVIOR OF A TUNABLE MAGNETIC VIBRATION ABSORBER

A magnetic vibration absorber (MVA), completely relying on magnetic forces, is used to reduce the displacement of a vibrating structure. The distinctive feature of this absorber is the ability of tuning its linear stiffness together with its nonlinear cubic and quintic stiffnesses. Repulsive and corrective magnets are used to finely tune the values of these stiffness coefficients. A modelisation, relying on a multipolar expansion of the magnetic fields of each magnets, is used to predict the values of the stiffnesses from the geometry. Using only three geometrical parameters the MVA can be passively designed either as a nonlinear tuned vibration absorber (NLTVA), a nonlinear energy sink (NES), or a bi-stable absorber with negative linear stiffness.

INTRODUCTION

Due to its passive feature, the vibration mitigation of mechanical structures using vibration absorbers is an important solution for engineering issues. Linear vibration absorbers like the well-known Tuned-Mass Damper (TMD) [START_REF] Frahm | Device for Damping Vibrations of Bodies[END_REF][START_REF] Hartog | Mechanical Vibrations[END_REF] have been studied for the vibration reduction of both linear undamped [START_REF] Ormondroyd | The Theory of the Dynamic Vibration Absorber[END_REF] and damped [START_REF] Asami | Analytical solutions to H∞ and H 2 optimization of dynamic vibration absorbers attached to damped linear systems[END_REF] primary structures (PS). However, the main drawback of the TMD is related to its narrow bandwidth of optimal control. To overcome this limitation a Nonlinear Energy Sink (NES) with an essentially nonlinear restoring force can be used. Having no natural frequency, the NES can thus adapt itself to the frequency of the PS [START_REF] Manevitch | Energy pumping in nonlinear mechanical oscillators, I: dynamics of the underlying Hamiltonian systems[END_REF][START_REF] Vakakis | Energy pumping in nonlinear mechanical oscillators, II: resonance capture[END_REF]. Another idea is to use the nonlinearity of the absorber in order to control the nonlinearity of the PS and has led to the concept of the nonlinear tuned vibration absorber (NLTVA). Recently, bi-stable vibration absorber devices have been investigated to make smaller the energy barrier required to activate the energy transfer between the PS and a NES [START_REF] Manevitch | Dynamics of a Linear Oscillator Coupled to a Bistable Light Attachment: Analytical Study[END_REF]. If numerous experimental devices have been proposed to experiment these absorbers they are often designed for a specific application [START_REF] Al-Shudeifat | Numerical and experimental investigation of a highly effective single-sided vibro-impact non-linear energy sink for shock mitigation[END_REF][START_REF] Grappasonni | Practical design of a nonlinear tuned vibration absorber[END_REF][START_REF] Yamakawa | Behavior of a new type dynamic vibration absorber[END_REF].

The proposed magnetic vibration absorber (MVA) has the ability of properly tuning its linear and nonlinear characteristics. Thus, this flexible device can be used either as an NES, an NLTVA, or a bi-stable vibration absorber, all these tunings being realized passively with a simple change in the geometry of the system. The experimental realisation of the MVA is presented in this paper. Then, preliminary results of the reduction of the PS vibration are presented when the MVA is tuned as an NLTVA, an NES and a bi-stable absorber.

THE MAGNETIC VIBRATION ABSORBER

The magnetic vibration absorber is shown in Fig. 1. It is composed of 7 permanent ring magnets. Their length, internal ) are fixed on plastic rods. The black and white parts of each magnet give the direction of their axial magnetisation. Magnets 2 and 3 are named the repulsive magnets since their magnetisation is the opposite of the magnetisation of the magnet 1. The amplitude of the repulsive force is tuned by modifying the geometric parameter r. Magnets 4, 5, 6 and 7 are named the corrective magnets since their magnetisation is the same that the magnetisation of the magnet 1. The amplitude of the corrective force is tuned by modifying the geometric parameters R and d. Therefore, the total force F Tot applied on the mass of the MVA is tuned by the independent modifications of the geometric parameters r, R and d. Modeling the MVA using a multipolar expansion, this force can be written as

F Tot (x) ≈ -K 1 x -K 3 x 3 -K 5 x 5 .
Modifying the geometric parameters r, R, and d, the linear, cubic and quintic stiffness terms can be tuned to change the properties of the MVA designing it as an NLTVA, an NES or a bi-stable absorber. More details about the design of the MVA can be found in [START_REF] Benacchio | Design of a Magnetic Vibration Absorber with Tunable Stiffnesses[END_REF].

VIBRATION MITIGATION

The MVA is then used to reduce the displacement of a plate selected as a PS vibrating with a large amplitude around one of its modal frequencies. Two opposite sides of the rectangular plate are clamped, whereas the other two are free. The device is attached to the PS and tuned successively as an NLTVA, an NES and a bi-stable absorber. Figure 2 shows the measured maximum displacement of the PS in each case and when the MVA is removed from the plate. These results present the effects of the linear stiffness coefficient tuning. The measurements first show undoubtedly the effect of the vibration absorber on the nonlinear dynamics of the plate. Depending on the tuning, one can expect to control different parameters area in the frequency response curve. Current measurements are realised in order to analyze more deeply the advantages of each configurations as well as showing the best tuning that can be expected.

Figure 1 :

 1 Figure 1: Diagram of the magnetic vibration absorber (MVA). and external diameters are denoted L, D int and D ext respectively. Oscillating around the central position x = 0, the magnet 1 plays the role of the vibrating mass of the absorber. The other magnets (2, 3, 4, 5, 6 and 7) are fixed on plastic rods. The black and white parts of each magnet give the direction of their axial magnetisation. Magnets 2 and 3 are named the repulsive magnets since their magnetisation is the opposite of the magnetisation of the magnet 1. The amplitude of the repulsive force is tuned by modifying the geometric parameter r. Magnets 4, 5, 6 and 7 are named the corrective magnets since their magnetisation is the same that the magnetisation of the magnet 1. The amplitude of the corrective force is tuned by modifying

Figure 2 :

 2 Figure 2: Maximum displacement of the primary structure without the MVA [ooo] and with the MVA tuned as an NLTVA [ooo] (K 1 > 0), an NES [ooo] (K 1 ≈ 0) and a bi-stable absorber [ooo] (K 1 < 0). The gray circles [ooo] indicate the linear displacement of the primary structure for a lower excitation force. Circles and dots correspond to forward and backward sweeps respectively.

* Corresponding author. Email: jean.boisson@ensta-paristech.fr