
Finite Element Meshes and Suitable Data Structures
Stefan M. Holzer (Uni Stuttgart)
The representation that is best suited for finite element and/or boundary
element
meshes is topological representation in a BRep (boundary representation)
data structure.
In such a data structure, geometric data as well as boundary conditions can
be handled as
attributes to the topological entities vertex (v), edge (e), and face (f).
Various
data structures are suitable for representing a vefgraph. However, most
finite element
programs still stick to the simplest possible representation, i.e. to a
representation that
stores only the (f,v) relation. If the spatial decomposition is a simplicial
one (i.e.,
triangles in 2D or tetrahedra in 3D), then such a mesh can be represented in
a relational
database by tables with a fixed number of columns, based on the (f,v) relation.
Considering adaptive mesh refinement rather than densitybased remeshing,
such a data structure
is no longer satisfactory. Local hierarchical mesh refinement (which is also
needed for
geometrical multigrid) requires bisection of edges, insertion of new nodes
on old edges,
splitting of old faces, and so on. Intermediate topologies that arise during
such a refinement
procedure are outside the scope of a data structure that is based on
fixedsize tables for
the (f,v) relation only. Also, topological queries such as adjacencies are
expensive on such
a simple data structure. Topological queries play a major role in adaptive
methods (e.g.,
for evaluating BabuskaMiller error estimates) and in parallelization (e.g.,
graphtheory based
domain partioning algorithms).
A twodimensional finite element mesh as well as a surface mesh for a
threedimensional body
can both be considered as twomanifolds. Data structures for twomanifolds
are available. For
the purpose of designing versatile finite element codes, the most attractive
BRep data structure
for FE meshes is the Winged Edge data structure introduced by Baumgart in
the mid80ies. We discuss
the application of such a data structure in the context of uniform
pextension Finite Element methods for plate bending problems on locally
refined meshes, as well as application in a
greedy algorithm for dynamic domain partitioning. We also discuss possible
data structures
for threedimensional finite element meshes, ranging from combined BRep and
sweep representation
to fully 3D nonmanifold representations.
Finally, an algorithm for 3D finite element meshing of typical Civil
Engineering structures is
presented.

