Automatic construction of non‐obtuse boundary and/or interface Delaunay triangulations for control volume methods

A Delaunay mesh without triangles having obtuse angles opposite to boundary and interface edges (obtuse boundary/interface triangles) is the basic requirement for problems solved using the control volume method. In this paper we discuss postprocess algorithms that allow the elimination of obtuse boundary/interface triangles of any constrained Delaunay triangulation with minimum angle ε. This is performed by the Delaunay insertion of a finite number of boundary and/or interface points. Techniques for the elimination of two kinds of obtuse boundary/interface triangles are discussed in detail: 1‐edge obtuse triangles, which have a boundary/interface (constrained) longest edge; and 2‐edge obtuse triangles, which have both their longest and second longest edge over the boundary/interface. More complex patterns of obtuse boundary/interface triangles, namely chains of 2‐edge constrained triangles forming a saw diagram and clusters of triangles that have constrained edges sharing a common vertex are managed by using a generalization of the above techniques. Examples of the use of these techniques for semiconductor device applications and a discussion on their generalization to 3‐dimensions (3D) are also included. Copyright © 2002 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.     

Delaunay versus max-min solid angle triangulations for three-dimensional mesh generation

The Delaunay triangulation has been used in several methods for generating finite element tetrahedral meshes in three-dimensional polyhedral regions. Other types of three-dimensional triangulations are possible, such as a triangulation satisfying a local max-min solid angle criterion. In this paper, we present experimental results to show that max-min solid angle triangulations are better than Delaunay triangulations for finite element tetrahedral meshes, since the former type of triangulations contains tetrahedra of better shape than the latter type. We also describe how mesh points are generated and triangulated in our tetrahedral mesh generation method.     

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.     

Local maximum‐entropy approximation schemes: a seamless bridge between finite elements and meshfree methods

We present a one‐parameter family of approximation schemes, which we refer to as local maximum‐entropy approximation schemes, that bridges continuously two important limits: Delaunay triangulation and maximum‐entropy (max‐ent) statistical inference. Local max‐ent approximation schemes represent a compromise—in the sense of Pareto optimality—between the competing objectives of unbiased statistical inference from the nodal data and the definition of local shape functions of least width. Local max‐ent approximation schemes are entirely defined by the node set and the domain of analysis, and the shape functions are positive, interpolate affine functions exactly, and have a weak Kronecker‐delta property at the boundary. Local max‐ent approximation may be regarded as a regularization, or thermalization, of Delaunay triangulation which effectively resolves the degenerate cases resulting from the lack or uniqueness of the triangulation. Local max‐ent approximation schemes can be taken as a convenient basis for the numerical solution of PDEs in the style of meshfree Galerkin methods. In test cases characterized by smooth solutions we find that the accuracy of local max‐ent approximation schemes is vastly superior to that of finite elements. Copyright © 2005 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.     

3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

Triangulation of cubic panorama for view synthesis

An unstructured triangulation approach, new to our knowledge, is proposed to apply triangular meshes for representing and rendering a scene on a cubic panorama (CP). It sophisticatedly converts a complicated three-dimensional triangulation into a simple three-step triangulation. First, a two-dimensional Delaunay triangulation is individually carried out on each face. Second, an improved polygonal triangulation is implemented in the intermediate regions of each of two faces. Third, a cobweblike triangulation is designed for the remaining intermediate regions after unfolding four faces to the top/bottom face. Since the last two steps well solve the boundary problem arising from cube edges, the triangulation with irregular-distribution feature points is implemented in a CP as a whole. The triangular meshes can be warped from multiple reference CPs onto an arbitrary viewpoint by face-to-face homography transformations. The experiments indicate that the proposed triangulation approach provides a good modeling for the scene with photorealistic rendered CPs.     

Mesh generation/refinement using fractal concepts and iterated function systems

A novel method of mesh generation is proposed which is based on the use of fractal concepts to derive contractive, affine transformations. The transformations are constructed in such a manner that the attractors of the resulting maps are a union of the points, lines and surfaces in the domain. In particular, the mesh nodes may be generated recursively as a sequence of points which are obtained by applying the transformations to a coarse background mesh constructed from the given boundary data. A Delaunay triangulation or similar edge connection approach can then be performed on the resulting set of nodes in order to generate the mesh. Local refinement of an existing mesh can also be performed using the procedure. The method is easily extended to three dimensions, in which case the Delaunay triangulation is replaced by an analogous 3-D tesselation.     

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.     

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

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

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.     

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.     

Parameterization of planar curves immersed in triangulations with application to finite elements

We construct a method for the parameterization of a class of planar piecewise C²‐curves over a collection of edges in an ambient triangulation. The map from the collection of edges to the curve is the closest‐point projection. A distinguishing feature of the method is that edges in the ambient triangulation need not interpolate the curve. We formulate conditions on the ambient triangulations so that the resulting parameterization over its selected edges is (i) bijective, (ii) maps simple, connected collection of edges to simple, connected components of the curve, and (iii) is C¹ within each edge of the collection. These properties of the parameterization make it particularly useful in the construction of high‐order finite element approximation spaces on planar curves immersed in triangulations. We discuss this application and illustrate it with numerical examples. The parameterization method applies to a large class of planar curves, including most ones of interest in engineering and computer graphics applications, and to a large family of triangulations, including acute‐angled triangulations. Copyright © 2011 John Wiley & Sons, Ltd.     

A duality‐based method for generating geometric representations of polycrystals

We present a method, which we have termed Relaxed Dual Complex (RDC), for generating geometric representations and computational models of polycrystals of arbitrary shape. The RDC method combines a first topological step, which defines an initial unrelaxed polycrystal geometry as the barycentric dual of an input triangulation of the solid, and a second relaxation step, in which the grain boundaries are relaxed by means of a gradient flow driven by grain boundary energy. The RDC method applies to arbitrary solids defined by means of a triangulation and, in this manner, it couples seamlessly to standard solid modelling engines. An additional appealing feature of the RDC method is that it generates a conforming tetrahedral mesh of the polycrystal that can be used as a basis for subsequent simulations. The RDC method also affords some control over the statistical properties of the polycrystal, including grain size, which provides a convenient device for matching experimental statistical data. The range, versatility, and performance of the RDC method have been demonstrated by means of selected examples. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

A new reliability evaluation method for networks with imperfect vertices using BDD

As an efficient data structure for representation and manipulation of Boolean functions, binary decision diagrams (BDDs) have been applied to network reliability analysis. However, most of the existing BDD methods on network reliability analysis have assumed perfectly reliable vertices, which is often not true for real‐world networks where the vertices can fail because of factors such as limited resources (eg, power and memory) or harsh operating environments. Extensions have been made to the existing BDD methods (particularly, edge expansion diagram and boundary set–based methods) to address imperfect vertices. But these extended methods have various constraints leading to problems in accuracy or space efficiency. To overcome these constraints, in this paper, we propose a new BDD‐based algorithm called ordered BDD dependency test for K‐terminal network reliability analysis considering both edge and vertex failures. Based on a newly defined concept “dependency set”, the proposed algorithm can accurately compute the reliability of networks with imperfect vertices. In addition, the proposed algorithm has no restrictions on the starting vertex for the BDD model construction. Comprehensive examples and experiments are provided to show effectiveness of the proposed approach.