Preliminary Discussion on the Refinement Mesh Generation for Adaptive Analysis ()
1. Introduction
Mesh generation is the process of dividing the continuous geometric domain into a number of discrete sub-domains, which is the key part of numerical analysis method. The mesh used for scientific computation can be divided into two categories; one is structured mesh; the other is unstructured mesh [1]. According to the engineering needs, different types of elements can be used in different parts of the same physical model, which can spend the least calculation cost and get the highest calculation accuracy. The automatic mesh generation tool with high performance is indispensable in the process of adaptive analysis, because the mesh quality has a direct impact on the accuracy and computational efficiency of numerical calculation results [2]. As the one-dimensional problem is very simple and only involves the segmentation of line segments, so the main discussion is for two-dimensional and three-dimensional problem domain mesh segmentation. The development of an automatic mesh generator with strong robustness can solve complex problems and is currently limited to two-dimensional problems, because arbitrary three-dimensional mesh generation is still difficult to achieve [3].
The most important character of structured mesh is that there is a regular mapping relationship between nodes and grid elements; that is to say, the connection mode between each node and its adjacent nodes is fixed, and the connection information of each node can be obtained by calculating the node number, which makes structured grid generation relatively easy, but it can only be applied to models with relatively simple geometric structure. Two-dimensional quadrilateral element and three-dimensional hexahedron element are structured meshes. Unstructured mesh can be applied to the model with complex geometry structure, but its generation is more difficult and there is no mapping relationship between nodes and mesh elements. Triangles in 2D and tetrahedrons in 3D are all unstructured meshes.
Because tetrahedral meshes are usually regarded as triangular meshes in three-dimensional space, the study of triangulation techniques using both triangular and tetrahedral meshes is called triangulation techniques. One-dimensional simplex is a line segment, while two-dimensional and three-dimensional simplexes are triangles and tetrahedrons, respectively. Triangular mesh generation is the most flexible mesh generation method, which can automatically generate 2D and 3D models. Triangular meshes are more flexible than quadrilateral meshes and hexahedral meshes. Triangular and tetrahedral meshes can simulate any complex geometric model or complex boundary [4]. Although the computational accuracy of the quadrilateral and hexahedron elements is higher than that of the triangle and tetrahedron elements, it is difficult to generate quadrilateral and hexahedron meshes automatically for arbitrary 2D and 3D problems.
2. Delaunay Triangulation Algorithm
Delaunay triangulation was first proposed by the Russian mathematician Delaunay [5] in 1934, but it did not receive much attention at that time. Until the 1970s, with the great success of finite element method in more and more engineering application fields, mesh generation has gradually become the bottleneck restricting the further development of finite element analysis, and a large number of researchers have focused on the Delaunay triangulation algorithm. The core algorithm of Delaunay triangulation has attracted more and more attention of researchers.
The Delaunay triangulation algorithm has become the most famous and in-depth study method in the field of automatic mesh generation because of its good mathematical and graph-theoretical foundation. The following will introduce three of the most representative of the core algorithm for Delaunay triangulation including Lawson algorithm, Bowyer-Waston algorithm and dual graph Voronoi diagram algorithm.
2.1. Lawson Algorithm
Lawson algorithm is a Delaunay triangulation algorithm based on vertex-by-vertex insertion and local edges swapping, which was first proposed by Lawson [6] in 1977. In 1989, Joe [7] designed a decision criterion based on space out ball, at the same time, extended the 2D Lawson algorithm based on edge exchange to the 3D Delaunay triangulation algorithm based on face exchange.
The Idea of the two dimensional Lawson algorithm is very simple, that is, through the diagonal exchange of all convex quadrilaterals formed by two triangles sharing sides in the mesh, the situation which does not meet the Delaunay triangulation standard in the mesh is eliminated, and it has been proved theoretically that for the triangulation of any point set. Both of them can transform the existing local non-Delaunay triangulation meshes into the Delaunay triangulation standard meshes by using finite number of diagonal transformations.
The basic idea of the two dimensional Lawson algorithm is as follows:
1) First, a set of initial Delaunay triangulation should be set up;
2) Generating a set of nodes to be inserted, after inserting new nodes, selecting a triangle containing the inserted new nodes, respectively connecting the vertices of the triangle and the newly inserted nodes in turn, and cutting the original triangle into three small triangles;
3) Testing the empty circumcircle criterion for the newly created three small triangles in turn, if the three small triangles can meet the empty circumcircle test, then jump to the second step to re-insert the next node;
4) If there is a circumcircle including nodes, we need to swap the diagonals of the quadrilateral to create two new triangles, and when all the newly created triangles meet the empty circumcircle criterion, we stop the edge swapping operation;
5) Perform the insertion circularly until the set of points to be inserted is empty, that is, all the nodes are inserted.
The whole process of Lawson edge switching algorithm is shown in Figure 1. After adding a new node in the initial mesh, the triangle initial mesh with general quality is generated, and the empty circumcircle criterion is detected for these triangles, and the diagonal exchange operation is performed for the triangles that do not meet the empty circumcircle criterion, which is exactly aimed at the triangle mesh with low quality and starts the optimization operation of edge exchange. The red lines in the figure are the diagonal lines that need to be changed. Replace the red diagonal lines with blue diagonal lines, and finally generate a better quality and conform to the Delaunay characteristics of the mesh.
The Lawson edge exchange algorithm aims at 2D triangulation, and extends to 3D problem, then exchanges the diagonal faces of tetrahedron. Considering that there are many kinds of construction methods of tetrahedron and the exchange
![]()
Figure 1. Local edge exchange algorithm for two dimensional triangle subdivision.
methods of diagonal faces, the complexity of 3D Delaunay triangulation algorithm based on face exchange is much more than 2D algorithm based on edge exchange.
2.2. The Bowyer-Waston Algorithm
The Bowyer-Waston algorithm is a new algorithm, which is the combination of the algorithms proposed by British scientist Bowyer [8] and Australian scientist Waston [9], respectively in 1981. It is based on the combination of the two algorithms. The specific implementation steps of Bowyer-Waston algorithm are as follows:
1) First, an initial Delaunay mesh is created;
2) The points to be inserted in the node set are sequentially inserted in the positions other than the initial grid nodes;
3)After the new nodes are inserted into the initial Delaunay mesh, the triangles whose circumcircle contains the new insertion point are found out respectively from the triangle chain list, and the common sides of these triangles which do not conform to the Delaunay null circumcircle property are deleted;
4) A new Delaunay triangulation is formed by connecting every vertex of the polygon obtained from the deleted-triangles with the new insertion point;
5) Loop executes step 2 of the algorithm until the set including insertion points is empty.
2.3. The Dual Graph Voronoi Diagram Algorithm
Voronoi Diagram is a kind of graph composed of two-dimensional polygon or three-dimensional polyhedron, which is mainly used to study the problem of planar point set and its domain, proposed by Voronoi [10] in 1908, every point in the point set has a region satisfying certain conditions, which can be called Voronoi polygon. Voronoi polygons are pieced together to form a Voronoi diagram.
As shown in Figure 2(a), it is easy to see that each Voronoi polygon is similar to a cell, and that Voronoi diagram is a diagram contain a plurality of cells, each cell contain a red nucleus, and each cell, that is, the area related to the nucleus, is called Voronoi polygon or Voronoi element; A Delaunay triangulation can be obtained by connecting the red nuclei of two adjacent cells sharing a common edge with a blue solid line, and the red nuclei are the vertices of the triangulation, as shown in Figure 2(b). Delaunay triangulation is dual to Voronoi diagram, so we can obtain Delaunay triangulation by Voronoi diagram.
The Delaunay triangulation of 2D and 3D problems has something in common in many aspects. Therefore, most of the successful algorithms in 2D problems can be improved and applied to 3D problems, but there are some difficulties in the process of extending to 3D space both in theory and in practice. Three-dimensional Delaunay triangulation is far from reaching the nearly perfect state of two-dimensional Delaunay triangulation, so far it is still the research focus of many researchers. The PLC (Piecewise Linear Complex) is used to describe the three-dimensional region which needs to be calculated, and the Piecewise Linear Complex is the expansion of the planar line graph from two-dimensional plane to three-dimensional space.
3. Mesh Generation
This paper introduces two high performance mesh generators based on Delaunay technology to generate unstructured mesh elements of triangle and tetrahedron. The 2D mesh code Triangle and 3D mesh code Tetgen are very suitable to be embedded into the main program of adaptive analysis simulation software.
3.1. Two Dimension
Triangle [11] is a robust 2D triangle mesh generator developed for Quake project by Professor Shewchuk of University of California, Berkeley, using standard C language. The Quake project is a tool that can simulate the propagation of energy during large-scale earthquakes, hoping to help reduce the loss of life and property in earthquake-prone countries and regions. It can be imagined that as an important part of the Quake project, Triangle with excellent mesh partition
![]()
Figure 2. Voronoi diagram and the dual graph of Voronoi diagram. (a) Voronoi diagram; (b) The dual graph of Voronoi diagram.
ability is beyond doubt. Based on Delaunay technique, Triangle constructs triangular meshes in any two-dimensional domain, and can triangulate the two-dimensional domain with some restrictions, which can generate high quality triangular meshes and Voronoi graphs. Triangle can also do full Delaunay triangulation, limited Delaunay triangulation, consistent Delaunay triangle.
3.2. Three Dimension
Tetgen [12] is an open source three-dimensional tetrahedral mesh generation program published by the Computational Mathematics and Scientific Computing Research Group in Germany. Tetgen can be used to discretize any polyhedron into tetrahedral meshes of good quality which makes it used by more and more well-known finite element open source software and commercial pre-processor now. In addition to being a tetrahedral mesh generator, Tetgen can be widely used in scientific research and engineering applications as a mesh generation component [13] [14].
4. Mesh H-Type Refinement Strategy
In the iterative process of adaptive analysis, the new node information needed to be added can be obtained according to the calculation of the previous step, combined with the mesh information of the previous step, the mesh is reconstructed by using mesh subdivision code, and the new mesh after node refinement is generated, which can be used for the next calculation and analysis. For two-dimensional triangle element and three-dimensional tetrahedron element, this chapter respectively designed a simple and intuitive H-type mesh refinement strategy [15] [16], as shown in Figure 3(a), white nodes represent the original nodes, black nodes represent the newly added nodes, add a new node in the midpoint of each side of the triangular element, and the original triangle is subdivided into four small triangles.
The refinement strategy of tetrahedron is carried out in two steps, as shown in Figure 3(b): The first step is to add a new black node at the midpoint position of all edges of the tetrahedral element, nodes 1, 2, 3 and 4 are original nodes, and black nodes 5, 6, 7, 8, 9 and 10 are new added nodes, and six new nodes are
![]()
Figure 3. H-type mesh refinement strategy. (a) Triangle; (b) Tetrahedron.
needed to subdivide a tetrahedral element. According to the connection mode of the nodes in the figure, it is not difficult to find that after excising the four vertex small tetrahedrons of the original tetrahedral element, the remaining polyhedron can still be further subdivided into four small tetrahedrons, and finally, the original tetrahedral element 1234 can be subdivided into eight small tetrahedral elements.
5. Conclusion
Adaptive analysis technique is an effective way to improve the efficiency and accuracy of numerical methods by estimating the error of some intermediate results of numerical methods and refining the mesh in the region where the gradient of field variables changes sharply, with the ultimate goal of obtaining the highest computational accuracy by minimizing the computational cost. In this work, the following conclusions can be drawn: 1) Mesh generation is one of the main problems in adaptive analysis. 2) Three most representative algorithms of Dealaulay triangulation are introduced. 3) Two mesh generators are very suitable to be embedded into the development of adaptive analysis. Triangle and Tetgen are separately responsible for triangle and tetrahedral mesh generation and reconstruction. 4) A simple and efficient strategy is designed to subdivide 2D triangular elements and 3D tetrahedral elements by adding nodes.
Acknowledgements
This work is funded by Scientific Research Fund of Hunan Provincial Education Department (18B384).
NOTES
*Corresponding author.