Generation and
Refinement of Unstructured Mixed-Element Meshes in Parallel --- GRUMMP
We are working to develop automatic mesh generation software for
unstructured meshes with mixed element types. The goal is to produce
high-quality meshes which meet user-defined mesh density requirements,
using elements appropriate for the geometry and physics of a particular
problem.
The most recent version of the GRUMMP software and documentation are maintained
at Carl Ollivier-Gooch's site
at the University of British Columbia.
Automatic mesh generation for complex two and three dimensional domains
has recently become a topic of intensive research. It is imperative
that automatic mesh generation tools be capable of generating quality
finite element meshes. There must be a balance between resolution of
the boundary and surface features and complexity of the problem. In
addition, for problems with isotropic physics, element aspect ratio must
be small to minimize linear system condition number and interpolation
error. On the other hand, problems with anisotropic physics (for
example, a shear layer in viscous fluid flow) require highly anisotropic
elements for efficient solution. A further level of complication is
that for some physical problems and applications, quadrilateral (2D) or
hexahedral (3D) elements are preferred, even though filling space with
high quality elements is easier using triangular (2D) or tetrahedral
(3D) elements.
Mesh generated using a prototype version of GRUMMP for a tire
incinerator geometry used in our collaboration with Nalco Fuel Tech in which we are
modeling commercial combustion systems.
Project Goals
A general-purpose automatic mesh generator should address all of these
issues without excessive user intervention. We envision a system in
which common types of physical problems have pre-defined mesh sizing and
element aspect ratio functions, allowing easy generation of meshes for
these applications areas. For flexibility and generality, the user will
also be able to prescribe these functions (for totally different
applications) or modify the pre-defined behaviors (to provide a quality
mesh in the wake of an airplane wing, for example).
The output generated by the algorithm will include data files that contain
information pertaining to nodal coordinates, element connectivities, and
analysis specific data.
In addition we will include options to create extended databases that
reflect the original geometry to allow for remeshing and node repositioning
during the course of a solution run.
The first release of GRUMMP is now available from
Carl's site at the
University of British Columbia.
Surface Mesh Generation
We propose to solve this problem in two pieces: generation of
high-quality surface meshes from geometry data and generation of
high-quality volume meshes from surface meshes. Automatic surface mesh
generation requires a reliable interface to CAD data, allowing the
automatic generation of surface meshes from complex object definitions.
This may include curved boundaries in two dimensions (see the picture of
an airfoil, for example), curved surfaces embedded in three- dimensional
space (such as those used for modeling potential flow around airplanes
and submarines), as well as fully three-dimensional objects (such as
multicomponent structures problems). A surface mesh generator must not
only provide good spacing control, but also allow the generation of
anisotropic and/or quadrilateral faces when appropriate.
Volume Mesh Generation
Filling the Region Defined by the Surface Mesh
Automatic volume mesh generation from a surface mesh is performed
in two stages. First, a tetrahedral mesh filling the interior of the
domain is generated. We have implemented two complementary
algorithms for initial tetrahedralization. The first is a modified
version of an existing theoretical approach to this problem which has
apparently never been tested in practice. This algorithm, due to
Chazelle and Palios, solves the problem robustly and with asymptotically
optimal complexity. The resulting tetrahedralization is guaranteed to
exactly fill the space defined by the surface mesh, and the surface mesh
will be a subset of the faces of the volume mesh to within rearrangement
of co-planar faces. This algorithm is excellent for simple polyhedra,
but has difficulties for the common case of a well-resolved surface
triangulation; the surface triangulation tends to be projected
onto distant, less highly-resolved surfaces, resulting in meshes which
are subjectively poor.
Because of this problem, we have also implemented an initial
tetrahedralization scheme which tetrahedralizes the initial point set
and performs local transformations to recover surface edges and
triangles where necessary. This algorithm does a much better job with
smooth, triangulated geometries (aircraft wings, for example). The
Chazelle and Palios algorithm is tried first; if it fails, the surface
recovery algorithm is used instead.
Mesh Improvement via Point Insertion
After an initial tetrahedral mesh is generated, the final volume mesh is
generated by successive insertion of points. The location of these
points is determined by construction to ensure high mesh quality. Mesh
quality is further improved by local reconnection of elements (face and
edge swapping) and by smoothing
of point coordinates.
When the simplicial mesh generation code is stable and robust, attention
will turn to generation of mixed-element meshes. For this case, point
placement strategies are especially important to ensure that tetrahedra
(triangles) can be combined to form high-quality hexahedra, prisms and
pyramids (quadrilaterals). These element types will be formed in a
post-processing step.
Point insertion can also be used as a tool for solution based
adaptivity, using a mesh quality measure which includes information
about solution error. This allows more flexibility in refinement than
edge bisection at the expense of greater difficulty in de-refinement.
These difficulties are not, however, insurmountable.
Current Project Status
Currently, the GRUMMP library is in the final phase of pre-release
testing. In the near future, a beta release of triangular and
tetrahedral mesh generators based on this code is planned. The initial
release is intended in part as robustness testing, especially for 3D.
Later releases will include parallel versions of the code and an API so
that users can include GRUMMP routines in their applications code to
enable adaptive refinement.
For further information or to participate in beta
testing of the current version of the code, send mail to gooch@mcs.anl.gov .
Previous: Overview
Next: Mesh Smoothing
Back: Unstructured Mesh Home Page