Graded tetrahedral finite element meshes

Vertices in the body centred cubic (bcc) lattice are used to create a tetrahedral spatial decomposition. With this spatial decomposition an octree approach is combined with Delaunay triangulations to decompose solids into tetrahedral finite element meshes. Solids must have their surfaces triangulated and the vertices in the triangulation are finite element nodes. Local densities of interior tetrahedra are controlled by the densities of surface triangles. Accuracy of the decomposition into finite elements depends on the accuracy of the surface triangulation which can be constructed with state of the art computer aided design systems.     

An approach to refining three-dimensional tetrahedral meshes based on Delaunay transformations

A technique for refining three-dimensional tetrahedral meshes is proposed in this paper. The proposed technique is capable of treating arbitrary unstructured tetrahedral meshes, convex or non-convex with multiple regions resulting in high quality constrained Delaunay triangulations. The tetrahedra generated are of high quality (nearly equilateral). Sliver tetrahedra, which present a real problem to many algorithms are not produced with the new method. The key to the generation of high quality tetrahedra is the iterative application of a set of topological transformations based on the Voronoi–Delaunay theory and a reposition of nodes technique. The computational requirements of the proposed technique are in linear relationship with the number of nodes and tetrahedra, making it ideal for direct employment in a fully automatic finite element analysis system for 3-D adaptive mesh refinement. Application to some test problems is presented to show the effectiveness and applicability of the new method.     

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.     

Variational Delaunay approach to the generation of tetrahedral finite element meshes

We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set à priori. The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty‐sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re‐formulate Delaunay triangulation as a linear programming problem. Copyright © 2001 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.     

Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions

A method using techniques of computational geometry for generating tetrahedral finite element meshes in three-dimensional polyhedral regions is presented. The input to the method consists of the boundary faces of the polyhedral region and possibly internal and hole interfaces, plus the desired number of tetrahedra and other scalar parameters. The region is decomposed into convex polyhedra in two stages so that tetrahedra of one length scale can be generated in each subregion. A mesh distribution function, which is either automatically constructed from the first-stage convex polyhedron decomposition or supplied by the user, is used to determine the tetrahedron sizes in the subregions. Then a boundary-constrained triangulation is constructed in each convex polyhedron, with local transformations being used to improve the quality of the tetrahedra. Experimental results from triangulations of three regions are provided.     

Numerical convergence of discrete exterior calculus on arbitrary surface meshes

Discrete exterior calculus (DEC) is a structure-preserving numerical framework for partial differential equations solution, particularly suitable for simplicial meshes. A longstanding and widespread assumption has been that DEC requires special (Delaunay) triangulations, which complicated the mesh generation process especially for curved surfaces. This paper presents numerical evidence demonstrating that this restriction is unnecessary. Convergence experiments are carried out for various physical problems using both Delaunay and non-Delaunay triangulations. Signed diagonal definition for the key DEC operator (Hodge star) is adopted. The errors converge as expected for all considered meshes and experiments. This relieves the DEC paradigm from unnecessary triangulation limitation.     

Comparison of four-point adding algorithms for Delaunay-type threedimensional mesh generators

Four different approaches to generating three-dimensional tetrahedral meshes were tested and compared in regard to the complexity and quality of the elements they produce as points are added into the existing coarse meshes. Points are added according to Delaunay triangulation. It was found that there is a marked difference between the different approaches and that the method suggested by D.F. Watson (1981) is the better one in terms of quality of the meshes generated, although its time complexity is a little higher than that of the other methods     

New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations

In this paper I introduce a new mathematical tool for dealing with the refinement and/or the improvement of unstructured triangulations: the Longest-Edge Propagation Path associated with each triangle to be either refined and/or improved in the mesh. This is defined as the (finite) ordered list of successive neighbour triangles having longest-edge greater than the longest edge of the preceding triangle in the path. This ideal is used to introduce two kinds of algorithms (which make use of a Backward Longest-Edge point insertion strategy): (1) a pure Backward Longest-Edge Refinement Algorithm that produces the same triangulations as previous longest-edge algorithms in a more efficient, direct and easy-to-implement way; (2) a new Backward Longest-Edge Improvement Algorithm for Delaunay triangulations, suitable to deal (in a reliable, robust and effective way) with the three important related aspects of the (triangular) mesh generation problem: mesh refinement, mesh improvement, and automatic generation of good-quality surface and volume triangulation of general geometries including small details. The algorithms and practical issues related with their implementation (both for the polygon and surface quality triangulation problems) are discussed in this paper. In particular, an effective boundary treatment technique is also discussed. The triangulations obtained with the LEPP–Delaunay algorithm have smallest angles greater than 30° and are, in practice, of optimal size. Furthermore, the LEPP–Delaunay algorithms naturally generalize to three-dimensions. © 1997 by John Wiley & Sons, Ltd.     

Algorithms for refining triangular grids suitable for adaptive and multigrid techniques

Two general algorithms for refining triangular computational meshes based on the bisection of triangles by the longest side are presented and discussed. The algorithms can be applied globally or locally for selective refinement of any conforming triangulation and always generate a new conforming triangulation after a finite number of interactions even when locally used. The algorithms also ensure that all angles in subsequent refined triangulations are greater than or equal to half the smallest angle in the original triangulation; the shape regularity of all triangles is maintained and the transition between small and large triangles is smooth in a natural way. Proofs of the above properties are presented. The second algorithm is a simpler, improved version of the first which retains most of the properties of the latter. The algorithms can be used either for constructing irregular computational meshes or for locally refining any given triangulation. In this sense they can be adequately combined with adaptive and/or multigrid techniques for solving finite element systems. Examples of the application of the algorithms are given and two possible generalizations are pointed out.     

Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints

A method is described which constructs three-dimensional unstructured tetrahedral meshes using the Delaunay triangulation criterion. Several automatic point creation techniques will be highlighted and an algorithm will be presented which can ensure that, given an initial surface triangulation which bounds a domain, a valid boundary conforming assembly of tetrahedra will be produced. Statistics of measures of grid quality are presented for several grids. The efficiency of the proposed procedure reduces the computer time for the generation of realistic unstructured tetrahedral grids to the order of minutes on workstations of modest computational capabilities.     

Accuracy of Galerkin finite elements for groundwater flow simulations in two and three‐dimensional triangulations

In standard finite element simulations of groundwater flow the correspondence between hydraulic head gradients and groundwater fluxes is represented by the stiffness matrix. In two‐dimensional problems the use of linear triangular elements on Delaunay triangulations guarantees a stiffness matrix of type M. This implies that the local numerical fluxes are physically consistent with Darcy's law. This condition is fundamental to avoid the occurrence of local maxima or minima, and is of crucial importance when the calculated flow field is used in contaminant transport simulations or pathline evaluation. In three spatial dimensions, the linear Galerkin approach on tetrahedra does not lead to M‐matrices even on Delaunay meshes. By interpretation of the Galerkin approach as a subdomain collocation scheme, we develop a new approach (OSC, orthogonal subdomain collocation) that is shown to produce M‐matrices in three‐dimensional Delaunay triangulations. In case of heterogeneous and anisotropic coefficients, extra mesh properties required for M‐stiffness matrices will also be discussed. Copyright © 2001 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation in convex primitives

This paper presents a method for generating tetrahedral meshes in three-dimensional primitives. Given a set of closed and convex polyhedra having non-zero volume and some mesh controlling parameters, the polyhedra are automatically split to tetrahedra satisfying the criteria of standard finite element meshes. The algorithm tries to generate elements close to regular tetrahedra by maximizing locally the minimum solid angles associated to a set of a few neighbouring tetrahedra. The input parameters define the size of the tetrahedra and they can be used to increase or decrease the discretization locally. All the new nodes, which are not needed to describe the geometry, are generated automatically.     

Automatic generation of transitional meshes

Advances in commercial computer‐aided design software have made finite element analysis with three‐dimensional solid finite elements routinely available. Since these analyses usually confine themselves to those geometrical objects for which particular CAD systems can produce finite element meshes, expanding the capability of analyses becomes an issue of expanding the capability of generating meshes. This paper presents a method for stitching together two three‐dimensional meshes with diverse elements that can include tetrahedral, pentahedral and hexahedral solid finite elements. The stitching produces a mesh that coincides with the edges which already exist on the portion of boundaries that will be joined. Moreover, the transitional mesh does not introduce new edges on these boundaries. Since the boundaries of the regions to be stitched together can have a mixture of triangles and quadrilaterals, tetrahedral and pyramidal elements provide the transitional elements required to honor these constraints. On these boundaries a pyramidal element shares its base face with the quadrilateral faces of hexahedra and pentahedra. Tetrahedral elements share a face with the triangles on the boundary. Tetrahedra populate the remaining interior of the transitional region. Copyright © 2001 John Wiley & Sons, Ltd.     

An apporach to automatic three-dimensional finite element mesh generation

Recently developed solid modelling systems for the design of complex physical solids using interactive computer graphics offer the exciting possibility of an integrated design/analysis system. Called geometric modellers, these systems build complex solids from primitive solids (cubes, cylinders, spheres, solid patches, etc.) and macro solids (combination of primitives)^{3, 4, 8, 16, 18, 25, 38}. To provide an effective structural analysis capability for these systems, methods must be devised to ease the burden of discretizing the solid geometry into a user controlled (usually locally graded) finite element mesh. The purpose of this paper is to describe an interactive solid mesh generation system capable of generating valid meshes of well-proportional tetrahedral finite elements for the decomposition of multiply connected solid structures. The system uses a semi-automatic node insertion procedure to locate element node points within and on the surface of a structure. An independent automatic three-dimensional triangulator then accepts these nodes as input and connects them to form a valid finite element mesh oftetrahedral elements. Although this report makes use of a modeller based on a constructive solid geometry representation (a so-called CSG modeller), the mesh generation strategy elaborated herein is completely general and makes no particular use of the CSG representation.     

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.     

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.     

Tetrahedral mesh generation using Delaunay refinement with non‐standard quality measures

This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non‐standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between 18^circ and 154^°. Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between 14^° and 154^° can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius‐to‐shortest‐edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above 20^°, regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

面向四面体网格生成的曲面Delaunay三角化算法

提出了一种曲面域Delaunay三角网格的直接构造算法。该算法在曲面网格剖分的边界递归算法和限定Delaunay四面体化算法的基础上,利用曲面采样点集的空间Delaunay四面体网格来辅助曲面三角网格的生成,曲面上的三角网格根据最小空球最小准则由辅助四面体网格中选取,每个三角形都满足三维Delaunay空球准则,网格质量有保证,并且极大的方便了进一步的曲面边界限定下的Delaunay四面体化的进行。