A parallel mesh generation algorithm based on the vertex label assignment scheme

In this article a new mesh generation algorithm is presented. The algorithm is based on a new approach called the vertex label assignment scheme to provide the information for the mesh generation so that parallel processing becomes possible. The algorithm generates 2D meshes of quadrilaterals on the basis of individual faces; conformity and smoothness of the resultant mesh are automatically assured. Local and selective mesh-refinements are also supported. A regular quadrilateral network which defines the geometry of the problem and an associated subdivision level assignment which specifies mesh density data on the network are the only input information.     

Insertion of triangulated surfaces into a meccano tetrahedral discretization by means of mesh refinement and optimization procedures

In this paper, we present a new method for inserting several triangulated surfaces into an existing tetrahedral mesh generated by the meccano method. The result is a conformal mesh where each inserted surface is approximated by a set of faces of the final tetrahedral mesh. First, the tetrahedral mesh is refined around the inserted surfaces to capture their geometric features. Second, each immersed surface is approximated by a set of faces from the tetrahedral mesh. Third, following a novel approach, the nodes of the approximated surfaces are mapped to the corresponding immersed surface. Fourth, we untangle and smooth the mesh by optimizing a regularized shape distortion measure for tetrahedral elements in which we move all the nodes of the mesh, restricting the movement of the edge and surface nodes along the corresponding entity they belong to. The refining process allows approximating the immersed surface for any initial meccano tetrahedral mesh. Moreover, the proposed projection method avoids computational expensive geometric projections. Finally, the applied simultaneous untangling and smoothing process delivers a high‐quality mesh and ensures that the immersed surfaces are interpolated. Several examples are presented to assess the properties of the proposed method.     

Automatic merging of tetrahedral meshes

A generic algorithm is proposed to merge arbitrary solid tetrahedral meshes automatically into one single valid finite element mesh. The intersection segments in the form of distinct nonoverlapping loops between the boundary surfaces of the given solid objects are determined by the robust neighbor tracing technique. Each intersected triangle on the boundary surface will be triangulated to incorporate the intersection segments onto the boundary surface of the objects. The tetrahedra on the boundary surface associated with the intersected triangular facets are each divided into as many tetrahedra as the number of subtriangles on the triangulated facet. There is a natural partition of the boundary surfaces of the solid objects by the intersection loops into a number of zones. Volumes of intersection can now be identified by collected bounding surfaces from the surface patches of the partition. Whereas mesh compatibility has already been established on the boundary of the solid objects, mesh compatibility has yet to be restored on the bounding surfaces of the regions of intersection. Tetrahedra intersected by the cut surfaces are removed, and new tetrahedra can be generated to fill the volumes bounded by the cut surfaces and the portion of cavity boundary connected to the cut surfaces to restore mesh compatibility at the cut surfaces. Upon restoring compatibility on the bounding surfaces of the regions of intersection, the objects are ready to be merged together as all regions of intersection can be detached freely from the objects. All operations, besides the determination of intersections structurally in the form of loops, are virtually topological, and no parameter and tolerance is needed in the entire merging process. Examples are presented to show the steps and the details of the mesh merging procedure. Copyright © 2012 John Wiley & Sons, Ltd.     

Tool design problems in a punch press flexible manufacturing system

In this paper, we study tool design problems encountered in using a punch press Flexible Manufacturing System (FMS) for producing flat sheet-metal parts. We consider the problem of designing the minimum number of tools needed to punch a given set of holes in the parts. Holes described by a single attribute as well as two attributes are considered. We model the tool design problems as graph theoretic problems. Such an approach is believed to be new for the problem studied. We have made the following major contributions: First, we show that the two-attribute tool design problem is equivalent to the minimum clique cover problem on the intersection graph of rectangles, which is a well known NP-complete problem. Second, we develop a fast algorithm to construct a set-covering formulation from the underlying graph model. In addition, we show that our approach has applications beyond the tool design problem (e.g., location problems).     

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.     

Initialization of high‐order accuracy immersed interface CFD solvers using complex CAD geometry

This study concerns the development of a numerical methodology for initializing immersed interface‐based CFD solvers for using complex computer‐aided design (CAD) geometry. CFD solvers with higher‐order discretization stencils require larger stencil widths, which become problematic in regions of space where insufficient mesh resolution is available. This problem becomes especially challenging when convoluted triangulated surface meshes generated from complex solid models are used to initialize the cut‐cells. A pragmatic balance between desired local geometry resolution and numerical accuracy is often required to find a practical solution. Here, a robust iterative fill algorithm is presented that balances geometry resolution with numerical accuracy (via stencil size). Several examples are presented to illustrate the use of this initialization procedure that employs both the original CAD generated triangulated surface mesh, along with a level set representation of the surface to initialize cut‐cells and boundary proximity measures for creation of CFD stencils. Convergence error analysis of surface area and enclosed volumes is first presented to show the effects of fill on the geometry as a function of desired stencil size and grid resolution. The algorithm is then applied to geometrically complex problems using large eddy simulation. Two problems are considered. The first is flow around the Eiffel Tower. The second is a combustion swirler in the context of a design problem. Copyright © 2016 John Wiley & Sons, Ltd.     

COMBINATION OF ADAPTIVITY AND MESH SMOOTHING FOR THE FINITE ELEMENT ANALYSIS OF SHELLS WITH INTERSECTIONS

A compatible hierarchical adaptive scheme is proposed which allows to control both density and geometrical properties of meshes with four-node linear finite shell elements. The algorithm produces a sequence of meshes with two aims, nearly equal distribution of the local error in each element and a mesh with regular elements, thus internal element angles near 90° and length ratios of adjacent element sides near unity. This goal is achieved in an efficient manner imposing a combination of a local smoothing algorithm with the adaptive mesh generation. New created nodes are positioned on the real shell surface and shell boundaries which may be given e.g. by CAD data. Also the shell directors are determined from the normals on the real geometry. Shell intersections are detected automatically as common curves of two adjacent shell parts. As a shell continuum cannot be assumed for these intersections and thus simple standard adaptive schemes fail, shell intersections have to be treated in a way similar to shell boundaries. For some numerical examples the developed algorithms are demonstrated and the resulting meshes are shown. © 1997 by John Wiley & Sons, Ltd.     

Interface handling for three‐dimensional higher‐order XFEM‐computations in fluid–structure interaction

Three‐dimensional higher‐order eXtended finite element method (XFEM)‐computations still pose challenging computational geometry problems especially for moving interfaces. This paper provides a method for the localization of a higher‐order interface finite element (FE) mesh in an underlying three‐dimensional higher‐order FE mesh. Additionally, it demonstrates, how a subtetrahedralization of an intersected element can be obtained, which preserves the possibly curved interface and allows therefore exact numerical integration. The proposed interface algorithm collects initially a set of possibly intersecting elements by comparing their ‘eXtended axis‐aligned bounding boxes’. The intersection method is applied to a highly reduced number of intersection candidates. The resulting linearized interface is used as input for an elementwise constrained Delaunay tetrahedralization, which computes an appropriate subdivision for each intersected element. The curved interface is recovered from the linearized interface in the last step. The output comprises triangular integration cells representing the interface and tetrahedral integration cells for each intersected element. Application of the interface algorithm currently concentrates on fluid–structure interaction problems on low‐order and higher‐order FE meshes, which may be composed of any arbitrary element types such as hexahedra, tetrahedra, wedges, etc. Nevertheless, other XFEM‐problems with explicitly given interfaces or discontinuities may be tackled in addition. Multiple structures and interfaces per intersected element can be handled without any additional difficulties. Several parallelization strategies exist depending on the desired domain decomposition approach. Numerical test cases including various geometrical exceptions demonstrate the accuracy, robustness and efficiency of the interface handling. Copyright © 2009 John Wiley & Sons, Ltd.     

A simple and efficient algorithm of automatic mesh generation for a general plate and frame structure with holes

The creation of the geometry for a general plate and frame structure with holes is discussed, and a simple and efficient algorithm of the mesh generation of the structure is presented for structural and thermal analysis. Mainly quadrilateral elements are generated and triangular elements are partially used in transient regions on the surface of the structure. For the frame parts of the structure, beam elements are generated for structural analysis and bar elements for conduction, convection and radiation for thermal analysis compatible with adjacent plate elements. A simple method to generate nodes at arbitrary point of the structure is also described.Numerical examples are given to demonstrate the effectiveness of the method on PC.     

On curvature element‐size control in metric surface mesh generation

A new procedure is suggested for controlling the element‐size distribution of surface meshes during automatic adaptive surface mesh generation. In order to ensure that the geometry of the surface can be accurately captured, the curvature properties of the surface are first analysed. Based on the principal curvatures and principal directions of the surface, the curvature element‐size requirement is defined in the form of a metric tensor field. This element‐size controlling metric tensor field, which can either be isotopic or anisotopic depending on the user requirement, is then employed to control the element size distribution during mesh generation. The suggested procedure is local, adaptive and can be easily used with many parametric surface mesh generators. As the proposed scheme defines the curvature element‐size requirement in an implicit manner, it can be combined with any other user defined element size specification using the standard metric intersection procedure. This eventually leads to a simple implementation procedure and a high computational efficiency. Numerical examples indicate that the new procedure can effectively control the element size of surfacemeshes in the cost of very little additional computational effort. Copyright © 2001 John Wiley & Sons, Ltd.     

A polygonal finite element method for modeling arbitrary interfaces in large deformation problems

In this paper, a polygonal-FEM technique is presented in modeling of arbitrary interfaces in large deformations. The method is used to model the internal interfaces and arbitrary geometries using a uniform non-conformal mesh. The technique is applied to capture discontinuous deformations in the non-conformal elements, which are cut by the interface in a uniform regular mesh. In this approach, a uniform non-conformal mesh is decomposed into sub-elements that conform to the internal interfaces. The geometry of interface is used to produce various triangular, quadrilateral and pentagonal elements at the intersection of interface with regular FE mesh, in which the extra degrees-of-freedom are defined along the interface. The level set method is employed to describe the material geometry on the background mesh. The technique is used to extrude any arbitrary geometry from an initial background mesh and model under different external effects. An important feature of the technique is the decomposition of the uniform non-conformal mesh to the polygonal-FEM mesh, which is conformed to the material interfaces. Finally, several numerical examples are analyzed to demonstrate the efficiency of proposed technique in modeling arbitrary interfaces in large deformations.     

Delaunay triangulation of non-convex planar domains

This paper investigates the possibility of integrating the two currently most popular mesh generation techniques, namely the method of advancing front and the Delaunay triangulation algorithm. The merits of the resulting scheme are its simplicity, efficiency and versatility. With the introduction of ‘non-Delaunay’ line segments, the concept of using Delaunay triangulation as a means of mesh generation is clarified. An efficient algorithm is proposed for the construction of Delaunay triangulations over non-convex planar domains. Interior nodes are first generated within the planar domain. These interior nodes and the boundary nodes are then linked up together to produce a valid triangulation. In the mesh generation process, the Delaunay property of each triangle is ensured by selecting a node having the smallest associated circumcircle. In contrast to convex domains, intersection between the proposed triangle and the domain boundary has to be checked; this can be simply done by considering only the ‘non-Delaunay’ segments on the generation front. Through the study of numerous examples of various characteristics, it is found that high-quality triangular element meshes are obtained by the proposed algorithm, and the mesh generation time bears a linear relationship with the number of elements/nodes of the triangulation.     

The boundary recovery and sliver elimination algorithms of three‐dimensional constrained Delaunay triangulation

A boundary recovery and sliver elimination algorithm of the three‐dimensional constrained Delaunay triangulation is proposed for finite element mesh generation. The boundary recovery algorithm includes two main procedures: geometrical recovery procedure and topological recovery procedure. Combining the advantages of the edges/faces swappings algorithm and edges/faces splittings algorithm presented respectively by George and Weatherill, the geometrical recovery procedure can recover the missing boundaries and guarantee the geometry conformity by introducing fewer Steiner points. The topological recovery procedure includes two phases: ‘dressing wound’ and smoothing, which will overcome topology inconsistency between 3D domain boundary triangles and the volume mesh. In order to solve the problem of sliver elements in the three‐dimensional Delaunay triangulation, a method named sliver decomposition is proposed. By extending the algorithm proposed by Canvendish, the presented method deals with sliver elements by using local decomposition or mergence operation. In this way, sliver elements could be eliminated thoroughly and the mesh quality could be improved in great deal. Copyright © 2006 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.     

An efficient integration technique for the voxel‐based finite cell method

The finite cell method is a fictitious domain approach based on hierarchical Ansatz spaces of higher order. The method avoids time‐consuming and often error‐prone mesh‐generation and favorably exploits Cartesian grids to embed structures of complex geometry in a simple‐shaped computational domain thus shifting parts of the computational effort from mesh generation to the computation within the embedding finite cells of regular shape. This paper presents an effective integration approach for voxel‐based models of linear elasticity that drastically reduces the computational effort on cell level. The applied strategy allows the pre‐computation of an essential part of the cell matrices and vectors of higher order, representing stiffness and load, respectively. Several benchmark problems show the potential of the proposed method in particular for heterogeneous material properties as common in biomedical applications based on computer tomography scans. The applied strategy ensures a fast computation for time‐critical simulations and even allows user‐interactive simulations for models of moderate size at a high level of accuracy. Copyright © 2012 John Wiley & Sons, Ltd.     

Three‐dimensional brittle fracture: configurational‐force‐driven crack propagation

This paper presents a computational framework for quasi‐static brittle fracture in three‐dimensional solids. The paper sets out the theoretical basis for determining the initiation and direction of propagating cracks based on the concept of configurational mechanics, consistent with Griffith's theory. Resolution of the propagating crack by the FEM is achieved by restricting cracks to element faces and adapting the mesh to align it with the predicted crack direction. A local mesh improvement procedure is developed to maximise mesh quality in order to improve both accuracy and solution robustness and to remove the influence of the initial mesh on the direction of propagating cracks. An arc‐length control technique is derived to enable the dissipative load path to be traced. A hierarchical hp‐refinement strategy is implemented in order to improve both the approximation of displacements and crack geometry. The performance of this modelling approach is demonstrated on two numerical examples that qualitatively illustrate its ability to predict complex crack paths. All problems are three‐dimensional, including a torsion problem that results in the accurate prediction of a doubly‐curved crack. Copyright © 2013 John Wiley & Sons, Ltd.     

Aspects of three-dimensional constrained Delaunay meshing

Presented in this paper are the theoretical aspects of node addition to a non-convex, multiboundary mesh of tetrahedral elements as used in finite element modelling. The method used is derived from Watson¹ and Shenton and Cendes² and is extended to deal with node addition on inter-material boundaries. Several situations are identified that result in an illegal insertion polyhedron (IP), these could be caused by the ‘constrained’ nature of the mesh, adjacent objects with different material properties, or degenerate node configurations. A new Delaunay algorithm is described that checks for illegal cases of the IP and then corrects them, this checking relies on the consistent ordering of the element nodes. It is shown that a particular type of illegal IP can easily be identified and corrected using this technique. The Delaunay algorithm is then applied to automatic mesh generation, and modification to the basic Delaunay algorithm is described so that previously meshed edges and faces of the current object being meshed are not deleted during the addition of subsequent nodes. This ‘protection’ method only becomes viable by recognizing the node ordering sense of the IP faces.     

Surface triangulation over intersecting geometries

A method for the rapid construction of meshes over intersecting triangulated shapes is described. The method is based on an algorithm that automatically generates a surface mesh from intersecting triangulated surfaces by means of Boolean intersection/union operations. After the intersection of individual components is obtained, the exposed surface parts are extracted. The algorithm is intended for rapid interactive construction of non‐trivial surfaces in engineering design, manufacturing, visualization and molecular modelling applications. Techniques to make the method fast and general are described. The proposed algorithm is demonstrated on a number of examples, including intersections of multiple spheres, planes and general engineering shapes, as well as generation of surface and volume meshes around clusters of intersecting components followed by the computation of flow field parameters. Copyright © 1999 John Wiley & Sons, Ltd.     

A parallel implicit/explicit hybrid time domain method for computational electromagnetics

The numerical solution of Maxwell's curl equations in the time domain is achieved by combining an unstructured mesh finite element algorithm with a cartesian finite difference method. The practical problem area selected to illustrate the application of the approach is the simulation of three‐dimensional electromagnetic wave scattering. The scattering obstacle and the free space region immediately adjacent to it are discretized using an unstructured mesh of linear tetrahedral elements. The remainder of the computational domain is filled with a regular cartesian mesh. These two meshes are overlapped to create a hybrid mesh for the numerical solution. On the cartesian mesh, an explicit finite difference method is adopted and an implicit/explicit finite element formulation is employed on the unstructured mesh. This approach ensures that computational efficiency is maintained if, for any reason, the generated unstructured mesh contains elements of a size much smaller than that required for accurate wave propagation. A perfectly matched layer is added at the artificial far field boundary, created by the truncation of the physical domain prior to the numerical solution. The complete solution approach is parallelized, to enable large‐scale simulations to be effectively performed. Examples are included to demonstrate the numerical performance that can be achieved. Copyright © 2009 John Wiley & Sons, Ltd.