thgdalg.html

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

 
 </ul>


There will be two useful variants of intersection:

 
<h3><a NAME="partintersect">Partial Intersection </a></h3>


In the case of partial intersection, only one "basic" segment of the
first cogeometry and it's boundary will be subdivided. On the other
hand, information about the second cogeometry will be used only in
this segment. Thus, the second cogeometry may not be defined outside
this segment. More accurate, the input simplex and the output flag may
be partially outside the segment, but if the input flag is not in (or
on the boundary of) the segment the function f(k) may be not defined.

  <p>Remark that the basic segment is not necessarily a region. It may
be also a boundary segment of arbitrary codimension.

 
<h3><a NAME="charfunc">Characteristic Functions </a></h3>


It simplifies especially the higher order functions of the
intersection if the codimension of the second cogeometry is fixed. An
useful example is the cogeometry induced by a smooth real-valued
function and the simple cogeometry on the real line consisting of two
regions (&gt; 0 and &lt; 0) and the single boundary point 0. The
resulting induced cogeometry on X has the codimension 1. Thus, as for
the general, as for the partial intersection with this cogeometry the
implementation will be simple. This method to modify the cogeometry by
intersection we denote as <b>modification by a characteristic
function</b>. It is a simple but powerful possibility to create
complicate cogeometries in a few number of simple steps.

<h2><a NAME="gdbypic">Graphical Input </a></h2>


An interesting possibility of the contravariant geometry description is the
usage of graphical input. There will be different possibilities to use
such input.

  <p>The simplest possibility is to define a 2D cogeometry by a
picture using the principle one color --- one region. This allows to
use paint programs to define 2D cogeometries. How to implement this is
straightforward. We only have to implement the region function.

  <p>Another possibility is to use the color value of the pixel to
encode one, two or three functions on the 2D space. These functions
may be used or interpreted in a different way. For example, they may
be used to define a mapping into the three-dimensional "color space",
and any cogeometry in this color space may be used to define an
induced 2D cogeometry. Another example is to use the color value of a
geographical map to define the elevation. Then this elevation may be
used to define the 3D cogeometry of this region.
<h2><a NAME="gdbysimplex">Using a Simplicial Grid </a></h2>


Consider now the algorithms which may be used if the geometry will be
described by a simplicial grid. That means, we assume that for every
codimension the segments are defined as the union of simplices of the
related dimension.

  <p>If we exclude the problem how to find the necessary simplices in
the data structure, the algorithm is straightforward. In the general
case, we can really compute the intersection line and travel along
this line to find the correct continuation as defined by the formal
definition also for big simplices. A lot of code to handle degenerate
cases will be necessary in the implementation, but our general
strategy to handle these cases is sufficient. Thus, the central
problem for the algorithm is to find the simplices we need, especially
if the number of simplices is very large.

  <p>For the functions f(k) with k &gt; 0 we have always an input
flag which position in the simplex data structure was already found at
the call which has created this flag as output. To avoid a double
search, it will be enough to save the related information into the
flag data. The standard mechanism to transfer attributes may be used
for this purpose. Remark, that this information can also help to
handle degenerated cases. For a flag on the boundary between different
simplices we use on of these simplices to define the segment of the
flag. If we have saved the information about this simplex, we have
saved also the information how we have managed this degeneration.

  <p>If we want to travel along the intersection line, we have to
switch from a given simplex to it's neighbour. Thus, to obtain an
efficient implementation the related neighbourhood information must be
available very fast. In this case, we have no problem to get an
algorithm which is efficient enough for the functions f(k) with k
&gt; 0.

  <p>Only for the case of the region function f(0) we have no input
flag which may be used for the start of the neighbourhood search. In
principle, a good starting point will be one of the nearest previously
found points. But the information about this is not available in the
function f(0) itself. But often it will be available in the function
which calls f(0). That's why, to allow the usage of this
information, we have to modify the interface. We must allow the
calling function to transfer the pointer to a good starting point so that
it may be used by f(0).

  <p>This may be easily realized in the C++ interface. We simply
include some pointer to a starting point into the cogeometry class and
allow to modify this value. It will be initialized with the null
pointer, and after each call of f(0) it will be the argument of this
call. Thus, if the calling function does not use this possibility, the
position of the last point will be used as the starting point. This seems
to be an optimal solution of this problem.

  <p>If we have a good starting point, the same algorithm as used for f(1)
may be used also for f(0). The only difference is that in the case of f(1)
we return immediately if we find a boundary intersection, in the case of f(0)
we have to travel form the start to the end of the edge.

<h2><a NAME="gdbybgrid">Using a Boundary Grid </a></h2>


The most usual way to describe a geometry --- the boundary grid --- is
similar to the previous case, but does not contain simplices of
codimension 0. Instead, we have the information about the left and the
right region for segments of codimension 1.  The higher order
functions do not cause any problems, because the algorithm used for
the complete grid may be used also if we do not have a grid in the
regions. But to obtain an efficient algorithm for f(0) and f(1) we
need another algorithm.

  <p>Thus, we have to find the boundary simplex which has the first
intersection with a given edge. For a small number of simplices, we
can use a simple loop over all simplices. To make the algorithm fast
enough for a large number of simplices, we have to create an additional
data structure which helps us to find this simplex. The usual way is
to use a search tree. Another possibility is to add a grid in the
regions, e.g. using Delaunay techniques.

  <p>Another problem is the degeneration. If the edge intersects
approximately the common border of different boundary face simplices,
we have to consider all these simplices together and cannot use simply
the first intersection, because rounding errors may lead to an
incorrect order of these intersections on the edge.

  <p>Thus, in principle it is possible to implement a fast algorithm
for a boundary grid, but this type of input may be considered as the
"worst case" for the cogeometry.
<h2><a NAME="gdbyother">Other Possibilities </a></h2>


There will be also other natural possibilities to create and modify
cogeometries. They usually may be easily implemented, at least for the
region function f(0). For example:

 
 <ul>
 <li>The union of different segments of a cogeometry.
 
 <li>Different manipulations of attribute values do not immediately
change the cogeometry, but it is useful to implement them as
operations on the cogeometry.
 
 <li>If there is an order relation between the segments of each codimension,
the minimum or maximum of different cogeometries may be defined.
 
 </ul>


The real power of the contravariant geometry description is that it allows
to combine all these separate methods. A 3D cogeometry defined by a
grid may be intersected with a 3D cogeometry induced by some mapping.
Attributes may be used to define mappings. To switch between different
dimensions is trivial.  The elevation profile of a region may be used
to define the 3D surface geometry of this region. This may be combined
with other maps of this region to subdivide the surface into parts.

 
<h2><a NAME="gdalgtime">Time Requirements</a></h2>


Let's consider now the time required by the different algorithms we
have considered before. For simplicity, we consider only the case of
isotropic simplices. The general algorithm we have to consider
consists of the simplex subdivision algorithm and the call of some of
the special algorithms for the smallest simplices. The time necessary
for a single call of f(k) for k &gt; 0 depends obviously of the
following data:

 
 <dl>
 <dt>0 
 <dd> the required accuracy of boundary computation.
 
 <dt>1 
 <dd> the dimension of the input simplex.
 
 <dt>2 
 <dd> the dimension of a simplex which is small enough to
call the special algorithm.
 
 </dl>


 If 0 = 2 the time for a call of the special
algorithm may be estimated by a constant.
 

More accurate, this has to be considered as a natural condition for a
fast algorithm.  Really, we simply have to solve a single question
with a finite number of possible answers: Is there an intersection
inside or which side of the simplex contains the continuation. Then we
can simply use the middle point or the middle of the side as the
position of the output flag. If this requires too much time, we
obviously use a bad algorithm.

 <p>In principle, this time depends on the size of the data of the
geometry description. E.g. for the case of the boundary grid with
search tree we obtain a logarithmic dependence on the size of the
boundary grid. If the typical size of the simplex 3 in a volume
or boundary grid is smaller than 0 (that means we use an input
grid which is too fine) we obtain an additional factor
0 / 3.

  <p>A <b>regular geometry</b> is a geometry so that the length of the
intersection line of the segment with the simplex may be estimated by1 and the number of intersections of the k-segments with a
k-simplex may be estimated by a constant.