Mesh generation
Encyclopedia
Mesh generation is the practice of generating a polygon
al or polyhedral
mesh
that approximates a geometric domain. The term "grid generation" is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as finite element analysis or computational fluid dynamics
. The input model form can vary greatly but common sources are CAD, NURBS, B-rep and STL (file format)
. The field is highly interdisciplinary, with contributions found in mathematics
, computer science
, and engineering
.
Three-dimensional meshes created for finite element analysis need to consist of tetrahedra
, pyramid
s, prism
s or hexahedra
. Those used for the finite volume method
can consist of arbitrary polyhedra
. Those used for finite difference method
s usually need to consist of piecewise structured arrays of hexahedra known as multi-block structured meshes.
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
al or polyhedral
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
mesh
Polygon mesh
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
that approximates a geometric domain. The term "grid generation" is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as finite element analysis or computational fluid dynamics
Computational fluid dynamics
Computational fluid dynamics, usually abbreviated as CFD, is a branch of fluid mechanics that uses numerical methods and algorithms to solve and analyze problems that involve fluid flows. Computers are used to perform the calculations required to simulate the interaction of liquids and gases with...
. The input model form can vary greatly but common sources are CAD, NURBS, B-rep and STL (file format)
STL (file format)
STL is a file format native to the stereolithography CAD software created by 3D Systems. This file format is supported by many other software packages; it is widely used for rapid prototyping and computer-aided manufacturing. STL files describe only the surface geometry of a three dimensional...
. The field is highly interdisciplinary, with contributions found in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, and engineering
Engineering
Engineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...
.
Three-dimensional meshes created for finite element analysis need to consist of tetrahedra
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
, pyramid
Pyramid (geometry)
In geometry, a pyramid is a polyhedron formed by connecting a polygonal base and a point, called the apex. Each base edge and apex form a triangle. It is a conic solid with polygonal base....
s, prism
Prism (geometry)
In geometry, a prism is a polyhedron with an n-sided polygonal base, a translated copy , and n other faces joining corresponding sides of the two bases. All cross-sections parallel to the base faces are the same. Prisms are named for their base, so a prism with a pentagonal base is called a...
s or hexahedra
Hexahedron
A hexahedron is any polyhedron with six faces, although usually implies the cube as a regular hexahedron with all its faces square, and three squares around each vertex....
. Those used for the finite volume method
Finite volume method
The finite volume method is a method for representing and evaluating partial differential equations in the form of algebraic equations [LeVeque, 2002; Toro, 1999]....
can consist of arbitrary polyhedra
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
. Those used for finite difference method
Finite difference method
In mathematics, finite-difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives.- Derivation from Taylor's polynomial :...
s usually need to consist of piecewise structured arrays of hexahedra known as multi-block structured meshes.
See also
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Fortune's algorithmFortune's algorithmFortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O time and O space...
- Polygon meshPolygon meshA polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
- Regular gridRegular gridA regular grid is a tessellation of n-dimensional Euclidean space by congruent parallelotopes . Grids of this type appear on graph paper and may be used in finite element analysis as well as finite volume methods and finite difference methods...
- Ruppert's algorithmRuppert's algorithmIn mesh generation, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm for creating quality Delaunay triangulations. The algorithm takes a planar straight-line graph and returns a conforming Delaunay triangulation of only quality triangles...
- TessellationTessellationA tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
- Unstructured gridUnstructured gridAn unstructured 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...
External links
- Bubble Mesh ... Physically-based triangulation, a research project held by IBM
- Mesh generation in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, the Computational Geometry Algorithms Library:
- Mesh generators list, a list of public domain and commercial mesh generators