Mesh generation is the practice of creating a
mesh
Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...
, a subdivision of a continuous geometric space into discrete geometric and topological cells.
Often these cells form a
simplicial complex
In mathematics, a simplicial complex is a structured Set (mathematics), set composed of Point (geometry), points, line segments, triangles, and their ''n''-dimensional counterparts, called Simplex, simplices, such that all the faces and intersec ...
.
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
A simulation is an imitative representation of a process or system that could exist in the real world. In this broad sense, simulation can often be used interchangeably with model. Sometimes a clear distinction between the two terms is made, in ...
such as
finite element analysis
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical models, mathematical modeling. Typical problem areas of interest include the traditional fields of structural ...
or
computational fluid dynamics
Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid dynamics, fluid flows. Computers are used to perform the calculations required ...
. 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
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle m ...
, 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
Solid modeling (or solid modelling) is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes '' (solids)''. Solid modeling is distinguished within the broader related areas of geometric modeling and ...
,
Geometric modeling
__NOTOC__
Geometric modeling is a branch of applied mathematics and computational geometry that studies methods and algorithms for the mathematical description of shapes.
The shapes studied in geometric modeling are mostly two- or three-dimensi ...
,
NURBS
Non-uniform rational basis spline (NURBS) is a mathematical model using basis splines (B-splines) that is commonly used in computer graphics for representing curves and surfaces. It offers great flexibility and precision for handling both analy ...
,
B-rep
In solid modeling and computer-aided design, boundary representation (often abbreviated B-rep or BREP) is a method for representing a 3D shape by defining the limits of its volume. A Solid modeling, solid is represented as a collection of con ...
,
STL or a
point cloud
A point cloud is a discrete set of data Point (geometry), points in space. The points may represent a 3D shape or object. Each point Position (geometry), position has its set of Cartesian coordinates (X, Y, Z). Points may contain data other than ...
.
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
Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. ...
rendering, and
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a mesh is sometimes referred to as a ''
tessellation
A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...
.''
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
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
, 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 layer
In physics and fluid mechanics, a boundary layer is the thin layer of fluid in the immediate vicinity of a Boundary (thermodynamic), bounding surface formed by the fluid flowing along the surface. The fluid's interaction with the wall induces ...
s of elements for fluid flow.
In structured mesh generation the entire mesh is a
lattice graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
, 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; se
Automatic Hex-Mesh Generationbased on
polycube
image:tetracube_categories.svg, upAll 8 one-sided tetracubes – if chirality is ignored, the bottom 2 in grey are considered the same, giving 7 free tetracubes in total
image:9L cube puzzle solution.svg, A puzzle involving arranging nine L tricube ...
. Another direct method is to cut the structured cells by the domain boundary; se
sculptbased on
Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are somet ...
.
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
In geometry, a tetragonal trapezohedron, or deltohedron, is the second in an infinite series of trapezohedra, which are dual to the antiprisms. It has eight faces, which are congruent kites, and is dual to the square antiprism.
Applications ...
. 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; se
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
Parallel may refer to:
Mathematics
* Parallel (geometry), two lines in the Euclidean plane which never intersect
* Parallel (operator), mathematical operation named after the composition of electrical resistance in parallel circuits
Science a ...
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

The grid generation by algebraic methods is based on mathematical
interpolation function
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a ...
. It is done by using known functions in one, two or three
dimensions taking arbitrary shaped regions. The computational domain might not be rectangular, but for the sake of simplicity, the domain is taken to be rectangular. The main advantage of the methods is that they provide explicit control of physical grid shape and spacing. The simplest procedure that may be used to produce boundary fitted computational mesh is the normalization transformation.
For a nozzle, with the describing function
the grid can easily be generated using uniform division in ''y''-direction with equally spaced increments in ''x''-direction, which are described by
:
:
where
denotes the y-coordinate of the nozzle wall. For given values of (
,
), the values of (
,
) can be easily recovered.
Differential equation methods
Like algebraic methods,
differential equation methods are also used to generate grids. The advantage of using the
partial differential equations
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to how ...
(PDEs) is that the solution of grid generating equations can be exploited to generate the mesh. Grid construction can be done using all three classes of
partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to ho ...
s.
Elliptic schemes
Elliptic PDEs generally have very smooth solutions leading to smooth contours. Using its smoothness as an advantage
Laplace's equation
In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties in 1786. This is often written as
\nabla^2\! f = 0 or \Delta f = 0,
where \Delt ...
s can preferably be used because the
Jacobian found out to be positive as a result of maximum principle for
harmonic function
In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function f\colon U \to \mathbb R, where is an open subset of that satisfies Laplace's equation, that i ...
s. After extensive work done by Crowley (1962) and Winslow (1966) on PDEs by transforming physical domain into computational plane while mapping using
Poisson's equation
Poisson's equation is an elliptic partial differential equation of broad utility in theoretical physics. For example, the solution to Poisson's equation is the potential field caused by a given electric charge or mass density distribution; with t ...
, Thompson et al. (1974) have worked extensively on elliptic
PDEs to generate grids. In Poisson grid generators, the mapping is accomplished by marking the desired grid points
on the boundary of the physical domain, with the interior point distribution determined through the solution of equations written below
:
:
where,
are the co-ordinates in the computational domain, while P and Q are responsible for point spacing within D. Transforming above equations in computational space yields a set of two
elliptic PDEs of the form,
:
:
where
:
These systems of equations are solved in the computational plane on uniformly spaced grid which provides us with the
co-ordinates of each point in physical space. The advantage of using
elliptic PDEs is the solution linked to them is smooth and the resulting grid is smooth. But, specification of P and Q becomes a difficult task thus adding it to its disadvantages. Moreover, the grid has to be computed after each time step which adds up to computational time.
Hyperbolic schemes
This grid generation scheme is generally applicable to problems with open domains consistent with the type of
PDE describing the physical problem. The advantage associated with
hyperbolic PDEs is that the governing equations need to be solved only once for generating grid. The initial point distribution along with the approximate boundary conditions forms the required input and the solution is the then marched outward. Steger and Sorenson (1980) proposed a volume orthogonality method that uses Hyperbolic PDEs for mesh generation.
For a 2-D problem, Considering computational space to be given by
, the inverse of the
Jacobian is given by,
:
where
represents the area in physical space for a given area in computational space. The second equation links the orthogonality of grid lines at the boundary in physical space which can be written as
:
For
and
surfaces to be perpendicular the equation becomes
:
The problem associated with such system of equations is the specification of
. Poor selection of
may lead to shock and discontinuous propagation of this information throughout the mesh. While mesh being orthogonal is generated very rapidly which comes out as an advantage with this method.
Parabolic schemes
The solving technique is similar to that of
hyperbolic PDEs by advancing the solution away from the initial data surface satisfying the boundary conditions at the end. Nakamura (1982) and Edwards (1985) developed the basic ideas for parabolic grid generation. The idea uses either of
Laplace
Pierre-Simon, Marquis de Laplace (; ; 23 March 1749 – 5 March 1827) was a French polymath, a scholar whose work has been instrumental in the fields of physics, astronomy, mathematics, engineering, statistics, and philosophy. He summariz ...
or the
Poisson's equation
Poisson's equation is an elliptic partial differential equation of broad utility in theoretical physics. For example, the solution to Poisson's equation is the potential field caused by a given electric charge or mass density distribution; with t ...
and especially treating the parts which controls elliptic behavior. The initial values are given as the coordinates of the point along the surface
and the advancing the solutions to the outer surface of the object satisfying the boundary conditions along
edges.
The control of the grid spacing has not been suggested until now. Nakamura and Edwards, grid control was accomplished using non uniform spacing. The parabolic grid generation shows an advantage over the hyperbolic grid generation that, no shocks or discontinuities occur and the grid is relatively smooth. The specifications of initial values and selection of step size to control the grid points is however time-consuming, but these techniques can be effective when familiarity and experience is gained.
Variational methods
This method includes a technique that minimizes
grid
Grid, The Grid, or GRID may refer to:
Space partitioning
* Regular grid, a tessellation of space with translational symmetry, typically formed from parallelograms or higher-dimensional analogs
** Grid graph, a graph structure with nodes connec ...
smoothness,
orthogonality
In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''. Although many authors use the two terms ''perpendicular'' and ''orthogonal'' interchangeably, the term ''perpendicular'' is more specifically ...
and volume variation. This method forms mathematical platform to solve grid generation problems. In this method an alternative grid is generated by a new
mesh
Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...
after each iteration and computing the grid speed using
backward difference method. This technique is a powerful one with a disadvantage that effort is required to solve the equations related to grid. Further work needed to be done to minimize the
integrals
In mathematics, an integral is the continuous analog of a sum, which is used to calculate areas, volumes, and their generalizations. Integration, the process of computing an integral, is one of the two fundamental operations of calculus,Int ...
that will reduce the CPU time.
Unstructured grid generation
The main importance of this scheme is that it provides a method that will generate the grid automatically. Using this method, grids are segmented into blocks according to the surface of the element and a structure is provided to ensure appropriate connectivity. To interpret the data
flow solver is used. When an unstructured scheme is employed, the main interest is to fulfill the demand of the user and a grid generator is used to accomplish this task. The information storage in structured scheme is
cell
Cell most often refers to:
* Cell (biology), the functional basic unit of life
* Cellphone, a phone connected to a cellular network
* Clandestine cell, a penetration-resistant form of a secret or outlawed organization
* Electrochemical cell, a de ...
to cell instead of grid to grid and hence the more memory space is needed. Due to random cell location, the solver
efficiency
Efficiency is the often measurable ability to avoid making mistakes or wasting materials, energy, efforts, money, and time while performing a task. In a more general sense, it is the ability to do things well, successfully, and without waste.
...
in unstructured is less as compared to the structured scheme.
Some points are needed to be kept in mind at the time of grid
construction
Construction are processes involved in delivering buildings, infrastructure, industrial facilities, and associated activities through to the end of their life. It typically starts with planning, financing, and design that continues until the a ...
. The grid point with high resolution creates difficulty for both structured and unstructured. For example, in case of
boundary layer
In physics and fluid mechanics, a boundary layer is the thin layer of fluid in the immediate vicinity of a Boundary (thermodynamic), bounding surface formed by the fluid flowing along the surface. The fluid's interaction with the wall induces ...
, structured scheme produces elongated grid in the direction of flow. On the other hand, unstructured grids require a higher cell
density
Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be u ...
in the boundary layer because the cell needs to be as
equilateral
An equilateral triangle is a triangle in which all three sides have the same length, and all three angles are equal. Because of these properties, the equilateral triangle is a regular polygon, occasionally known as the regular triangle. It is the ...
as possible to avoid errors.
We must identify what information is required to identify the cell and all the neighbors of the cell in the
computational
A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms.
Mechanical or electronic devices (or, historic ...
mesh. We can choose to locate the
arbitrary
Arbitrariness is the quality of being "determined by chance, whim, or impulse, and not by necessity, reason, or principle". It is also used to refer to a choice made without any specific criterion or restraint.
Arbitrary decisions are not necess ...
points anywhere we want for the unstructured grid. A point insertion scheme is used to insert the points independently and the cell connectivity is determined. This suggests that the point be identified as they are inserted.
Logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
for establishing new connectivity is determined once the points are inserted. Data that form grid point that identifies grid cell are needed. As each cell is formed it is numbered and the points are sorted. In addition the neighbor cell information is needed.
Adaptive grid
A problem in solving
partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to ho ...
s using previous methods is that the grid is constructed and the points are distributed in the physical domain before details of the solution is known. So the grid may or may not be the best for the given problem.
Adaptive methods are used to improve the
accuracy
Accuracy and precision are two measures of ''observational error''.
''Accuracy'' is how close a given set of measurements (observations or readings) are to their ''true value''.
''Precision'' is how close the measurements are to each other.
The ...
of the solutions. The adaptive method is referred to as ‘h’ method if mesh refinement is used, ‘r’ method if the number of grid point is fixed and not redistributed and ‘p’ if the order of solution scheme is increased in finite-element theory. The multi dimensional problems using the equidistribution scheme can be accomplished in several ways. The simplest to understand are the Poisson Grid Generators with control function based on the equidistribution of the weight function with the
diffusion
Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical p ...
set as a multiple of desired cell volume. The equidistribution scheme can also be applied to the unstructured problem. The problem is the connectivity hampers if mesh point movement is very large.
Steady flow
In physics, physical chemistry and engineering, fluid dynamics is a subdiscipline of fluid mechanics that describes the flow of fluids – liquids and gases. It has several subdisciplines, including (the study of air and other gases in motio ...
and the time-accurate flow calculation can be solved through this adaptive method. The grid is refined and after a predetermined number of iteration in order to adapt it in a steady flow problem. The grid will stop adjusting to the changes once the solution converges. In time accurate case coupling of the
partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to ho ...
s of the physical problem and those describing the grid movement is required.
Image-based meshing
Cell topology
Usually the cells are
polygon
In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain.
The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
al or
polyhedral
In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary surfa ...
and form a
mesh
Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...
that partitions the domain.
Important classes of two-dimensional elements include triangles (simplices) and quadrilaterals (topological squares).
In three-dimensions the most-common cells are tetrahedra (simplices) and hexahedra (topological cubes).
Simplicial meshes may be of any dimension and include triangles (2D) and tetrahedra (3D) as important instances.
''Cubical meshes'' is the pan-dimensional category that includes quads (2D) and hexes (3D). In 3D, 4-sided pyramids and 3-sided prisms appear in conformal meshes of mixed cell type.
Cell dimension
The mesh is embedded in a geometric space that is typically
two
2 (two) is a number, numeral and digit. It is the natural number following 1 and preceding 3. It is the smallest and the only even prime number.
Because it forms the basis of a duality, it has religious and spiritual significance in many ...
or
three dimensional, although sometimes the dimension is increased by one by adding the time-dimension. Higher dimensional meshes are used in niche contexts. One-dimensional meshes are useful as well. A significant category is surface meshes, which are 2D meshes embedded in 3D to represent a curved surface.
Duality
Dual graph
In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...
s have several roles in meshing. One can make a polyhedral
Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (calle ...
mesh by dualizing a
Delaunay triangulation
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
simplicial mesh. One can create a cubical mesh by generating an arrangement of surfaces and dualizing the intersection graph; see
spatial twist continuum. Sometimes both the primal mesh and its dual mesh are used in the same simulation; see
Hodge star operator
In mathematics, the Hodge star operator or Hodge star is a linear map defined on the exterior algebra of a Dimension (vector space), finite-dimensional orientation (vector space), oriented vector space endowed with a Degenerate bilinear form, nonde ...
. This arises from physics involving
divergence
In vector calculus, divergence is a vector operator that operates on a vector field, producing a scalar field giving the rate that the vector field alters the volume in an infinitesimal neighborhood of each point. (In 2D this "volume" refers to ...
and
curl (mathematics)
In vector calculus, the curl, also known as rotor, is a vector operator that describes the Differential (infinitesimal), infinitesimal Circulation (physics), circulation of a vector field in three-dimensional Euclidean space. The curl at a poin ...
operators, such as
flux
Flux describes any effect that appears to pass or travel (whether it actually moves or not) through a surface or substance. Flux is a concept in applied mathematics and vector calculus which has many applications in physics. For transport phe ...
&
vorticity
In continuum mechanics, vorticity is a pseudovector (or axial vector) field that describes the local spinning motion of a continuum near some point (the tendency of something to rotate), as would be seen by an observer located at that point an ...
or
electricity & magnetism, where one variable naturally lives on the primal faces and its counterpart on the dual faces.
Mesh type by use
Three-dimensional meshes created for
finite element analysis
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical models, mathematical modeling. Typical problem areas of interest include the traditional fields of structural ...
need to consist of
tetrahedra
In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...
,
pyramid
A pyramid () is a structure whose visible surfaces are triangular in broad outline and converge toward the top, making the appearance roughly a pyramid in the geometric sense. The base of a pyramid can be of any polygon shape, such as trian ...
s,
prism
PRISM is a code name for a program under which the United States National Security Agency (NSA) collects internet communications from various U.S. internet companies. The program is also known by the SIGAD . PRISM collects stored internet ...
s or
hexahedra. Those used for the
finite volume method
The finite volume method (FVM) is a method for representing and evaluating partial differential equations in the form of algebraic equations.
In the finite volume method, volume integrals in a partial differential equation that contain a divergen ...
can consist of arbitrary
polyhedra
In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
. Those used for
finite difference method
In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating Derivative, derivatives with Finite difference approximation, finite differences. Both the spatial doma ...
s consist of piecewise structured arrays of
hexahedra known as multi-block structured meshes.
4-sided pyramids are useful to conformally connect hexes to tets. 3-sided prisms are used for boundary layers conforming to a tet mesh of the far-interior of the object.
Surface meshes are useful in computer graphics where the surfaces of objects reflect light (also
subsurface scattering
Subsurface scattering (SSS), also known as subsurface light transport (SSLT), is a mechanism of light transport in which light that penetrates the surface of a translucent object is scattering, scattered by interacting with the Material (comput ...
) and a full 3D mesh is not needed. Surface meshes are also used to model thin objects such as sheet metal in auto manufacturing and building exteriors in architecture. High (e.g., 17) dimensional cubical meshes are common in astrophysics and
string theory
In physics, string theory is a theoretical framework in which the point-like particles of particle physics are replaced by one-dimensional objects called strings. String theory describes how these strings propagate through space and intera ...
.
Mathematical definition and variants
What is the precise definition of a ''mesh?'' There is not a universally-accepted mathematical description that applies in all contexts.
However, some mathematical objects are clearly meshes: a
simplicial complex
In mathematics, a simplicial complex is a structured Set (mathematics), set composed of Point (geometry), points, line segments, triangles, and their ''n''-dimensional counterparts, called Simplex, simplices, such that all the faces and intersec ...
is a mesh composed of simplices.
Most polyhedral (e.g. cubical) meshes are ''conformal,'' meaning they have the cell structure of a
CW complex
In mathematics, and specifically in topology, a CW complex (also cellular complex or cell complex) is a topological space that is built by gluing together topological balls (so-called ''cells'') of different dimensions in specific ways. It generali ...
, a generalization of a
simplicial complex
In mathematics, a simplicial complex is a structured Set (mathematics), set composed of Point (geometry), points, line segments, triangles, and their ''n''-dimensional counterparts, called Simplex, simplices, such that all the faces and intersec ...
. A mesh need not be simplicial because an arbitrary subset of nodes of a cell is not necessarily a cell: e.g., three nodes of a quad does not define a cell.
However, two cells intersect at cells: e.g. a quad does not have a node in its interior. The intersection of two cells may be several cells: e.g., two quads may share two edges. An intersection being more than one cell is sometimes forbidden and rarely desired; the goal of some mesh improvement techniques (e.g. pillowing) is to remove these configurations. In some contexts, a distinction is made between a topological mesh and a geometric mesh whose embedding satisfies certain quality criteria.
Important mesh variants that are not CW complexes include non-conformal meshes where cells do not meet strictly face-to-face, but the cells nonetheless partition the domain. An example of this is an
octree
An octree is a tree data structure in which each internal node has exactly eight child node, children. Octrees are most often used to partition a three-dimensional space by recursive subdivision, recursively subdividing it into eight Octant (geo ...
, where an element face may be partitioned by the faces of adjacent elements. Such meshes are useful for flux-based simulations. In overset grids, there are multiple conformal meshes that overlap geometrically and do not partition the domain; see e.g.,
Overflow, the OVERset grid FLOW solver. So-called meshless or
meshfree methods
In the field of numerical analysis, meshfree methods are those that do not require connection between nodes of the simulation domain, i.e. a mesh, but are rather based on interaction of each node with all its neighbors. As a consequence, origin ...
often make use of some mesh-like discretization of the domain, and have basis functions with overlapping support. Sometimes a local mesh is created near each simulation degree-of-freedom point, and these meshes may overlap and be non-conformal to one another.
Implicit triangulations are based on a delta complex: for each triangle the lengths of its edges, and a gluing map between face edges. (please expand)
High-order elements
Many meshes use linear elements, where the mapping from the abstract to realized element is linear, and mesh edges are straight segments.
Higher order polynomial mappings are common, especially quadratic.
A primary goal for higher-order elements is to more accurately represent the domain boundary, although they have accuracy benefits in the interior of the mesh as well.
One of the motivations for cubical meshes is that linear cubical elements have some of the same numerical advantages as quadratic simplicial elements.
In the
isogeometric analysis simulation technique, the mesh cells containing the domain boundary use the CAD representation directly instead of a linear or polynomial approximation.
Mesh improvement
Improving a mesh involves changing its discrete connectivity, the continuous geometric position of its cells, or both. For discrete changes, for simplicial elements one swaps edges and inserts/removes nodes. The same kinds of operations are done for cubical (quad/hex) meshes, although there are fewer possible operations and local changes have global consequences. E.g., for a hexahedral mesh, merging two nodes creates cells that are not hexes, but if diagonally-opposite nodes on a quadrilateral are merged and this is propagated into collapsing an entire face-connected column of hexes, then all remaining cells will still be hexes.
In
adaptive mesh refinement
In numerical analysis, adaptive mesh refinement (AMR) is a method of adapting the accuracy of a solution within certain sensitive or turbulent regions of simulation, dynamically and during the time the solution is being calculated. When solutions ...
, elements are split (h-refinement) in areas where the function being calculated has a high gradient.
Meshes are also coarsened, removing elements for efficiency. The
multigrid method does something similar to refinement and coarsening to speed up the numerical solve, but without actually changing the mesh.
For continuous changes, nodes are moved, or the higher-dimensional faces are moved by changing the polynomial order of elements. Moving nodes to improve quality is called "smoothing" or "r-refinement" and increasing the order of elements is called "p-refinement." Nodes are also moved in simulations where the shape of objects change over time. This degrades the shape of the elements. If the object deforms enough, the entire object is remeshed and the current solution mapped from the old mesh to the new mesh.
Research community
Practitioners
The field is highly interdisciplinary, with contributions found in
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
,
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, and
engineering
Engineering is the practice of using natural science, mathematics, and the engineering design process to Problem solving#Engineering, solve problems within technology, increase efficiency and productivity, and improve Systems engineering, s ...
. Meshing R&D is distinguished by an equal focus on discrete and continuous math and computation, as with
computational geometry, but in contrast to
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
(discrete) and
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
(continuous). Mesh generation is deceptively difficult: it is easy for humans to see how to create a mesh of a given object, but difficult to program a computer to make good decisions for arbitrary input a priori. There is an infinite variety of geometry found in nature and man-made objects. Many mesh generation researchers were first users of meshes. Mesh generation continues to receive widespread attention, support and funding because the human-time to create a mesh dwarfs the time to set up and solve the calculation once the mesh is finished. This has always been the situation since numerical simulation and computer graphics were invented, because as computer hardware and simple equation-solving software have improved, people have been drawn to larger and more complex geometric models in a drive for greater fidelity, scientific insight, and artistic expression.
Journals
Meshing research is published in a broad range of journals. This is in keeping with the interdisciplinary nature of the research required to make progress, and also the wide variety of applications that make use of meshes. About 150 meshing publications appear each year across 20 journals, with at most 20 publications appearing in any one journal. There is no journal whose primary topic is meshing. The journals that publish at least 10 meshing papers per year are in bold.
* ''
Advances in Engineering Software''
* ''
American Institute of Aeronautics and Astronautics Journal'' (AIAAJ)
* ''
Algorithmica
''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief i ...
''
* ''
Applied Computational Electromagnetics Society Journal''
* ''
Applied Numerical Mathematics''
* ''
Astronomy and Computing
''Astronomy and Computing'' is a peer-reviewed scientific journal covering research on applications computer science in astronomy published by Elsevier. It was established in 2013 and is abstracted and indexed in the Astrophysics Data System, INSPE ...
''
* ''
Computational Geometry: Theory and Applications''
* ''
Computer-Aided Design
Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve c ...
'', SPM proceedings, IMR extended papers
* ''
Computer Aided Geometric Design'' (CAGD)
* ''
Computer Graphics Forum
A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic sets of operations known as ''programs'', wh ...
'' (Eurographics), special issue proceedings
* ''
Computer Methods in Applied Mechanics and Engineering''
* ''
Discrete and Computational Geometry''
* ''
Engineering with Computers''
* ''
Finite Elements in Analysis and Design''
* ''
International Journal for Numerical Methods in Engineering'' (IJNME)
* ''
International Journal for Numerical Methods in Fluids
The ''International Journal for Numerical Methods in Fluids'' is a Peer review, peer-reviewed scientific journal covering developments in numerical methods applied to fluid dynamics. It is published by John Wiley & Sons. Its editors-in-chief is Ch ...
''
* ''
International Journal for Numerical Methods in Biomedical Engineering''
* ''
International Journal of Computational Geometry & Applications
The ''International Journal of Computational Geometry and Applications'' (IJCGA) is a bimonthly journal published since 1991, by World Scientific. It covers the application of computational geometry in design and analysis of algorithms, focusing o ...
''
*
''Journal of Computational Physics (JCP)''
* ''
Journal on Numerical Analysis
A journal, from the Old French ''journal'' (meaning "daily"), may refer to:
*Bullet journal, a method of personal organization
*Diary, a record of personal secretive thoughts and as open book to personal therapy or used to feel connected to onesel ...
''
* ''
Journal on Scientific Computing'' (SISC)
*
''Transactions on Graphics (ACM TOG)''
*
''Transactions on Mathematical Software (ACM TOMS)''
*
''Transactions on Visualization and Computer Graphics (IEEE TVCG)''
* ''
Lecture Notes in Computational Science and Engineering'' (LNCSE)
* ''
Computational Mathematics and Mathematical Physics'' (CMMP)
Conferences
(Conferences whose primary topic is meshing are in bold.)
* Aerospace Sciences Meeting AIAA (15 meshing talks/papers)
* Canadian Conference on Computational Geometry CCCG
* CompIMAGE: International Symposium Computational Modeling of Objects Represented in Images
* Computational Fluid Dynamics Conference AIAA
* Computational Fluid Dynamics Conference ECCOMAS
* Computational Science & Engineering CS&E
* Conference on Numerical Grid Generation ISGG
* Eurographics Annual Conference (Eurographics)] (proceedings in
Computer Graphics Forum
A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic sets of operations known as ''programs'', wh ...
)
* Geometric & Physical Modeling SIAM
* International Conference on Isogeometric Analysis IGA
*
Symposium on Computational Geometry, International Symposium on Computational Geometry SoCG
* Numerical Geometry, Grid Generation and Scientific Computing (NUMGRID) (proceedings in
Lecture Notes in Computational Science and Engineering)
*
International Meshing Roundtable, SIAM IMR workshop. (Refereed proceedings and special journal issue.)
*
SIGGRAPH
SIGGRAPH (Special Interest Group on Computer Graphics and Interactive Techniques) is an annual conference centered around computer graphics organized by ACM, starting in 1974 in Boulder, CO. The main conference has always been held in North ...
(proceedings in
ACM Transactions on Graphics)
*
Symposium on Geometry Processing SGP (
Eurographics
Eurographics is a Europe-wide professional computer graphics association. The association supports its members in advancing the state of the art in computer graphics and related fields such as multimedia, scientific visualization and human–compu ...
) (proceedings in
Computer Graphics Forum
A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic sets of operations known as ''programs'', wh ...
)
* Symposium on Physical Modeling SPM
Solid Modeling Association* World Congress on Engineering
Workshops
Workshops whose primary topic is meshing are in bold.
* Conference on Geometry: Theory and Applications CGTA
* European Workshop on Computational Geometry EuroCG
* Fall Workshop on Computational Geometry
* Finite Elements in Fluids FEF
* MeshTrends Symposium (in WCCM or USNCCM alternate years)
* Polytopal Element Methods in Mathematics and Engineering
* Tetrahedron workshop
See also
*
Chazelle polyhedron
Chazelle polyhedron is a non-convex polyhedron constructed by removing pieces of wedges from both top and bottom of a cube's sides, leaving the notches. Its saddle surface can be considered as the set of line segments that lie forming the hyperb ...
*
*
*
Grid classification
*
Mesh parameterization Given two surfaces with the same topology, a bijective mapping between them exists. On triangular mesh surfaces, the problem of computing this mapping is called mesh parameterization. The parameter domain is the surface that the mesh is mapped ont ...
*
Meshfree methods
In the field of numerical analysis, meshfree methods are those that do not require connection between nodes of the simulation domain, i.e. a mesh, but are rather based on interaction of each node with all its neighbors. As a consequence, origin ...
*
Parallel mesh generation
*
Principles of grid generation
*
Polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedron, polyhedral object's surface. It simplifies Rendering (computer graphics), rendering, as in a wire-frame model. The fac ...
*
Regular grid
A regular grid is a tessellation of ''n''-dimensional Euclidean space by Congruence_(geometry), congruent parallelepiped#Parallelotope, parallelotopes (e.g. bricks). Its opposite is Unstructured grid, irregular grid.
Grids of this type appear on ...
*
*
Stretched grid method
The stretched grid method (SGM) is a Numerical analysis, numerical technique for finding approximate solutions of various mathematical and engineering problems that can be related to an elastic grid behavior.
In particular, meteorologists use the ...
*
Tessellation (computer graphics)
In computer graphics, tessellation is the dividing of datasets of polygons (sometimes called ''vertex sets'') presenting objects in a scene into suitable structures for Rendering (computer graphics), rendering. Especially for Real-time computer ...
*
Types of mesh
*
Unstructured grid
An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis wh ...
References
Bibliography
*.
*.
*
*
*.
*
CGAL
The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) a ...
The Computational Geometry Algorithms Library
*
*
*
* Jan Brandts, Sergey Korotov, Michal Krizek: "Simplicial Partitions with Applications to the Finite Element Method", Springer Monographs in Mathematics, (2020). url="https://www.springer.com/gp/book/9783030556761"
Grid Generation Methods - Liseikin, Vladimir D.
External links
Periodic Table of the Finite Elements
;Mesh generators
Many commercial product descriptions emphasize simulation rather than the meshing technology that enables simulation.
*Lists of mesh generators (external):
*
ANSA Pre-processor
*
ANSYS
*
CD-adapco and
Siemens DISW
Comet Solutions*
CGAL
The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) a ...
Computational Geometry Algorithms Library
*
Mesh generation*
2D Conforming Triangulations and Meshes*
3D Mesh GenerationCUBIT
Ennova*
Gmsh
Hextreme meshesMeshLab*
MSC Software
MSC Software Corporation is an American simulation software technology company based in Newport Beach, California, that specializes in simulation software.
In February 2017, the company was acquired by Swedish technology company Hexagon AB fo ...
Omega_hTri/Tet Adaptivity
Open FOAMMesh generation and conversion
module
*
TetGen
TetWild
; Multi-domain partitioned mesh generators
These tools generate the partitioned meshes required for multi-material finite element modelling.
MDMMultiple Domain Meshing) generates unstructured tetrahedral and hexahedral meshes for a composite domain made up of heterogeneous materials, automatically and efficiently
QMDM(Quality Multi-Domain Meshing) produces a high quality, mutually consistent triangular surface meshes for multiple domains
QMDMNG (Quality Multi-Domain Meshing with No Gap), produces a quality meshes with each one a two-dimensional manifold and no gap between two adjacent meshes.
SOFA_mesh_partitioning_toolsgenerates partitioned tetrahedral meshes for multi-material FEM, based on CGAL.
; Articles
Another Fine Mesh, MeshTrends Blog, PointwiseMesh Generation group on LinkedIn
; Research groups and people
Mesh Generation people on Google ScholarDavid Bommes, Computer Graphics Group, University of Bern*
Jonathan Shewchuk'
Meshing and Triangulation in Graphics, Engineering, and Modeling*
Scott A. Mitchell
Robert Schneiders
; Models and meshes
Useful models (inputs) and meshes (outputs) for comparing meshing algorithms and meshes.
HexaLabhas models and meshes that have been published in research papers, reconstructed or from the original paper.
Princeton Shape Benchmark
Shape Retrieval Contest SHREChas different models each year, e.g.,
*
Shape Retrieval Contest of Non-rigid 3D Watertight Meshes 2011Thingi10kmeshed models from th
Thingiverse
; CAD models
Modeling engines linked with mesh generation software to represent the domain geometry.
ACIS by SpatialOpen Cascade
; Mesh file formats
Common (output) file formats for describing meshes.
NetCDFXDMFVTK/VTUANSYS mesh*
OFF
Off or OFF may refer to:
Art and entertainment
* ''Off'' (video game), a video game by Mortis Ghost.
*Sven Väth, German DJ and singer who uses the pseudonym OFF
* ''Off'' (album), by Ciwan Haco, 2006
* ''Off!'' (album), by Off!
* Off!, an Ameri ...
*
Wavefront OBJ
*
PLY
*
STL
meshiocan convert between all of the above formats.
; Mesh visualizers
BlenderMesh ViewerParaview
; Tutorials
{{Authority control
Mesh generation people
Mesh generators
Geometric algorithms
Computer-aided design
Triangulation (geometry)
Numerical analysis
Numerical differential equations
Computational fluid dynamics
3D computer graphics