Mesh generation
s of a curved domain Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells.
≈ 12 min read
Mesh generation. encyclopegia.org, snapshot enwiki-001348218866. /a/mesh-generation
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
s of a curved domain 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.…
s of a curved domain]] 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.
For a nozzle, with the describing function y = x^2 the grid can easily be generated using uniform division in y-direction with equally spaced increments in x-direction, which are described by \xi=x \, \eta = \frac{y}{y_\max} \, where y_\max denotes the y-coordinate of the nozzle wall. For given values of ( \xi , \eta ), the values of ( x , y ) can be easily recovered.
Elliptic schemes
Elliptic PDEs generally have very smooth solutions leading to smooth contours. Using its smoothness as an advantage Laplace's equations can preferably be used because the Jacobian found out to be positive as a result of maximum principle for harmonic functions.
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, 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 (x,y) on the boundary of the physical domain, with the interior point distribution determined through the solution of equations written below \xi_{xx} + \xi_{yy} = P(\xi, \eta) \eta_{xx} + \eta_{yy} = Q(\xi, \eta) where,
(\xi,\eta) 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, \alpha x_{\xi\xi} -2\beta x_{\xi\eta} + \gamma x_{\eta\eta} = -I^2 (Px_\xi + Qx_\eta) \alpha y_{\xi\xi} -2\beta y_{\xi\eta} + \gamma y_{\eta\eta} = -I^2 (Py_\xi + Qy_\eta) where \begin{align} \alpha & = x^2_\eta + y^2_\eta \\ \beta & = x_\eta x_\xi + y_\xi y_\eta \\ \gamma & = x^2_\xi + y^2_\xi \\ I & = \frac{\delta(x, y)}{\delta(\xi, \eta)} = y_\eta x_\xi - y_\xi x_\eta \end{align} These systems of equations are solved in the computational plane on uniformly spaced grid which provides us with the (x,y) 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 \Delta\xi = \Delta\eta = 1 , the inverse of the Jacobian is given by, x_\xi y_\eta - x_\eta y_\xi = I where I 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 d\xi = 0 = \xi_x \, dx + \xi_y \, dy.
For \xi and \eta surfaces to be perpendicular the equation becomes x_\xi x_\eta + y_\xi y_\eta = 0. The problem associated with such system of equations is the specification of I . Poor selection of I 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 or the Poisson's equation and especially treating the parts which controls elliptic behavior.
The initial values are given as the coordinates of the point along the surface \eta = 0 and the advancing the solutions to the outer surface of the object satisfying the boundary conditions along \xi 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 smoothness, orthogonality 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 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 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 to cell instead of grid to grid and hence the more memory space is needed. Due to random cell location, the solver efficiency 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. The grid point with high resolution creates difficulty for both structured and unstructured. For example, in case of boundary layer, structured scheme produces elongated grid in the direction of flow.
On the other hand, unstructured grids require a higher cell density in the boundary layer because the cell needs to be as equilateral 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 mesh. We can choose to locate the arbitrary 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 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 equations 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 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 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 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 equations of the physical problem and those describing the grid movement is required.
Bibliography
CGAL The Computational Geometry Algorithms Library Grid Generation Methods - Liseikin, Vladimir D. Mesh Generation people on Google Scholar David Bommes, Computer Graphics Group, University of Bern David Eppstein's Geometry in Action, Mesh Generation Jonathan Shewchuk's 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. HexaLab has models and meshes that have been published in research papers, reconstructed or from the original paper.
Princeton Shape Benchmark Shape Retrieval Contest SHREC has different models each year, e.g., Shape Retrieval Contest of Non-rigid 3D Watertight Meshes 2011 Thingi10k meshed models from the Thingiverse CAD models Modeling engines linked with mesh generation software to represent the domain geometry. ACIS by Spatial Open Cascade Mesh file formats Common (output) file formats for describing meshes.
NetCDF Genesis/Exodus XDMF VTK/VTU MEDIT MED/Salome Gmsh ANSYS mesh OFF Wavefront OBJ PLY STL meshio can convert between all of the above formats. Mesh visualizers Blender Mesh Viewer Paraview Tutorials Cubit tutorials
Text derived from https://en.wikipedia.org/w/index.php?oldid=1348218866 under CC BY-SA 4.0; modifications have been made.