Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine (have small elements) in areas that are important for the subsequent calculations. Meshes are used for rendering to a computer screen and for physical simulation such as finite element analysis or computational fluid dynamics. Meshes are composed of simple cells like triangles because, e.g., we know how to perform operations such as finite element calculations (engineering) or ray tracing (computer graphics) on triangles, but we do not know how to perform these operations directly on complicated spaces and shapes such as a roadway bridge. We can simulate the strength of the bridge, or draw it on a computer screen, by performing calculations on each triangle and calculating the interactions between triangles. A major distinction is between structured and unstructured meshing. In structured meshing the mesh is a regular lattice, such as an array, with implied connectivity between elements. In unstructured meshing, elements may be connected to each other in irregular patterns, and more complicated domains can be captured. This page is primarily about unstructured meshes. While a mesh may be a triangulation, the process of meshing is distinguished from point set triangulation in that meshing includes the freedom to add vertices not present in the input. "Facetting" (triangulating) CAD models for drafting has the same freedom to add vertices, but the goal is to represent the shape accurately using as few triangles as possible and the shape of individual triangles is not important. Computer graphics renderings of textures and realistic lighting conditions use meshes instead. Many mesh generation software is coupled to a CAD system defining its input, and simulation software for taking its output. The input can vary greatly but common forms are Solid modeling, Geometric modeling, NURBS, B-rep, STL or a point cloud.
Terminology The terms "mesh generation," "grid generation," "meshing," " and "gridding," are often used interchangeably, although strictly speaking the latter two are broader and encompass mesh improvement: changing the mesh with the goal of increasing the speed or accuracy of the numerical calculations that will be performed over it. In computer graphics rendering, and mathematics, a mesh is sometimes referred to as a tessellation. Mesh faces (cells, entities) have different names depending on their dimension and the context in which the mesh will be used. In finite elements, the highest-dimensional mesh entities are called "elements," "edges" are 1D and "nodes" are 0D. If the elements are 3D, then the 2D entities are "faces." In computational geometry, the 0D points are called vertices. Tetrahedra are often abbreviated as "tets"; triangles are "tris", quadrilaterals are "quads" and hexahedra (topological cubes) are "hexes."
Techniques
Many meshing techniques are built on the principles of the Delaunay triangulation, together with rules for adding vertices, such as Ruppert's algorithm. A distinguishing feature is that an initial coarse mesh of the entire space is formed, then vertices and triangles are added. In contrast, advancing front algorithms start from the domain boundary, and add elements incrementally filling up the interior. Hybrid techniques do both. A special class of advancing front techniques creates thin boundary layers of elements for fluid flow. In structured mesh generation the entire mesh is a lattice graph, such as a regular grid of squares. In block-structured meshing, the domain is divided into large subregions, each of which is a structured mesh. Some direct methods start with a block-structured mesh and then move the mesh to conform to the input; see Automatic Hex-Mesh Generation based on polycube. Another direct method is to cut the structured cells by the domain boundary; see sculpt based on Marching cubes. Some types of meshes are much more difficult to create than others. Simplicial meshes tend to be easier than cubical meshes. An important category is generating a hex mesh conforming to a fixed quad surface mesh; a research subarea is studying the existence and generation of meshes of specific small configurations, such as the tetragonal trapezohedron. Because of the difficulty of this problem, the existence of combinatorial hex meshes has been studied apart from the problem of generating good geometric realizations; see Combinatorial Techniques for Hexahedral Mesh Generation. While known algorithms generate simplicial meshes with guaranteed minimum quality, such guarantees are rare for cubical meshes, and many popular implementations generate inverted (inside-out) hexes from some inputs. Meshes are often created in serial on workstations, even when subsequent calculations over the mesh will be done in parallel on super-computers. This is both because of the limitation that most mesh generators are interactive, and because mesh generation runtime is typically insignificant compared to solver time. However, if the mesh is too large to fit in the memory of a single serial machine, or the mesh must be changed (adapted) during the simulation, meshing is done in parallel.
Algebraic methods
… excerpt ends here. Continue reading the full article.
