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.     

Selective refinement: A new strategy for automatic node placement in graded triangular meshes

Automating triangular finite element mesh generation involves two interrelated tasks: generatine a distribution of well-placed nodes on the boundary and in the interior of a domain, and constructing a triangulation of these nodes. For a given distribution of nodes, the Delaunay triangulation generally provides a suitable mesh, and Watson's algorithm²⁶ provides a flexible means of constructing it. In this paper, a new method is described for automating node placement in a Delaunay triangulation by seieclive refinement of an initial triangulation. Grading of the mesh is controlled by an explicit or implicit node spacing function. Although this paper describes the technique only in the planar context, the method generalizes to three dimensions as well.     

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.     

Node placement for triangular mesh generation by Monte Carlo simulation

A new approach of node placement for unstructured mesh generation is proposed. It is based on the Monte Carlo method to position nodes for triangular or tetrahedral meshes. Surface or volume geometries to be meshed are treated as atomic systems, and mesh nodes are considered as interacting particles. By minimizing system potential energy with Monte Carlo simulation, particles are placed into a near‐optimal configuration. Well‐shaped triangles or tetrahedra can then be created after connecting the nodes by constrained Delaunay triangulation or tetrahedrization. The algorithm is simple, easy to implement, and works in an almost identical way for 2D and 3D meshing. Copyright © 2005 John Wiley & Sons, Ltd.     

A two-step approach to finite element ordering

A two-step approach to finite element ordering is introduced. The scheme involves ordering of the finite elements first, based on their adjacency, followed by a local numbering of the nodal variables. The ordering of the elements is performed by the Cuthill-McKee algorithm. This approach takes into consideration the underlying structure of the finite element mesh, and may be regarded as a ‘natural’ finite element ordering scheme. The experimental results show that this two-step scheme is more efficient than the reverse Cuthill-McKee algorithm applied directly to the nodes, in terms of both execution time and the number of fill-in entries, particularly when higher order finite elements are used. In addition to its efficiency, the two-step approach increases modularity and flexibility in finite element programs, and possesses potential application to a number of finite element solution methods.     

THREE-DIMENSIONAL FINITE ELEMENT MESHING BY INCREMENTAL NODE INSERTION

This paper describes an efficient algorithm for fully automated three-dimensional finite element meshing which is applicable to non-convex geometry and non-manifold topology. This algorithm starts with sparsely placed nodes on the boundaries of a geometric model and a corresponding 3-D Delaunay triangulation. Nodes are then inserted incrementally by checking the tetrahedral mesh geometry and topological compatibility between Delaunay triangulation and the geometric model. Topological compatibility is checked in a robust manner by a method which relies more on a mesh's topology than its geometry. The node placement strategy is tightly coupled to an incremental Delaunay triangulation algorithm, and results in a low growth rate of computational time.     

Automatic quadrilateral/triangular free-form mesh generation for planar regions

Automation of finite element mesh generation holds great benefits for mechanical product development and analysis. In addition to freeing engineers from mundane tasks, automation of mesh generation reduces product cycle design and eliminates human-related errors. Most of the existing mesh generation methods are either semi-automatic or require specific topological information. A fully automatic free-form mesh generation method is described in this paper to alleviate some of these problems. The method is capable of meshing singly or multiply connected convex/concave planar regions. These regions can be viewed as crosssectional areas of 2 1/2 D objects analysed as plane stress, plane strain or axisymmetric stress problems. In addition to being fully automatic, the method produces quadrilateral or triangular elements with aspect rations near one. Moreover, it does not require any topological constraints on the regions to be meshed; i.e. it provides free-form mesh generation. The input to the method includes the region's boundary curves, the element size and the mesh grading information. The method begins by decomposing the planar region to be meshed into convex subregions. Each subregion is meshed by first generating nodes on its boundaries using the input element size. The boundary nodes are then offset to mesh the subregion. The resulting meshes are merged together to form the final mesh. The paper describes the method in detail, algorithms developed to implement it and sample numerical examples. Results on parametric studies of the method performance are also discussed.     

A hierarchical approach to automatic finite element mesh generation

A point-based two-stage hierarchical method for automatic finite element mesh generation from a solid model is presented. Given the solid model of a component and the required nodal density distribution, nodes are generated according to the hierarchy—vertex, edge, face and solid. At the vertices, nodes are established naturally. Nodes on the edges, faces and inside the solid model are generated by recursive subdivision. The nodes are then connected to form a valid and well-conditioned finite element mesh of tetrahedron elements using modified Delaunay Triangulation. Checks are conducted to ensure the compatibility of geometry and topology between the solid model and the mesh.     

三维泡泡布点方法及网格生成

本文研究如何在三维区域上生成高质量的节点集并基于节点集进行网格生成.根据区域边界的几何描述和理想间隔控制函数,先后对曲面及区域内部用泡泡布点法进行节点布置.节点布置结束后,对区域边界的节点集运用高质量点集的局部网格生成算法(BLMG)进行网格剖分,对区域内部的点集直接进行Delaunay三角剖分.通过计算节点集生成Delaunay网格单元的质量来评价区域节点集的质量.泡泡均匀分布与非均匀分布的算例均表明,该算法生成的节点具有较高的质量并且在泡泡非均匀分布时具有很好的渐进性.     

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.     

Converting an unstructured quadrilateral mesh to a standard T-spline surface

This paper presents a novel method for converting any unstructured quadrilateral mesh to a standard T-spline surface, which is C ²-continuous except for the local region around each extraordinary node. There are two stages in the algorithm: the topology stage and the geometry stage. In the topology stage, we take the input quadrilateral mesh as the initial T-mesh, design templates for each quadrilateral element type, and then standardize the T-mesh by inserting nodes. One of two sufficient conditions is derived to guarantee the generated T-mesh is gap-free around extraordinary nodes. To obtain a standard T-mesh, a second sufficient condition is provided to decide what T-mesh configuration yields a standard T-spline. These two sufficient conditions serve as a theoretical basis for our template development and T-mesh standardization. In the geometry stage, an efficient surface fitting technique is developed to improve the geometric accuracy. In addition, the surface continuity around extraordinary nodes can be improved by adjusting surrounding control nodes. The algorithm can also preserve sharp features in the input mesh, which are common in CAD (Computer Aided Design) models. Finally, a Bézier extraction technique is used to facilitate T-spline based isogeometric analysis. Several examples are tested to show the robustness of the algorithm.     

Automatic element reordering for finite element analysis with frontal solution schemes

This paper describes an element reordering algorithm which is suitable for use with a frontal solution package. The procedure is shown to generate efficient element numberings for a wide variety of test examples. In an effort to obtain an optimum elimination order, the algorithm first renumbers the nodes, and then uses this result to resequence the elements. This intermediate step is necessary because of the nature of the frontal solution procedure, which assembles variables on an element-by-element basis but eliminates them node by node. To renumber the nodes, a modified version of the King¹ algorithm is used. In order to minimize the number of nodal numbering schemes that need to be considered, the starting nodes are selected automatically by using some concepts from graph theory. Once the optimum numbering sequence has been ascertained, the elements are then reordered in an ascending sequence of their lowest-numbered nodes. This ensures that the new elimination order is preserved as closely as possible. For meshes that are composed of a single type of high-order element, it is only necessary to consider the vertex nodes in the renumbering process. This follows from the fact that mesh numberings which are optimal for low-order elements are also optimal for high-order elements. Significant economies in the reordering strategy may thus be achieved. A computer implementation of the algorithm, written in FORTRAN IV, is given.     

An alternative pseudoperipheral node finder for resequencing schemes

Many resequencing algorithms for reducing the bandwidth, profile and wavefront of sparse symmetric matrices have been published. In finite element applications, the sparsity of a matrix is related to the nodal ordering of the finite element mesh. Some of the most successful algorithms, which are based on graph theory, require a pair of starting pseudoperipheral nodes. These nodes, located at nearly maximal distance apart, are determined using heuristic schemes. This paper presents an alternative pseadoperipheral node finder, which is based on the algorithm developed by Gibbs, Poole and Stockmeyer. This modified scheme is suitable for nodal reordering of finite meshes and provides more consistency in the effective selection of the starting nodes in problems where the selection becomes arbitrary due to the number of candidates for these starting nodes. This case arises, in particular, for square meshes. The modified scheme was implemented in Gibbs-Poole-Stockmeyer, Gibbs-King and Sloan algorithms. Test problems of these modified algorithms include: (1) Everstine's 30 benchmark problems; (2) sets of square, rectangular and annular (cylindrical) finite element meshes with quadrilateral and triangular elements; and (3) additional examples originating from mesh refinement schemes. The results demonstrate that the modifications to the original algorithms contribute to the improvement of the reliability of all the resequencing algorithms tested herein for the nodal reordering of finite element meshes.     

Dynamic three dimensional computations for solids,with variable nodal connectivity for severe distortions

This paper presents a three dimensional algorithm for dynamic Lagrangian computations for solids, with variable nodal connectivity to allow for severe distortions. The nodes are analogous to flexible spheres. When they move closer together than their equilibrium distance they generate compressive, repulsive forces. Conversely, when they move apart, they generate tensile attractive forces. Material strength effects are also included. Because a node can be affected only by its ‘neighbour’ nodes, the approach has been designated the ‘NABOR’ approach. The distinguishing feature of this technique is that it is possible to have variable connectivity. A node can acquire new neighbours, thus allowing all forms of distortion. The three dimensional NABOR algorithm has been incorporated as an option into the explicit finite element code, EPIC-3. By using both the NABOR grid and the traditional EPIC-3 finite element grid together, it is possible to perform Lagrangian computations for a wider range of problems.     

Dynamic Lagrangian computations for solids,with variable nodal connectivity for severe distortions

This paper presents an algorithm for dynamic Lagrangian computations for solids, in plane strain geometry, with variable nodal connectivity to allow for severe distortions. The nodes are somewhat analogous to flexible circular disks. When they move closer together than their equilibrium distance they generate compressive, repulsive forces. Conversely, when they move apart, they generate tensile, attractive forces. Material strength effects are also included. Because a node can only be affected by its ‘neighbour’ nodes, the approach has been designated the ‘NABOR’ approach. The key to this approach is that it is possible to have variable nodal connectivity—a node can acquire new neighbours, thus allowing all forms of distortion. The NABOR algorithm has been incorporated as an option into the explicit finite element code, EPIC-2. By using both the NABOR grid and the EPIC-2 finite element grid together, it is possible to perform Lagrangian computations for a wide range of problems.     

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.     

Local error indicator in finite element analysis of Laplacian fields based on the green integration formula

The paper presents a simple and practical method for the local error assessment In the finite element solution of fields in linear media governed by the Laplace equation. The local error is estimated for each node or element of the mesh model by applying the Green integration formula, with the error distribution being used for the adaptive mesh refinement. Several alternatives of the local error estimation algorithm are compared and numerical examples are given for a typical ‘L’-section potential problem. These confirm the efficiency of the proposed method.     

Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations

The centroidal Voronoi tessellation based Delaunay triangulation (CVDT) provides an optimal distribution of generating points with respect to a given density function and accordingly generates a high‐quality mesh. In this paper, we discuss algorithms for the construction of the constrained CVDT from an initial Delaunay tetrahedral mesh of a three‐dimensional domain. By establishing an appropriate relationship between the density function and the specified sizing field and applying the Lloyd's iteration, the constrained CVDT mesh is obtained as a natural global optimization of the initial mesh. Simple local operations such as edges/faces flippings are also used to further improve the CVDT mesh. Several complex meshing examples and their element quality statistics are presented to demonstrate the effectiveness and efficiency of the proposed mesh generation and optimization method. Copyright © 2003 John Wiley & Sons, Ltd.     

‘Ultimate’ robustness in meshing an arbitrary polyhedron

Given a boundary surface mesh (a set of triangular facets) of a polyhedron, the problem of deciding whether or not a triangulation exists is reported to be NP‐hard. In this paper, an algorithm to triangulate a general polyhedron is presented which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning, and a final phase that makes it possible to remove the additional points defined in the previous step. Following this phase, the resulting mesh conforms to the given boundary surface mesh. The proposed method results in a discussion of theoretical interest about existence and complexity issues. In practice, however, the method should provide what we call ‘ultimate’ robustness in mesh generation methods. Copyright © 2003 John Wiley & Sons, Ltd.