1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305

/*! \mainpage UG4.0 Reference Manual
*
*
* \section intro Introduction
*
* This is the introduction.
*
* \section mods Modules
*
<ul>
<li> \ref ug </li>
<ul>
<li> \ref dev </li>
<li> \ref dom </li>
<ul>
<li> \ref std </li>
</ul>
<li> \ref gm </li>
<li> \ref graphics </li>
<li> \ref low </li>
<li> \ref np </li>
<li> \ref ui </li>
</ul>
</ul>
\section chapter2 Overview of UGs data structures
This page will give an overview of the data types defined in UG
that are used to represent meshes and geometries. All data types discussed here are
defined in the header file gm.h of the grid manager module.
A description of the individual data types can be found in
separate pages for each data type. UGs data structure is very flexible
and covers two and threedimensional elements and a general sparse
matrix structure. You can have different numbers of degrees of freedom
in nodes, edges, sides
and elements of a threedimensional mesh. Therefore the data structure
can be used e.g. also for nonconforming or mixed finite element discretizations.
To structure the data you can group vectors by using BLOCKVECTORs; this
yields blockmatrices too.
UGs refinement module can refine and coarsen a given mesh structure. In
order to do that it needs a complete description of the geometry of the
domain. For full flexibility, the geometry is defined by patches, which are
mappings from a d1 dimensional parameter space to d dimensional euclidean space.
If we imagine a threedimensional mesh we can identify a hierarchy of
geometrical objects like `elements, sides, edges` and `nodes`.
By element we mean just a simple geometric shape like
a triangle, a quadrilateral, a tetrahedron or a hexahedron. In our notation the element
does not include the number of degrees of freedom or the definition of the shape functions
as it is common in the Finite Element context. A side is meant to be a face of an element, that
is a d1 dimensional object if we have a mesh in d dimensions (d=2,3). An edge is a connection
of two nodes, i.~e. a onedimensional object and a node is a point in space (as far as geometry
is concerned). Note that in two space dimensions sides coincide with edges, or we can say that
a side consists of one edge and two nodes in that case.
The TeX version of this page contains a graphical representation of the data
structure.
Size limitations of the data structure are described in a separate page LIMITS.
All data types have names with uppercase letters. Now we give a brief description
of all data types for which a separate page is provided.
. DOMAIN  Structure that describes a two or threedimensional domain.
. BOUNDARY_SEGMENT  A DOMAIN is constructed from several BOUNDARY_SEGMENT objects.
UG can handle also `internal` boundaries, e.g. for material interfaces.
. PROBLEM  Stores references to user defined coefficient functions. The purpose
of these functions depends on the problem class library. A problem corresponds
to a DOMAIN and provides a BOUNDARY_CONDITION for each BOUNDARY_SEGMENT
besides the coefficient functions. There may be several problems defined on a domain.
. BOUNDARY_CONDITION  For each BOUNDARY_SEGMENT a corresponding BOUNDARY_CONDITION
object must be allocated.
. FORMAT  This structure parametrizes the data structure. The format determines
the layout of the sparse matrix data structure and how it is determined from
the mesh data.
. ELEMENT  UGs data structure is element oriented, so this is the basic data
type from which other objects can be reached locally. The variable element
concept allows several element types (e.g. triangles and quadrilaterals) in one mesh.
Elements give you access to the corresponding nodes and to neighboring elements.
. NODE  Corners of the elements are described by the NODE structure. Only the
information that is different per level is stored here. E.g. geometric information
for a node e.g. is stored only once in a VERTEX object. Several NODE objects share
share one VERTEX if they are at the same position on different levels.
. VERTEX  Geometric data of a NODE. This contains x,y (,z), i.e global
coordinates, the position in the coarser grid level (local coordinates) and
boundary information if the node is on the boundary (see VSEGMENT).
. LINK  The mesh structure implies a neighbor relationship on the NODE
objects (the `mesh graph`).
Since the mesh is unstructured a linked list must be used to provide
references to all neighbors. The LINK data type forms that list and each
LINK object represents one neighbor.
. EDGE  The LINK structure represents a directed edge of the mesh graph from
some node `a` to node `b`. The LINK from node `b` to node `a` must always exist
since the neighbor relation is symmetric and therefore the two LINK objects
are combined to form an (undirected) EDGE object.
. GEOM_OBJECT  This is an union of ELEMENT, NODE and EDGE, the basic
geometric objects.
. VECTOR  This structure is part of UGs sparse matrix data structure. Degrees
of freedom (and additional values) associated with `one geometric object`
(ELEMENT, NODE, EDGE and also sides in 3D for which there is no extra data type)
are stored in a VECTOR object. In each VECTOR starts a list of MATRIX objects
representing the rows of the global stiffness matrix corresponding to all
degrees of freedom in the VECTOR.
. MATRIX  Contains all matrix entries coupling the degrees of freedom
in two VECTOR objects. MATRIX objects come in pairs connecting two
VECTOR objects in both directions. If the VECTOR objects are identical (which is
the case for diagonal entries) then there is only one MATRIX.
The graph induced by the MATRIXVECTOR
structure is completely independent from the mesh graph represented by the
LINKNODE structure.
. CONNECTION  The two (or one, s.a.) MATRIX objects connecting two VECTOR objects
are combined to a CONNECTION object. This is similar to the combination of two
LINK objects in an EDGE.
. GRID  All objects allocated on one grid level can be accessed via the
GRID structure.
. MULTIGRID  Several grid levels are combined to form a MULTIGRID structure.
It also provides access to the data structure parameters (FORMAT), the
geometry (DOMAIN) and the problem description (PROBLEM). The MULTIGRID
structure is basically an environment item (see ENVIRONMENT). Several
MULTIGRID objects can be handled simultaneously by the grid manager module.
`IMPORTANT:` The access to all components of the data types is realized with
macros. Through the use of macros the data structure can be changed without
changing the code that uses it.
\sa
LIMITS, all data types mentioned above.
.p DataStructure.eps
.cb
Graphical representation of the data structure with references.
.ce
\section LIMITS Constants defining limitations of the data structure
There are some constants defining limitations of the data structure.
They are explained here. The actual value of the definition should
be extracted from the source code via the uggrep shell script
provided with UG.
`In file gm.h`
. MAXLEVEL  Maximum number of grid levels allowed in MULTIGRID.
. MAXOBJECTS  Maximum number of different objects in free list.
. MAX_SIDES_OF_ELEM  Maximum number of sides of an element (of any type).
. MAX_EDGES_OF_ELEM  Maximum number of edges of an element (of any type).
. MAX_CORNERS_OF_ELEM  Maximum number of corners of an element (of any type).
. MAX_EDGES_OF_SIDE  Maximum number of edges per side.
. MAX_CORNERS_OF_SIDE  Maximum number of corners per side.
. MAX_CORNERS_OF_EDGE  Maximum number of corners per edge (is always 2).
. MAX_SIDES_OF_EDGE  In 3D two sides always have on edge in common.
. MAX_SONS  Maximum number of sons per element.
. MAX_SIDES_TOUCHING  Maximum number of sides on the next finer mesh that make up
a side on the coarser mesh.
. MAXMATRICES  Maximum number of MATRIX types with different size.
. MAXCONNECTIONS  Maximum number of different CONNECTION types.
. MSIZEMAX  Maximum size of a MATRIX object in bytes.
. NO_OF_ELEM_MAX  Maximum number of elements touching the same edge.
`In file switch.h`
. DIM_MAX  Maximum space dimension (is 3).
. DIM_OF_BND_MAX  Maximum dimension of boundary (is DIM_MAX1).
. MAXVECTORS  Maximum number of different VECTOR types.
\section REFINEMENT The interface to the grid refinement module
The interface to the grid refinement will change in the near future.
Therefore only a rudimentary documentation is provided.
UGs local refinement capability is element oriented, i.e. the
error estimator (part of the problem class) selects all or
part of the elements for refinement. To that end the error
estimator calls the function
\verbatim
INT MarkForRefinement (ELEMENT *theElement, INT rule, INT side);
\endverbatim
where rule is one of the following rules
\verbatim
NO_REFINEMENT
COPY
RED
BLUE
BISECTION_1
BISECTION_2_Q
BISECTION_2_T1
BISECTION_2_T2
BISECTION_3
UNREFINE
\endverbatim
and side is some orientation necessary for those rules
that are not invariant under rotation (e.g. the edge to bisect).
The RED rule selects standard isotropic refinement independent
of the element type. Triangles are subdivided in four triangles
by connecting the edge midpoints, quadrilaterals are subdivided
by connecting edge midpoints with the centroid and tetrahedral
elements are subdivided using the refinement strategy of J. Bey.
For RED refinement the side information is arbitrary.
The MarkForRefinement function may only be called for those elements
where
\verbatim
INT EstimateHere (ELEMENT *theElement);
\endverbatim
returns true. EstimateHere is true for the leave elements of the element
hierarchy, i.e. those elements that are not further refined. Care
must be taken when the estimator for an element needs also information
on the solution in neighboring elements (see e.g. the implementation
of the error estimator in the diff2d package).
After the desired elements have been tagged for refinement the refine
of the UG command language is used to actually refine the elements.
\subsection Example Example2
The following function selects all (possible) elements in a MULTIGRID for refinement and
returns the number of elements selected for refinement.
\verbatim
static INT MarkAll (MULTIGRID *theMG)
{
GRID *theGrid;
ELEMENT *theElement;
int k,j;
INT cnt;
// get number of levels
j = TOPLEVEL(theMG);
// cnt will hold the number elements to be refined
cnt = 0;
// mark elements
for (k=0; k<=j; k++)
{
theGrid = GRID_ON_LEVEL(theMG,k);
for (theElement=FIRSTELEMENT(theGrid); theElement!=NULL; theElement=SUCCE(theElement))
if (EstimateHere(theElement))
{
cnt++;
MarkForRefinement(theElement,RED,0);
}
}
// return cnt
return(cnt);
}
\endverbatim
\sa
MarkForRefinement(), EstimateHere(), refine()
REFERENCES:
[1] J. Bey: Tetrahedral Grid Refinement. To be published in Computing.
[2] J. Bey: AGM^3D Manual. Technical Report, Universit�t T�bingen, 1994.
[3] R.E. Bank, A.H. Sherman, A. Weiser: Refinement Algorithms and Data
Structures for Regular Local Mesh Refinement. In: Scientific Computing,
IMACS, NorthHolland, Amsterdam, 1983.
*/
