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.     

Small polyhedron reconnection for mesh improvement and its implementation based on advancing front technique

Local transformation, or topological reconnection, is one of the effective procedures for mesh improvement method, especially for three‐dimensional tetrahedral mesh. The most frequently used local transformations for tetrahedral mesh are so‐called elementary flips, such as 2‐3 flip, 3‐2 flip, 2‐2 flip, and 4‐4 flip. Owing to the reason that these basic transformations simply make a selection from several possible configurations within a relatively small region, the improvement of mesh quality is confined. In order to further improve the quality of mesh, the authors recently suggested a new local transformation operation, small polyhedron reconnection (SPR) operation, which seeks for the optimal tetrahedralization of a polyhedron with a certain number of nodes and faces (typically composed of 20–40 tetrahedral elements). This paper is an implementation of the suggested method. The whole process to improve the mesh quality by SPR operation is presented; in addition, some strategies, similar to those used in advancing front technique, are introduced to speed up the operation. The numerical experiment shows that SPR operation is quite effective in mesh improvement and more suitable than elementary flips when combined with smoothing approach. The operation can be applied to practical problems, gaining high mesh quality with acceptable cost for computational time. Copyright © 2009 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.     

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.     

Applications of mesh smoothing: copy,morph, and sweep on unstructured quadrilateral meshes

Mesh smoothing is demonstrated to be an effective means of copying, morphing, and sweeping unstructured quadrilateral surface meshes from a source surface to a target surface. Construction of the smoother in a particular way guarantees that the target mesh will be a ‘copy’ of the source mesh, provided the boundary data of the target surface is a rigid body rotation, translation, and/or uniform scaling of the original source boundary data and provided the proper boundary node correspondence between source and target has been selected. Copying is not restricted to any particular smoother, but can be based on any locally elliptic second‐order operator. When the bounding loops are more general than rigid body transformations the method generates high‐quality, ‘morphed’ meshes. Mesh sweeping, if viewed as a morphing of the source surface to a set of target surfaces, can be effectively performed via this smoothing algorithm. Published in 1999 by John Wiley & Sons, Ltd. This article is a U.S. government work and is in the public domain in the United States.     

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.     

Tetrahedral mesh generation in convex primitives

This paper presents a method for generating tetrahedral meshes in three-dimensional primitives. Given a set of closed and convex polyhedra having non-zero volume and some mesh controlling parameters, the polyhedra are automatically split to tetrahedra satisfying the criteria of standard finite element meshes. The algorithm tries to generate elements close to regular tetrahedra by maximizing locally the minimum solid angles associated to a set of a few neighbouring tetrahedra. The input parameters define the size of the tetrahedra and they can be used to increase or decrease the discretization locally. All the new nodes, which are not needed to describe the geometry, are generated automatically.     

A Lagrangian gradient smoothing method for solid‐flow problems using simplicial mesh

A novel Lagrangian gradient smoothing method (L‐GSM) is developed to solve “solid‐flow” (flow media with material strength) problems governed by Lagrangian form of Navier‐Stokes equations. It is a particle‐like method, similar to the smoothed particle hydrodynamics (SPH) method but without the so‐called tensile instability that exists in the SPH since its birth. The L‐GSM uses gradient smoothing technique to approximate the gradient of the field variables, based on the standard GSM that was found working well with Euler grids for general fluids. The Delaunay triangulation algorithm is adopted to update the connectivity of the particles, so that supporting neighboring particles can be determined for accurate gradient approximations. Special techniques are also devised for treatments of 3 types of boundaries: no‐slip solid boundary, free‐surface boundary, and periodical boundary. An advanced GSM operation for better consistency condition is then developed. Tensile stability condition of L‐GSM is investigated through the von Neumann stability analysis as well as numerical tests. The proposed L‐GSM is validated by using benchmarking examples of incompressible flows, including the Couette flow, Poiseuille flow, and 2D shear‐driven cavity. It is then applied to solve a practical problem of solid flows: the natural failure process of soil and the resultant soil flows. The numerical results are compared with theoretical solutions, experimental data, and other numerical results by SPH and FDM to evaluate further L‐GSM performance. It shows that the L‐GSM scheme can give a very accurate result for all these examples. Both the theoretical analysis and the numerical testing results demonstrate that the proposed L‐GSM approach restores first‐order accuracy unconditionally and does not suffer from the tensile instability. It is also shown that the L‐GSM is much more computational efficient compared with SPH, especially when a large number of particles are employed in simulation.     

Simultaneous untangling and smoothing of moving grids

In this work, a technique for simultaneous untangling and smoothing of meshes is presented. It is based on an extension of an earlier mesh smoothing strategy developed to solve the computational mesh dynamics stage in fluid–structure interaction problems. In moving grid problems, mesh untangling is necessary when element inversion happens as a result of a moving domain boundary. The smoothing strategy, formerly published by the authors, is defined in terms of the minimization of a functional associated with the mesh distortion by using a geometric indicator of the element quality. This functional becomes discontinuous when an element has null volume, making it impossible to obtain a valid mesh from an invalid one. To circumvent this drawback, the functional proposed is transformed in order to guarantee its continuity for the whole space of nodal coordinates, thus achieving the untangling technique. This regularization depends on one parameter, making the recovery of the original functional possible as this parameter tends to 0. This feature is very important: consequently, it is necessary to regularize the functional in order to make the mesh valid; then, it is advisable to use the original functional to make the smoothing optimal. Finally, the simultaneous untangling and smoothing technique is applied to several test cases, including 2D and 3D meshes with simplicial elements. As an additional example, the application of this technique to a mesh generation case is presented. Copyright © 2008 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.     

Obtaining smooth mesh transitions using vertex optimization

Mesh optimization has proven to be an effective way to improve mesh quality for arbitrary Lagrangian Eulerian (ALE) simulations. To date, however, most of the focus has been on improving the geometric shape of individual elements, and these methods often do not result in smooth transitions in element size or aspect ratio across groups of elements. We present an extension to the mean ratio optimization that addresses this problem and yields smooth transitions within regions and across regions in the ALE simulation. While this method is presented in the context of ALE simulations, it is applicable to a wider set of applications that require mesh improvement, including the mesh generation process. Published in 2007 by 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.     

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 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.     

Smoothed Galerkin methods using cell-wise strain smoothing technique

A smoothed Galerkin method (SGM) using cell-wise strain smoothing operation is formulated in this paper. In present method, the field nodes can be divided into two types: boundary field nodes and interior field nodes. The background cells are divided into SC smoothing cells, and the strains in each smoothing cell are obtained using a gradient smoothing technique which can avoid evaluating derivatives of shape functions at integration point. The field variables of boundary points are approximated using linear interpolation of neighbour boundary field nodes, and the shape functions possess the Kronecker Delta property and facilitate the impositions of essential boundary conditions. The field variables of interior points are approximated using moving least-squares approximation using the support field nodes around them. A number of numerical examples are studied and confirm the significant features of the present methods: (1) can pass the standard patch test; (2) can easily impose essential boundary conditions as those in finite element method; (3) can avoid evaluating derivatives of shape functions; (4) no numerical parameter is required.     

实验观测数据的最优正则平滑方法

为了滤除测量噪声 ,提出了一种对实验观测数据进行最优化正则平滑的数据处理方法 .文中阐述了方法的基本原理 ,并就稳定泛函和正则参数的选择等关键问题作了分析和论述 .通过一个数学模拟实例对正则化平滑方法的效果进行了验证 ,这种正则化平滑方法在数学物理反问题求解等领域具有独特的优点     

A minimal element distortion strategy for computational mesh dynamics

Mesh motion strategy is one of the key points in many fluid–structure interaction (FSI) problems. Due to the increasing application of FSI to solve the current challenging engineering problems, this topic has become of great interest. There are several different strategies to solve this problem, some of them use a discrete and lumped spring–mass system to propagate the boundary motion into the volume mesh, and many others use an elastostatic problem to deform the mesh. In all these strategies there is always risk of producing an invalid mesh, i.e. a mesh with some elements inverted. Normally this condition is irreversible and once an invalid mesh is obtained it is difficult to continue. In this paper the mesh motion strategy is defined as an optimization problem. By its definition this strategy can be classified as a particular case of an elastostatic problem where the material constitutive law is defined in terms of the minimization of certain energy functional that takes into account the degree of element distortion. Some advantages of this strategy are its natural tendency to high quality meshes, its robustness and its straightforward extension to 3D problems. Several examples included in this paper show these capabilities. Even though this strategy seems to be very robust it is not able to recover a valid mesh starting from an invalid one. This improvement is left for future work. Copyright © 2006 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.     

高精度自适应的四边形网格重建

提出了海量数据点集的四边形网格重建算法。首先根据精度要求简化数据点,按一定规则连接相邻的简化数据点生成多边形网格,对网格中高斯曲率较大的顶点进行局部细分提高其精度,然后对多边形网格进行整体细分使其全部转化为四边形网格,最后分裂度较大的顶点对其进行优化。实验结果表明,算法对拓扑结构较为复杂的海量数据点集的四边形网格重建是行之有效的。