A local cell quality metric and variational grid smoothing algorithm

Abstract

A local cell quality metric is introduced and used to construct a variational functional for a grid smoothing algorithm. A maximum principle is proved and the properties of the local quality measure, which combines element shape and size control metrics, are investigated. Level set contours are displayed to indicate the effect of cell distortion. The approach is demonstrated for meshes of triangles and quadrilaterals in 2D and a test case with hexahedral cells in 3D. Issues such as the use of a penalty for folded meshes and the effect of valence change in the mesh patches are considered.

1 Introduction

Generating quality meshes that permit reliable accurate simulations remains a major technical and theoretical problem. The need to solve more complex applications for multi-material domains with irregular geometry and varying spatial scales exacerbates the difficulty. For example, large scale simulations now involve meshes with millions of cells and feature sizes that vary by orders of magnitude. Generated meshes are often mathematically incorrect (e.g. contain folded cells) or unreliable, so generating, remeshing, and improving the mesh have become time consuming but pressing tasks. This adversely impacts our ability to do efficient simulation and design. In simulations where moving boundaries arise, the situation can be much worse since the mesh deteriorates as cells deform degrading accuracy, conditioning, and computational effectiveness (more iterations and shorter timesteps). Periodic remeshing and frequent grid smoothing are needed, as well as other corrective actions.

The present work examines this issue from the standpoint of local cell quality and a novel scalar cell quality indicator is introduced based on the mapping from the reference cell and the associated Jacobian. This new quality measure differs from similar measures in the literature in several key ways. It controls both shape and size and satisfies a maximum principle. This indicator is used to construct a global functional for mesh optimization that we use here as a mesh smoothing and correction strategy that is investigated numerically in several test problems. Algorithms based on such optimization strategies have been utilized previously, one of the earliest studies being that of Winslow [1]. More recent works [2–7] develop related ideas.

The outline of the present treatment is as follows: we first summarize some basic ideas underlying harmonic maps and Laplace-type grid smoothing in a variational setting. This leads us to introduce a local “distortion measure” and its reciprocal defines the local cell quality indicator. We prove a maximum principle and discuss the properties of the associated global functional obtained as an accumulation of the element contributions. The optimization descent problem is solved using a damped Newton scheme and representative performance for test cases is shown. Several case studies are provided in the results section to illustrate the features of the indicator, unfolding of meshes and treatment of valence changes.

2 Mapping and variational statement

A popular strategy in structured grid generation is to map a uniform Cartesian grid in a reference domain ${\hat \Omega }$ to a curvlinear grid of well-shaped cells in the physical domain Ω. The properties of conformal maps can often be exploited to ensure a good mesh. The associated properties of analytic functions of a complex variable have led to the use of harmonic functions from complex analysis and, indirectly, to schemes using functions that satisfy the associated Laplace equation. Since the potential and stream function solutions to Laplace’s equation form a suitable coordinate family for a 2D mesh, this idea has motivated partial differential equation solver strategies for mesh generation. In particular, the Laplace problems

$$ \Delta x = 0,\quad \Delta y = 0 $$

(1)

for the coordinate map from the 2D reference domain ${\hat \Omega}$ may be used for the mesh smoothing in a convex physical domain Ω. A more robust strategy is to introduce the Laplace problems

$$ \Delta \xi = 0,\quad \Delta \eta = 0 $$

(2)

in the 2D physical domain Ω, which may be nonconvex. These can be mapped to quasilinear PDE’s in the reference domain ${\hat \Omega}$ and solved for untangled meshes in Ω.

Alternatively, variational formulations for these PDE problems can be easily constructed and an equivalent optimization problem is obtained. For (2), the variational functional is the classical Dirichlet integral for the Laplacian [8] and we have

$$ \mathcal{I} = \int\limits_\Omega {\left[ {\left( {\nabla \xi } \right)^2 + \left( {\nabla \eta } \right)^2 } \right]{\text{d}}x{\text{d}}y} . $$

(3)

The pair of Laplace problems (2) follow as the associated Euler-Lagrange equations. Mapping the variational problems to the reference domain we have

$$ \mathcal{I} = \int\limits_{\hat \Omega } {\frac{{x_\xi ^2 + x_\eta ^2 + y_\xi ^2 + y_\eta ^2 }} {{x_\xi y_\eta - x_\eta y_\xi }}{\text{d}}\xi {\text{d}}\eta } $$

(4)

and the variational statement yields a quasilinear second order PDE system as Euler-Lagrange equations. However, more importantly here, (4) can be expressed compactly as

$$ \mathcal{I} = \int\limits_{\hat \Omega } {\frac{{{\text{tr}}\left( {S^T S} \right)}} {{\det S}}{\text{d}}\xi {\text{d}}\eta } $$

where tr denotes the trace and S is the Jacobian matrix of the map between the two frames. From this, following the idea of describing grid quality by metric-tensor invariants [5, 9] or functions of the Jacobian matrix [10], we define the local distortion measure

$$ \beta (S) = \frac{{\frac{1} {2}{\text{tr}}\left( {S^T S} \right)}} {{\det S}} $$

(5)

and local mesh quality as Q ₀=β⁻¹. In fact, this distortion measure generalizes to any dimension directly [11] as

$$ \beta (S) = \frac{{\left( {\frac{1} {n}{\text{tr}}\left( {S^T S} \right)} \right)^{{n}/{2}} }} {{\det S}} $$

(6)

and measures shape distortion. The map and distortion measure here are for a general reference domain but we are particularly interested in the map from a reference cell to an arbitrary cell in the physical domain. Note that β(S) is invariant under dilation, which will be a problem in treating the effect of valence changes and where graded meshes are desirable. The size of the cell can be controlled by introducing a second local measure which we term the dilation measure. For a “desired” uniform size distribution, we compute an average Jacobian determinant as

$$ v = \frac{{\int\nolimits_{\hat \Omega } {\det S{\text{d}}\xi {\text{d}}\eta } }} {{\int\nolimits_{\hat \Omega } {{\text{d}}\xi {\text{d}}\eta } }}. $$

The ratios det S/v and v/det S indicate the departure of det S from v. Since det S can be above or below v we introduce the symmetric dilation measure [7]

$$ \mu (S) = \frac{1} {2}\left( {\frac{v} {{\det S}} + \frac{{\det S}} {v}} \right). $$

(7)

Then μ=1 when v = det S and μ → ∞ as det S → ∞ or 0. If we consider the map for one cell only, then v is a “desired” cell size (related to area in 2D and volume in 3D). This also implies that a target distribution of v can be specified to maintain a desired mesh grading as shown later.

Following the ideas of multi-objective functions [2, 6], we introduce an additive distortion-dilation measure (other forms are clearly possible)

$$ E_\theta (S) = (1 - \theta )\beta (S) + \theta \mu (S), $$

(8)

where coefficient 0≤θ<1 can be adjusted to emphasize the respective distortion and dilation terms.

Now the variational grid smoothing formulation can be stated as follows: minimize the functional

$$ \mathcal{I} = \int\limits_{\hat \Omega } {E_\theta (S){\text{d}}\xi {\text{d}}\eta } , $$

(9)

subject to relevant boundary (or other) constraints. The Euler-Lagrange equations for the new functional (9) for the 2D case, written in the physical domain, are

$$ \begin{aligned} - (1 - \theta )\Delta \xi + v\theta \left( {\left( {\det S} \right)_y^{ - 1} \eta _x - \left( {\det S} \right)_x^{ - 1} \eta _y } \right) = & 0, \\ - (1 - \theta )\Delta \eta + v\theta \left( {\left( {\det S} \right)_y^{ - 1} \xi _x - \left( {\det S} \right)_x^{ - 1} \xi _y } \right) = & 0 \\ \end{aligned} $$

and can be compared with (2). In order to obtain the discretized problem formulation, the map is interpreted as the sequence of maps from a single reference element or, equivalently, from a union of reference elements in the reference domain (in a manner similar to the Galerkin finite element method). Then the integral in (9) is decomposed to a sum of element (or cell) contributions. Contributions to the functional from each cell c are approximated using a numerical integration rule as

$$ \mathcal{I}_h = \sum\limits_{c = 1}^{N_c } {\sum\limits_{q(c) = 1}^{N_q } {\sigma _{q(c)} E_\theta \left( {\left. S \right|_{q(c)} } \right)} } , $$

(10)

where {q(c)} identify the quadrature points and σ _q(c) are the corresponding quadrature weights for cell c.

Remarks: 1. The formulation can be applied to any unstructured grid containing different types of cells, using appropriate quadrature rules; 2. Topologically unstructured grids will have varying nodal valence and this effect will also be investigated in the numerical work of Sect. 6. 3. The desired element size v can be specified to vary over the physical domain, which can be used to achieve adaptive cell size distribution throughout the mesh. 4. In the grid smoothing formulation the starting grid is assumed here to be a valid grid but this will be generalized to handle folded grids in Sect. 5.

3 Local quality measure

We first describe some general properties of the local measures (6) and (8) and then focus on their behavior for meshes using the basic triangle and quadrilateral cells since they are most widely used in grid generation.

The function β(S), reformulated in terms of invariants of the metric tensor of coordinate transformation G=S ^T S, was considered in [5]. It was shown that β(S) controls the cell angles and cell aspect ratio in the 2D case and has similiar properties in 3D. The estimates for the angle α between two cell edges and cell aspect ratio F (ratio of the lengths of the edges) for 2D quadrilateral cells are

$$ \sin ^2 \alpha \geq \left( {1/\beta } \right)^2 ,\quad 2 \leq F + 1/F \leq 4\beta ^2 - 2. $$

Thus β→1 enforces α→π/2 and F→1; i.e. a square cell.

The modified distortion measure E _θ retains these properties of β(S). It is an indicator for quasi-isometry of the mapping [7, 11]; that is, it is an analog of mapping conformality characterization, in the sense that the following inequality

$$ \gamma ^2 I \leq S^T S \leq \Gamma ^2 I, $$

holds, where γ and Γ can be estimated from E _θ.

In the following sections we will examine the local measure E _θ(S) or corresponding local quality measure Q _θ(S)=1/E _θ(S) (for θ=0, Q ₀(S)=1/β(S)) on linear mapped simplex elements and bilinear isoparametric elements.

3.1 Simplex elements

Let us first consider the 2D triangular element, which has been most extensively analyzed in the literature (see [5, 12] for references), and then extend to the tetrahedron. Taking the reference element to be the equilateral triangle with sides of length 1 and computing the constant Jacobian matrix of the linear map onto an arbitrary triangular element with area A and edges of lengths l ₁, l ₂, l ₃, we get

$$ \det S = \frac{4} {{\sqrt 3 }}A,\quad {\text{tr}}\left( {S^T S} \right) = \frac{2} {3}\left( {l_1^2 + l_2^2 + l_3^2 } \right). $$

Thus

$$ \beta = \frac{{l_1^2 + l_2^2 + l_3^2 }} {{4\sqrt 3 A}} $$

and quality measure Q ₀ is equal to

$$ Q_0 = \frac{{4\sqrt 3 A}} {{l_1^2 + l_2^2 + l_3^2 }}. $$

This is a well known example [13, 14] of a “fair” geometric measure in the sense that it is equal to 0 on any type of degenerate triangle. It is also normalized (takes values from the interval [0,1]).

The corresponding additive measure from (8) is

$$ E_\theta = \left( {1 - \theta } \right)\frac{{l_1^2 + l_2^2 + l_3^2 }} {{4\sqrt 3 A}} + \frac{\theta } {2}\left( {\frac{{\sqrt 3 }} {{4A}} + \frac{{4A}} {{\sqrt 3 }}} \right). $$

The level sets of the corresponding modified quality measure Q _θ=E ⁻¹_θ for a triangle with fixed edge (0,0)−(0,1) as a function of the coordinates (x,y) of the opposite vertex are shown in Fig. 1 for different values of parameter θ. As θ increases, the quality measure becomes less restrictive in the sense that it admits more points in the regions Q _θ >const, as can be seen by comparing the “interior” areas for a given level curve in each graph of Fig. 1. However, it remains a “fair” measure.

Fig. 1

Level sets of Q _θ(x,y) on triangle with vertices (0,0), (0,1), (x,y)

For the mapping of an arbitrary tetrahedron onto the regular tetrahedral reference element with edges of length 1 we have

$$ \det S = 6\sqrt 2 V,\quad {\text{tr}}\left( {S^T S} \right) = \frac{1} {2}\sum\limits_{i = 1}^6 {l_i^2 } , $$

where V is the volume of the tetrahedron and l ₁, ..., l ₆ are its edge lengths. Thus for the quality and additive distortion-dilation measures, respectively, we get

$$ \begin{aligned} Q_0 = & \frac{{72\sqrt 3 V}} {{\left( {\sum\nolimits_{i = 1}^6 {l_i^2 } } \right)^{3/2} }}, \\ E_\theta = & (1 - \theta )\frac{{\left( {\sum\nolimits_{i = 1}^6 {l_i^2 } } \right)^{3/2} }} {{72\sqrt 3 V}} + \frac{\theta } {2}\left( {\frac{1} {{6\sqrt 2 V}} + 6\sqrt 2 V} \right), \\ \end{aligned} $$

and Q _θ=E ⁻¹_θ which are also “fair” measures in the sense given above. A similar tetrahedron shape measure

$$ \eta = \frac{{12\left( {3V} \right)^{2/3} }} {{\sum\nolimits_{i = 1}^6 {l_i^2 } }} = \left( {Q_0 } \right)^{2/3} $$

was derived in [15] from the singular values of transformation S. Geometrically η reflects the shape of the inscribed ellipsoid. The fact that η=(Q ₀)^2/3 indicates that both measures are closely related and are equally able to identify “poor” shaped elements, although their sensitivity is not the same.

3.2 Tensor product linear elements

The case of the n−linear cell in dimension n ≥ 2 is more complex, since the Jacobian matrix is not constant on the cell. Nevertheless, E _θ satisfies a “maximum principle” [11], in the sense that it is bounded from above by a finite linear convex combination of its values on certain bases (matrices). Consider each n × n matrix as a collection of its columns

$$ S = \left( {S\left( { \cdot ,1} \right),S\left( { \cdot ,2} \right), \ldots ,S\left( { \cdot ,n} \right)} \right). $$

The general algebraic property of the additive measure is stated in the following lemma:

Lemma 1 Let an n × n matrix S have a following representation

$$ S = \sum\limits_{j = 1}^m {S_j \Lambda _j } ,\quad \sum\limits_{j = 1}^m {\Lambda _j = I} ,\quad \Lambda _j \geq 0,{\enspace} m \geq 2, $$

(11)

where Λ _j are diagonal matrices, which can be equivalently written as

$$ \begin{aligned} S( \cdot ,i) = & \sum\limits_{j = 1}^m {S_j \left( { \cdot ,i} \right)\lambda _{ij} } , \\ \sum\limits_{j = 1}^m {\lambda _{ij} } = & 1,\quad \lambda _{ij} \geq 0,{\enspace} \forall i = 1, \ldots ,n. \\ \end{aligned} $$

Let us introduce a multi-index α=(α₁, ..., α _n ) with 1 ≤ α _i ≤ m, and define “combinational matrices”

$$ \tilde S_\alpha = \left( {S_{\alpha _1 } \left( { \cdot ,1} \right),S_{\alpha _2 } \left( { \cdot ,2} \right), \ldots ,S_{\alpha _n } \left( { \cdot ,n} \right)} \right). $$

(12)

If for any α

$$ E_\theta \left( {\tilde S_\alpha } \right) \leq C,\quad \det \tilde S_\alpha > 0, $$

holds then there exist coefficients a _α≥0, ∑_α a _α=1, such that

$$ E_\theta (S) \leq \sum\limits_\alpha {a_\alpha E_\theta (\tilde S_\alpha )} , $$

(13)

where the sum contains m ⁿ terms.

The coefficients a _α in the last inequality depend upon S, so the more useful consequence of the lemma is

$$ E_\theta (S) \leq \mathop {\max }\limits_\alpha E_\theta (\tilde S_\alpha ) \leq C. $$

(14)

Proof: The proof of the maximum principle by induction consists of the following major steps:

• 1. For the matrix $S = \frac{1} {2}S_1 + \frac{1} {2}S_2$ one can show that

  $$ {\text{tr}}\left( {S^T S} \right) \leq \frac{1} {{2^n }}\sum\limits_\alpha {{\text{tr}}\left( {\tilde S_\alpha ^T \tilde S_\alpha } \right)} $$

  and

  $$ \det S \leq \frac{1} {{2^n }}\sum\limits_\alpha {\det \tilde S_\alpha } $$

  hold. Then by the Holder inequality

  $$\beta(S) \det S \leq {{1}\over {2^n}} \sum_{\alpha} \beta(\tilde{S}_{\alpha}) \det \tilde{S}_{\alpha}.$$

• 2. Inequality

  $$ \beta \left( {(1 - \xi )S_1 + \xi S_2 } \right) \leq \sum\limits_\alpha {a_\alpha \beta (\tilde S_\alpha )} $$

  is proved for any 0≤ξ≤1 using the bisection argument and step 1. That is, for any ξ ∈ [0,1] we can find two sequences of points {l _i } ^∞₁ , {r _i } ^∞₁ obtained from the bisection of the interval [0,1], such that l _i → ξ from the left and r _i → ξ from the right as i → ∞. Using step 1 it can be shown that for each bisection point the maximum principle for β holds. Thus, by continuity of functions β and det the maximum principle holds for any ξ.

• 3. The statement of step 2 is generalized by induction to an arbitrary number of terms in the representation (11) of S. It is first proved for Λ _j =λ _j I, then the general case is shown to reduce to such a form.

• 4. Using the Cauchy inequality one can show that

  $$ \mu (S) \leq \sum\limits_\alpha {a_\alpha \mu (\tilde S_\alpha )} .\quad \blacksquare $$

Thus, an upper bound for the additive measure (lower bound for quality measure) can always be computed. Matrices for this bound are a full set of constant matrices arising from a representation of the Jacobian matrix on the tensor product cell.

For example, the bilinear map of unit square 0≤ξ₁, ξ₂≤1 onto the cell with vertices r _jk , j,k=0,1 can be written as

$$ {\mathbf{r}} = \sum\limits_{j,k = 0}^1 {(1 - \xi _1 )^{(1 - j)} \xi _1^j (1 - \xi _2 )^{(1 - k)} \xi _2^k {\mathbf{r}}_{jk} } $$

(15)

and its Jacobian matrix is

$$ \begin{aligned} S = & \sum\limits_{j,k = 0}^1 {(1 - \xi _1 )^{(1 - j)} \xi _1^j (1 - \xi _2 )^{(1 - k)} \xi _2^k \left( {{\mathbf{r}}_{1k} - {\mathbf{r}}_{0k} ,{\mathbf{r}}_{j1} - {\mathbf{r}}_{j0} } \right)} \\ = & \sum\limits_{j,k = 0}^1 {c_{jk} \tilde S_{jk} } ,\;{\text{with}}\;\sum\limits_{j,k = 0}^1 {c_{jk} = 1} , \\ \end{aligned} $$

(16)

where c _jk =(1−ξ₁)^(1-j) ξ ^j₁ (1−ξ₂)^(1-k) ξ ^k₂ are the scalar coefficients in (16) and the corresponding pairs of vectors are the columns of matrices $\tilde S_{jk} = ({\mathbf{r}}_{1k} - {\mathbf{r}}_{0k} ,{\mathbf{r}}_{j1} - {\mathbf{r}}_{j0} ).$

Thus for the bilinear cell, the bound is a convex linear combination of additive measures computed at vertices of the quadrilateral cell. That is,

$$ E_\theta \leq \sum\limits_{j,k = 0}^1 {a_{jk} E_\theta (\tilde S_{jk} )} \leq \mathop {\max }\limits_{j,k} E_\theta (\tilde S_{jk} ),\quad {\text{where}}\;\sum\limits_{j,k = 0}^1 {a_{jk} = 1} ,\quad a_{jk} \geq 0. $$

For a trilinear cell, this type of representation of the Jacobian matrix contains 64 different constant matrices. They can be obtained from trilinear images of the basis triples in reference space. All 64 such basis triples can be obtained from the four distinct vector triples, shown as bold vectors in Fig. 2, by rotation and reflection (after reflection the orientation should be changed to preserve right basis orientation).

Fig. 2

Types of basis triples for computation of upper bound for E _θ on trilinear element

The level sets for the lower bound of the quality measure Q _θ for the bilinear cell are shown in Fig. 3, where quality contours are graphed as functions of the position (x,y) of one vertex of the quadrilateral with the other vertices fixed at points (0,0), (0,1) and (1,0).

Fig. 3

Level sets of lower bound for Q _θ(x,y) on quadrilateral element with vertices (0,0), (0,1), (1,0), (x,y)

The existence of the upper bound on the local additive measure E _θ implies that in order to control cell quality it is sufficient to control the bound; that is, the values of the additive measure on a finite number of combinations of cell vertex basis vectors. Thus the choice of these combinations as quadrature points for approximating the discrete functional (10) will guarantee the improvement in mesh quality sought for solving minimization problem (9).

4 Numerical implementation

The gradient of the smoothing functional (10) is nonlinear so an iterative optimization algorithm, such as Newton’s method or another gradient descent method, should be applied to the associated algebraic problem. In this work, the damped Newton method is used. After each iteration the global minimum quality measure

$$ \left.{\left(Q_\theta\right)} \right|_{\min } = \mathop {\min }\limits_{q(c)} \frac{1} {E_\theta \left( S_{q(c)} \right)} $$

(17)

is computed in order to monitor the optimization process. Iterations cease when the difference between the minimum quality (17) of two subsequent grids is less than a given tolerance (other criteria are possible).

5 Algorithm modifications

If the initial grid is folded or has nonconvex cells, the functional can be modified by adding penalty terms to enforce a valid grid (see, for example, [6]). The original functional (10) has an infinite barrier on the set of grids with convex cells which is due to the presence of det S in the denominator of the integrand. This barrier implies that a valid grid will be preserved, but also that an initial folded grid will remain folded. To circumvent the latter situation, a penalty formulation can be developed by replacing this factor det S by an exterior penalty function χ_ɛ(det S), such that the new integrand will be a finite approximation of the original infinite barrier. This modification allows the minimization procedure to start from a folded grid and, since the value of the functional I _h is significantly increased when folded cells are present in the grid, the final grid will not contain nonconvex cells (assuming there exists such a mesh solution for the given connectivity and boundary conditions). After the grid is unfolded, the algorithm automatically switches back to the smoothing formulation, which prevents “refolding” of the mesh.

Since the distortion measure β(S) provides control over element shape, one can define a priori the desired element shape by introducing a metric in reference coordinates. These metrics essentially use different reference elements for different cells in the grid. Minimization of the correspondingly modified functional will result in a grid with cells having the shape as close as possible (under given connectivity of the grid and imposed boundary conditions) to the target shapes. Hence hybrid grids containing a mixture of different cell or element types can be conveniently handled.

6 Numerical examples

6.1 Smoothing of a triangular grid in nonconvex domain

The Laplace smoother based on solving Eqs. (1) may produce overlapping grids in nonconvex domains, so it is important to check the behavior of the present type of smoother for such domains. Consider the nonconvex (v-shaped) domain with triangular grid and fixed boundary nodes shown on the left in Fig. 4. Smoothing with the presented additive functional using θ=0.8 produces the grid on the right in Fig. 4. There is no overlap and the mesh lines are well behaved. Cells at the peak on the symmetry line are slightly dilated and those at the reentrant corner are slightly compressed.

Fig. 4

Triangular grid in nonconvex domain. Initial mesh (left) and smoothed mesh (right)

6.2 2D meshes with points of changing valence

The following numerical tests demonstrate the advantages of the new smoothing algorithm, when operating on a grid with varying valence. Some algorithms will produce significant local dilation effects in the regions where valence changes.

Figure 5 demonstrates the smoother behavior on triangular grids with changing valence. All boundary nodes are fixed in this example. There is some disparity in dilation effects but the behavior is satisfactory for smoothing with θ=0.8, whereas smoothing with θ=0.2 produces significant dilation.

Fig. 5

Triangular grids. Initial meshes (left), smoothed meshes, θ=0.2 (middle) and smoothed meshes θ=0.8 (right)

The effect of smoothing on a mesh of quadrilateral cells is shown in Fig. 6. The initial grid consists of two block-generated subgrids corresponding to a trapezoidal subdomain and its continuation to the annular region. Boundary nodes on the exterior circular boundary are fixed and nodes on the vertical diameter boundary of the semicircle are allowed to “slide” along this line. The initial mesh and the “evolving” mesh at iterations 1, 2, and 3 are shown.

Fig. 6

Quadrilateral grid during smoothing. From left to right: initial grid, grid after 1, 2 and 3 iterations of the smoother. Top smoothing with θ=0.8, bottom smoothing with θ=0.2

The minimal quality (Q _θ)_min and minimal value of the Jacobian determinant for this test are shown in Fig. 7 as functions of the number of iterations.

Fig. 7

Smoothing. (Q _θ)_min and J _min versus number of iterations

These tests demonstrate that significant dilation occurs in grids with varying valence after smoothing with the accent on the shape control metric (similar behavior is seen for Laplacian-type smoothers), whereas increasing the size control moderates this difficulty. It can be observed from the lower curves (θ=0.2) in Fig. 7 that minimization of a global functional with more weight on shape control does not improve the minimal values of the quality metric and Jacobian determinant as iterations continue. Note that the comparison here is to their values for the initial mesh. Although global quality of the mesh improves during the minimization, local quality of the cells surrounding the valence-3 nodes deteriorates, i.e. the value of such a functional depends more on the global mesh structure than on any individual cell contribution. On the other hand, when the weight is shifted towards the size control metric, all local quality metric values improve during smoothing. Thus, adding weight on the dilation metric makes our smoothing procedure insensitive to the varying valence of the mesh. However, this will be problem dependent and will be influenced by the choice of starting grid iterate. It does suggest, however, that one may be able to adaptively select θ varying from values close to 1 near the nodes of irregular valence to values close to 0 near the domain boundary.

6.3 Mesh unfolding in nonconvex domain

Barrier formulations of variational smoothing algorithms facilitate mesh unfolding, as well as smoothing. As an example, let us consider the unfolding of a folded quadrilateral mesh for an annular cylindrical domain. For the initial grid, we relocate the nodes interior to a cylindrical polar mesh for a semicircular annulus and place them at the origin as indicated by the mesh on the left in Fig. 8. Thus, all cells have vertices outside the domain and are overlapping. After applying the penalized smoothing algorithm with different choices of θ for 5 iterations, the grid is close to equidistributed, as seen in the center and on the right in Fig. 8.

Fig. 8

Unfolding. Initial mesh (left), smoothed mesh, θ=0.2 (middle) and smoothed mesh, θ=0.8 (right)

The dynamics for the minimal quality metric and minimal Jacobian determinant during unfolding is shown in Fig. 9. It can be observed from these plots that unfolding with the accent on the shape control metric requires fewer iterations compared to the case with the accent on size control. This is natural, since unfolding is mainly a shape recovery procedure.

Fig. 9

Unfolding. (Q _θ)_min and J _min versus number of iterations

6.4 Initially adaptive quadrilateral grid with folded cells

In the next example, the smoothing procedure is applied to a more elaborate grid generated to adaptively fit a multi-airfoil domain. This grid has many nodes with irregular valence and it initially had several folded cells. The most relevant part of this grid before and after smoothing is shown in Fig. 10. The initial grid (top) has a very fine mesh graded into an extremely thin boundary layer at the airfoil surface. For θ=0.2 (middle) this boundary layer mesh has been “dilated” during the smoothing process as seen by the dark bands adjacent to the airfoils. Then in the lower figure (θ=0.8) we have an intermediate situation with some dilation near the airfoils but the boundary layer mesh relatively well preserved. This example indicates the importance of distributed cell size control (via μ(S)), since without it the smoothing procedure “undoes” desired clustering near the airfoils and tends to promote a uniform grid, which is unacceptable because boundary layers need to be resolved. Thus, the volumetric factors v were computed for each cell, and then the smoothing algorithm was run using these values. The improvement in the grid details can be seen in Fig. 11.

Fig. 10

Subregion showing initial grid (top), smoothed with θ=0.2 grid (middle) and smoothed with θ=0.8 grid (bottom)

Fig. 11

Fragments of initial grid (left), smoothed with θ=0.2 grid (middle) and smoothed with θ=0.8 grid (right)

It can also be observed from Fig. 11 that even with distributed dilation control (the weight θ=0.8) may not be adequate to retain enough clustering in the boundary layers. One can locally increase θ, or, in order to have a grid that retains the initial mesh density in the boundary layer, a block smoothing strategy may be utilized.

6.5 3D mesh smoothing

The general approach and its application extend naturally to 3D. This is demonstrated in Fig. 12 for a 3D mesh analogous to that in Fig. 6 earlier. An interior hexahedral mesh block is connected to another hexahedral grid block of spherical annular shape and then smoothed. The cutaway octant in the Figure shows layers of cells near the boundaries x=0, y=0 and z=0. Again, smoothing with more weight on the shape control metric produces a grid with more element dilation due to the changing valence in the mesh, whereas smoothing with more weight on the size control results in the nearly uniform grid, as seen on the right in Fig. 12.

Fig. 12

From left to right: layer of cells near the boundaries x=0, y=0, z=0 for initial grid, grid smoothed with θ=0.2, and grid smoothed with θ=0.8

7 Concluding remarks

The variational smoothing algorithm developed here employs a global optimization approach based on a novel composite local metric. Bounds on the metric are established and its properties investigated analytically and numerically. It is shown to be robust and to yield satisfactory results for triangular and quadrilateral meshes in 2D and 3D meshes of hexahedral cells. In particular, it handles several of the difficulties that have been troublesome for other smoothers. It is applicable to general element types and hybrid grids as well as 3D. Results of preliminary 3D studies are given here and more detailed numerical experiments are ongoing. We have also carried out tests on higher resolution grids and explored the effect of varying the weight coefficient θ. Other issues related to the effect of different local valence are also investigated. Modifications to the scheme permit automatic unfolding of tangled grids and control of dilation to preserve layer structures. Clearly, in engineering and scientific applications it is desirable to grade the mesh to obtain accurate approximations efficiently. In [16] we extend the metric to include error control for the approximation problem. We also consider combining redistribution with adaptive mesh refinement and the treatment of “handing node” constraint. Recently we have also extended the ideas to treat elements with curved boundaries. These extensions are described in further detail in a forthcoming paper [17].