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.     

Surface triangulation over intersecting geometries

A method for the rapid construction of meshes over intersecting triangulated shapes is described. The method is based on an algorithm that automatically generates a surface mesh from intersecting triangulated surfaces by means of Boolean intersection/union operations. After the intersection of individual components is obtained, the exposed surface parts are extracted. The algorithm is intended for rapid interactive construction of non‐trivial surfaces in engineering design, manufacturing, visualization and molecular modelling applications. Techniques to make the method fast and general are described. The proposed algorithm is demonstrated on a number of examples, including intersections of multiple spheres, planes and general engineering shapes, as well as generation of surface and volume meshes around clusters of intersecting components followed by the computation of flow field parameters. Copyright © 1999 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.     

Analysis of a triangulation based approach for specimen generation for discrete element simulations

Discrete element methods are emerging as useful numerical analysis tools for engineers concerned with granular materials such as soil, food grains, or pharmaceutical powders. Obviously, the first step in a discrete element simulation is the generation of the geometry of the system of interest. The system geometry is defined by the boundary conditions as well as the shape characteristics (including size) and initial coordinates of the particles in the system. While a variety of specimen generation methods for particulate materials have been developed, there is no uniform agreement on the optimum specimen generation approach. This paper proposes a new triangulation based approach that can easily be implemented in two or three dimensions. The concept of this approach (in two dimensions) is to triangulate a system of points within the domain of interest, creating a mesh of triangles. Then the particles are inserted as the incircles of these triangles. Extension to three dimensions using a mesh of tetrahedra and inserting the inspheres is relatively trivial. The major advantages of this approach include the relative simplicity of the algorithm and the small computational cost associated with the preparation of an initial particle assembly. The sensitivity of the characteristics of the particulate material that is generated to the topology of the triangular mesh used is explored. The approach is compared with other currently used methods in both two and three dimensions. These comparisons indicate that while this approach can successfully generate relatively dense two-dimensional particle assemblies, the three- dimensional implementation is less effective at generating dense systems than other available approaches. The research presented in this paper made use of software developed by other researchers. For the two-dimensional study the program Triangle developed by Jonathan Shewchuk was used. The three-dimensional analysis used the Geompack++ program developed by Barry Joe as well as an implementation of the Jodrey and Tory (1985) algorithm by Monika Bargiel and Jacek Moscinski called NSCP3D.     

Geometry-based fully automatic mesh generation and the delaunay triangulation

One approach to fully automatic mesh generation in two and three dimensions is to generate and triangulate a set of points within and on the boundary of a geometry using the properties of the Delaunay triangulation. Because the point data generate mesh topology of greater dimension, it is necessary to insure topological compatibility and perform classification of the resulting mesh with respect to the original geometry. Necessary and sufficient conditions for classification of mesh topology on three-dimensional planar geometry are given, as well as a discussion of the more complex case of curved geometry. This paper also presents conditions to insure topological compatibility along with techniques for identifying and resolving cases of incompatibility.     

Automatic triangulation of arbitrary planar domains for the finite element method

The object of this paper is to describe a new algorithm for the semi-automatic triangulation of arbitrary, multiply connected planar domains. The strategy is based upon a modification of a finite element mesh genration algorithm recently developed. ¹ The scheme is designed for maximum flexibility and is capable of generating meshes of triangular elements for the decomposition of virtually any multiply connected planar domain. Moreover, the desired density of elements in various regions of the problem domain is specified by the user, thus allowing him to obtain a mesh decomposition appropriate to the physical loading and/or boundary conditions of the particular problem at hand. Several examples are presented to illustrate the applicability of the algorithm. An extension of the algorithm to the triangulation of shell structures is indicated.     

A parallel mesh generation algorithm based on the vertex label assignment scheme

In this article a new mesh generation algorithm is presented. The algorithm is based on a new approach called the vertex label assignment scheme to provide the information for the mesh generation so that parallel processing becomes possible. The algorithm generates 2D meshes of quadrilaterals on the basis of individual faces; conformity and smoothness of the resultant mesh are automatically assured. Local and selective mesh-refinements are also supported. A regular quadrilateral network which defines the geometry of the problem and an associated subdivision level assignment which specifies mesh density data on the network are the only input information.     

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.     

等值面的生成原理与算法

本文从工程实际中引出,由四变量离散数据图示等值曲面的问题,提出了构造等值曲面的四维画法几何生成方法,在用计算机实现此生成方法的过程中,从理论上证明了1982年Nguyen-Van-Phai提出的四面体网格化算法,这种算法的性质,即四面体球面过剩为最大的情况下是最佳的,可以有效地应用于计算机绘图和有限元分析的网格自动生成等方面。本文用此算法求出四变量离散数据的等值点,从而实现等值曲面的拟合。     

Automatic sizing functions for unstructured surface mesh generation

Accurate sizing functions are crucial for efficient generation of high‐quality meshes, but to define the sizing function is often the bottleneck in complicated mesh generation tasks because of the tedious user interaction involved. We present a novel algorithm to automatically create high‐quality sizing functions for surface mesh generation. First, the tessellation of a Computer Aided Design (CAD) model is taken as the background mesh, in which an initial sizing function is defined by considering geometrical factors and user‐specified parameters. Then, a convex nonlinear programming problem is formulated and solved efficiently to obtain a smoothed sizing function that corresponds to a mesh satisfying necessary gradient constraint conditions and containing a significantly reduced element number. Finally, this sizing function is applied in an advancing front mesher. With the aid of a walk‐through algorithm, an efficient sizing‐value query scheme is developed. Meshing experiments of some very complicated geometry models are presented to demonstrate that the proposed sizing‐function approach enables accurate and fully automatic surface mesh generation. Copyright © 2016 John Wiley & Sons, Ltd.     

Recovery of an arbitrary edge on an existing surface mesh using local mesh modifications

This study describes an algorithm for recovering an edge which is arbitrarily inserted onto a pre‐triangulated surface mesh. The recovery process does not rely on the parametric space of the surface mesh provided by the geometric modeller. The topological and geometrical validity of the surface mesh is preserved through the entire recovery process. The ability of inserting and recovering an arbitrary edge onto a surface mesh can be an invaluable tool for a number of meshing applications such as boundary layer mesh generation, solution adaptation, preserving the surface conformity, and possibly as a primary tool for mesh generation. The edge recovery algorithm utilizes local surface mesh modification operations of edge swapping, collapsing and splitting. The mesh modification operations are decided by the results of pure geometrical checks such as point and line projections onto faces and face‐line intersections. The accuracy of these checks on the recovery process are investigated and the substantiated precautions are devised and discussed in this study. Copyright © 2001 John Wiley & Sons, Ltd.     

Source Field Modeling by Mesh Incidence Matrices

In this paper, an algorithm using mesh incidence matrices is developed for the fast generation of source magnetic fields. The mesh incidence matrices arise by applying cohomology concepts to the discrete form of the topological laws for source magnetic fields. The algorithm admits a unique and very fast integer Gaussian elimination procedure. The same algorithm is used to generate solenoidal current density in stranded conductors     

The quasi-uniformity condition for reproducing kernel element method meshes

The reproducing kernel element method is a hybrid between finite elements and meshfree methods that provides shape functions of arbitrary order and continuity yet retains the Kronecker-δ property. To achieve these properties, the underlying mesh must meet certain regularity constraints. This paper develops a precise definition of these constraints, and a general algorithm for assessing a mesh is developed. The algorithm is demonstrated on several mesh types. Finally, a guide to generation of quasi-uniform meshes is discussed.     

Application of variational mesh generation approach for selecting centers of radial basis functions collocation method

In this paper, a two-dimensional variational mesh generation method is applied to obtain adaptive centers for radial basis functions (RBFs). At first, a set of uniform centers is distributed in the domain, then mesh generation differential equations are used to move the centers to region with high gradients. An iterative algorithm is introduced to solve steady-state mesh generation differential equations with RBFs. Functions with steep variation in the domains are used to validate the adaptive centers generation method. In addition to the centers adaption process is applied to solve elliptic partial differential equations via RBFs collocation method. Numerical results of Helmholtz differential equation show a clear reduction in the error, when the adaptive centers are used for RBFs.     

A combined octree/delaunay method for fully automatic 3-D mesh generation

Fully automatic three-dimensional mesh generation is a fundamental requirement for automating the numerical solution of partial differential equations. Two techniques in particular—the octree and Delaunay approaches—have been used towards this end. A method that combines both approaches to fully automatic mesh generation is presented here. The resulting algorithm provides the linear growth rate and divide-and-conquer approach of the octree method with the simplicity and optimal properties of the Delaunay triangulation.     

Variational surface reconstruction based on Delaunay triangulation and graph cut

A novel method for surface reconstruction from an unorganized point set is presented. An energy functional based on a weighted minimal surface model is proposed for surface reconstruction, which is efficiently minimized by graph cut methods. By solving the minimization problem on the graph dual to a Delaunay‐based tetrahedral mesh, the advantages of explicit and implicit methods for surface reconstruction are well integrated. A triangular surface mesh homeomorphic to the original surface can be extracted directly from the tetrahedral mesh provided a sufficient sampling density exists. Difficult cases involving undersampling, non‐uniformity, noises and topological complexities can be handled effectively as well. Furthermore, for the first time, multi‐phase surface reconstruction is realized based on the graph cut methods. Various examples are included for demonstrating the efficiency and effectiveness of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Nonlinear T- $Omega$ Formulation Including Motion for Multiply Connected 3-D Problems

An automatic cut generation algorithm based on the tree/co-tree technique is presented for treating multiply connected regions in 3D transient solutions including rigid motion. In the cutting domains, the zero curl condition of vector potential is strongly imposed. As part of the algorithm, a separation technique is introduced to confine the generation of each cutting domain to either the stationary or moving regions for nonconforming mesh coupling and reducing computational cost.