A hypergraph-grammar for the longest-edge refinement of triangular and tetrahedral meshes

Abstract

Mesh refinement is a critical step in mesh adaptation. In this talk, we will present a hypergraphgrammar for the Rivara's longest-edge refinement algorithm [1] of unstructured triangular and tetrahedral meshes. We represent the computational mesh as a hypergraph, and then we construct all the necessary productions to express the mesh refinement steps. A first strategy for triangular meshes is presented in [3]; in this talk, a new graph structure is considered that allows to generalise to tetrahedral meshes. The hypergraph-grammar based algorithm automatically guarantees the validity and conformity of the generated mesh; it prevents from the generation of duplicated nodes and edges, and due to the Rivara’s algorithm it guarantees a minimum quality. The same hypergraph-grammar can be used to remove automatically all the hanging nodes from a given mesh. Due to its concurrent nature, using a hypergraph-grammar allows us to refine the mesh in parallel. Also, we can use partitioning algorithms developed for hypergraphs [2]. As an application of the technique, we will present a terrain mesh generator based on the hypergraph-grammar, and some applications to mesh adaptation in both two and three dimensions.