Regular grid
A grid in the geometry is a complete and non-overlapping partition of a region of space by a set of grid cells. The lattice cells are defined by a set of grid points, which are interconnected by a set of grid lines.
Gratings are used in science and technology for measuring, modeling, and for numerical calculations.
- 2.1 triangular lattice
- 2.2 Adaptive Grid
- 3.1 technology
- 3.2 Surveying
- 3.3 Numerical Mathematics
Classification
Based on their topology and geometry mesh are divided into different categories. It is fundamentally different between structured and unstructured grids.
Structured grid
Structured grids (English structured grids ) have a regular topology, but not necessarily a regular cell geometry. For structured grids, the cells are in a regular grid, so that the cells can be indexed by integer numbers clearly. One-dimensional grid ( grid line ) are always structured, the cells can be obtained by counting by i = 1. N ( N = number of elements). Two-dimensional grid is an element by the indices ( i, j), wherein the three-dimensional by the indices (i, j, k) is unique. Advantage of using structured grids over the unstructured grid described below is that it is possible through this unique indexing neighboring cells determine without computational effort. Structured grid always consist of an element type. In the two-dimensional rectangular elements and rarely triangular elements are most often used. Three-dimensional lattice are almost always hexahedron and only sometimes tetrahedron. The use of triangular elements or tetrahedron has the disadvantage that they fill the space poorly and more elements are necessary. Thus, a tetrahedron having an edge length of 1, only a volume of 1/6 as a cube having a volume of 1. Therefore need approximately for flow simulation tetrahedral mesh very many cells use to achieve sufficient resolution.
In the lattice structured complex structures are possible in which the grid system is regularly, but overall curved or adapted to a complex geometry. As multiblock structures can be used, in which the grating is formed from a plurality of structured blocks of different size. Such structured grid can only be semi-automatically create.
For curved gratings ( English curvilinear grid), the grid lines are given by parametric curves. The term is rather uncommon. One then speaks simply of structured grids.
Rectangular grid (English rectilinear grids ) divide the space completely in parallel to the axes areas, which need not be equal. In three-dimensional space arise as cuboids of different or the same size.
A uniform grid (English regular grid) divides the space completely in axis-parallel rectangular regions, edges along an axis always have the same length.
The simplest case is a Cartesian grid (English Cartesian grid), in which all edge lengths are equal. In two-dimensional space is created a square face and three-dimensional volume of cubes.
Unstructured grid
Unstructured grids ( unstructured grids English ) have no fixed topology and no uniform grid cell geometry. Unstructured grids are usually the result of an adaptation process. Even lattice of complex cells called Polyedergitter are known. The cell structure is similar to here the soap scum.
Unstructured grids are to be used very flexible and can be generated automatically also easy. Data management is, however, more complex than in structured grids. On one hand, the grid points are not arranged as in structured grids in a regular pattern, but must be stored separately. On the other hand it is clear even from the outset, what are the neighboring cells to a specific cell in the grid. Also this neighborhood information must either be stored explicitly in the mesh generation or at run time are calculated consuming. Therefore unstructured grids generally require a multiple of the memory requirements of structured grids and usually cause a higher computational effort.
Grid generation
As grid generation or meshing refers to a group of methods in computer graphics, in which a given surface or into a given volume of space is approximated by a number of smaller, mostly very simple elements ( approximated ) is. The resulting grid is a simplified description of the surface, which can be used eg for further calculations then, about using the finite element method ( FEM).
For two-dimensional surfaces are used in the mesh generation most commonly triangular or quadrilateral elements for application in three-dimensional bodies usually tetrahedral or square.
The generation of a grid of triangular elements is also known as triangulation (or triangulation ) refers (just like the resulting triangle mesh ), the generation of a grid of square elements also means Paving. If the number of outer edges of a surface fixed and of an odd number, so not a pure square - Paving is possible (there is at least one element with an odd number of vertices, eg a triangle).
Triangular lattice
As a triangle mesh, triangle mesh or triangulation is referred to in trigonometry and elementary geometry, the division of a surface into triangles. Seen graph theory, triangular lattice of type " undirected graph without multiple edges " whose subgraphs " circles with three nodes " (and correspondingly three edges) are. The generalization of triangle meshes are meshes.
A triangulation of a set of points in the plane referred to a decomposition of the convex hull of the set of points in the triangles, the vertices of the triangles are exactly the points from. Thus, the triangulation is a plane triangulation. If the amount is in convex position, then the number of possible triangulations exactly the th Catalan number, where the number of points referred to.
Often it is of interest to compute a triangulation with special properties. For example there is the Delaunay triangulation which avoids sharp angles in triangles, or minimum -weight triangulation which minimizes the total length of all edges.
Adaptive grid
It is further distinguished between adaptive and non-adaptive discretizations.
Not Adaptive grids have everywhere the same resolution. For small geometric structures or areas with strong curves, sharp angles or different material parameters defined a coarse grid with large grid cells is no longer sufficient to adequately discretize also those problem areas accurately. A global refinement of the grid is usually not meaningful due to the associated increased memory and computational time required.
Here, the method of adaptive grid generation accesses (english adaptive meshing ) that where large errors are expected, the grid selects fine. This is done either by a priori knowledge about the problem under consideration, or by methods which refine from the given error estimates dynamically where the error is just great. The latter is especially important for transient problems, that is, when the problematic points in the change over time of their position.
Another method for discretization of critical areas is the sub- grid technology.
Applications
Technology
- In the technical design theory for modeling curved surfaces, particularly in the context of computer-aided design ( CAD)
- In robotics, for the determination of joint positions; induced to yield highly dynamic triangle meshes that represent the movement
- In the building industry for the measurement of a building with triangles: Here were triangulated meshes - mainly rectangular ( 3:4:5 ) and equilateral - already in the building huts in the Gothic usual. Modern applications are CAM methods
Surveying
- In geodesy as a surveying network for point determination, see Triangulation (geodesy ): By means of the network are trigonometric points (TP ) was measured as survey points
- Here are at zeilenweisem sampling square nets widespread (but can be easily converted into triangle meshes to make it to the specific algorithms available ) - For the photogrammetry for detecting the data
- In the GIS technology and other satellite-based measurement methods for converting the mostly linear series of measurements on an earth model
Numerical Mathematics
As a computational grid is referred to in numerical mathematics a discrete decomposition of the space on which a partial differential equation to be solved. For a time discretization of the term is not commonly used. The intersection of two grid lines are referred to as nodes, cells, either as cell, in finite element method as well as elements, and the finite volume method as a volume. The grid can be spatially stationary or move with the times or be adapted in the course of the invoice.
At the edges of the region boundary conditions must be prescribed.
Computational grid need not be one-dimensional. For three-dimensional lattices very large numbers of cells can be achieved quickly. A simple rectangular grid, which dissolves at an edge 100 cells in the third dimension has been 1 million cells.
On modern PC with 2 GB of main memory about 1.5-5 million cells can be calculated depending on the software system today. If higher resolution is required, then the calculation on mainframe computers or computer networks must be performed.
Examples
Grid generation in computer graphics
A planar triangular mesh for FEM modeling
Adaptive flat triangle mesh for FEM modeling