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.     

Quality improvements in extruded meshes using topologically adaptive generalized elements

This paper describes a method to extrude near‐body volume meshes that exploits topologically adaptive generalized elements to improve local mesh quality. Specifically, an advancing layer algorithm for extruding volume meshes from surface meshes of arbitrary topology, appropriate for viscous fluid flows, is discussed. First, a two‐layer reference mesh is generated from the layer initial surface mesh by extruding along the local surface normals. The reference mesh is then smoothed using a Poisson equation. Local quality improvement operations such as edge collapse, face refinement, and local reconnection are performed in each layer to drive the mesh toward isotropy and improve the transition from the extruded mesh to a void‐filling tetrahedral mesh. A few example meshes along with quality plots are presented to demonstrate the efficacy of this approach. Copyright © 2004 John Wiley & Sons, Ltd.     

Anisotropic tetrahedral meshing via bubble packing and advancing front

This paper presents a new computational method for anisotropic tetrahedral meshing. The method can control element anisotropy based on a specified 3×3 tensor field defined over a volumetric domain. Our method creates a tetrahedral mesh in two steps: (1) placing nodes at the centres of tightly packed ellipsoidal cells, called bubbles, in the domain, and (2) connecting the nodes by a modified advancing front followed by local transformation. The method creates a high‐quality anisotropic mesh that conforms well to a specified tensor field. Copyright © 2003 John Wiley & Sons, Ltd.     

A new method for coarsening tetrahedral meshes

To coarsen a mesh, we usually remove a set of selected nodes one by one. Currently, the basic operation used to remove a node is edge collapsing, which does not perform well when applied to handling narrow regions in a tetrahedron mesh and could produce low‐quality elements or even fail to give valid results. To overcome the drawbacks of edge collapsing, we present a new node‐removal operator created by revising a topological transformation called small polyhedron reconnection. This new operator can guarantee success if the cavity that forms after a node is removed is meshable, and it produces higher‐quality results and keeps the nodes unmoved, which is preferred for applications such as multigrid hierarchies. In addition, 2 other aspects of mesh coarsening that determine whether a node should be removed and the sequence in which to remove the selected nodes are also studied. Our strategy consists of constructing a coarse node set using the sphere‐packing method and removing the nodes in a reversed kd‐tree sequence. The excellent performance of the new method is demonstrated by applying it to examples of adaptive meshing and multigrid hierarchy creation and comparing the results with those of the edge collapsing method.     

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.     

Localized remeshing techniques for three‐dimensional metal forming simulations with linear tetrahedral elements

The localized remeshing technique for three‐dimensional metal forming simulations is proposed based on a mixed finite element formulation with linear tetrahedral elements in the present study. The numerical algorithm to generate linear tetrahedral elements is developed for finite element analyses using the advancing front technique with local optimization method which keeps the advancing fronts smooth. The surface mesh generation using mesh manipulations of the boundary elements of the old mesh system was made to improve mesh quality of the boundary surface elements, resulting in reduction of volume change in forming simulations. The mesh quality generated was compared with that obtained from the commercial CAD package for the complex geometry like lumbar. The simulation results of backward extrusion and bevel gear and spider forgings indicate that the currently developed simulation technique with the localized remeshing can be used effectively to simulate the three‐dimensional forming processes with a reduced computation time. Copyright © 2006 John Wiley & Sons, Ltd.     

Variational Delaunay approach to the generation of tetrahedral finite element meshes

We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set à priori. The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty‐sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re‐formulate Delaunay triangulation as a linear programming problem. Copyright © 2001 John Wiley & Sons, Ltd.     

Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II—A framework for volume mesh optimization and the condition number of the Jacobian matrix

Three‐dimensional unstructured tetrahedral and hexahedral finite element mesh optimization is studied from a theoretical perspective and by computer experiments to determine what objective functions are most effective in attaining valid, high‐quality meshes. The approach uses matrices and matrix norms to extend the work in Part I to build suitable 3D objective functions. Because certain matrix norm identities which hold for 2×2 matrices do not hold for 3×3 matrices, significant differences arise between surface and volume mesh optimization objective functions. It is shown, for example, that the equality in two dimensions of the smoothness and condition number of the Jacobian matrix objective functions does not extend to three dimensions and further, that the equality of the Oddy and condition number of the metric tensor objective functions in two dimensions also fails to extend to three dimensions. Matrix norm identities are used to systematically construct dimensionally homogeneous groups of objective functions. The concept of an ideal minimizing matrix is introduced for both hexahedral and tetrahedral elements. Non‐dimensional objective functions having barriers are emphasized as the most logical choice for mesh optimization. The performance of a number of objective functions in improving mesh quality was assessed on a suite of realistic test problems, focusing particularly on all‐hexahedral ‘whisker‐weaved’ meshes. Performance is investigated on both structured and unstructured meshes and on both hexahedral and tetrahedral meshes. Although several objective functions are competitive, the condition number objective function is particularly attractive. The objective functions are closely related to mesh quality measures. To illustrate, it is shown that the condition number metric can be viewed as a new tetrahedral element quality measure. Published in 2000 by 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.     

Converting a tetrahedral mesh to a prism–tetrahedral hybrid mesh for FEM accuracy and efficiency

This paper presents a computational method for converting a tetrahedral mesh to a prism–tetrahedral hybrid mesh for improved solution accuracy and computational efficiency of finite element analysis. The proposed method performs this conversion by inserting layers of prism elements and deleting tetrahedral elements in sweepable sub‐domains, in which cross‐sections remain topologically identical and geometrically similar along a certain sweeping path. The total number of finite elements is reduced because roughly three tetrahedral elements are converted to one prism element. The solution accuracy of the finite element analysis improves since a prism element yields a more accurate solution than a tetrahedral element due to the presence of higher‐order terms in the shape function. Only previously known method for creating such a prism–tetrahedral hybrid mesh was to manually decompose a target volume into sweepable and non‐sweepable sub‐volumes and mesh each of the sub‐volumes separately. Unlike the previous method, the proposed method starts from a cross‐section of a tetrahedral mesh and replaces the tetrahedral elements with layers of prism elements until prescribed quality criteria can no longer be satisfied. A series of computational fluid dynamics simulations and structural analyses have been conducted, and the results verified a better performance of prism–tetrahedral hybrid mesh. Copyright © 2009 John Wiley & Sons, Ltd.     

Robust generation of high‐quality unstructured meshes on realistic biomedical geometry

In this paper, we propose efficient and robust unstructured mesh generation methods based on computed tomography (CT) and magnetic resonance imaging (MRI) data, in order to obtain a patient‐specific geometry for high‐fidelity numerical simulations. Surface extraction from medical images is carried out mainly using open source libraries, including the Insight Segmentation and Registration Toolkit and the Visualization Toolkit, into the form of facet surface representation. To create high‐quality surface meshes, we propose two approaches. One is a direct advancing front method, and the other is a modified decimation method. The former emphasizes the controllability of local mesh density, and the latter enables semi‐automated mesh generation from low‐quality discrete surfaces. An advancing‐front‐based volume meshing method is employed. Our approaches are demonstrated with high‐fidelity tetrahedral meshes around medical geometries extracted from CT/MRI data. Copyright © 2005 John Wiley & Sons, Ltd.     

Improvements in the reliability and element quality of parallel tetrahedral mesh generation

The paper presents a parallel tetrahedral mesh generation approach based on recursive bidivisions using triangular surfaces. Research was conducted for addressing issues concerning mesh generation reliability and element quality. A novel procedure employing local modification techniques is proposed for repairing the intersecting interdomain mesh instead of directly repeating the bidivision procedure, which improves the robustness of the complete meshing procedure significantly. In addition, a new parallel quality improvement scheme is suggested for optimizing the distributed volume meshes. The scheme is free of any communication cost and highly efficient. Finally, mesh experiments of hundreds of millions of elements are performed to demonstrate the reliability, effectiveness and efficiency of the proposed method and its potential applications to large‐scale simulations of complex aerodynamics models. Copyright © 2012 John Wiley & Sons, Ltd.     

An algebraic method for smoothing surface triangulations on a local parametric space

This paper presents a new procedure to improve the quality of triangular meshes defined on surfaces. The improvement is obtained by an iterative process in which each node of the mesh is moved to a new position that minimizes a certain objective function. This objective function is derived from algebraic quality measures of the local mesh (the set of triangles connected to the adjustable or free node). If we allow the free node to move on the surface without imposing any restriction, only guided by the improvement of the quality, the optimization procedure can construct a high‐quality local mesh, but with this node in an unacceptable position. To avoid this problem the optimization is done in the parametric mesh, where the presence of barriers in the objective function maintains the free node inside the feasible region. In this way, the original problem on the surface is transformed into a two‐dimensional one on the parametric space. In our case, the parametric space is a plane, chosen in terms of the local mesh, in such a way that this mesh can be optimally projected performing a valid mesh, that is, without inverted elements. Several examples and applications presented in this work show how this technique is capable of improving the quality of triangular surface meshes. Copyright © 2005 John Wiley & Sons, Ltd.     

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions

A method using techniques of computational geometry for generating tetrahedral finite element meshes in three-dimensional polyhedral regions is presented. The input to the method consists of the boundary faces of the polyhedral region and possibly internal and hole interfaces, plus the desired number of tetrahedra and other scalar parameters. The region is decomposed into convex polyhedra in two stages so that tetrahedra of one length scale can be generated in each subregion. A mesh distribution function, which is either automatically constructed from the first-stage convex polyhedron decomposition or supplied by the user, is used to determine the tetrahedron sizes in the subregions. Then a boundary-constrained triangulation is constructed in each convex polyhedron, with local transformations being used to improve the quality of the tetrahedra. Experimental results from triangulations of three regions are provided.     

Tetrahedral mesh improvement using swapping and smoothing

Automatic mesh generation and adaptive refinement methods for complex three-dimensional domains have proven to be very successful tools for the efficient solution of complex applications problems. These methods can, however, produce poorly shaped elements that cause the numerical solution to be less accurate and more difficult to compute. Fortunately, the shape of the elements can be improved through several mechanisms, including face- and edge-swapping techniques, which change local connectivity, and optimization-based mesh smoothing methods, which adjust mesh point location. We consider several criteria for each of these two methods and compare the quality of several meshes obtained by using different combinations of swapping and smoothing. Computational experiments show that swapping is critical to the improvement of general mesh quality and that optimization-based smoothing is highly effective in eliminating very small and very large angles. High-quality meshes are obtained in a computationally efficient manner by using optimization-based smoothing to improve only the worst elements and a smart variant of Laplacian smoothing on the remaining elements. Based on our experiments, we offer several recommendations for the improvement of tetrahedral meshes. © 1997 John Wiley & Sons, Ltd.     

Advances in tetrahedral mesh generation for modelling of three‐dimensional regions with complex,curvilinear crack shapes

Advances in tetrahedral mesh generation for general, three‐dimensional domains with and without cracks are described and validated through extensive studies using a wide range of global geometries and local crack shapes. Automated methods are described for (a) implementing geometrical measures in the vicinity of the crack to identify irregularities and to improve mesh quality and (b) robust node selection on crack surfaces to ensure optimal meshing both locally and globally. The resulting numerical algorithms identify both node coincidence and also local crack surface penetration due to discretization of curved crack surfaces, providing a proven approach for removing inconsistencies. Numerical examples using the resulting 3D mesh generation program to mesh complex 3D domains containing a range of crack shapes and sizes are presented. Quantitative measures of mesh quality clearly show that the element shape and size distributions are excellent, including in regions surrounding crack fronts. Copyright © 2005 John Wiley & Sons, Ltd.     

Fully‐automated hex‐dominant mesh generation with directionality control via packing rectangular solid cells

A new fully automatic hex‐dominant mesh generation technique of an arbitrary 3D geometric domain is presented herein. The proposed method generates a high‐quality hex‐dominant mesh by: (1) controlling the directionality of the output hex‐dominant mesh; and (2) avoiding ill‐shaped elements induced by nodes located too closely to each other. The proposed method takes a 3D geometric domain as input and creates a hex‐dominant mesh consisting mostly of hexahedral elements, with additional prism and tetrahedral elements. Rectangular solid cells are packed on the boundary of and inside the input domain to obtain ideal node locations for a hex‐dominant mesh. Each cell has a potential energy field that mimics a body‐centred cubic (BCC) structure (seen in natural substances such as NaCl) and the cells are moved to stable positions by a physically based simulation. The simulation mimics the formation of a crystal pattern so that the centres of the cells provide ideal node locations for a hex‐dominant mesh. Via the advancing front method, the centres of the packed cells are then connected to form a tetrahedral mesh, and this is converted to a hex‐dominant mesh by merging some of the tetrahedrons. Copyright © 2003 John Wiley & Sons, Ltd.     

Two improvements in formulation of nine‐node element MITC9

The paper concerns a well‐known two‐dimensional nine‐node quadrilateral element MITC9, which is based on two‐level approximations of strains (assumed strain method). The element has good accuracy, but does not pass the patch test. As the first improvement, we propose a modification of the element's transformations, partly resolving the problem with the patch test. The source of the problem is the use of covariant components in a (local) natural co‐basis, different at each sampling point. As the second improvement, we use the corrected shape functions of Celia MA, Gray WG. An improved isoparametric transformation for finite element analysis. International Journal for Numerical Methods in Engineering 1984; 20 :1447–1459, extending their applicability to the nine‐node element for plane elasticity and the 3 × 3 integration. Originally, they are tested for an eight‐node element for the heat conduction equation and the 4 × 4 integration. The improved element, designated as MITC9i, is based on the Green strain and derived from the potential energy for the plane stress condition. It is subjected to a range of tests, to confirm that it passes the patch test for several types of mesh distortions, to prove its coarse mesh accuracy and the absence of locking as well as to establish its sensitivity to mesh distortions. The improved element MITC9i performs substantially better than the MITC9 element, QUAD9** element, and our previous 9‐AS element.Copyright © 2012 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.