thggstd.html

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

regions (one-level difference rule). To organize this regularization
different techniques may be used (propagation, recursive calls,
another variant see <a HREF="thbib.html#Yang1992"> [Yang1992] </a>).
  <p>This method can be considered as a localization of the
 <a HREF="thggstd.html#mgtensor">tensor product method</a> to
avoid the global refinement effect of local refinement.  It is
possible to generalize this method also to prismatic grids (see
 <a HREF="thbib.html#Siebert1993"> [Siebert1993] </a>).
  <p>This method allows anisotropic refinement. The numerical quality of the
resulting grid (at least in the inner of the domain) is ideal as for standard
FEM as for finite volume discretization also in the case of anisotropic
refinement. The grid in the inner of the domain doesn't change if the boundary
changes.
  <p>A problem for the refinement in this approach is that anisotropic refinement
works only in directions which are parallel to the coordinate axes. In other,
skew directions we obtain de-facto only isotropic refinement.
  <p> The resulting grid doesn't contain the real boundary. So this
method has to be combined with a <a HREF="thggstd.html#mgbcomp">boundary computation</a> methods.
  <p> Often quadtrees and octrees will be used for other reasons. They
are an ideal data structure for search operations. In 3D this method
often will be used only for the generation of a point set which will
be triangulated with the <a HREF="thggstd.html#mgDelaunay">Delaunay</a> method (see
 <a HREF="thbib.html#Schroeder1990"> [Schroeder1990] </a>,
 <a HREF="thbib.html#Shepard1991"> [Shepard1991] </a>,
 <a HREF="thbib.html#Ramakrishnan1992"> [Ramakrishnan1992] </a>,
 <a HREF="thbib.html#Tanigushi1993"> [Tanigushi1993] </a>).
 We also use this combination.

 
<h2><a NAME="mgbcomp">Boundary Computation</a> </h2>


The region of interest will be included into a grid which is defined
in an independent way and not connected with the boundary grid of the
region. This may be a regular grid, but it may be also a more
complicate grid obtained by the <a HREF="thggstd.html#mgtree">octree</a> method or <a HREF="thggstd.html#mgrefine">refinement</a>. Elements which do not intersect the
region will be removed, purely internal elements become part of the
grid. For elements intersecting the boundary there are different
possibilities:

 
 <ul>
 <li>They can be considered as parts of the grid. So we obtain only a coarse
approximation of the boundary.
 
 <li> They can be splitted into a part inside and outside the
domain. For this purpose <a HREF="thggstd.html#mginsert">point
insertion</a> can be used.
 
 <li> They can be modified by <a HREF="thggstd.html#mgbshift">shifting points </a> to the boundary so that they will be
completely inside or outside the domain.
 
 <li> They may be transformed using <a HREF="thggstd.html#mgswap">local transformations</a> so that the resulting element
will be completely inside or outside the domain.
 
 </ul>


 
<h2><a NAME="mgDelaunay">Delaunay Method </a> </h2>


The Delaunay grid is a grid which is uniquely (modulo degenerate
cases) defined for an arbitrary set of points. It is the dual to the
Voronoi tessalation (
 <a HREF="thbib.html#Voronoi1908"> [Voronoi1908] </a>,
 <a HREF="thbib.html#Delaunay1934"> [Delaunay1934] </a>).
 There is a well-known algorithm for the generation of a Delaunay grid
--- the Watson algorithm. The algorithm is sequential. In every step
of the algorithm one point will be included into an existing Delaunay
grid, creating a new Delaunay grid (see
 <a HREF="thbib.html#Bowyer1981"> [Bowyer1981] </a> - <a HREF="thbib.html#Dey1992"> [Dey1992] </a> for algorithms for Delaunay grid generation). This step
can be used also for the modification of an existing grid by
 <a HREF="thggstd.html#mginsert">point insertion</a>.
  <p>Often the Delaunay grid will be used as a start grid for further
modifications. Such modifications are necessary especially in 3D FEM
applications, because there may be degenerate tetrahedra in the Delaunay grid
which create big problems in FEM discretizations (so called slivers).
  <p>Another problem of the algorithm is that in the resulting grid the boundary may
be intersected by edges and elements. So grid modifications, for example
 <a HREF="thggstd.html#mginsert">point insertion</a> or <a HREF="thggstd.html#mgswap">local transformations</a> are necessary
to obtain a correct geometry.
  <p> The quality of the resulting grid naturally depends on the set of
points used.  Often this set will be defined by other methods --- for
example <a HREF="thggstd.html#mgtree">the octree
method</a>. Often the Delaunay grid of the previous step will be
used to define new points on places where the grid quality is bad or
the grid is too coarse.
  <p>
 
<h2><a NAME="mgrefine">Local Refinement </a> </h2>


Here we start with a "coarse" grid created by another method like <a HREF="thggstd.html#mgmanu">manual grid generation</a>, <a HREF="thggstd.html#mgtensor">tensor product grids</a>. This grid
will be refined locally to obtain high point density only in regions
where it is necessary. We don't consider here the refinement criteria
--- this is a very complicate problem which has to be considered
separately for every concrete equation. There are different techniques
to refine a grid:

 
 <ul>
 <li> the bisection method. Here a triangle or tetrahedron will be
refined by dividing one of the edges into two parts. There are different
possibilities to define which edge has to be refined if the element has to be
refined (the longest edge or a specially marked edge).

 
 <li> the PLTMG-algorithm: regular ("red") triangles will be refined
regularly.  For triangles with neighbours with higher refinement level
some special irregular ("green") refinement will be used (see
 <a HREF="thbib.html#Bank1983"> [Bank1983] </a>,
 <a HREF="thbib.html#Bank1990"> [Bank1990] </a>).

 
 <li> A generalization of the PLTMG-algorithm for 3D is possible, but much more
complicate.

 
 </ul>


Usually the numerical quality of the elements of the refined grid is
not so good as in the coarse grid. Upper bounds for this effect are
possible. Often other techniques (<a HREF="thggstd.html#mgsmooth">grid smoothing</a>,
<a HREF="thggstd.html#mgswap">local transformations</a>) will be used to obtain
better grid quality.
  <p>Local refinement often will be used for grid generation in multi-grid methods.

 
<h2><a NAME="mginsert">Point Insertion </a> </h2>


This method can be considered as a variant of the local refinement. But
we consider it here as a separate method. To include a point we have different
possibilities:

 
 <ul>
 <li> For Delaunay grids we can use the <a HREF="thggstd.html#mgDelaunay"> Watson algorithm </a>.
 
 <li> We can find the element containing the new point and subdividing
this element.  To avoid bad grid quality this can be combined with
<a HREF="thggstd.html#mgswap">local transformations</a>.
 
 </ul>


Point insertion can be used also to increase grid quality inside a
region. So it is possible to start with the Delaunay grid created by
given boundary points --- a very coarse grid --- and to include points
in the region. The resulting grid depends on the strategy used for
point insertion. One strategy is to detect bad elements and to insert
a point into such elements.  The necessary set of points can be
created also independent by other grid generation methods (<a HREF="thggstd.html#mgtensor">tensor product grids</a> or <a HREF="thggstd.html#mgtree">the octree method</a>).
  <p>Point insertion will be used also to correct the grid near the boundary. So in
the Delaunay grid there may be edges going through the boundary. Here we can
insert a new boundary point at the place of the intersection with the boundary.
Point insertion also can be used to eliminate slivers.

 
<h2><a NAME="mgcoarse">Grid Coarsening </a> </h2>


This is the inverse operation to <a HREF="thggstd.html#mgrefine">refinement</a>. Especially in time-dependent problems with moving
fronts the grid may be too fine in the parts of the grid behind the
front. For these cases grid coarsening combined with <a HREF="thggstd.html#mgrefine">refinement</a> is a fast alternative
to the creation of a new grid.
  <p>The grid coarsening algorithm usually depends on the refinement algorithm used.
Often some information of the refinement history (for example the order of
point creation) have to be saved to make coarsening possible. Then we have to
identify refinement patterns which can be reversed.
  <p>Another possibility, which doesn't depend on the refinement algorithm used, is
to mark some points which have to be removed. Removing a point is in general not
so easy as to include a new point.  Points which are part of only three triangles
or four tetrahedra can be easily removed, but this is a very rare situation. So
the environment of the point usually has to be rebuilt to create such a
situation.

 
<h2><a NAME="mgswap">Local Element Transformations </a> </h2>


These are local operations changing the grid without changing the points of the
grid. The most important example is the 2D "edge swapping" procedure. Here two
neighbour triangles will be replaced by two other triangles by replacing the
common edge of the old triangles by the line connecting the other two points.
This operation is possible if this line is inside the union of the two
triangles. Usually this operation is enough for 2D problems. For example, using
only this operation every 2D grid can be transformed into the Delaunay grid.
  <p>In 3D the situation is more complicate. The generalization of the edge swapping
procedure is not symmetric. It creates (or deletes) one new edge, and often we
have situations where it is not possible to use this operation. So it seams
necessary to consider also other, more complicate local transformations.
  <p>Local transformations usually will be used to eliminate elements with bad
quality (triangles with obtuse angles, slivers). They also can be used to
remove edges intersecting boundaries.

 
<h2><a NAME="mgshift">Shifting Points </a> </h2>


Often points will be shifted. There will be a lot of reasons to shift points, and
different methods to do this. Let's consider some of these methods:
  <p>
 
<h3><a NAME="mgdeformation">Grid Deformation </a> </h3>


If we have a time-dependent problem with a velocity field the grid for the next
time step can be defined by the old grid by shifting the points of the old grid
to their new position defined by the velocity and the time step. This operation
is obviously very fast. But the quality of the resulting grid may be worse, the
grid may be incorrect (overlapping, turning over, etc. of elements). So often
this method will be combined with other methods (especially with
 <a HREF="thggstd.html#mgswap">local transformations</a>) to
avoid such effects.
  <p>Another possibility is to detect only the correctness of the resulting grid and
to create a new grid if a failure will be detected.
  <p>About moving elements see also
 <a HREF="thbib.html#Smith1992"> [Smith1992] </a>,
 <a HREF="thbib.html#Bank1993"> [Bank1993] </a>.

 
<h3><a NAME="mgsmooth">Grid Smoothing </a> </h3>


The most usual method of grid smoothing is barycentrage: Every point is
relocated to the weighted barycentre of it's neighbours (may be including the
point itself). This procedure can be iterated. There may be used also other
methods to find a more optimal position for the point in it's local environment.
  <p>Usually this operation makes the grid better. The main problem of this method
is that there is no guarantee. A Delaunay grid may become non-Delaunay. Locally
the grid may become even incorrect (overlapping, turning over, etc. of
elements). Another problem is that restrictions for the boundary points have to
be made. A boundary point can be shifted only on the boundary.
  <p>
 
<h3><a NAME="mgbshift">Moving Points to the Boundary </a> </h3>


This is another possibility to solve problems which arise around the boundary
in  <a HREF="thggstd.html#mgbcomp">boundary computation</a> or  <a HREF="thggstd.html#mgDelaunay">Delaunay grids</a>. A point from
inside (or outside) the domain will be shifted to a boundary position. As a
result edges which intersect the boundary before don't do this after the
operation.
  <p> An interesting property of this method is that we will have not
so much inner points near the boundary. This may be useful for some
numerical methods, because we can obtain problems if the Voronoi box
of an inner point near the boundary intersects this boundary. On the
other hand, the grid may become too coarse near the boundary.