Polygon and polyhedron meshing algorithms
Fondecyt cod 1211484
Project Abstract:
This project focus on the design and implementation of polygon and polyhedron meshing strategies that can be used to generate proper domain discretizations to solve several scientific and engineering problems such as fracture mechanics simulations in solid mechanics, landscape representation for hydrological distributed modeling and rock and porous media modeling, among others. Currently, there are two main numerical methods that use this kind of meshes: the 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.
Polygon (polyhedron) meshes are 2D(3D) discretizations composed of polygons (polyhedra) of any number of sides(faces). The mesh cells can obviously be composed of triangles and rectangles (tetrahedra and hexahedra) wherever they are appropriate. Recent works show that there is an increasing interest in the use of polygon/polyhedron meshes, particularly because of their extreme flexibility in representing very complex domain geometries, refining coarse cells, and derefining overly dense regions. Additionally, polygon/polyhedron meshes have the advantage that for some problems and numerical methods a proper mesh can be obtained with less cells and points than in a triangular/tetrahedral mesh. 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 new numerical methods without putting the main effort in the whole mesh generation process.
The main goal of this project is to develop novel algorithms for the generation of polygon/polyhedron 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. This research proposal is the natural continuation of our previous work but here we want to put emphasis in the generation of a new algorithm that can generate from the first step an initial polygon/polyhedron partition of the domain. The main differences with meshes based on the Voronoi diagram are that the initial cells are from the beginning inside the domain and polygons/polyhedra might be non-convex. We expect that for the same point density, these meshes will be formed by less edges and cells than meshes based on the Voronoi meshes, and so improve the performance of numerical solvers that depends on the number of edges and cells. We think that this kind of meshes will benefit several applications in science and engineering, but in particular the problems that can be solved with the VEM in order to provide an alternative spatial discretization, more easily to adapt to complex geometries and to refine mesh elements than meshes based on the Voronoi diagram. We propose to start with a polygon/polyhedron mesh, that represents exactly the domain geometry. Polygons and polyhedra will be generated from terminal-edge regions obtained from Delaunay meshes. Terminal-edges regions are built from triagle sets that fulfil certain geometric characteristics.
A result, we are going to provide new meshing algoritms to the scientific and engineering community and open source prototype meshing tools. We expect that these tools allow them to solve more complex problems than before. 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.
Project objectives:
General and specific goals The main goal of this project is to propose novel strategies to generate polygon/polyhedron meshes that can be useful for solving scientific and engineering problems with numerical methods that benefit from these kind of meshes.
The specific goals planned to reach the general goal are:
- Study the geometric properties of polygons/polyhedra generated from terminal-edge regions from both Delaunay and non-Delaunay partitions.
- Identify and develop quality metrics for polygons/polyhedra to guide the refinement and optimization processes of a mesh
- Develop an algorithm to generate an initial polygon/polyhedron mesh from terminal-edge regions
- Design or extend current refinement optimization strategies to fulfil the point density requirements imposed by the used numerical method and the problem itself.
- Compare the generated meshes with Voronoi based meshes in terms of number of points/elements, accuracy of the simulation results and simulation time/memory, among other comparison criteria.
- Explore the design of gpu based algorithms to accelerate mesh generation and the evaluation processes for 2D polygon meshes