Adaptive Refinement of Hierarchical Meshes

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

MESHING
RESEARCH
CORNER

AEA Technology GmbH, Staudenfeldweg 12, D-83624 Otterfing, Germany
rg@ascg.de

Abstract

In this paper an extension of the algorithms introduced in a previous work [1] for the adaptive refinement of hierarchical tetrahedral meshes to more general unstructured meshes consisting of tetrahedra, prisms, pyramids and hexahedra is presented.

The adaptive mesh refinement method for tetrahedral meshes is based on the red-green or regular-irregular refinement technique first introduced by Bank et al. 1983. The main properties of the algorithms are:

(i) Stability: through the introduction of a second element type, the octahedron, and a corresponding set of refinement rules. The application of the algorithm to any initial element generates elements of at most two congruence classes.

(ii) Performance: all refinement operations are based on the topology of the mesh and driven by table lookups. Furthermore, irregular elements are virtual, i.e. they actually are not stored in the data structures.

(iii) Progressive Transmission: new data structures were introduced which allow for an abstract description of the mesh hierarchy and a progressive manipulation [2]. Only the coarse mesh and a set of records for the reconstruction of the hierarchy are stored or transmitted across the network.

In this work these concepts are extended to more general unstructured meshes. A set of regular refinement rules for prisms, pyramids and hexahedra is introduced. A pyramid is subdivided into 6 pyramids and 4 tetrahedra. The set of rules generates only one congruence class for hexahedra and prisms, and two congruence classes for pyramids. For the irregular refinement, we first irregularly refine the faces and connect the resulting triangles or quadrilaterals with a vertex introduced at the barycenter. The refinement of a mesh consisting of 135,616 hexahedra, 183,236 pyramids and 335,680 tetrahedra into a mesh with 310,768 hexahedra, 460,512 pyramids and 849,728 tetrahedra took 4.4 sec on a SGI O2, 195 MHZ R10000. The generation of the virtual elements for an iso-surface computation in a mesh with 725,459 elements and 191,585 regular elements, i.e. the generation of 533,874 irregular elements, took 0.08 sec. These results clearly demonstrate the performance of the refinement algorithm. Furthermore, the use of virtual elements makes the storage of the mesh hierarchy very efficient, as it can be seen from the large number of irregular elements in the example given above.

References

[1] R. Grosso and Th. Ertl. Progressive Iso-Surface Extraction from Hierarchical 3D Meshes. In EUROGRAPHICS'98, volume 17, 1998.

[2] R. Grosso and G. Greiner. Hierarchical tetrahedral-octahedral subdivision for volume visualization. The Visual Computer, special issue, 1999.