thgdstd.html

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

<h1><a NAME="thgdstd">Usual Concepts for Geometry Description </a></h1>


  <p>The current situation in 3D geometry modeling was summarized in
<a HREF="thbib.html#Saxena1995"> [Saxena1995] </a> in the following words: "The
state-of-the-art in commercial geometric modeling technology is solid
modeling. Topologically, a solid model is a two-manifold object. [...]
There is a growing awareness in the CAD/CAM/CAE community of the
importance of providing systems which can model and represent
non-manifold objects. Unfortunately, this functionality is not yet a
commercial reality." Here, "non-manifold object" refers to a geometry
with inner boundaries, boundary lines and so on.

  <p>The geometry description proposed in this (and other like
 <a HREF="thbib.html#Shepard1987"> [Shepard1987] </a>) papers is based on a
separate "topology description" developed by Weiler
 <a HREF="thbib.html#Weiler1986"> [Weiler1986] </a> which lists all regions and
boundaries and the neighbourhood relations between them, and
"geometric entity data" which are usually functions from the basic
boundary entities into the space.  They are usually taken from some
special function space, the current favorite seems to be NURBS
(non-uniform rational B-splines). See also
 <a HREF="thbib.html#Barnhill1992"> [Barnhill1992] </a>,
 <a HREF="thbib.html#Hagen1992a"> [Hagen1992a] </a>,
 <a HREF="thbib.html#Hagen1992"> [Hagen1992] </a>,
 <a HREF="thbib.html#Farin1991"> [Farin1991] </a>,
 <a HREF="thbib.html#Stoyanov1992"> [Stoyanov1992] </a>.

Let's at first consider the basic ideas of
these geometry descriptions.

 
<h2><a NAME="gdstd">The Standard Geometry Description </a></h2>


  <p>There are a lot of geometry descriptions, including the usual CAD
systems, which may be considered as different variants of a single
concept.  Almost all are based on one main idea --- the cell complex.

  <p> A <b>cell complex</b> may be defined by induction. A 0-dimensional
cell complex is a discrete set of points. A k-dimensional cell complex
may be created based on a (k-1)-dimensional cell complex and a set of
k-dimensional cells. A <b>k-cell</b> is some standard k-dimensional
reference cell (for example the k-dimensional simplex or cube). To
define the k-dimensional cell complex, we identify the boundary points
of the k-cells with points of the (k-1)-dimensional cell complex using
some boundary mapping. That means, the cell complex is defined by a
set of cells and boundary mappings.  For a given space X, a <b>cell
complex in X</b> is simply a continuous mapping from the cell complex
into X. Thus, a cell complex in X will be defined by a set of cells
and their mappings into the space X. On the boundary of the cells, the
mapping must coincide with the mappings of the related boundary cells.
A cell complex in X is smooth if all these mappings are smooth.

  <p>A <b>standard geometry</b> on the n-dimensional manifold X consists of:

 
 <ul>
 <li>An n-dimensional cell complex in X so that the related mapping is a
homeomorphism.
 
 <li>A definition of the k-segments as unions of k-cells so that for every k-cell
there is a uniquely defined k-segment containing this cell.
 
 </ul>


This definition leads to the following induction scheme of the
description of an n-dimensional geometry:

 
 <ul>
 <li>Subdivide all k-segments into elementary k-cells.
 
 <li>At first, define the mapping for the 0-cells. This is simply the
position of the related points in X.
 
 <li>In the step k, the mappings of the k-cells have to be
defined. These mappings have to coincide on the boundary with the
previously defined mappings of the related (k-1)-cells.
 
 </ul>


  <p>If only the geometry has to be defined by the cell complex, it is
not necessary to define explicitly the n-dimensional cells. Only the
neighbourhood relations have to be described correctly. In this case,
the geometry will be defined by a <b>boundary description</b>.

  <p>In applications, a lot of different variants of this general
scheme will be used:

 
 <ul>
 <li>Different types of cells may be used like
        
 <ul>
 <li>simplices (triangular and tetrahedral grids),
        
 <li>cubes (rectangular and hexahedral grid),
        
 <li>other cells (prisms, pyramids and so on).
        
 </ul>

 
 <li>Different types of functions may be used. In applications,
finite-dimensional function spaces will be used like
        
 <ul>
 <li>linear functions,
        
 <li>quadrics,
        
 <li>Bezier curves,
        
 <li>B-splines
        
 </ul>

and other types of splines.
 
 </ul>


<h2><a NAME="gdstdprobl">Problems of the Standard Geometry Description</a></h2>


  <p>The main failure of this formalization of the geometry is that it
does not lead to a natural realization of the induced geometry:

  If we have a mapping f: X --> Y and a cell complex on X,
this defines a natural cell complex on Y.
 

  <p>The have simply to use the composition of the mapping from the
cell complex into X with the mapping f. In the language of category
theory, the cell complex is covariant (transforms from X to Y), that
means it is different from the behaviour of a geometry which is
contravariant (transforms from Y to X).  That's why this cell complex
usually cannot be used to define a geometry on Y.

  The related cell complex on Y defines a geometry if f is
a homeomorphism.
 

Indeed, in this case it simply coincides with the geometry induced
on Y by f^{-1}: Y --> X.

  <p>Thus, only in the case of the homeomorphism we obtain a natural
possibility to describe the induced geometry by a cell complex. In the
general case, there is no such general scheme which allows to
define the cell complex of the induced geometry. This leads to
complicate algorithms also for a lot of other useful and natural
methods to create geometries:

 
 <ul>
 <li>Higher dimensional extension of a lower dimensional geometry.
 
 <li>Restriction of a higher-dimensional geometry to a surface.
 
 <li>Intersection of different geometries on a given space.
 
 </ul>


The obvious reason is that all these operations may be considered as
induced geometries. Thus, the intersection may be considered as
induced by the diagonal function  X --> X &times; X from the
"outer intersection" of the geometries which is defined on the product
space X &times; X.

  <p>To describe some special 3D geometry is usually not a big problem
using one of the available CAD systems. Problems with the standard
geometry description we obtain if we need general algorithms, for
example if we have time-dependent geometries. For example, assume we
have defined a geometry by a boundary grid and a velocity field on
this boundary grid.  Let's look what we have to do now to compute the
geometry for the next time step. We shift the boundary grid in the
direction of the velocity field. But after that we have to control the
correctness of the resulting boundary grid:

 
 <ul>
 <li> There may be caustics. It is necessary to detect and to
eliminate them. In the case of a constant growth rate in 2D caustics are
local self-intersections of the boundary line. But already for the
case of non-constant grow rate we can obtain also caustics without
self-intersection. In 3D caustics are very complex global objects. So
detection and elimination of the caustics is very complicate.
 
 <li> There may be other intersections of the shifted boundary grid,
may be with other boundary grids, may be self-intersections. These
intersections also have to be detected, but they cannot be eliminated,
but require a change of the topology. This requires a very accurate
classification of the intersection, because every failure leads to an
obsolete data structure or global errors. Especially we have to think
about rounding errors.
 
 <li>The intersecting parts are obviously in the same space region,
but usually "far away" in the data structure of the boundary grid. To
make the tests fast enough we have to use search tree structures. This
makes the data structure more complicate.
 
 <li> In 2D these effects are local --- we have to find an
intersection point. In 3D (and any higher dimension) as caustics, as
the other intersections will be global objects. Caustics may have
intersections with boundaries and other intersection curves.
 
 <li> The grid quality of the shifted grid is usually worse. So grid
rebuilding procedures will be necessary to obtain better grid quality.
 
 </ul>


Thus, even a simple modification requires a very complicate
program. That's why in most applications a lot of simplifications will
be used. Often only one region is allowed, may be even with
topological restrictions (f.e. no holes).  Usually topological changes
are not allowed, and small time steps are required to avoid
caustics. An example of a program which detects and eliminates
intersections is SAMPLE-3D (see <a HREF="thbib.html#Helmsen1992"> [Helmsen1992] </a>, <a HREF="thbib.html#Scheckler1992"> [Scheckler1992] </a>).

<h2><a NAME="gdstdother">Other Usual Concepts </a></h2>


  <p>As already mentioned, the majority of implementations is based on
the ideas of the cell complex. But some parts of our dual concept also
may be found in some applications.

  <p>The idea of the first of our intersection functions f(0) which
returns the region containing a given point is very simple, and often
even this information is available. That's why in many applications
this function will be used to describe the geometry.  If necessary,
the boundary position will be approximated by a simple iteration.  But
in this way it is not possible to describe the geometry of the
boundary itself.  So usually such a geometry description will be
considered only as a poor substitute of a complete geometry
description.

  <p> To obtain a unique, modular interface for different geometry
descriptions which use a lot of different spline types it is a natural
idea to use intersection functions instead of the explicit mapping
functions.  This idea was also already used for geometry description,
for example in <a HREF="thbib.html#Shepard1987"> [Shepard1987] </a>. But, for
the description of the topological neighbourhood relations, the
classical cell-complex concept was used. The resulting concept is
only for 3D and is based in many parts on the bottom-up strategy from lower
to higher cell dimension.