Automatic generation of multiblock decompositions of surfaces

Multiblock‐structured meshes have significant advantages over fully unstructured meshes in numerical simulation, but automatically generating these meshes is considerably more difficult. A method is described herein for automatically generating high‐quality multiblock decompositions of surfaces with boundaries. Controllability and flexibility are useful capabilities of the method. Additional alignment constraints for forcing the appearance of particular features in the decomposition can be easily handled. Also, adjustments are made according to input metric tensor fields that describe target element size properties. The general solution strategy is based around using a four‐way symmetry vector‐field, called a cross‐field, to describe the local mesh orientation on a triangulation of the surface. Initialisation is performed by propagating the boundary alignment constraints to the interior in a fast marching method. This is similar in a way to an advancing‐front or paving method but much more straightforward and flexible because mesh connectivity does not have to be managed in the cross‐field. Multiblock decompositions are generated by tracing the separatrices of the cross‐field to partition the surface into quadrilateral blocks with square corners. The final task of meshing the decomposition requires solving an integer programming problem for block division numbers. 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.     

Hierarchical tree‐based finite element mesh generation

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

Towards automatic structured multiblock mesh generation using improved transfinite interpolation

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

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

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

Unified fluid–structure interpolation and mesh motion using radial basis functions

A multivariate interpolation scheme, using radial basis functions, is presented, which results in a completely unified formulation for the fluid–structure interpolation and mesh motion problems. The method has several significant advantages. Primarily, all volume mesh, structural mesh, and flow‐solver type dependence is removed, and all operations are performed on totally arbitrary point clouds of any form. Hence, all connectivity and user‐input requirements are removed from the computational fluid dynamics–computational structural dynamics (CFD–CSD) coupling problem, as only point clouds are required to determine the coupling. Also, it may equally well be applied to structured and unstructured grids, or structural and aerodynamic grids that intersect, again because no connectivity information is required. Furthermore, no expensive computations are required during an unsteady simulation, just matrix–vector multiplications, since the required dependence relations are computed only once prior to any simulation and then remain constant. This property means that the method is both perfectly parallel, since only the data relevant to each structured block or unstructured partition are required to move those points, and totally independent from the flow solver. Hence, a completely generic ‘black box’ tool can be developed, which is ideal for use in an optimization approach. Aeroelastic behaviour of the Brite–Euram MDO wing is analysed in terms of both static deflection and dynamic responses, and it is demonstrated that responses are strongly dependent on the exact CFD–CSD interpolation used. Mesh quality is also examined during the motion resulting from a large surface deformation. Global grid quality is shown to be preserved well, with local grid orthogonality also being maintained well, particularly at and near the moving surface, where the original orthogonality is retained. Copyright © 2007 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.     

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.     

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.     

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.     

Higher‐resolution convection schemes for flow in porous media on highly distorted unstructured grids

Higher‐resolution schemes are presented for convective flow approximation on highly distorted unstructured grids. The schemes are coupled with continuous full‐tensor Darcy‐flux approximations. A sequence of non‐uniform and distorted grid formulations are developed and compared for a range of unstructured meshes with variable grid spacing. The higher‐order schemes are constructed using non‐uniform grid slope limiters such that they are stable with a local maximum principle, ensuring that solutions are free of spurious oscillations. Benefits of the resulting schemes are demonstrated for classical test problems in reservoir simulation including cases with full‐tensor permeability fields. The test cases involve a range of unstructured grids with variations in grid spacing, orientation and permeability that lead to flow fields that are poorly resolved by standard simulation methods. The higher‐order formulations are shown to effectively reduce numerical diffusion, leading to improved resolution of concentration and saturation fronts. Copyright © 2008 John Wiley & Sons, Ltd.     

Variational generation of prismatic boundary‐layer meshes for biomedical computing

Boundary‐layer meshes are important for numerical simulations in computational fluid dynamics, including computational biofluid dynamics of air flow in lungs and blood flow in hearts. Generating boundary‐layer meshes is challenging for complex biological geometries. In this paper, we propose a novel technique for generating prismatic boundary‐layer meshes for such complex geometries. Our method computes a feature size of the geometry, adapts the surface mesh based on the feature size, and then generates the prismatic layers by propagating the triangulated surface using the face‐offsetting method. We derive a new variational method to optimize the prismatic layers to improve the triangle shapes and edge orthogonality of the prismatic elements and also introduce simple and effective measures to guarantee the validity of the mesh. Coupled with a high‐quality tetrahedral mesh generator for the interior of the domain, our method generates high‐quality hybrid meshes for accurate and efficient numerical simulations. We present comparative study to demonstrate the robustness and quality of our method for complex biomedical geometries. Copyright © 2009 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.     

Implicit boundary method for finite element analysis using non‐conforming mesh or grid

In the finite element method (FEM), a mesh is used for representing the geometry of the analysis and for representing the test and trial functions by piece‐wise interpolation. Recently, analysis techniques that use structured grids have been developed to avoid the need for a conforming mesh. The boundaries of the analysis domain are represented using implicit equations while a structured grid is used to interpolate functions. Such a method for analysis using structured grids is presented here in which the analysis domain is constructed by Boolean combination of step functions. Implicit equations of the boundary are used in the construction of trial and test functions such that essential boundary conditions are guaranteed to be satisfied. Furthermore, these functions are constructed such that internal elements, through which no boundary passes, have the same stiffness matrix. This approach has been applied to solve linear elastostatic problems and the results are compared with analytical and finite element analysis solutions to show that the method gives solutions that are similar to the FEM in quality but is less computationally expensive for dense mesh/grid and avoids the need for a conforming mesh. Copyright © 2007 John Wiley & Sons, Ltd.     

Mesh objective continuum damage models for ductile fracture

During machining processes, the work piece material is subjected to high deformation rates, increased temperature, large plastic deformations, damage evolution and fracture. In this context the Johnson‐Cook failure model is often used even though it exhibits pathological mesh size dependence. To remove the mesh size sensitivity, a set of mesh objective damage models is proposed based on a local continuum damage formulation combined with the concept of a scalar damage phase field. The first model represents a mesh objective augmentation of the well‐established element removal model, whereas the second one degrades the continuum stress in a smooth fashion. Plane strain plate and hat specimens are used in the finite element simulations, with the restriction to the temperature and rate independent cases. To investigate the influence of mesh distortion, a structured and an unstructured meshes were used for the respective specimen. For structured meshes, the results clearly show that the pathological mesh size sensitivity is removed for both models. When considering unstructured meshes, the mesh size sensitivity is more complex as revealed by the considered hat‐specimen shear test. Nevertheless, the present work indicates that the proposed models can predict realistic ductile failure behaviors in a mesh objective fashion. Copyright © 2015 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.     

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

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

Fully automatic two dimensional mesh generation using normal offsetting

A technique, based on a normal offsetting procedure, for the fully automatic generation of two dimensional meshes suitable for finite element analysis is presented. The method positions nodes by first meshing the geometric entities that compose the object boundary, then offsetting those nodal locations along vectors normal to the boundary geometry. The offset row of nodes is processed to ensure a good nodal spacing appropriate for generating well shaped elements. Following processing, the new row is offset again and the cycle is repeated until the entire area is filled with nodes. The boundary based technique ensures good quality element shapes for analysis in critical boundary regions and facilitates applications involving integration of mesh generation with design geometry databases. Nodal locations are calculated based on local parameters avoiding the higher order time complexities associated with global calculations. A technique for controlling mesh density by overlaying an independent mesh density function on the geometry is also presented as part of the method. This approach allows mesh density to be automatically controlled by a variety of factors, such as previous analysis results, that are external to the actual mesh generation process. The independent nature of the function method allows different sources of density information to be used interchangeably without modification to the mesh generation procedure.     

An embedded mesh method for treating overlapping finite element meshes

A new technique for treating the mechanical interactions of overlapping finite element meshes is presented. Such methods can be useful for numerous applications, for example, fluid–solid interaction with a superposed meshed solid on an Eulerian background fluid grid. In this work, we consider the interaction of two elastic domains: one mesh is the foreground and defines the surface of interaction, the other is a background mesh and is often a structured grid. Many of the previously proposed methods employ surface defined Lagrange multipliers or penalties to enforce the boundary constraints. It has become apparent that these methods will cause mesh locking under certain conditions. Appropriately applied, the Nitsche method can overcome this locking, but, in its canonical form, is generally not applicable to non‐linear materials such as hyperelastics. The relationship between interior point penalty, discontinuous Galerkin and Nitsche's method is well known. Based on this relationship, a nonlinear theory analogous to the Nitsche method is proposed to treat nonlinear materials in an embedded mesh. Here, a discontinuous Galerkin derivative based on a lifting of the interface surface integrals provides a consistent treatment for non‐linear materials and demonstrates good behavior in example problems. Published 2012. This article is a US Government work and is in the public domain in the USA.     

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.