Inserting a surface into an existing unstructured mesh

In this work, a new method for inserting a surface as an internal boundary into an existing unstructured tetrahedral mesh is developed. The surface is discretized by initially placing vertices on its bounding curves, defining a length scale at every location on each boundary curve based on the local underlying mesh, and equidistributing length scale along these curves between vertices. The surface is then sampled based on this boundary discretization, resulting in a surface mesh spaced in a way that is consistent with the initial mesh. The new points are then inserted into the mesh, and local refinement is performed, resulting in a final mesh containing a representation of the surface while preserving mesh quality. The advantage of this algorithm over generating a new mesh from scratch is in allowing for the majority of existing simulation data to be preserved and not have to be interpolated onto the new mesh. This algorithm is demonstrated in two and three dimensions on problems with and without intersections with existing internal boundaries. Copyright © 2015 John Wiley & Sons, Ltd.     

Improvement of PUFEM for the numerical solution of high‐frequency elastic wave scattering on unstructured triangular mesh grids

The purpose of this paper, which builds on previous work (Int. J. Numer. Meth. Engng 2009; 77 :1646–1669), is to improve a numerical scheme based on the partition of unity finite element method (PUFEM) for the solution of the time harmonic elastic wave equations. The approach consists to approximate the displacement field by the standard finite element shape functions, enriched locally by superimposing pressure (P) and shear (S) plane waves. The aim is to accurately model two‐dimensional elastic wave problems on relatively coarse mesh grids, capable of containing many wavelengths per nodal spacing, for wide ranges of frequencies. This allows us to relax the traditional requirement of about 10 nodal points per S wavelength. In this work, an exact integration scheme for the linear triangular finite element is developed to evaluate the oscillatory integrals arising from the use of the PUFEM. The main contribution here consists in developing an explicit closed‐form solution for two‐dimensional wave‐based integrals, when the phase variation is linear in the local coordinate element system. The evaluation of the element mass matrix is performed from appropriate edge integrals. All other element matrices, obtained by adequate splitting of the element stress tensor matrix, are simply deduced from the element mass matrix entries. The results show clearly that the proposed integration scheme evaluates accurately the entries of the global matrix with drastic reduction of the computational time. Numerical tests dealing with the scattering of S elastic plane waves by a circular rigid body show that, for the same discretization level, it is possible to improve the accuracy by using large elements associated with high numbers of approximating plane waves rather than using small elements with less plane waves. However, this increases the conditioning and the fill‐in of the global matrix. At high frequency, it is even possible to push the number of degrees of freedom per S wavelength under 2 and still achieve good accuracy. Finally, some remarks on the choice of the numbers of P and S plane waves leading to better accuracy and conditioning are discussed. Copyright © 2010 John Wiley & Sons, Ltd.     

P1‐conservative solution interpolation on unstructured triangular meshes

This paper presents an interpolation operator on unstructured triangular meshes that verifies the properties of mass conservation, P ¹‐exactness (order 2), and maximum principle. This operator is important for the resolution of the conservation laws in computational fluid dynamics by means of mesh adaptation methods as the conservation properties are not verified throughout the computation. Indeed, the mass preservation can be crucial for the simulation accuracy. The conservation properties are achieved by local mesh intersection and quadrature formulae. Derivatives reconstruction are used to obtain an order 2 method. Algorithmically, our goal is to design a method that is robust and efficient. The robustness is mandatory to apply the operator to highly anisotropic meshes. The efficiency will permit the extension of the method to dimension 3. Several numerical examples are presented to illustrate the efficiency of the approach. Copyright © 2010 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.     

Automatic sizing functions for unstructured surface mesh generation

Accurate sizing functions are crucial for efficient generation of high‐quality meshes, but to define the sizing function is often the bottleneck in complicated mesh generation tasks because of the tedious user interaction involved. We present a novel algorithm to automatically create high‐quality sizing functions for surface mesh generation. First, the tessellation of a Computer Aided Design (CAD) model is taken as the background mesh, in which an initial sizing function is defined by considering geometrical factors and user‐specified parameters. Then, a convex nonlinear programming problem is formulated and solved efficiently to obtain a smoothed sizing function that corresponds to a mesh satisfying necessary gradient constraint conditions and containing a significantly reduced element number. Finally, this sizing function is applied in an advancing front mesher. With the aid of a walk‐through algorithm, an efficient sizing‐value query scheme is developed. Meshing experiments of some very complicated geometry models are presented to demonstrate that the proposed sizing‐function approach enables accurate and fully automatic surface mesh generation. Copyright © 2016 John Wiley & Sons, Ltd.     

Recovery of an arbitrary edge on an existing surface mesh using local mesh modifications

This study describes an algorithm for recovering an edge which is arbitrarily inserted onto a pre‐triangulated surface mesh. The recovery process does not rely on the parametric space of the surface mesh provided by the geometric modeller. The topological and geometrical validity of the surface mesh is preserved through the entire recovery process. The ability of inserting and recovering an arbitrary edge onto a surface mesh can be an invaluable tool for a number of meshing applications such as boundary layer mesh generation, solution adaptation, preserving the surface conformity, and possibly as a primary tool for mesh generation. The edge recovery algorithm utilizes local surface mesh modification operations of edge swapping, collapsing and splitting. The mesh modification operations are decided by the results of pure geometrical checks such as point and line projections onto faces and face‐line intersections. The accuracy of these checks on the recovery process are investigated and the substantiated precautions are devised and discussed in this study. Copyright © 2001 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.     

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.     

Improving multigrid performance for unstructured mesh drift–diffusion simulations on 147,000 cores

This study considers the scaling of three algebraic multigrid aggregation schemes for a finite element discretization of a drift–diffusion system, specifically the drift–diffusion model for semiconductor devices. The approach is more general and can be applied to other systems of partial differential equations. After discretization on unstructured meshes, a fully coupled multigrid preconditioned Newton–Krylov solution method is employed. The choice of aggregation scheme for generating coarser levels has a significant impact on the performance and scalability of the multigrid preconditioner. For the test cases considered, the uncoupled aggregation scheme, which aggregates/combines the immediate neighbors, followed by repartitioning and data redistribution for the coarser level matrices on a subset of the Message Passing Interface (MPI) processes, outperformed the two other approaches, including the baseline aggressive coarsening scheme. Scaling results are presented up to 147,456 cores on an IBM Blue Gene/P platform. A comparison of the scaling of a multigrid V‐cycle and W‐cycle is provided. Results for 65,536 cores demonstrate that a factor of 3.5 × reduction in time between the uncoupled aggregation and baseline aggressive coarsening scheme can be obtained by significantly reducing the iteration count due to the increased number of multigrid levels and the generation of better quality aggregates. Copyright © 2012 John Wiley & Sons, Ltd.     

A multigrid accelerated hybrid unstructured mesh method for 3D compressible turbulent flow

 A cell vertex finite volume method for the solution of steady compressible turbulent flow problems on unstructured hybrid meshes of tetrahedra, prisms, pyramids and hexahedra is described. These hybrid meshes are constructed by firstly discretising the computational domain using tetrahedral elements and then by merging certain tetrahedra. A one equation turbulence model is employed and the solution of the steady flow equations is obtained by explicit relaxation. The solution process is accelerated by the addition of a multigrid method, in which the coarse meshes are generated by agglomeration, and by parallelisation. The approach is shown to be effective for the simulation of a number of 3D flows of current practical interest. Sponsored by The Research Council of Norway, project number 125676/410 Dedicated to the memory of Prof. Mike Crisfield, a respected colleague     

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.     

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.     

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.     

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.     

Optimization of a regularized distortion measure to generate curved high‐order unstructured tetrahedral meshes

We present a robust method for generating high‐order nodal tetrahedral curved meshes. The approach consists of modifying an initial linear mesh by first, introducing high‐order nodes, second, displacing the boundary nodes to ensure that they are on the computer‐aided design surface, and third, smoothing and untangling the mesh obtained after the displacement of the boundary nodes to produce a valid curved high‐order mesh. The smoothing algorithm is based on the optimization of a regularized measure of the mesh distortion relative to the original linear mesh. This means that whenever possible, the resulting mesh preserves the geometrical features of the initial linear mesh such as shape, stretching, and size. We present several examples to illustrate the performance of the proposed algorithm. Furthermore, the examples show that the implementation of the optimization problem is robust and capable of handling situations in which the mesh before optimization contains a large number of invalid elements. We consider cases with polynomial approximations up to degree ten, large deformations of the curved boundaries, concave boundaries, and highly stretched boundary layer elements. The meshes obtained are suitable for high‐order finite element analyses. Copyright © 2015 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.     

Metric-driven mesh optimization using a local simulated annealing algorithm

We report on results obtained with a metric-driven mesh optimization procedure for simplicial meshes based on the simulated annealing (SA) method. The use of SA improves the chances of removing pathological clusters of bad elements, that have the tendency to lock into frozen configurations in difficult regions of the model such as corners and complex face intersections, prejudicing the overall quality of the final grid. A local version of the algorithm is developed that significantly lowers the computational cost. Numerical examples illustrate the effectiveness of the proposed methodology, which is compared to a classical greedy Gauss–Seidel optimization. Substantial improvement in the quality of the worst elements of the grid is observed for the local simulated annealing optimization. Furthermore, the method appears to be robust to the choice of the algorithmic parameters. Copyright © 2006 John Wiley & Sons, Ltd.     

Simultaneous surface and tetrahedron mesh adaptation using mesh‐free techniques

We present a method to adapt a tetrahedron mesh together with a surface mesh with respect to a size criterion. The originality of our work lies in the fact that both surface and tetrahedron mesh adaptation are carried out simultaneously and that no CAD is required to adapt the surface mesh. The adaptation procedure consists of splitting or removing interior and surface edges which violate a given size criterion. The enrichment process is based on a bisection technique. In order to guarantee mesh conformity during the refinement process, all possible remeshing configurations of tetrahedra have been examined. Once the tetrahedron mesh has been adapted, surface nodes are projected on a geometrical model. The building of a surface model from discrete data has already been presented in this journal. The method is based on a mesh‐free technique called Hermite Diffuse Interpolation. Surface and volume mesh optimization procedures are carried out during the adaptation and at the end of the process to enhance the mesh. Copyright © 2003 John Wiley & Sons, Ltd.