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.     

An indirect approach for automatic generation of quadrilateral meshes with arbitrary line constraints

A new approach to the automatic generation of a quadrilateral mesh with arbitrary line constraints is proposed in this paper. It is an indirect all‐quad mesh generation and presented in the following steps: (1) discretizing the constrained lines within the domain; (2) converting the above domain to a triangular mesh together with the line constraints; (3) transforming the generated triangular mesh with line constraints to an all‐quad mesh through performing an advancing front algorithm from the line constraints, which enables the construction of quadrilaterals layer by layer, and roughly keeps the feature of the initial triangular mesh; (4) optimizing the topology of the quadrilateral mesh to reduce the number of irregular nodes; (5) smoothing the generated mesh toward high‐quality all‐quad mesh generation. Finally, a few application examples are given to demonstrate the reliability and usefulness of the proposed algorithm. Copyright © 2011 John Wiley & Sons, Ltd.     

Unconstrained plastering—Hexahedral mesh generation via advancing‐front geometry decomposition

The generation of all‐hexahedral finite element meshes has been an area of ongoing research for the past two decades and remains an open problem. Unconstrained plastering is a new method for generating all‐hexahedral finite element meshes on arbitrary volumetric geometries. Starting from an unmeshed volume boundary, unconstrained plastering generates the interior mesh topology without the constraints of a pre‐defined boundary mesh. Using advancing fronts, unconstrained plastering forms partially defined hexahedral dual sheets by decomposing the geometry into simple shapes, each of which can be meshed with simple meshing primitives. By breaking from the tradition of previous advancing‐front algorithms, which start from pre‐meshed boundary surfaces, unconstrained plastering demonstrates that for the tested geometries, high quality, boundary aligned, orientation insensitive, all‐hexahedral meshes can be generated automatically without pre‐meshing the boundary. Examples are given for meshes from both solid mechanics and geotechnical applications. Copyright © 2009 John Wiley & Sons, Ltd.     

Automatic metric 3D surface mesh generation using subdivision surface geometrical model. Part 2: Mesh generation algorithm and examples

In this paper, a new metric advancing front surface mesh generation scheme is suggested. This new surface mesh generator is based on a new geometrical model employing the interpolating subdivision surface concept. The target surfaces to be meshed are represented implicitly by interpolating subdivision surfaces which allow the presence of various sharp and discontinuous features in the underlying geometrical model. While the main generation steps of the new generator are based on a robust metric surface triangulation kernel developed previously, a number of specially designed algorithms are developed in order to combine the existing metric advancing front algorithm with the new geometrical model. As a result, the application areas of the new mesh generator are largely extended and can be used to handle problems involving extensive changes in domain geometry. Numerical experience indicates that, by using the proposed mesh generation scheme, high quality surface meshes with rapid varying element size and anisotropic characteristics can be generated in a short time by using a low‐end PC. Finally, by using the pseudo‐curvature element‐size controlling metric to impose the curvature element‐size requirement in an implicit manner, the new mesh generation procedure can also generate finite element meshes with high fidelity to approximate the target surfaces accurately. Copyright © 2003 John Wiley & Sons, Ltd.     

A new finite point generation scheme using metric specifications

A new approach to generate finite point meshes on 2D flat surface and any bi‐variate parametric surfaces is suggested. It can be used to generate boundary‐conforming anisotropic point meshes with node spacing compatible with the metric specifications defined in a background point mesh. In contrast to many automatic mesh generation schemes, the advancing front concept is abandoned in the present method. A few simple basic operations including boundary offsetting, node insertion and node deletion are used instead. The point mesh generation schemeis initialized by a boundary offsetting procedure. The point mesh quality is then improved by node insertion and deletion such that optimally spaced nodes will fill up the entire problem domain. In addition to the point mesh generation scheme, a new way to define the connectivity of a point mesh is also suggested. Furthermore, based on the connectivity information, a new scheme to perform smoothing for a point mesh is proposed toimprove the node spacing quality of the mesh. Timing shows thatdue to the simple node insertion and deletion operations, the generation speed of the new scheme is nearly 10 times faster than a similar advancing front mesh generator. Copyright © 2000 John Wiley & Sons, Ltd.     

Anisotropic tetrahedral meshing via bubble packing and advancing front

This paper presents a new computational method for anisotropic tetrahedral meshing. The method can control element anisotropy based on a specified 3×3 tensor field defined over a volumetric domain. Our method creates a tetrahedral mesh in two steps: (1) placing nodes at the centres of tightly packed ellipsoidal cells, called bubbles, in the domain, and (2) connecting the nodes by a modified advancing front followed by local transformation. The method creates a high‐quality anisotropic mesh that conforms well to a specified tensor field. Copyright © 2003 John Wiley & Sons, Ltd.     

Localized remeshing techniques for three‐dimensional metal forming simulations with linear tetrahedral elements

The localized remeshing technique for three‐dimensional metal forming simulations is proposed based on a mixed finite element formulation with linear tetrahedral elements in the present study. The numerical algorithm to generate linear tetrahedral elements is developed for finite element analyses using the advancing front technique with local optimization method which keeps the advancing fronts smooth. The surface mesh generation using mesh manipulations of the boundary elements of the old mesh system was made to improve mesh quality of the boundary surface elements, resulting in reduction of volume change in forming simulations. The mesh quality generated was compared with that obtained from the commercial CAD package for the complex geometry like lumbar. The simulation results of backward extrusion and bevel gear and spider forgings indicate that the currently developed simulation technique with the localized remeshing can be used effectively to simulate the three‐dimensional forming processes with a reduced computation time. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

On advancing front mesh generation in three dimensions

This paper deals with some aspects of unstructured mesh generation in three dimensions by the advancing front technique. In particular, the parameters used in the algorithm are characterized, and strategies that may be used to improve robustness are suggested. We also describe a method whereby structured tetrahedral meshes with exceptionally stretched elements adjacent to boundary surfaces may be produced. The suggested method can be combined with the advancing front concept in a natural way.     

Fully‐automated hex‐dominant mesh generation with directionality control via packing rectangular solid cells

A new fully automatic hex‐dominant mesh generation technique of an arbitrary 3D geometric domain is presented herein. The proposed method generates a high‐quality hex‐dominant mesh by: (1) controlling the directionality of the output hex‐dominant mesh; and (2) avoiding ill‐shaped elements induced by nodes located too closely to each other. The proposed method takes a 3D geometric domain as input and creates a hex‐dominant mesh consisting mostly of hexahedral elements, with additional prism and tetrahedral elements. Rectangular solid cells are packed on the boundary of and inside the input domain to obtain ideal node locations for a hex‐dominant mesh. Each cell has a potential energy field that mimics a body‐centred cubic (BCC) structure (seen in natural substances such as NaCl) and the cells are moved to stable positions by a physically based simulation. The simulation mimics the formation of a crystal pattern so that the centres of the cells provide ideal node locations for a hex‐dominant mesh. Via the advancing front method, the centres of the packed cells are then connected to form a tetrahedral mesh, and this is converted to a hex‐dominant mesh by merging some of the tetrahedrons. Copyright © 2003 John Wiley & Sons, Ltd.     

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.     

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.     

Nodal grafting for crack propagation studies

A simple, efficient method for propagating cracks through a finite element mesh is presented: nodes, borrowed from other points in the mesh, are ‘grafted’ along the advancing crack front. The method requires neither an increase in bandwidth nor a mesh regeneration. It can be easily implemented in any existing program using iso(sub)parametric elements of at least quadratic order.     

An extended advancing front technique for closed surfaces mesh generation

An extended advancing front technique (AFT) with shift operations and Riemann metric named as shifting‐AFT is presented for finite element mesh generation on 3D surfaces, especially 3D closed surfaces. Riemann metric is used to govern the size and shape of the triangles in the parametric space. The shift operators are employed to insert a floating space between real space and parametric space during the 2D parametric space mesh generation. In the previous work of closed surface mesh generation, the virtual boundaries are adopted when mapping the closed surfaces into 2D open parametric domains. However, it may cause the mesh quality‐worsening problem. In order to overcome this problem, the AFT kernel is combined with the shift operator in this paper. The shifting‐AFT can generate high‐quality meshes and guarantee convergence in both open and closed surfaces. For the shifting‐AFT, it is not necessary to introduce virtual boundaries while meshing a closed surface; hence, the boundary discretization procedure is largely simplified, and moreover, better‐shaped triangles will be generated because there are no additional interior constraints yielded by virtual boundaries. Comparing with direct methods, the shifting‐AFT avoids costly and unstable 3D geometrical computations in the real space. Some examples presented in this paper have demonstrated the advantages of shift‐AFT in 3D surface mesh generation, especially for the closed surfaces. Copyright © 2007 John Wiley & Sons, Ltd.     

A new computational method for MAT of injected parts integrated in part modelling stage

In this paper we present a simple and fast approach for MAT generation in discrete form. It is used for manufacturability analysis in the part modelling stage of injected parts. The method is a volume thinning method based on straight skeleton computation, modified and applied in 3D on B-rep models in STL. The volume thinning of the B-rep model is based on its boundary surfaces offset towards the model interior. The surfaces’ offset is done with an adequately proposed offset distance which makes some of the non adjacent offset model surfaces overlap (they ‘meet’ in mid-surface or MAT). Offset surfaces are used to reconstruct the topology of a new B-rep model (offset model). Overlapping surfaces in the offset model are detected, separated and aggregated to MAT. For adequate MAT precision and adequate MAT radius function, we propose to treat B-rep model concave edges (vertices) as cylinders (spheres) of zero-radius and offset them in an adequate way. On these bases, we present an iterative algorithm in which MAT is constructed in an incremental way by consecutive volume thinning of the obtained offset models. MAT construction is finished when an empty offset model is obtained. An algorithm has been created and implemented in Visual C++. Some of the obtained results are presented in this paper.     

An adaptive remeshing procedure for discontinuous finite element limit analysis

An adaptive remeshing procedure is proposed for discontinuous finite element limit analysis. The procedure proceeds by iteratively adjusting the element sizes in the mesh to distribute local errors uniformly over the domain. To facilitate the redefinition of element sizes in the new mesh, the interelements discontinuous field of elemental bound gaps is converted into a continuous field, ie, the intensity of bound gap, using a patch‐based approximation technique. An analogous technique is subsequently used for the approximation of element sizes in the old mesh. With these information, an optimized distribution of element sizes in the new mesh is defined and then scaled to match the total number of elements specified for each iteration in the adaptive remeshing process. Finally, a new mesh is generated using the advancing front technique. This adaptive remeshing procedure is repeated several times until an optimal mesh is found. Additionally, for problems involving discontinuous boundary loads, a novel algorithm for the generation of fan‐type meshes around singular points is proposed explicitly and incorporated into the main adaptive remeshing procedure. To demonstrate the feasibility of our proposed method, some classical examples extracted from the existing literary works are studied in detail.     

Automatic three-dimensional finite element mesh generation via modified ray casting

Three-dimensional (3-D) finite element mesh generation has been the target of automation due to the complexities associated with generating and visualizing the mesh. A fully automatic 3-D mesh generation method is developed. The method is capable of meshing CSG solid models. It is based on modifying the classical ray-casting technique to meet the requirements of mesh generation. The modifications include the utilization of the element size in the casting process, the utilization of 3-D space box enclosures, and the casting of ray segments (rays with finite length). The method begins by casting ray segments into the solid. Based on the intersections between the segments and the solid boundary, the solid is discretized into cells arranged in a structure. The cell structure stores neighbourhood relations between its cells. Each cell is meshed with valid finite elements. Mesh continuity between cells is achieved via the neighbourhood relations. The last step is to process the boundary elements to represent closely the boundary. The method has been tested and applied to a number of solid models. Sample examples are presented.     

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.     

Tetrahedral mesh generation based on advancing front technique and optimization scheme

In recent years, demand for three‐dimensional simulations has continued to grow in the field of computer‐aided engineering. Especially, in the analysis of forming processes a fully automatic and robust mesh generator is necessary for handling complex geometries used in industry. For three‐dimensional analyses, tetrahedral elements are commonly used due to the advantage in dealing with such geometries. In this study, the advancing front technique has been implemented and modified using an optimization scheme. In this optimization scheme, the distortion metric determines ‘when and where’ to smooth, and serves as an objective function. As a result, the performance of the advancing front technique is improved in terms of mesh quality generated. Copyright © 2003 John Wiley & Sons, Ltd.