Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part I—a framework for surface mesh optimization

Structured mesh quality optimization methods are extended to optimization of unstructured triangular, quadrilateral, and mixed finite element meshes. New interpretations of well‐known nodally based objective functions are made possible using matrices and matrix norms. The matrix perspective also suggests several new objective functions. Particularly significant is the interpretation of the Oddy metric and the smoothness objective functions in terms of the condition number of the metric tensor and Jacobian matrix, respectively. Objective functions are grouped according to dimensionality to form weighted combinations. A simple unconstrained local optimum is computed using a modified Newton iteration. The optimization approach was implemented in the CUBIT mesh generation code and tested on several problems. Results were compared against several standard element‐based quality measures to demonstrate that good mesh quality can be achieved with nodally based objective functions. Published in 2000 by John Wiley & Sons, Ltd.     

Tetrahedral mesh improvement via optimization of the element condition number

We present a new shape measure for tetrahedral elements that is optimal in that it gives the distance of a tetrahedron from the set of inverted elements. This measure is constructed from the condition number of the linear transformation between a unit equilateral tetrahedron and any tetrahedron with positive volume. Using this shape measure, we formulate two optimization objective functions that are differentiated by their goal: the first seeks to improve the average quality of the tetrahedral mesh; the second aims to improve the worst‐quality element in the mesh. We review the optimization techniques used with each objective function and present experimental results that demonstrate the effectiveness of the mesh improvement methods. We show that a combined optimization approach that uses both objective functions obtains the best‐quality meshes for several complex geometries. Copyright © 2001 John Wiley & Sons, Ltd.     

A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling

We propose a multiobjective mesh optimization framework for mesh quality improvement and mesh untangling. Our framework combines two or more competing objective functions into a single objective function to be solved using one of various multiobjective optimization methods. Methods within our framework are able to optimize various aspects of the mesh such as the element shape, element size, associated PDE interpolation error, and number of inverted elements, but the improvement is not limited to these categories. The strength of our multiobjective mesh optimization framework lies in its ability to be extended to simultaneously optimize any aspects of the mesh and to optimize meshes with different element types. We propose the exponential sum, objective product, and equal sum multiobjective mesh optimization methods within our framework; these methods do not require articulation of preferences. However, the solutions obtained satisfy a sufficient condition of weak Pareto optimality. Experimental results show that our multiobjective mesh optimization methods are able to simultaneously optimize two or more aspects of the mesh and also are able to improve mesh qualities while eliminating inverted elements. We successfully apply our methods to real‐world applications such as hydrocephalus treatment and shape optimization. Copyright © 2013 John Wiley & Sons, Ltd.     

Octree‐based reasonable‐quality hexahedral mesh generation using a new set of refinement templates

An octree‐based mesh generation method is proposed to create reasonable‐quality, geometry‐adapted unstructured hexahedral meshes automatically from triangulated surface models without any sharp geometrical features. A new, easy‐to‐implement, easy‐to‐understand set of refinement templates is developed to perform local mesh refinement efficiently even for concave refinement domains without creating hanging nodes. A buffer layer is inserted on an octree core mesh to improve the mesh quality significantly. Laplacian‐like smoothing, angle‐based smoothing and local optimization‐based untangling methods are used with certain restrictions to further improve the mesh quality. Several examples are shown to demonstrate the capability of our hexahedral mesh generation method for complex geometries. Copyright © 2008 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation based on advancing front technique and optimization scheme

In recent years, demand for three‐dimensional simulations has continued to grow in the field of computer‐aided engineering. Especially, in the analysis of forming processes a fully automatic and robust mesh generator is necessary for handling complex geometries used in industry. For three‐dimensional analyses, tetrahedral elements are commonly used due to the advantage in dealing with such geometries. In this study, the advancing front technique has been implemented and modified using an optimization scheme. In this optimization scheme, the distortion metric determines ‘when and where’ to smooth, and serves as an objective function. As a result, the performance of the advancing front technique is improved in terms of mesh quality generated. Copyright © 2003 John Wiley & Sons, Ltd.     

Anisotropic mesh adaption by metric‐driven optimization

We describe a Gauss–Seidel algorithm for optimizing a three‐dimensional unstructured grid so as to conform to a given metric. The objective function for the optimization process is based on the maximum value of an elemental residual measuring the distance of any simplex in the grid to the local target metric. We analyse different possible choices for the objective function, and we highlight their relative merits and deficiencies. Alternative strategies for conducting the optimization are compared and contrasted in terms of resulting grid quality and computational costs. Numerical simulations are used for demonstrating the features of the proposed methodology, and for studying some of its characteristics. Copyright © 2004 John Wiley & Sons, Ltd.     

The generation of hexahedral meshes for assembly geometry: survey and progress

The finite element method is being used today to model component assemblies in a wide variety of application areas, including structural mechanics, fluid simulations, and others. Generating hexahedral meshes for these assemblies usually requires the use of geometry decomposition, with different meshing algorithms applied to different regions. While the primary motivation for this approach remains the lack of an automatic, reliable all‐hexahedral meshing algorithm, requirements in mesh quality and mesh configuration for typical analyses are also factors. For these reasons, this approach is also sometimes required when producing other types of unstructured meshes. This paper will review progress to date in automating many parts of the hex meshing process, which has halved the time to produce all‐hex meshes for large assemblies. Particular issues which have been exposed due to this progress will also be discussed, along with their applicability to the general unstructured meshing problem. Published in 2001 by John Wiley & Sons, Ltd.     

Quality improvement of non‐manifold hexahedral meshes for critical feature determination of microstructure materials

This paper describes a novel approach to improve the quality of non‐manifold hexahedral meshes with feature preservation for microstructure materials. In earlier works, we developed an octree‐based isocontouring method to construct unstructured hexahedral meshes for domains with multiple materials by introducing the notion of material change edge to identify the interface between two or more materials. However, quality improvement of non‐manifold hexahedral meshes is still a challenge. In the present algorithm, all the vertices are categorized into seven groups, and then a comprehensive method based on pillowing, geometric flow and optimization techniques is developed for mesh quality improvement. The shrink set in the modified pillowing technique is defined automatically as the boundary of each material region with the exception of local non‐manifolds. In the relaxation‐based smoothing process, non‐manifold points are identified and fixed. Planar boundary curves and interior spatial curves are distinguished, and then regularized using B‐spline interpolation and resampling. Grain boundary surface patches and interior vertices are improved as well. Finally, the optimization method eliminates negative Jacobians of all the vertices. We have applied our algorithms to two beta titanium data sets, and the constructed meshes are validated via a statistics study. Finite element analysis of the 92‐grain titanium is carried out based on the improved mesh, and compared with the direct voxel‐to‐element technique. Copyright © 2009 John Wiley & Sons, Ltd.     

All‐hexahedral mesh smoothing with a node‐based measure of quality

This research work deals with the analysis and test of a normalized‐Jacobian metric used as a measure of the quality of all‐hexahedral meshes. Instead of element qualities, a measure of node quality was chosen. The chosen metric is a bound for deviation from orthogonality of faces and dihedral angles. We outline the main steps and algorithms of a program that is successful in improving the quality of initially invalid meshes to acceptable levels. For node movements, the program relies on a combination of gradient‐driven and simulated annealing techniques. Some examples of the results and speed are also shown. Copyright © 2001 John Wiley & Sons, Ltd.     

Anisotropic mesh optimization and its application in adaptivity

The construction of solution-adapted meshes is addressed within an optimization framework. An approximation of the second spatial derivative of the solution is used to get a suitable metric in the computational domain. A mesh quality is proposed and optimized under this metric, accounting for both the shape and the size of the elements. For this purpose, a topological and geometrical mesh improvement method of high generality is introduced. It is shown that the adaptive algorithm that results recovers optimal convergence rates in singular problems, and that it captures boundary and internal layers in convection-dominated problems. Several important implementation issues are discussed. © 1997 John Wiley & Sons, Ltd.     

Towards automatic structured multiblock mesh generation using improved transfinite interpolation

The quality of any numerical flowfield solution is inextricably linked to the quality of the mesh used. It is normally accepted that structured meshes are of higher quality than unstructured meshes, but are much more difficult to generate and, furthermore, for complex topologies a multiblock approach is required. This is the most resource‐intensive approach to mesh generation, since block structures, mesh point distributions, etc., need to be defined before the generation process, and so is seldom used in an industrial design loop, particularly where a novice user may be involved. This paper considers and presents two significant advances in multiblock mesh generation: the development of a fast, robust, and improved quality interpolation‐based generation scheme and a fully automatic multiblock optimization and generation method. A volume generation technique is presented based on a form of transfinite interpolation, but modified to include improved orthogonality and spacing control and, more significantly, an aspect ratio‐based smoothing algorithm that removes grid crossover and results in smooth meshes even for discontinuous boundary distributions. A fully automatic multiblock generation scheme is also presented, which only requires surface patch(es) and a target number of mesh cells. Hence, all user input is removed from the process, and a novice user is able to obtain a high‐quality mesh in a few minutes. It also means the code can be run in batch mode, or called as an external function, and so is ideal for incorporation into a design or optimization loop. To demonstrate the power and efficiency of the code, multiblock meshes of up to 256 million cells are presented for wings and rotors in hover and forward flight. Copyright © 2007 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations

The centroidal Voronoi tessellation based Delaunay triangulation (CVDT) provides an optimal distribution of generating points with respect to a given density function and accordingly generates a high‐quality mesh. In this paper, we discuss algorithms for the construction of the constrained CVDT from an initial Delaunay tetrahedral mesh of a three‐dimensional domain. By establishing an appropriate relationship between the density function and the specified sizing field and applying the Lloyd's iteration, the constrained CVDT mesh is obtained as a natural global optimization of the initial mesh. Simple local operations such as edges/faces flippings are also used to further improve the CVDT mesh. Several complex meshing examples and their element quality statistics are presented to demonstrate the effectiveness and efficiency of the proposed mesh generation and optimization method. Copyright © 2003 John Wiley & Sons, Ltd.     

On advancing front mesh generation in three dimensions

This paper deals with some aspects of unstructured mesh generation in three dimensions by the advancing front technique. In particular, the parameters used in the algorithm are characterized, and strategies that may be used to improve robustness are suggested. We also describe a method whereby structured tetrahedral meshes with exceptionally stretched elements adjacent to boundary surfaces may be produced. The suggested method can be combined with the advancing front concept in a natural way.     

Automated refinement of conformal quadrilateral and hexahedral meshes

Conformal refinement using a shrink and connect strategy, known as pillowing or buffer insertion, contracts and reconnects contiguous elements of an all‐quadrilateral or an all‐hexahedral mesh in order to locally increase vertex density without introducing hanging nodes or non‐cubical elements. Using layers as shrink sets, the present method automates the anisotropic refinement of such meshes according to a prescribed size map expressed as a Riemannian metric field. An anisotropic smoother further enhances vertex clustering to capture the features of the metric. Both two‐ and three‐dimensional test cases with analytic control metrics confirm the feasibility of the present approach and explore strategies to minimize the trade‐off between element shape quality and size conformity. Additional examples using discrete metric maps illustrate possible practical applications. Although local vertex removal and reconnection capabilities have yet to be developed, the present refinement method is a step towards an automated tool for conformal adaptation of all‐quadrilateral and all‐hexahedral meshes. Copyright © 2004 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation using Delaunay refinement with non‐standard quality measures

This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non‐standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between 18^circ and 154^°. Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between 14^° and 154^° can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius‐to‐shortest‐edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above 20^°, regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth. Copyright © 2011 John Wiley & Sons, Ltd.     

Surface mesh quality evaluation

This paper proposes a method to evaluate the size quality as well as the shape quality of constrained surface meshes, the constraint being either a given metric or the geometric metric associated with the surface geometry. In the context of numerical simulations, the metric specifications are those related to the finite element method. The proposed measures allow to validate the surface meshes within a general mesh adaption scheme, the metric map being usually provided via an a posteriori error estimate. Several examples of surface meshes are proposed to illustrate the relevance of the approach. Copyright © 1999 John Wiley & Sons, Ltd.     

Hierarchical tree‐based finite element mesh generation

Hierarchical grid generation and its use as a basis for finite element mesh generation are considered in this paper. The hierarchical grids are generated by recursive subdivision using quadtrees in two dimensions and octrees in three dimensions. A numbering system for efficient storage of the quadtree grid information is examined, tree traversal techniques are devised for neighbour finding, and accurate boundary representation is considered. It is found that hierarchical grids are straightforward to generate from sets of seeding points which lie along domain boundaries. Quadtree grids are triangularized to provide finite element meshes in two dimensions. Three‐dimensional tetrahedral meshes are generated from octree grids. The meshes can be generated automatically to model complicated geometries with highly irregular boundaries and can be adapted readily at moving boundaries. Examples are given of two‐ and three‐dimensional hierarchical tree‐based finite element meshes and their application to modelling free surface waves. Copyright © 1999 John Wiley & Sons, Ltd.     

A universal measure of the conformity of a mesh with respect to an anisotropic metric field

In this paper, a method is presented to measure the non‐conformity of a mesh with respect to a size specification map given in the form of a Riemannian metric. The measure evaluates the difference between the metric tensor of a simplex of the mesh and the metric tensor specified on the size specification map. This measure is universal because it is a unique, dimensionless number which characterizes either a single simplex of a mesh or a whole mesh, both in size and in shape, be it isotropic or anisotropic, coarse or fine, in a small or a big domain, in two or three dimensions. This measure is important because it can compare any two meshes in order to determine unequivocally which of them is better. Analytical and numerical examples illustrate the behaviour of this measure. Copyright © 2004 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation based on space indicator functions

An algorithm for the generation of tetrahedral volume meshes is developed for highly irregular objects specified by volumetric representations such as domain indicator functions and tomography data. It is based on red–green refinement of an initial mesh derived from a body‐centered cubic lattice. A quantitative comparison of alternative types of initial meshes is presented. The minimum set of best‐quality green refinement schemes is identified. Boundary conformity is established by deforming or splitting surface‐crossing elements. Numerical derivatives of input data are strictly avoided. Furthermore, the algorithm features surface‐adaptive mesh density based on local surface roughness, which is an integral property of finite surface portions. Examples of applications are presented for computer tomography of porous media. Copyright © 2012 John Wiley & Sons, Ltd.