Computational geometry applied to parallel mesh generation

Fil: Novara, Pablo José. Universidad Nacional del Litoral. Facultad de Ingeniería y Ciencias Hídricas; Argentina.En esta tesis se presentan dos algoritmos para la tetraedrización de un conjunto de puntos. El primero de ellos toma como entrada un conjunto de puntos y genera una malla de tetraedros para el interior de su envolvente convexa. El resultado es una malla Delaunay, y el algoritmo generado es robusto frente a las ambigüedades conocidas del criterio Delaunay y frente a errores numéricos. El segundo algoritmo agrega a los datos de entrada una malla de frontera que deberá ser respetada en la malla de salida que se genere. Esta malla entonces cubrirá el volumen delimitado por la malla de frontera de entrada, aunque no todos sus elementos respetarán la condición Delaunay, dado que en caso de conflicto se respeta la frontera impuesta por sobre la condición Delaunay. Esta variación del algoritmo permite además mejorar la calidad de los elementos generados. Todos los algoritmos presentados mantienen invariante el conjunto de puntos. Para ambos métodos se proponen estrategias de paralelización para arquitecturas de hardware de memoria compartida y distribuida. Se discuten las ventajas y desventajas de cada una, los problemas encontrados y las posibles soluciones, las diferencias importantes en las implementaciones para cada tipo de arquitectura, y finalmente se presentan resultados y se analiza la eficiencia y escalabilidad de estas implementaciones. Se describen también todas las estructuras de datos utilizadas en ambos métodos y los algoritmos asociados a las mismas, junto con las justificaciones correspondientes para cada una de estas elecciones.This thesis presents two algorithms for parallel generation of unstructured all-tetrahedral meshes for a given set of points. The first method generates a Delaunay mesh for the interior of the point set's convex hull. This algorithm is robust in the sense that it solves all the problems related to numerical errors and Delaunay criterion's ambiguities. The second method adds to the input a fixed boundary mesh, and generates a Delaunay-dominant mesh for the domain defined by such boundary. This generated mesh fits the given boundary mesh connectivities and also improves mesh quality avoiding the generation of slivers, low-quality elements very common in Delaunay meshes. None of this methods will neither add nor move or remove nodes. This makes these algorithms suitable for many common interpolation operations, and for some particle-based simulations where nodes represents particles. Parallel implementations for both shared memory and distributed memory architectures are proposed for the two mesh generation problems presented. Advantages and disadvantages of each one, all problems found and the proposed solutions, and the major differences in the implementations for the two most usual kinds of parallel hardware architectures are described in this thesis. Finally, some results are presented and the parallel scalability and efficiency of the method is discussed. This thesis also includes descriptions for all the necessary data structures for the current implementations and the associated algorithms (for 2D and 3D, and both serial and parallel versions), along with all important details to justify those elections.Consejo Nacional de Investigaciones Científicas y Técnica