noderemoval.html

Delaunay三角形的网格剖分程序

<TITLE>COG 2.1: Node removal</TITLE>

<H1>Node Removal Algorithm</H1>

 <P>It should be noted that the <A HREF="cogenoctree.html">octree
algorithm</A> sometimes (unfortunately, not seldom) fails to create
nice grids, for various reasons.  An especially critical part is the
<B>node removal algorithm</B>.  The purpose of this algorithm is to
remove some nodes created by the standard octree algorithm.

<H2>Purpose and Problems of the Algorithm</H2>

 <P>In general, if there is no close relation between geometry and
grid (as for the rectangular boxes) the surface intersections with
the grid lines form a not very uniform surface grid:

 <P><IMG SRC="smallnearface.gif">

 <P>Without further action we obtain arbitrary small tetrahedra
resp. triangles near and on the surface, because an inner node, by
accident close to the surface, leads to close intersections with the
surface.  Most people don't like such things.  Nodes near inner
surfaces also have higher probabilities to cause geometry errors,
especially <B>bad region cell</B>.

 <P>To avoid such situations, we try to remove nodes near the surface
as well as some the surface nodes.  But this is a dangerous game.
Doing too much is problematic too.  Unfortunately, what is good in one
situation may be bad in another one.  Therefore, sometimes it may be
useful for you to be able to manipulate this algorithm.  Doing this
has the following influence on the grid:

 <UL>
 <LI> Removing more region nodes avoids errors of type <B>bad region
cell</B> and descreses the number of small cells near the bondary.
Removing too much of them leads to a slightly strange, unwanted grid
property: we usually need high refinement near the surface, but,
instead, immediately near the surface the grid becomes more coarse.
 <LI> Removing face nodes makes the surface grid better, decreases the
number of thin cells near the surface, and helps to avoid errors of
type <B>bad face cell</B>.  Removing too much of them creates errors
of type <B>bad region cell</B>.
 </UL>

<H2>Radical Try</H2>

 <P>The most radical way to influence this behaviour - to <B>omit</B>
the node removal completely or to <B>enforce</B> all reasonable
possibilities - are defined by the following calls:

<PRE>
  cogenOctree octree = ...;
  octree-&gt;omitRegionNodeRemoval();
  octree-&gt;omitFaceNodeRemoval();
  octree-&gt;omitEdgeNodeRemoval();
  octree-&gt;omitVertexNodeRemoval();
  octree-&gt;enforceRegionNodeRemoval();
  octree-&gt;enforceFaceNodeRemoval();
  octree-&gt;enforceEdgeNodeRemoval();
  octree-&gt;enforceVertexNodeRemoval();
</PRE>

 <P>Thus, to avoid <B>bad region cell</B> errors, try

<PRE>
  octree-&gt;enforceRegionNodeRemoval();
  octree-&gt;omitFaceNodeRemoval();
  octree-&gt;omitEdgeNodeRemoval();
  octree-&gt;omitVertexNodeRemoval();
</PRE>

 <P>I recommend to try these calls to understand if the node removal
algorithm is related with your problem or not.  If not, the fine
tuning of the algorithm described below will not help you too.

<H2>Fine Tuning</H2>

 <P>There are several independent parts of the node removal algorithm
which remove nodes which are "bad" in various situations. 

<H3>Removing Underdogs</H3>

 <P>The minimal node removal procedure removes inner nodes if face
nodes are in the immediate <I>delta</I>-neighbourhood, that means, in
the environment of accuracy of boundary computation.  In this case, we
assume that the grid node itself is located on the surface.  We move
the (approximately computed) surface position to the position of the
inner node (which is the exact surface position in the case of octree
boxes) and remove the related inner node (the <I>underdog</I>).  The
same happens for face nodes near edge nodes and edge nodes near
vertices.

 <P>To include/exclude this minimal node removal use the following
call:

<PRE>
  octree-&gt;removeUnderdogs(wzTrue);
  octree-&gt;removeUnderdogs(wzFalse);
</PRE>

<H3>Removing Irregular Neighbours</H3>

 <P>Another possibility which seems always reasonable to include is to
remove "irregular nodes".  These are the nodes without opposites in
cubes/rectangles where the refinement level changes.  If such cubes
have surface intersections it seems necessary to remove them. (Usually
in this case the cube will be regularized, so that such nodes do not
appear.)

<PRE>
  octree-&gt;removeIrregularNodes(wzTrue);
  octree-&gt;removeIrregularNodes(wzFalse);
</PRE>

<H3>Removing Face Intersections With Long Sides</H3>

 <P>This node removal possibility is especially important for
anisotropic grid generation and slightly skew surfaces.  In this
case, the non-beautiful situation of the left picture (named
<B>spider</B>) may appear:

 <P><IMG SRC="spider.gif"> <IMG SRC="spiderremoved.gif">

 <P>The following point removal procedure removes the critical nodes -
surface intersections with the longer sides - to obtain the right
picture:  

<PRE>
  octree-&gt;removeLongSideIntersections(wzTrue);
  octree-&gt;removeLongSideIntersections(wzFalse);
</PRE>

 <P>Unfortunately, in some situations this node removal leads to
<B>bad region cell</B> errors.  Moreover, in isotropic grids it is not
very helpful.