Polygonal/polyhedral mesh generation from Delaunay tessellations

Abstract

In computational modeling, the Virtual Element Method (VEM) represents a significant advancement, enabling the use of arbitrary polygonal and polyhedral cells for the spatial discretization of domains. This flexibility allows for a broader application spectrum, ranging from hydrological modeling to fracture mechanics and real-time visualization of physical phenomena. Unlike traditional Finite Element Method (FEM) simulations, which often require dense meshing to meet quality criteria, VEM's versatility in handling cells of any shape can lead to a reduction in the number of cells and points required, potentially enhancing simulation efficiency.

The challenge, however, lies in the generation of high-quality meshes that are optimally adapted to specific applications and numerical methods. While Voronoi diagrams and Delaunay partitions have been widely used for their favorable geometric properties, there is a growing need for more efficient and flexible meshing algorithms.

This doctoral thesis details the conceptual framework, the design, development, computational complexity and validation of Polylla, an algorithm for generating polygonal and polyhedral meshes with arbitrarily shaped polygons (convex and no convex polygons). Initially focused on 2D mesh generation, Polylla creates meshes from triangulations by building polygons around terminal-edge regions. This method offers a simpler and faster alternative to constrained Voronoi meshes, resulting in fewer polygons without compromising the performance of numerical methods such as the VEM.

The work expands to include a GPU-accelerated implementation for increased computational speed, and a compact half-edge data structure for reduced memory usage, and a preliminary 3D version of Polylla. The 3D extension introduces new concepts to facilitate volumetric mesh creation. The GPU version demonstrates significant speed improvements, achieving up to an x83.2 speedup over CPU implementation, and a speedup of x746.8 when the cost of copying the data from the host device and back is not included. The compact data structure reduces memory requirements for mesh topology by 99% and reduces the memory cost necessary for the generation of the meshes by a factor of 3.

The Polylla algorithm contributes a new type of mesh to the polygonal/polyhedral mesh generation community, enabling the modeling of the world with arbitrary shapes beyond the traditional constraints of triangles and quadrilaterals. This allows the user to represent complex real-life geometries with quality polygonal meshes of any size.

En la modelación computacional, el Método de Elementos Virtuales (VEM, por sus siglas en inglés) representa un avance significativo, permitiendo el uso de celdas poligonales y poliédricas arbitrarias (con poligonos convexos y no convexos) para la discretización de dominios geometricos. Esta flexibilidad permite un espectro de aplicación más amplio, que abarca desde el modelado hidrológico hasta la mecánica de fracturas, y la visualización en tiempo real de fenómenos físicos. A diferencia de las simulaciones tradicionales del Método de Elementos Finitos (FEM, por sus siglas en inglés), que a menudo requieren un mallado denso para cumplir con los criterios de calidad, la versatilidad del VEM en el manejo de celdas de cualquier forma puede llevar a una reducción en el número de celdas y puntos requeridos, mejorando potencialmente la eficiencia de la simulación. El desafío, sin embargo, radica en la generación de mallas de alta calidad que estén óptimamente adaptadas a aplicaciones y métodos numéricos específicos. Aunque los diagramas de Voronoi y las particiones de Delaunay han sido ampliamente utilizados por sus propiedades geométricas favorables, existe una creciente necesidad de algoritmos de mallado más eficientes y flexibles. Esta tesis doctoral detalla el marco conceptual, el diseño, desarrollo, complejidad computacional y validación de Polylla, un algoritmo para generar mallas poligonales y poliédricas con polígonos de forma arbitraria (polígonos convexos y no convexos). Inicialmente centrado en la generación de mallas 2D, Polylla crea mallas a partir de triangulaciones construyendo polígonos alrededor de regiones de aristas terminales ("terminal-edge regions"). Este método ofrece una alternativa más simple y rápida a las mallas de Voronoi restringidas ("constrained Voronoi meshes"), resultando en menos polígonos sin comprometer el rendimiento de métodos numéricos como el VEM. El trabajo se expande para incluir una implementación acelerada por GPU para aumentar el tiempo de generación de las mallas, una estructura de datos compacta de media arista ("half-edge") para reducir el uso de memoria, y una versión preliminar 3D de Polylla. La extensión 3D introduce nuevos conceptos para facilitar la creación de mallas volumétricas. La versión GPU demuestra mejoras significativas de velocidad, logrando una aceleración de hasta ×83.2 sobre la implementación en CPU, y una aceleración de ×746.8 cuando no se incluye el costo de copiar los datos desde el dispositivo anfitrión ("host") y de regreso. La estructura de datos compacta reduce los requisitos de memoria para la topología de la malla en un 99% y reduce el costo de memoria necesario para la generación de las mallas en un factor de 3. El algoritmo Polylla aporta un nuevo tipo de malla a la comunidad de generación de mallas poligonales/poliédricas, permitiendo modelar el mundo con formas arbitrarias más allá de las restricciones tradicionales de triángulos y cuadriláteros. Esto permite al usuario representar geometrías complejas de la vida real con mallas poligonales de calidad de cualquier tamaño.