Mesh generation methods

The various methods available for mesh generation can be enumerated as [Sha96] -

1.

Manual generation - In this approach the user defines each element by the vertices. This approach is feasible only when a limited number of elements are required and the domain is very simple.

2.

Transport mapping method - Also known as Transfinite Interpolation method, it involves blending of a mesh generated in a parametric domain into the real domain, as the parametric boundary blends into the real boundary.

3.

Explicit solution of Partial Differential Equations - In this approach the mesh is first generated in a parametric domain in a simple geometry (quadrilateral, tetrahedron etc.). Then a mapping function is defined to ensure properties such as boundary conformity, orthogonality of elements, variable density of elements and the like. Such methods result in structured meshes.

4.

Advancing Front Methods (AFM) - These methods are widely used to create planar, surface and volume grids which can have triangular, quadrilateral or higher order elements. The boundary is represented as continuous or discretised curve(s) (for 2D mesh generation) and triangulated or continuous surface(s) (for 3D mesh generation). A front, initialised by the boundary is established. The front is updated as new internal points are created till the front becomes empty, also symbolising the creation of the mesh in the entire domain.

5.

Delaunay-Voronoi Triangulation - This algorithm is widely used for tetrahedralisation of 3D domains (also known as 3D triangulation). This results in a mesh which is optimal for a set of given points in the domain. However, the quality of the mesh depends upon the points specified and a bad choice of points may result in poor triangulation. This method is much faster than the AFM.

6.

Sweepline method - This algorithm constructs the Voronoi tessellation by searching for Voronoi region boundaries in an orderly fashion. The nodes are sorted in a specific coordinate direction. A sweepline is defined as the description of the intersection of a moving line perpendicular to the specified direction with the Voronoi boundaries. The sweepline starts from the least value of sorted coordinates and moves to the other extreme. As each node is encountered by the sweepline, new bisectors of the lines joining two nodes are introduced in it. The aim is to detect the point of intersection of three bisectors to get the circumcenter of the triangle formed by three nodes. This is a relatively new and involved algorithm but a time complexity better than Delaunay's algorithm is claimed.