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.     

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.     

THE WHISKER WEAVING ALGORITHM: A CONNECTIVITY-BASED METHOD FOR CONSTRUCTING ALL-HEXAHEDRAL FINITE ELEMENT MESHES

This paper introduces a new algorithm called whisker weaving for constructing unstructured, all-hexahedral finite element meshes. Whisker weaving is based on the Spatial Twist Continuum (STC), a global interpretation of the geometric dual of an all-hexahedral mesh. Whisker weaving begins with a closed, all-quadrilateral surface mesh bounding a solid geometry, then constructs hexahedral element connectivity advancing into the solid. The result of the whisker weaving algorithm is a complete representation of hex mesh connectivity only: Actual mesh node locations are determined afterwards. The basic step of whisker weaving is to form a hexahedral element by crossing or intersecting dual entities. This operation, combined with seaming or joining operations in dual space, is sufficient to mesh simple block problems. When meshing more complex geometries, certain other dual entities appear such as blind chords, merged sheets, and self-intersecting chords. Occasionally specific types of invalid connectivity arise. These are detected by a general method based on repeated STC edges. This leads into a strategy for resolving some cases of invalidities immediately. The whisker weaving implementation has so far been successful at generating meshes for simple block-type geometries and for some non-block geometries. Mesh sizes are currently limited to a few hundred elements. While the size and complexity of meshes generated by whisker weaving are currently limited, the algorithm shows promise for extension to much more general problems.     

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.     

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.     

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.     

A normal offsetting technique for automatic mesh generation in three dimensions

A technique, based on a normal offsetting procedure, for the fully automatic generation of meshes suitable for finite element analysis in three dimensions is presented. The method is completely automatic, requiring no user intervention in the process and no special modelling procedures. The method is applied to three-dimensional solid geometries. The procedure positions nodes in the interior domain of an object by offsetting an initial set of nodes on the object boundary along vectors normal to the boundary to define a layer of new interior point locations. The offset points are processed to ensure good nodal spacing appropriate for generating well-shaped elements. Following processing, the offset points become a new boundary surrounding the remaining unmeshed region in the interior of the geometric domain. The offsetting procedure is applied again to this new boundary layer to form another offset layer farther into the domain interior. The offset-process-offset cycle is repeated until the entire region is filled with nodes. Tetrahedral elements are then formed by triangulation of the 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. Calculation of nodal locations are based on local parameters avoiding the higher-order time complexities associated with global calculations.     

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 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.     

Automatic generation of anisotropic quadrilateral meshes on three‐dimensional surfaces using metric specifications

A new algorithm for constructing full quadrilateral anisotropic meshes on 3D surfaces is proposed in this paper. The proposed method is based on the advancing front and the systemic merging techniques. Full quadrilateral meshes are constructed by systemically converting triangular elements in the background meshes into quadrilateral elements.By using the metric specifications to describe the element characteristics, the proposed algorithm is applicable to convert both isotropic and anisotropic triangular meshes into full quadrilateral meshes. Special techniques for generating anisotropic quadrilaterals such as new selection criteria of base segment for merging, new approaches for the modifications of the background mesh and construction of quadrilateral elements, are investigated and proposed in this study. Since the final quadrilateral mesh is constructed from a background triangular mesh and the merging procedure is carried out in the parametric space, the mesh generator is robust and no expensive geometrical computation that is commonly associated with direct quadrilateral mesh generation schemes is needed. Copyright © 2002 John Wiley & Sons, Ltd.     

A general advancing front technique for filling space with arbitrary objects

An advancing front space‐filling technique for arbitrary objects has been developed. The input required consists of the specification of the desired mean point distance in space and an initial triangulation of the surface. One object at a time is removed from the active front, and, if possible, surrounded by admissible new objects. This operation is repeated until no active objects are left. Two techniques to obtain maximum packing are discussed: closest object placement (during generation) and move/enlarge (after generation). Different deposition or layering patterns can be achieved by selecting the order in which objects are eliminated from the active front. Timings show that for simple objects like spheres the scheme is considerably faster than volume mesh generators based on the advancing front technique, making it possible to generate large (> 10⁶) yet optimal clouds of points in a matter of minutes on a PC. For more general objects, the performance may degrade depending on the complexity of the penetration checks. Several examples are included that demonstrate the capabilities of the technique. Copyright © 2004 John Wiley & Sons, Ltd.     

Automatic and efficient hybrid viscous mesh generation based on clipped Voronoi diagrams

The commonly used advancing layers method to generate hybrid meshes suffers from many drawbacks. The generation of isotropic meshes for far-field domains with irregular and complex boundary subdivisions after boundary layers advancing is time consuming and, in some cases, is not robust in 3D. To address these difficulties, this paper presents a novel method to generate hybrid polygonal meshes in 2D and polyhedral meshes in 3D for viscous flow simulations. In the proposed method, first, we generate a full Voronoi diagram for the appropriate distribution of generators that avoids the extra mesh generation required for the remaining holes in the advancing layers method. To recover the inner solid boundaries, we implement a robust boundary cell cutting process. Because the generators are located layer by layer near the boundaries, there is no requirement to consider all of the Voronoi cells. Only the first layer Voronoi cells must be cut, making the calculation very efficient. We have generated hybrid meshes using the present method for many viscous flow cases. The results show close agreement between the computations and the experimental results, thus indicating the reliability and effectiveness of the hybrid mesh generated by our method.     

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.     

One machine,one minute,three billion tetrahedra

This paper presents a new scalable parallelization scheme to generate the 3D Delaunay triangulation of a given set of points. Our first contribution is an efficient serial implementation of the incremental Delaunay insertion algorithm. A simple dedicated data structure, an efficient sorting of the points, and the optimization of the insertion algorithm have permitted to accelerate reference implementations by a factor three. Our second contribution is a multithreaded version of the Delaunay kernel that is able to concurrently insert vertices. Moore curve coordinates are used to partition the point set, avoiding heavy synchronization overheads. Conflicts are managed by modifying the partitions with a simple rescaling of the space-filling curve. The performances of our implementation have been measured on three different processors: an Intel core-i7, an Intel Xeon Phi, and an AMD EPYC, on which we have been able to compute three billion tetrahedra in 53 seconds. This corresponds to a generation rate of over 55 million tetrahedra per second. We finally show how this very efficient parallel Delaunay triangulation can be integrated in a Delaunay refinement mesh generator, which takes as input the triangulated surface boundary of the volume to mesh.     

UNSTRUCTURED GRID GENERATION AND A SIMPLE TRIANGULATION ALGORITHM FOR ARBITRARY 2-D GEOMETRIES USING OBJECT ORIENTED PROGRAMMING

This paper describes the logic of a dynamic algorithm for a general 2D Delaunay triangulation of arbitrarily prescribed interior and boundary nodes. The complexity of the geometry is completely arbitrary. The scheme is free of specific restrictions on the input of the geometrical data. The scheme generates triangles whose associated circumcircles contain no nodal points except their vertices. There is no predefined limit for the number of points and the boundaries. The direction of generation of the triangles cannot be determined a priori as opposed to the moving front techniques. An automatic node placement scheme reflecting the initial boundary point spacings is used. The successive refinement scheme results in such a point distribution that the triangulation algorithm need not perform any geometric intersection check for overlapped triangles and penetrated boundaries. Further computational saving is provided by using a special binary tree (ADT) in which the points are ordered such that contiguous points in the list are neighbours in physical space. The method consists of a set of simple rules to understand. The dynamic nature of the Object Oriented Programming (OOP) of the algorithms provides efficient memory management on the insertion, deletion and searching processes. The computational effort bears a linear relation-ship between the CPU time and the total number of nodes. Some of the existing methods in the literature regarding triangular mesh generation are discussed in context. © 1997 by John Wiley & Sons, Ltd.     

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

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

LayTracks: a new approach to automated geometry adaptive quadrilateral mesh generation using medial axis transform

A new mesh generation algorithm called ‘LayTracks’, to automatically generate an all quad mesh that is adapted to the variation of geometric feature size in the domain is described. LayTracks combines the merits of two popular direct techniques for quadrilateral mesh generation—quad meshing by decomposition and advancing front quad meshing. While the MAT has been used for the domain decomposition before, this is the first attempt to use the MAT, for the robust subdivision of a complex domain into a well defined sub‐domain called ‘Tracks’, for terminating the advancing front of the mesh elements without complex interference checks and to use radius function for providing sizing function for adaptive meshing. The process of subdivision of a domain is analogous to, formation of railway tracks by laying rails on the ground. Each rail starts from a node on the boundary and propagates towards the medial axis (MA) and then from the MA towards the boundary. Quadrilateral elements are then obtained by placing nodes on these rails and connecting them inside each track, formed by adjacent rails. The algorithm has been implemented and tested on some typical geometries and the quality of the output mesh obtained are presented. Extension of this technique to all hexahedral meshing is discussed. Copyright © 2004 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.     

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.