An algorithm for the generation of hexahedral element meshes

An important issue in the design of mechanical parts is the calculation of its properties by finite-element-simulations (e.g.~stess-strain-analysis). This allows to test and optimize parts in an early stage of the design cycle, thus avoiding expensive experiments. The task is however complicated by the fact that construction and simulation require different forms of object representation. While objects are usually constructed by cad systems and represented by a description of their boundary faces, a finite element simulation requires that the object is given as a mesh of tetrahedral or hexahedral elements. Since it would be too costly to create finite element meshes interactively, it is necessary to develop algorithms that automatically generate finite element meshes from cad models.

While many algorithms have been developed for the generation of tetrahedral element meshes, few algorithms for the generation of hexahedral element meshes exist. The CUBIT system uses an advancing-front technique. Another algorithm developed by the QUB finite element group at Queen's University of Belfast is based on a subdivision of the object which is achieved with the help its skeleton (medial axis). In the following we present an approach for that purpose. It will be explained by means of an example.

The algorithm starts by generating an initial fdm-like mesh in the interior of the object (see below). It remains to mesh the region near the boundary - the more difficult task. One can, however, achieve it with basically two-dimensional operations.


The technique for boundary meshing makes use of the fact that the surface of the initial mesh is a mesh of quadrilateral faces. The key idea of the algorithm is that an isomorphic quadrilateral element mesh is generated on the boundary (see below). It is important that a good mesh is constructed in this step, and this is achieved by a series of local modification and smoothing steps which are of two-dimensional nature.


The next picture shows how the boundary region is filled with hexahedra: A hexahedron is constructed from a face (A,B,C,D) of the initial meshs surface and the corresponding face (a,b,c,d) of the boundary mesh. The boundary region is filled with topologically correct hexahedra in this step.


Sometimes it cannot be avoided that the mesh on the boundary has degenerated quadrilaterals when three nodes of a face lie on the same edge of the input model. The hexahedra generated at these faces are not useful for fem calculations.

There are two ways to deal with distorted elements. One way is to insert elements at convex edges. This technique produces good-quality elements and should be prefered.


The technique can not be used at non-convex edges or at edges with too flat an angle. In this case degenerated elements are removed by using a splitting technique. For conformity reasons neighbor elements are split up too, and the mesh has a locally fine structure. Mesh quality is then enhanced by Laplacian smoothing.


Click here to see some examples.

The algorithm is integrated in the finite element preprocessor PEP+ that is developed by Martin Franzke at the Institut fuer Bildsame Formgebung at RWTH Aachen.

A description can be found in Robert Schneiders: A grid-based algorithm for the generation of hexahedral element meshes (submitted for publication in Engineering with Computers; Attention: 10MB postscript!).

Robert Schneiders 17. Mai 1995