Keywords: finite element method, mesh generation, submapping, structured mesh, hexahedral element, linear programming, transfinite interpolation.

Several algorithms have been developed to generate hexahedral meshes over the last decade [1]. However, a fully automatic unstructured hexahedral mesh generation algorithm is still an unreachable goal. Therefore, special attention has been focused on algorithms that decompose the entire geometry into several simpler pieces. The submapping algorithm is one of the most powerful methods to decompose a block geometry into pieces and then generate a structured mesh [2,3]. The basic idea is to decompose the entire geometry into patches that are logically equivalent to a hexahedral block. Then, each patch is meshed using a structured hexahedral mesh in such a way that all the compatibilities between patches are verified via a linear integer problem. This problem is called the compatibility problem, see [4] for details. The solution of the compatibility problem provides us the number of intervals (number of elements) of each edge.

Unfortunately, the application of submapping method is hampered by two constraints. First, the angle between two edges or faces should be, approximately, a multiple of pi/2. Second, improved algorithms have to be developed to discretize multiply connected geometries. In this paper we present two original contributions to relax the second constraint. The first contribution is devoted to the conversion of geometries that have voids to simply connected domains. To this end, the outer contour is connected with the inner boundaries using virtual surfaces. These surfaces are determined from a constrained Delaunay tetrahedralization [5]. Finally, when the geometry is converted into a simply connected domain, it can be meshed using the submapping method. The second contribution is focused in the assignment of the number of intervals. If the volume has through holes, we have to modify the compatibility problem. The faces of the geometry do not provide us all necessary equations in order to generate a structured mesh. In fact, we have to assign a compatible number of intervals to every closed path of edges. Although it may seem that the number of closed paths is prohibitive, we only need to assign a compatible number of intervals to a small number of them. These closed paths form a basis of the field of closed paths of edges. Therefore, the objective of this contribution is to compute a basis of closed paths and then solve the compatibility problem on this basis. Finally, we present several examples that illustrate the properties and applicability of the proposed strategies.

1

J.F. Thompson, B. Soni, N. Weatherill "Handbook of Grid Generation", CRC Press, 1999.

2

D. White, "Automatic Quadrilateral and hexahedral meshing of pseudo-cartesian geometries using virtual subdivision", Master thesis, Brigham Young University, 1996.

3

M. Whiteley, D. White, S. Benzley and T. Blacker, "Two and three-quarter dimensional meshing facilitators", Engineering with computers 12:144-154, 1996. doi:10.1007/BF01198730

4

S.A. Mitchell, "High fidelity interval assignment", International Journal of Computational Geometry and Applications 10:399-415, 2000. doi: 10.1142/S0218195900000231

5

H. Si, "A Quality Tetrahedral Mesh Generator and Three-Dimensional Delaunay Triangulator", http://tetgen.berlios.de

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)