Algorithmic and Implementation Aspects of Generating Isotropic and Anisotropic Tetrahedral Meshes

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

T. J. Baker
Geometricon,LLC and Princeton University
baker@tornado.princeton.edu

J. C. Vassberg
Geometricon,LLC and the Boeing Company

Abstract
The tetrahedral mesh generator GTO (Generation of Tetrahedra and Optimization) exploits a Delaunay triangulation technique, edge/face swapping procedures to reconstruct the boundary surface, and a combination of circum-center point insertion plus mesh optimization to create meshes whose tetrahedral elements display a consistently high quality [1]. GTO is now a key component in Pointwise's software Gridgen and has been ported to several different Unix platforms as well as NT windows. The mesh generator has proved to be robust and versatile. In this paper we will discuss a number of aspects whose resolution and implementation have significantly improved the flexibility and capability of the GTO mesh generator. These include:

1) A priori mesh size estimates. We will describe an algorithm to estimate the mesh size and hence memory allocation required when computing a volume mesh of tetrahedra for a given boundary surface triangulation. These estimates enable one to implement dynamic memory allocation in an efficient manner by significantly reducing the number of calls for further memory allocation.

2) Non-manifold boundary surfaces. The presence of membrane surfaces (triangular facets that represent internal barriers having mesh tetrahedra on both sides), and also the possibility of multiple components joining at common edges or vertices, complicates the data structure re-quirements for manipulating the boundary triangulation. A linked list data structure has been implemented to store and manipulate these more general boundary components in an efficient manner.

3) Anisotropic meshing. For many problems the presence of singular features such as shock-waves, boundary layers and cracks requires a mesh that is highly stretched in a particular direction. Although there is still some controversy about the stability and accuracy of finite element compu-tations with highly stretched tetrahedra, we believe that tetrahedral meshes are very satisfactory for many applications exhibiting anisotropy provided there are no large angles. To achieve a good quality stretched mesh that avoids large dihedral angles, we combine a point placement strategy in physical space with an affine transformation of the metric used for the Delaunay in-sphere test. The placement of points in physical space at locations normal to the boundary of the singularity allows one to maintain precise control over the position of the mesh nodes. On the other hand, the use of a modified metric in the Delaunay test ensures good connectivity with a layered arrangement of tetrahedra in the region of anisotropy.

The paper will discuss these various aspects in detail and present a number of examples to demonstrate their implementation in the GTO software.

Reference

[1] T.J.Baker and J.C.Vassberg, 'Tetrahedral Mesh Generation and Optimization' ,Proc. 6th Int. Conf. Numerical Grid Generation, (ed. M.Cross et al.), Greenwich, UK, July 1998, pp 337-349