Coarsening unstructured meshes by edge contraction

A new unstructured mesh coarsening algorithm has been developed for use in conjunction with multilevel methods. The algorithm preserves geometrical and topological features of the domain, and retains a maximal independent set of interior vertices to produce good coarse mesh quality. In anisotropic meshes, vertex selection is designed to retain the structure of the anisotropic mesh while reducing cell aspect ratio. Vertices are removed incrementally by contracting edges to zero length. Each vertex is removed by contracting the edge that maximizes the minimum sine of the dihedral angles of cells affected by the edge contraction. Rarely, a vertex slated for removal from the mesh cannot be removed; the success rate for vertex removal is typically 99.9% or more. For two‐dimensional meshes, both isotropic and anisotropic, the new approach is an unqualified success, removing all rejected vertices and producing output meshes of high quality; mesh quality degrades only when most vertices lie on the boundary. Three‐dimensional isotropic meshes are also coarsened successfully, provided that there is no difficulty distinguishing corners in the geometry from coarsely‐resolved curved surfaces; sophisticated discrete computational geometry techniques appear necessary to make that distinction. Three‐dimensional anisotropic cases are still problematic because of tight constraints on legal mesh connectivity. More work is required to either improve edge contraction choices or to develop an alternative strategy for mesh coarsening for three‐dimensional anisotropic meshes. Copyright © 2003 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.     

Verification of three‐dimensional anisotropic adaptive processes

A verification methodology for adaptive processes is devised. The mathematical claims made during the process are identified and measures are presented in order to verify that the mathematical equations are solved correctly. The analysis is based on a formal definition of the optimality of the adaptive process in the case of the control of the L^∞‐norm of the interpolation error. The process requires a reconstruction that is verified using a proper norm. The process also depends on mesh adaptation toolkits in order to generate adapted meshes. In this case, the non‐conformity measure is used to evaluate how well the adapted meshes conform to the size specification map at each iteration. Finally, the adaptive process should converge toward an optimal mesh. The optimality of the mesh is measured using the standard deviation of the element‐wise value of the L^∞‐norm of the interpolation error. The results compare the optimality of an anisotropic process to an isotropic process and to uniform refinement on highly anisotropic 2D and 3D test cases. Copyright © 2011 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.     

An L∞–Lp mesh‐adaptive method for computing unsteady bi‐fluid flows

This paper discusses the contribution of mesh adaptation to high‐order convergence of unsteady multi‐fluid flow simulations on complex geometries. The mesh adaptation relies on a metric‐based method controlling the L ^p‐norm of the interpolation error and on a mesh generation algorithm based on an anisotropic Delaunay kernel. The mesh‐adaptive time advancing is achieved, thanks to a transient fixed‐point algorithm to predict the solution evolution coupled with a metric intersection in the time procedure. In the time direction, we enforce the equidistribution of the error, i.e. the error minimization in L ^∞ norm. This adaptive approach is applied to an incompressible Navier–Stokes model combined with a level set formulation discretized on triangular and tetrahedral meshes. Applications to interface flows under gravity are performed to evaluate the performance of this method for this class of discontinuous flows. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

A new automatic adaptive 3D solid mesh generation scheme for thin‐walled structures

A new algorithm to generate three‐dimensional (3D) mesh for thin‐walled structures is proposed. In the proposed algorithm, the mesh generation procedure is divided into two distinct phases. In the first phase, a surface mesh generator is employed to generate a surface mesh for the mid‐surface of the thin‐walled structure. The surface mesh generator used will control the element size properties of the final mesh along the surface direction. In the second phase, specially designed algorithms are used to convert the surface mesh to a 3D solid mesh by extrusion in the surface normal direction of the surface. The extrusion procedure will control the refinement levels of the final mesh along the surface normal direction. If the input surface mesh is a pure quadrilateral mesh and refinement level in the surface normal direction is uniform along the whole surface, all hex‐meshes will be produced. Otherwise, the final 3D meshes generated will eventually consist of four types of solid elements, namely, tetrahedron, prism, pyramid and hexahedron. The presented algorithm is highly flexible in the sense that, in the first phase, any existing surface mesh generator can be employed while in the second phase, the extrusion procedure can accept either a triangular or a quadrilateral or even a mixed mesh as input and there is virtually no constraint on the grading of the input mesh. In addition, the extrusion procedure development is able to handle structural joints formed by the intersections of different surfaces. Numerical experiments indicate that the present algorithm is applicable to most practical situations and well‐shaped elements are generated. Copyright © 2004 John Wiley & Sons, Ltd.     

A distortion measure to validate and generate curved high‐order meshes on CAD surfaces with independence of parameterization

A framework to validate and generate curved nodal high‐order meshes on Computer‐Aided Design (CAD) surfaces is presented. The proposed framework is of major interest to generate meshes suitable for thin‐shell and 3D finite element analysis with unstructured high‐order methods. First, we define a distortion (quality) measure for high‐order meshes on parameterized surfaces that we prove to be independent of the surface parameterization. Second, we derive a smoothing and untangling procedure based on the minimization of a regularization of the proposed distortion measure. The minimization is performed in terms of the parametric coordinates of the nodes to enforce that the nodes slide on the surfaces. Moreover, the proposed algorithm repairs invalid curved meshes (untangling), deals with arbitrary polynomial degrees (high‐order), and handles with low‐quality CAD parameterizations (independence of parameterization). Third, we use the optimization procedure to generate curved nodal high‐order surface meshes by means of an a posteriori approach. Given a linear mesh, we increase the polynomial degree of the elements, curve them to match the geometry, and optimize the location of the nodes to ensure mesh validity. Finally, we present several examples to demonstrate the features of the optimization procedure, and to illustrate the surface mesh generation process. Copyright © 2015 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.     

The construction of improved‐quality mesh on a curved surface using mapping factors

Abstract

The Delaunay triangulation is broadly used on flat surfaces to generate well‐shaped elements. But the properties of Delaunay triangulation do not exist on curved surfaces whose Jacobians are different. In this paper we will present a modified algorithm to improve the shape of triangulation for the curved surface. The experiment results show that making use of “mapping factors” in the Delaunay triangulation and Laplacian method can produce better mesh (most aspect ratios≤3) on a curved surface.     

Remeshing for metal forming simulations—Part II: Three‐dimensional hexahedral mesh generation

In the present study, a hexahedral mesh generator was developed for remeshing in three‐dimensional metal forming simulations. It is based on the master grid approach and octree‐based refinement scheme to generate uniformly sized or locally refined hexahedral mesh system. In particular, for refined hexahedral mesh generation, the modified Laplacian mesh smoothing scheme mentioned in the two‐dimensional study (Part I) was used to improve the mesh quality while also minimizing the loss of element size conditions. In order to investigate the applicability and effectiveness of the developed hexahedral mesh generator, several three‐dimensional metal forming simulations were carried out using uniformly sized hexahedral mesh systems. Also, a comparative study of indentation analyses was conducted to check the computational efficiency of locally refined hexahedral mesh systems. In particular, for specification of refinement conditions, distributions of effective strain‐rate gradient and posteriori error values based on a Z² error estimator were used. From this study, it is construed that the developed hexahedral mesh generator can be effectively used for three‐dimensional metal forming simulations. Copyright © 2002 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.     

Universal meshes for smooth surfaces with no boundary in three dimensions

We introduce a method to mesh the boundary Γ of a smooth, open domain in immersed in a mesh of tetrahedra. The mesh follows by mapping a specific collection of triangular faces in the mesh to Γ. Two types of surface meshes follow: (a) a mesh that exactly meshes Γ, and (b) meshes that approximate Γ to any order, by interpolating the map over the selected faces; that is, an isoparametric approximation to Γ. The map we use to deform the faces is the closest point projection to Γ. We formulate conditions for the closest point projection to define a homeomorphism between each face and its image. These are conditions on some of the tetrahedra intersected by the boundary, and they essentially state that each such tetrahedron should (a) have a small enough diameter, and (b) have two of its dihedral angles be acute. We provide explicit upper bounds on the mesh size, and these can be computed on the fly. We showcase the quality of the resulting meshes with several numerical examples. More importantly, all surfaces in these examples were meshed with a single background mesh. This is an important feature for problems in which the geometry evolves or changes, because it could be possible for the background mesh to never change as the geometry does. In this case, the background mesh would be a universal mesh 1 for all these geometries. We expect the method introduced here to be the basis for the construction of universal meshes for domains in three dimensions. Copyright © 2016 John Wiley & Sons, Ltd.     

Node placement for triangular mesh generation by Monte Carlo simulation

A new approach of node placement for unstructured mesh generation is proposed. It is based on the Monte Carlo method to position nodes for triangular or tetrahedral meshes. Surface or volume geometries to be meshed are treated as atomic systems, and mesh nodes are considered as interacting particles. By minimizing system potential energy with Monte Carlo simulation, particles are placed into a near‐optimal configuration. Well‐shaped triangles or tetrahedra can then be created after connecting the nodes by constrained Delaunay triangulation or tetrahedrization. The algorithm is simple, easy to implement, and works in an almost identical way for 2D and 3D meshing. Copyright © 2005 John Wiley & Sons, Ltd.     

Q‐Morph: an indirect approach to advancing front quad meshing

Q‐Morph is a new algorithm for generating all‐quadrilateral meshes on bounded three‐dimensional surfaces. After first triangulating the surface, the triangles are systematically transformed to create an all‐quadrilateral mesh. An advancing front algorithm determines the sequence of triangle transformations. Quadrilaterals are formed by using existing edges in the triangulation, by inserting additional nodes, or by performing local transformations to the triangles. A method typically used for recovering the boundary of a Delaunay mesh is used on interior triangles to recover quadrilateral edges. Any number of triangles may be merged to form a single quadrilateral. Topological clean‐up and smoothing are used to improve final element quality. Q‐Morph generates well‐aligned rows of quadrilaterals parallel to the boundary of the domain while maintaining a limited number of irregular internal nodes. The proposed method also offers the advantage of avoiding expensive intersection calculations commonly associated with advancing front procedures. A series of examples of Q‐Morph meshes are also presented to demonstrate the versatility of the proposed method. Copyright © 1999 John Wiley & Sons, Ltd.     

Reduced order mesh optimisation using proper orthogonal decomposition and a modified cuckoo search

A new mesh optimisation scheme, reduced order mesh optimisation, is introduced. The technique uses proper orthogonal decomposition to reduce the number of dimensions in a mesh optimisation problem. This reduction in dimensionality allows the expression of the optimisation problem globally rather than the more traditional local mesh optimisation or smoothing algorithms. To perform the optimisation, the recently developed gradient‐free technique modified cuckoo search is applied. The effectiveness of the algorithm is shown by considering the problem of optimising meshes for use in co‐volume techniques. Co‐volume techniques require the existence of two mutually orthogonal meshes; this is achieved by utilising the Delaunay–Voronoi dual. A combination of considering the problem globally and the use of a gradient‐free technique results in a scheme that significantly outperforms previous methods in solving this particular problem. Although the examples presented in this paper are specific to optimising dual meshes, the technique is general and can be simply modified to any mesh optimisation problem. Copyright © 2012 John Wiley & Sons, Ltd.     

Universal meshes: A method for triangulating planar curved domains immersed in nonconforming meshes

We introduce a new method to triangulate planar, curved domains that transforms a specific collection of triangles in a background mesh to conform to the boundary. In the process, no new vertices are introduced, and connectivities of triangles are left unaltered. The method relies on a novel way of parameterizing an immersed boundary over a collection of nearby edges with its closest point projection. To guarantee its robustness, we require that the domain be C²‐regular, the background mesh be sufficiently refined near the boundary, and that specific angles in triangles near the boundary be strictly acute. The method can render both straight‐edged and curvilinear triangulations for the immersed domain. The latter includes curved triangles that conform exactly to the immersed boundary, and ones constructed with isoparametric mappings to interpolate the boundary at select points. High‐order finite elements constructed over these curved triangles achieve optimal accuracy, which has customarily proven difficult in numerical schemes that adopt nonconforming meshes. Aside from serving as a quick and simple tool for meshing planar curved domains with complex shapes, the method provides significant advantages for simulating problems with moving boundaries and in numerical schemes that require iterating over the geometry of domains. With no conformity requirements, the same background mesh can be adopted to triangulate a large family of domains immersed in it, including ones realized over several updates during the coarse of simulating problems with moving boundaries. We term such a background mesh as a universal mesh for the family of domains it can be used to triangulate. Universal meshes hence facilitate a framework for finite element calculations over evolving domains while using only fixed background meshes. Furthermore, because the evolving geometry can be approximated with any desired order, numerical solutions can be computed with high‐order accuracy. We present demonstrative examples using universal meshes to simulate the interaction of rigid bodies with Stokesian fluids. Copyright © 2014 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.     

An adaptive level set method based on two‐level uniform meshes and its application to dislocation dynamics

In this paper, we present an adaptive level set method for motion of high codimensional objects (e.g., curves in three dimensions). This method uses only two (or a few fixed) levels of meshes. A uniform coarse mesh is defined over the whole computational domain. Any coarse mesh cell that contains the moving object is further divided into a uniform fine mesh. The coarse‐to‐fine ratios in the mesh refinement can be adjusted to achieve optimal efficiency. Refinement and coarsening (removing the fine mesh within a coarse grid cell) are performed dynamically during the evolution. In this adaptive method, the computation is localized mostly near the moving objects; thus, the computational cost is significantly reduced compared with the uniform mesh over the whole domain with the same resolution. In this method, the level set equations can be solved on these uniform meshes of different levels directly using standard high‐order numerical methods. This method is examined by numerical examples of moving curves and applications to dislocation dynamics simulations. This two‐level adaptive method also provides a basis for using locally varying time stepping to further reduce the computational cost. Copyright © 2013 John Wiley & Sons, Ltd.     

3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.