Improving algorithms for the generation of polygonal and polyhedral meshes

2018 – 2021

Principal Investigator: Nancy Hitschfeld-Kahler.

Co-Investigator: Alejandro Ortiz-Bernardin.

Project funded by CONICYT-FONDECYT (Grant Nº 1181506)

This project is centered on the design and implementation of novel polygonal and polyhedral meshing strategies that can be used to solve several scientific and engineering problems such as fracture mechanics simulations in solid mechanics, landscape representation for hydrological distributed modeling, and geological simulations, among others. In particular, for fracture mechanics simulations, there exist two numerical methods that use this kind of meshes: polygonal/polyhedral finite elements (PFEM) and the virtual element method (VEM). In the PFEM, convex polygons/polyhedra are preferred due to the limitation of shape function construction. This limitation is not present in the VEM, where non-convex cells are equally usable.

Polygonal (polyhedral) meshes are 2D (3D) discretizations composed of polygons (polyhedra) of any number of sides(faces). The mesh cells can obviously be triangles and rectangles (tetrahedra and hexahedra) wherever they are appropriate. Recent works show that there is an increasing interest in the use of polygonal/polyhedral meshes, particularly because of their extreme flexibility in representing very complex domain geometries, refining coarse cells, and de-refining overly dense regions. Additionally, polygonal/polyhedral meshes have the advantage that a proper mesh can be obtained with less cells and points than in a triangular/tetrahedral mesh. To the best of our knowledge, since the numerical methods that handle polygonal(polyhedral) meshes are no more than ten years old, no attempts have been made in designing algorithms for the generation of polygonal/polyhedral meshes that fulfil both the fitting of the domain geometry and the point density requirements, while reducing the number of points and cells as much as possible. Currently, the most used polygonal/polyhedral cells are Voronoi regions or the ones generated by cutting triangles/quadrilaterals into polygons, because meshes composed of this kind of cells can be built fast, and thus the researchers can show the big potential of polygonal/polyhedral meshes without putting the main effort in the whole mesh generation process.

The main goal of this project is to develop novel methods for the generation of polygonal/polyhedral meshes and compare them with the traditional ones in terms of number of generated points and cells, computational time and memory, and accuracy of the simulation results, among others. We propose to start with a polygonal/polyhedral mesh, that represents exactly the domain geometry, and then refine the polygonal (polyhedral) cells into convex or non-convex cells, depending on the requirements of the used numerical method. We do not want to develop meshing algorithms for a specific numerical method, but instead we plan to identify, model and implement different refinement/improvement criteria, that can be easily interchanged so that a proper mesh for a specific method can be generated. Using this approach, the generated meshes can also be extended to requirements of other applications such as geological simulations or hydrological distributed modeling.

We have already been working in the generation of mixed element meshes, and very recently in the generation of 3D polyhedral Delaunay meshes for convex domains. Therefore, this project is not only a natural continuation of our previous research but also challenges us to design novel strategies to create, improve and extend meshing algorithms for the generation of polygonal/polyhedral meshes. We plan to work in: (a) the design of strategies to fit domain geometries with polygonal/polyhedral cells, (b) the design of strategies to refine, de-refine and improve cells more efficiently than current methods, and (c) the integration of these algorithms into a flexible mesh generator. We also plan to improve the performance of some algorithms by designing and implementing parallel solutions on GPU architectures, and if possible, to explore the parallelization on other parallel architectures.

As result of this research, we expect to contribute with novel algorithms that will allow us to model complex problems in less computational time and in a more accurate way than before. We also expect that these algorithms will be useful for several applications that can be benefit from polygonal/polyhedral meshes. The developed software will be left open source, and available for free to the research and academic community.