Dois métodos distintos são descritos e implementados. O primeiro método, proposto por Ruppert, possui garantias teóricas de qualidade quando a fronteira do domínio obedece certas restrições. O segundo método, proposto por Persson, possibilita um maior controle na densidade dos elementos que discretizam o domínio. As vantagens, desvantagens e particularidades de cada um dos métodos são descritas e detalhadas / Two distinct methods are described and implemented. The first method, proposed by Ruppert, has theoretical guarantees on the quality of elements when the domain boundaries respect certain restrictions. The second method, proposed by Persson, makes it possible to have greater control over the density of the elements that make up the domain. The advantages, disadvantages and specific points about each method are described and detailed

Em muitos problemas de simulação de fenômenos físicos ou fenômenos de engenharia, o uso das malhas é um componente muito importante. Uma malha é uma aproximação de uma dada geometria por um conjunto de elementos mais simples, tais como triângulos e quadriláteros (caso bidimensional) ou tetraedros, prismas, pirâmides e hexaedros (caso tridimensional). Nesse texto, as malhas de interesse são as não-estruturadas e compostas por triângulos. A escolha de uma malha é fortemente influenciada pelo desempenho e precisão dos resultados da simulação. O desempenho depende do número de elementos a serem processados, ou seja, quanto maior for a área coberta por cada elemento da malha, menos elementos são necessários, por conseguinte, mais rápida será a simulaçao. A precisão nos resultados da simulação está relacionada tanto com o formato quanto com o tamanho dos elementos. Diferente do desempenho, quanto menor forem os elementos, mais precisos serão os resultados. O formato dos elementos também influencia a precisão, em geral, elementos mais próximos dos equiláteros são preferidos. Como é possível observar, desempenho e precisão são requisitos conflitantes e geralmente é necessário fazer uma ponderação entre eles. Para um determinado grupo de aplicações, o melhor compromisso entre desempenho e precisão é conseguido com elementos finos, longos e corretamente alinhados sobre o domí?nio onde a malha está definida. São as chamadas malhas anisotrópicas. Além disso, um método de refinamento anisotrópico pode melhorar ainda mais a precisão dos resultados. O principal objetivo desse trabalho é desenvolver métodos de refinamento de malhas anisotrópicas, usando como base, e tendo como ponto de partida, os métodos de refinamento Delaunay isotrópicos, a saber, os métodos de refinamento Delaunay de Jim Ruppert [13] e de Paul Chew [6], e também realizar a simplificação Delaunay proposto por Olivier Devillers [8] / The use of polygonal meshes for numerical simulation of physical problems is a well known component. Mesh is an piecewise approximation from a given geometry defined by a set of simpler elements, such as triangles and quadrilaterals (two-dimensional case) or tetrahedra, prisms, pyramid and hexahedra (three-dimensional case). In this work, the interest is unstructured meshes of triangles. The choice of a mesh is aimed at the performance and the precision of the simulation results. The performance depends of the number of elements that will be processed, i.e., the larger is the covered area for each mesh element, the less element is needed, therefore the simulation is faster performed. The simulation precision is related with the shape and the size of the elements. On the other hand, the smaller the elements are, the more precise are the results. The shape of the elements also influences on precision, generally, equilateral elements are preferred. It is worth to mention that performance and precision are opposite requirements and it is important to ponder between them. For a group of applications, the best commitment between performance and precision is obtained with thin and long elements correctly aligned on the domain where the mesh is defined. These meshes are named anisotropic meshes. Furthermore, a method of anisotropic refinement can even improve the precision. We aim at developing anisotropic mesh methods based on isotropic properties from well known Delaunay refinement methods, viz., the Delaynay refinement methods by Jim Ruppert [13] and Paul Chew [6], and performing a Delaunay simplification proposed by Olivier Devillers [8]

Dans cette thèse, nous cherchons à reconstruire une approximation d'une variété connue seulement à partir d'un nuage de points de grande dimension l'échantillonnant. Nous nous efforçons de trouver des méthodes de reconstructions efficaces et produisant des approximations ayant la même topologie que la variété échantillonnée. Une attention particulière est consacrée aux flag-complexes et particulièrement aux complexes de Rips. Nous montrons que le complexe de Rips capture la topologie d'une variété échantillonnée en supposant de bonnes conditions d'échantillonnage. En tirant avantage de la compacité des flags-complexes qui peuvent être représentés de manière compacte avec un graphe, nous présentons une structure de données appelée squelette/bloqueurs pour complexes simpliciaux. Nous étudions ensuite deux opérations de simplifications, la contraction d'arête et le collapse simplicial, qui s'avèrent utiles pour réduire un complexe simplicial sans en changer sa topologie. / In this thesis, we look for methods for reconstructing an approximation of a manifold known only through a high-dimensional point cloud. Especially, we are interested in efficient methods that produce approximations that share the same topology as the sampled manifold. A particular attention is devoted to flag-complexes and more specially to Rips complexes due to their compactedness. We show that the Rips complex shares the topology of a sampled manifold under good sampling conditions. By taking advantage of the compactedness of flag-complexes, we present a data structure for simplicial complexes called skeleton/blockers. We then study two simplification operations, the edge contraction and the simplicial collapse, that turn out to be useful for reducing a simplicial complex without changing its topology.

Dois métodos distintos são descritos e implementados. O primeiro método, proposto por Ruppert, possui garantias teóricas de qualidade quando a fronteira do domínio obedece certas restrições. O segundo método, proposto por Persson, possibilita um maior controle na densidade dos elementos que discretizam o domínio. As vantagens, desvantagens e particularidades de cada um dos métodos são descritas e detalhadas / Two distinct methods are described and implemented. The first method, proposed by Ruppert, has theoretical guarantees on the quality of elements when the domain boundaries respect certain restrictions. The second method, proposed by Persson, makes it possible to have greater control over the density of the elements that make up the domain. The advantages, disadvantages and specific points about each method are described and detailed

[pt] Malhas são amplamente usadas na discretização de domínios geométricos em aplicações na engenharia, como simulações de fluxo, transmissão de calor e deformação mecânica. O problema de geração de malhas é bem conhecido e estudado, mas a geração automática de malhas para um domínio físico com geometrias complexas, criando elementos que obedeçam a forma do objeto, e de tamanho e qualidade adequados, ainda é um desafio. Neste trabalho, foram estudados e implementados métodos para gerar malhas com restrições arbitrárias. O gerador implementado é do tipo de Delaunay, que constrói malhas Delaunay com restrições, e utiliza as propriedades da malha para inserir novos vértices e melhorar a qualidade dos elementos. / [en] Meshes are widely used in the discretization of geometric domains for engineering applications such as fluid flow simulator, heat transfer simulations and mechanical deformation. The mesh generation problem is well known and studied, nevertheless the automatic generation of meshes to domains with complex geometry, creating elements that conform to the forms, and of adequate size and quality, is still a challenge. In this work, mesh generation methods capable of generation mesh of arbitrary restrictions were studied and implemented. The implemented generator is a Delaunay generator, which constructs constrained Delaunay meshes, and utilizes the properties of the mesh to insert new vertices and improve the quality of the elements.

Made available in DSpace on 2014-07-29T16:02:22Z (GMT). No. of bitstreams: 1 Dissertacao Luiz Souza.pdf: 3328860 bytes, checksum: 1983c2d013f54a9ebce4575a9b45bf38 (MD5) Previous issue date: 2008-05-30 / In this dissertation we have studied the articles The Surfaces of Delaunay, by James Eells, and Classi¯cation des Surfaces de Type Delaunay, by Ricardo Sa Earp and Eric Toubiana. Based on the ¯rst work we have classi¯ed the surfaces of revolution of constant mean curvature known as surfaces of Delaunay. By using the second one we have looked at special surfaces of Weingarten, whose mean and gaussian curvatures satis¯es the relation H = f(H2 ¡ K); where f is an elliptic function of class C1. We have classi¯ed the complete surfaces of revolution, that satis¯es the Weingarten relation. They are known as surfaces of Delaunay Type / Nesta dissertação ao estudamos os artigos The Surfaces of Delaunay, de Eells, James, e Classification des Surfaces de Type Delaunay, de Ricardo Sa Earp e Eric Toubiana Baseado no primeiro trabalho classificamos as superfícies de rotaação de curvatura média constante conhecidas como superfícies de Delaunay. Utilizando o segundo trabalho apre- sentamos um estudo sobre superfícies especiais de Weingarten, cuja curvatura média e Gaussiana satisfazem a relação H = f(H2¡K); onde f uma função elíptica de classe C1. Classificamos as superfícies de rotação completas, satisfazendo uma relação de Weingarten Elas são conhecidas como superfícies Tipo Delaunay

Spherical, Euclidean, and hyperbolic simplices can be characterized by the dihedral angles on their codimension-two faces. These characterizations analyze the Gram matrix, a matrix with entries given by cosines of dihedral angles. Hyperideal hyperbolic simplices are non-compact generalizations of hyperbolic simplices wherein the vertices lie outside hyperbolic space. We extend recent characterization results to include fully general hyperideal simplices. Our analysis utilizes the Gram matrix, however we use inversive distances instead of dihedral angles to accommodate fully general hyperideal simplices.For two-dimensional triangulations, an angle structure is an assignment of three face angles to each triangle. An angle structure permits a globally consistent scaling provided the faces can be simultaneously scaled so that any two contiguous faces assign the same length to their common edge. We show that a class of symmetric Euclidean angle structures permits globally consistent scalings. We develop a notion of virtual scaling to accommodate spherical and hyperbolic triangles of differing curvatures and show that a class of symmetric spherical and hyperbolic angle structures permit globally consistent virtual scalings.The double tetrahedron is a triangulation of the three-sphere obtained by gluing two congruent tetrahedra along their boundaries. The pentachoron is a triangulation of the three-sphere obtained from the boundary of the 4-simplex. As piecewise flat manifolds, the geometries of the double tetrahedron and pentachoron are determined by edge lengths that gives rise to a notion of a metric. We study notions of Einstein metrics on the double tetrahedron and pentachoron. Our analysis utilizes Regge's Einstein-Hilbert functional, a piecewise flat analogue of the Einstein-Hilbert (or total scalar curvature) functional on Riemannian manifolds.A notion of conformal structure on a two dimensional piecewise flat manifold is given by a set of edge constants wherein edge lengths are calculated from the edge constants and vertex based parameters. A conformal variation is a smooth one parameter family of the vertex parameters. The analysis of conformal variations often involves the study of degenerating triangles, where a face angle approaches zero. We show for a conformal variation that remains weighted Delaunay, if the conformal parameters are bounded then no triangle degenerations can occur.

Ingeniero Civil en Computación / La simulación de cuerpos que interactúan entre sí por medio de fuerzas y la detección de colisiones entre cuerpos son problemas estudiados en distintas áreas, como astrofísica, fisicoquímica y videojuegos. Un campo en particular corresponde al estudio de los coloides, partículas microscópicas suspendidas sobre otra sustancia y que tienen aplicaciones en distintas industrias. El problema consiste en simular la evolución de un sistema con distintos tipos de partículas coloidales a través del tiempo, cumpliendo las propiedades de volumen excluido, movimiento aleatorio y condiciones de borde periódicas. Además, la interacción de largo alcance entre coloides presenta la particularidad de no cumplir con el principio de acción y reacción. Se desarrolló un algoritmo de simulación completamente paralelo en GPU, implementado en la plataforma CUDA y C++. La solución utiliza una triangulación de Delaunay en memoria de la tarjeta gráfica para conocer eficientemente la vecindad de cada partícula, lo que permite resolver traslapes entre partículas sin tener que evaluar todo el sistema. Se utilizó una implementación reciente del algoritmo de edge-flip para mantener la triangulación actualizada en cada paso de tiempo, extendiendo además el algoritmo para corregir los triángulos invertidos. Para el caso de fuerzas de corto alcance, además se desarrolló un algoritmo paralelo que construye y utiliza listas de Verlet para manejar las vecindades entre partículas de forma más eficiente que la implementación anterior. Los resultados obtenidos con la implementación paralela presentan una mejora de hasta dos órdenes de magnitud con respecto al tiempo de la solución secuencial existente. Por otro lado, el algoritmo para fuerza de corto alcance mejora de igual magnitud con respecto a la solución de largo alcance desarrollada. También se verificó que la corrección de traslapes con triangulación de Delaunay se hace de forma eficiente, y que esta estructura puede ser aplicada para otros problemas relacionados, como implementar el cálculo de fuerzas de corto alcance (y compararlo con la implementación ya existente) o realizar simulaciones aproximadas utilizando triangulaciones. / Financiado parcialmente por el Proyecto FONDECYT # 1140778

Ingeniero Civil en Computación / El universo visto a gran escala presenta estructuras llamadas murallas cósmicas y vacíos cósmicos. Las murallas poseen una alta densidad galáctica, mientras que los vacíos presentan una notable baja densidad. En Astronomía son objeto de estudio y para el efecto es necesario analizar grandes volúmenes de datos, lo cual no es factible hacerlo manualmente, siendo necesarios algoritmos que identifiquen automáticamente ambos tipos de zonas cósmicas. Actualmente existen muy pocos algoritmos diseñados para esa tarea. Uno de los más recientes fue presentado en el año 2014 por Hervías et al. y permite determinar bajas densidades en "rebanadas" bidimensionales de datos volumétricos, pudiéndose extender naturalmente la forma en que trabaja al caso tridimensional. Recibe como entrada un conjunto de puntos, cada uno siendo la abstracción geométrica de una galaxia. El algoritmo tiene dos fases: triangulación y clasificación de triángulos. Se basa en la identificación de aristas largas en la triangulación de Delaunay asociada a los n puntos de entrada, para determinar bajas densidades galácticas. En su segunda fase determina en forma secuencial los triángulos que pertenecen a vacíos con una complejidad O(nlog(n)). A mediados de este año, Alonso presenta una extensión del algoritmo, agregándole una tercera fase de fusión de vacíos adyacentes. Logra una implementación que clasifica con complejidad O(nlog(n)) en forma experimental. En esta memoria se hace un razonamiento profundo sobre las propiedades de los conjuntos de triángulos que son identificados como vacíos en una triangulación. La investigación teórica realizada permite presentar tres nuevas formas de clasificación que proporcionan los mismos resultados que la original: una O(n) secuencial, una O(n) paralela y una O(log(n)²) paralela. Se implementan las O(n) desarrolladas, resultando ser experimentalmente más eficientes que la clasificación de la implementación de Alonso. En particular, la O(n) paralela exhibe un mejor desempeño que la O(n) secuencial. Con lo anterior se logra el objetivo de esta memoria. La O(log(n)²) paralela se deja propuesta para su implementación a futuro y tal vez conectarse a una triangulación de Delaunay paralela.

Ingeniero Civil en Computación / El método de elementos finitos, que permite resolver numéricamente problemas modelados por ecuaciones diferenciales parciales para el análisis de complejos problemas físicos sobre geometrías complejas, es una de las más importantes aplicaciones del ámbito científico. En estos problemas las geometrías son modeladas utilizando mallas geométricas, cuya calidad determina la precisión de los cálculos y de los resultados obtenidos por el método. En una malla geométrica definida por una triangulación, se entiende por calidad que el ángulo mínimo de cada triángulo esté acotado inferiormente por un valor acorde a la necesidad del problema. Dado un conjunto de puntos para construir una triangulación, las triangulaciones de tipo «Delaunay» se caracterizan por maximizar el ángulo mínimo interior de sus triángulos, y en consecuencia producen la triangulación de mejor calidad basada en tales puntos. Sin embargo, en caso de requerirse una mejor calidad, ésta puede mejorarse insertando nuevos puntos estratégicamente. En este contexto, los algoritmos tipo «Delaunay» de refinamiento de mallas juegan un rol de importancia ya que proveen métodos de mejoramiento de la calidad de una triangulación por medio de la inserción de puntos adicionales. Cada inserción se realiza mediante un proceso que mantiene la propiedad de «Delaunay» de la malla, e incrementan su calidad. Los distintos de algoritmos refinamiento tipo «Delaunay» presentan diferencias en cuanto a su desempeño y a la malla resultante. Ciertos algoritmos incorporan una etapa de «preprocesamiento», en la cual se prepara la malla para prevenir complicaciones durante el desempeño del resto del algoritmo. Adicionalmente, algunos se benefician de procesar los triángulos siguiendo un orden en particular. Omitir el preprocesamiento u ordenamiento en estos casos, altera el resultado obtenido. Es posible estudiar el comportamiento de los algoritmos al establecer comparaciones entre sus condiciones de procesamiento respecto a los resultados obtenidos. Existen programas computacionales que permiten la aplicación de un algoritmo de refinamiento sobre una malla y que como resultado presentan la malla mejorada y estadísticas respecto al desempeño del algoritmo durante la ejecución. Estas aplicaciones requieren ser ejecutadas una vez por cada refinamiento. Para el caso en que el número de algoritmos y/o mallas es considerable, lo anterior impone una dificultad. En particular cuando se busca establecer comparaciones relativas al comportamiento de los algoritmos, esta situación obliga al investigador a realizar un trabajo posterior de manejo de datos y visualización para los resultados obtenidos. Así, el tiempo de trabajo y esfuerzos adicionales, en casos de grandes volúmenes de pruebas y datos, pueden llegar a ser imprácticos fácilmente. En esta memoria se pretende elaborar una herramienta inteligente para comparar algoritmos de refinamiento tipo «Delaunay», realizar «tuning» de algunos algoritmos, proponer nuevos, etcétera, considerando diversas condiciones de procesamiento. Adicionalmente, se espera que la herramienta permita definir esquemas de ejecuciones de procesamiento, a través de los cuales sea posible analizar y obtener grandes cantidades de resultados de manera simple y práctica. Finalmente, la aplicación deberá generar «Reportes de Visualización de Resultados» en archivos «html», que incluyen cada detalle de la configuración y de los resultados, además de visualizaciones de gráficos para las tablas comparativas producidas. En las siguientes páginas se aborda en detalle el proceso de diseño e implementación de esta herramienta, cuyo desarrollo se ejecuta a partir de la elaboración de una biblioteca basada en la aplicación «Compare2DMesh», que fue producida en trabajos anteriores, la cual permite la ejecución individual y obtención de resultados de un refinamiento tipo «Delaunay» sobre una malla. Esta nueva biblioteca, llamada «C2M», supera a la aplicación original en múltiples aspectos. Además, se construye una nueva aplicación «BatchRefinement» que utiliza «C2M», y que provee una interfaz gráfica a través de la cual se proveen funcionalidades que satisfacen todos los requerimientos relacionado al trabajo con volúmenes de experimentos y generación de reportes con los análisis de los resultados. Estos reportes son creados en unos pocos segundos, de manera automática y flexible, y presentan información que habría tomado horas procesar sin esta herramienta. Las pruebas realizadas confirman la versatilidad de la aplicación, e indican una mejoría respecto a «Compare2DMesh» en muchos aspectos. A lo largo de este documento, se discuten temas relevantes y consideraciones relacionadas con la implementación actual y, en determinados casos, con los trabajos anteriores.