thggstd.html

有限元学习研究用源代码(老外的),供科研人员参考

In this part, we consider different questions connected with grid
generation. At first, we give an overview over usual grid generation
techniques.

 <p>Then we consider in detail some of the requirements for the grid
generation algorithm we need: the question of numerical stability and
the requirements of anisotropic grid generation.
 <p>At last, we consider in detail the grid generation algorithm which
we consider as optimal for our application and which we have
implemented in the grid generation package IBG.

<h1><a NAME="ggmethods">Popular Grid Generation Technics </a></h1>


In this section we consider shortly some popular grid generation
technics. This section cannot be considered as an overview over the
existent literature. Since grid generation is part of the majority of
computer simulations, there is a great number of publications about
grid generation, so such an overview will be beyond the scope of this
thesis. So we refer only a small subset of the existing
literature. So, almost all applications considered here are connected
with semiconductor technology. For other overviews see
 <a HREF="thbib.html#Castillo1991"> [Castillo1991] </a>,
 <a HREF="thbib.html#Glowinski1990"> [Glowinski1990] </a>,
 <a HREF="thbib.html#George1991"> [George1991] </a>,
 <a HREF="thbib.html#Flaverty1989"> [Flaverty1989] </a>.

  <p> The subdivision of the different algorithms into the methods
listed here is obviously artificial. Let's start with methods to create
a new grid:

 
 <dl>
 <dt><a HREF="thggstd.html#mgmanu">Manual</a>
 <dd> methods for cases with relatively simple geometries.

 
 <dt><a HREF="thggstd.html#mgtensor">Tensor product grids</a>
 <dd> of lower dimensional grids.

 
 <dt><a HREF="thggstd.html#mgmapp">Mapping methods</a>
 <dd> from a grid with simple geometry (rectangle, triangle) into the real
domain (curvilinear coordinates).

 
 <dt><a HREF="thggstd.html#mgcomp">Composition</a>
 <dd> of the grid from sub-grids on simpler subsets.

 
 <dt><a HREF="thggstd.html#mgfront">The advancing front algorithm</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgtree">The quadtree/octree approach</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgbcomp">Element removal</a>
 <dd> may be used to create a grid inside a region.

 
 <dt><a HREF="thggstd.html#mgDelaunay">Delaunay method</a>
 <dd> allows to create a grid for a given set of points.

 
 </dl>


There are also a lot of methods to change a previously defined grid. Usually
the previously listed grid generation methods will be combined with some of
these grid transformations to obtain the resulting grid. But often only these
transformations will be used, for example in time dependent problems to obtain
the new grid from the grid for the previous time step.

 
 <dl>
 <dt><a HREF="thggstd.html#mgrefine">Local refinement</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mginsert">Point insertion</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgcoarse">Grid coarsening</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgswap">Local transformations</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgshift">Point shifting</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgsmooth">Grid smoothing</a>
 <dd>
 
 <dt><a HREF="thggstd.html#mgdeformation">Grid deformation</a>
 <dd>
 
 </dl>



We consider here only methods for the generation of a single grid. But there
are also a lot of numerical methods which don't work with a single grid, but
use many different grids:

 
 <ul>
 <li> Multi-grid methods use a set of grids for the entire domain with
different number of points. Usually the points of the "coarser" grids
are a subset of the points of the "finer" grids. The coarser grids
will be used to obtain a good approximation or correction for the
solution on the finest grid very fast.
 
 <li>Domain decomposition uses a subdivision of the entire domain into several
parts. Usually this will be done on parallel computers --- every processor has
to solve the equation on some sub-domain.
 
 <li> Using overlapping grids is a variant of <a HREF="thggstd.html#mgcomp">composition</a>. But here the result is not a unique
grid. So the grid generation step is easier, because the different
parts of the grid must not be unified, but the solution process is
much more complicate.  To obtain a good description of the boundary
often <a HREF="thggstd.html#mgmapp">mapping</a> will be used.
 
 <li>Using multiple structured grids is a variant of the last method. Here different
regular grids will be used to obtain an analog of local refinement --- on the
critical part of the region a regular finer grid will be considered. The
advantage is the possibility to use more efficient algorithms (fast vector
routines on vector processors) since all grids are regular.
 
 </ul>


 
<h2><a NAME="mgmanu">Manual Grid Generation</a> </h2>


Here we can distinguish between enumerative methods (if the points, edges,
faces and elements of the mesh are explicitly given) and methods for special
simple geometries (for example a rectangle) there the connectivity is known in
advance.
  <p> These methods can be used only for relatively simple
geometries. Often they are used for the creation of coarse grid, and
<a HREF="thggstd.html#mgrefine">refinement</a> will be used to
create the resulting grid. Enumerative grid description can be also
used as a format for data transfer. Often possibilities for manual
grid generation are part of CAD systems, so that the input of
geometrical data (with the mouse) is easy for the user.

 
<h2><a NAME="mgtensor">Tensor Product Grids </a> </h2>


Tensor product grids are a simple possibility to obtain a higher dimensional
grid from lower dimensional grid generators. There will be three possibilities:

 
 <ul>
 <li>a 2D grid from two 1D grids (regular rectangular grid)
 
 <li>a 3D grid from three 1D grids (regular hexahedral grid)
 
 <li>a 3D grid from a 2D grid and a 1D grid (regular prismatic grid)
 
 </ul>


These methods allow to use the local refinement possibilities of the lower
dimensional grid generator for the higher dimension. But this refinement is not
local for the higher dimension. This leads to a lot of unnecessary points. This
methods can be successfully used if the problem itself has approximately a
tensor product structure. The regular structure of the resulting grid can be
exploited for parallelization.
  <p> Because of it's simplicity this method is very often used in
applications.  It can be used also as a start grid for other methods like
<a HREF="thggstd.html#mgrefine">refinement</a> or for the grid
generation on the simple parts of the <a HREF="thggstd.html#mgcomp">composition method</a>.

 
<h2><a NAME="mgmapp">Mapping Methods </a> </h2>


Here we have a mapping function which maps the mesh of an easy reference
domain onto the real domain.
  <p>There are different possibilities to build such a mapping. Usually we start
with an identification of some key points of the reference domain and the real
domain (for example the corners of the reference rectangle on the real
boundary). Then an interpolation formula has to be found, at first for
boundary lines, (in 3D also for boundary faces) and than for the inner part of
the domain. Often easy interpolation formulas will be used, but it is also
possible to solve numerically partial differential equations for this
interpolation to obtain better mesh quality.
  <p>The computation of the interpolation functions (especially if differential
equations will be used) is usually fully automatic, but some information
usually has to be fixed or defined "by hand" --- for example the topological
information or some key points. The algorithm creates good meshes if the form
of the real domain is not too far from the form of the reference domain,
sometimes also if it is far away. The grid in the inner of the domain,
especially the point density, depends on the form of the boundary, not of the
local characteristics of the problem. So this method often will be used in
fluid dynamics. Here the flow depends on the boundary, and often it is
possible to create grid so that the curved coordinate directions approximately
coincide with the flow direction (streamline coordinates).
  <p> This method can be used also locally for <a HREF="thggstd.html#mgcomp">the composition method</a>.  For time-dependent
problems it can be used if the geometry doesn't change very much,
especially if the topology doesn't change.

 
<h2><a NAME="mgcomp">Composition</a> </h2>


Here the region will be divided into simpler subregions. Then one of
the other methods like <a HREF="thggstd.html#mgmanu">manual</a>,
<a HREF="thggstd.html#mgtensor">tensor product</a>, <a HREF="thggstd.html#mgmapp">mapping</a> will be used to create a
mesh on the subregion, and at last the meshes of the subregions will be
composed into the final grid.
  <p> The work of subdividing the initial region often has to be done
"by hand". It seems difficult to automate this process (see
 <a HREF="thbib.html#Joe1986"> [Joe1986] </a> for such an algorithm). So
it often will be used in CAD system so that interactive control can be
used. In some sense the <a HREF="thggstd.html#mgtree">octree</a>
can be considered as an automatic variant of this algorithm.

 
<h2><a NAME="mgfront">Advancing Front Algorithm</a> </h2>


Here we start with a given grid on the boundary. The "front" will be
initialized by the boundary grid. Then successive triangles (2D) or
tetrahedra (3D) will be created on the inner side of the front. Then
the front will be updated. The point density inside the region depends
on the given boundary discretization, but can be controlled often by
additional external criteria.  The algorithm is fully
automatic. See, e.g.
 <a HREF="thbib.html#Jin1993"> [Jin1993] </a>,
 <a HREF="thbib.html#Paolini1988"> [Paolini1988] </a>,
 <a HREF="thbib.html#Lo1991"> [Lo1991] </a>.
  <p>The main problem is to avoid self-intersections of the front. There must be
used fast self-intersection search algorithms. Another problem, especially for
3D and/or time-dependent problems, is to obtain the initial boundary grid. A
change in the boundary mesh usually leads to a big change in the inner of the
domain. Especially in 3D the algorithm is very difficult to implement.

 
<h2><a NAME="mgtree">Quadtree/Octree Approach </a> </h2>


We start with a regular rectangular coarse grid. Then the rectangles
(cubes) will be locally subdivided into smaller rectangles (cubes). In
regions where the refinement density changes the rectangles (cubes)
with different refinement levels on their edges will be subdivided
into other elements (triangles, tetrahedra, prisms). Usually
regularization techniques will be used to avoid bad elements in these