Ingeniero Civil en Computación / Existen aplicaciones en donde una triangulación de buena calidad es esencial, entendiéndose por calidad que el ángulo mínimo de cada triángulo esté acotado inferiormente. El método de elementos finitos corresponde a una de las aplicaciones más importantes. Los algoritmos de refinamiento de triangulaciones eliminan aquellos triángulos que poseen algún ángulo interior menor a un umbral deseado, mediante la inserción de nuevos puntos en la triangulación original. Un subconjunto de estos algoritmos, que reciben el nombre de algoritmos de refinamiento Delaunay, toman como punto de partida una triangulación de Delaunay restringida de los datos de entrada, y mediante inserciones Delaunay de los nuevos vértices mantienen la condición de Delaunay tras cada inserción. Estos algoritmos son los más utilizados para obtener triangulaciones de calidad. En esta memoria se desarrolló un nuevo software de comparación de algoritmos de refinamiento llamado Compare2DMesh, el cual permite: hacer comparaciones experimentales rigurosas de los diferentes algoritmos de refinamiento Delaunay, manejar cualquier tamaño de mallas y geometrías complejas, visualizar cada inserción de un nuevo vértice mientras la triangulación está siendo refinada, refinar sin visualización del progreso, y configurar y ejecutar variaciones de los algoritmos. Este software usó como base un prototipo llamado MeshSuite. Para validar el desempeño de Compare2DMesh se realizaron experimentos de comparación entre los algoritmos implementados, y también se comparó con otros software de refinamiento. Se concluyó que Compare2DMesh supera considerablemente el rendimiento del prototipo del que fue originado, y que procesa mallas grandes en tiempos razonables, lo que permite que Compare2DMesh pueda ser utilizado para los fines de probar, comparar y afinar algoritmos.

El uso de elementos finitos para analizar fenómenos físicos modelados por ecuaciones diferenciales parciales requiere de una discretización del dominio, como lo son las triangulaciones en dos dimensiones. En este contexto se distinguen tres problemas: generar una triangulación a partir de un conjunto de vértices y segmentos, refinar una malla y mejorar la calidad de una malla. Los algoritmos que refinan triangulaciones Delaunay en general se basan en seleccionar nuevos puntos y realizar una inserción Delaunay de éstos. Los criterios usados para comparar algoritmos se basan en la cantidad de inserciones que realizan, la cantidad de triángulos generados y el tiempo de ejecución. Sin embargo, es difícil encontrar implementaciones que realicen las comparaciones bajo un mismo ambiente y condiciones. En esta memoria se ha diseñado un marco de experimentación que permite investigar y comparar algoritmos de refinamiento Delaunay dentro de un mismo ambiente. Se propone un proceso de refinamiento genérico y se desarrolla una herramienta que, haciendo uso de patrones de diseño de programación con orientación a objetos, implementa el proceso con la flexibilidad de poder extender la herramienta con nuevos algoritmos de forma simple. Se provee una interfaz gráfica que permite seguir el proceso de refinamiento en una forma clara y didáctica. La herramienta genera resultados comparables con los resultados de Triangle, una herramienta de refinamiento Delaunay rápida y eficiente, pero limitada en su extensibilidad y usabilidad. La extensibilidad de la herramienta se puso a prueba implementando los siguientes criterios de selección de puntos asociados a triángulos de mala calidad: Circuncentro, Off-Center, Lepp - Punto Medio, Lepp - Centroide y Lepp - Bisección (No Delaunay). Se evalúan también técnicas de priorización en el procesamiento de los triángulos de mala calidad. Se experimentó con un algoritmo nuevo, Lepp -Circuncentro, el cual presentó un buen rendimiento con las mallas estudiadas, alcanzando en algunos casos una exigencia de 37º como ángulo interior mínimo. Se estudiaron criterios de priorización en la selección de triángulos de mala calidad, concluyendo que el comportamiento de los algoritmos de tipo Lepp es independiente del uso de técnicas de priorización. En cambio, el algoritmo Off-Center aumenta considerablemente el número de puntos insertados si no se utiliza un orden de procesamiento adecuado.

Las mallas de triángulos son ampliamente utilizadas en aplicaciones científicas e ingeniería. Una triangulación de un conjunto de puntos puede construirse utilizando diversos algoritmos, pero usualmente se prefiere aquellos que además de ser eficientes en tiempo y espacio, entreguen triángulos cuyo menor ángulo se encuentre sobre cierta cota. La triangulación de Delaunay de un conjunto de puntos maximiza el ángulo mínimo de todos los triángulos de la triangulación. Sin embargo, el ángulo mínimo en una triangulación de Delaunay puede ser menor que el valor requerido en una aplicación dada. Existen métodos de refinamiento de triangulaciones basados en la inserción de nuevos puntos en la malla que incrementalmente mejoran el ángulo mínimo de una triangulación. De especial interés es la familia de métodos de refinamiento basados LEPP, que recorren los triángulos de una malla a través de las aristas más largas de los triángulos. El uso de los métodos de refinamiento basados en LEPP-Delaunay en aplicaciones, requiere la implementación de estructuras de datos para la representación de la malla, primitivas geométricas, algoritmos de triangulación y algoritmos de manipulación de los datos. El costo de escribir una aplicación desde cero se eleva al considerar los requisitos anteriormente mencionados. El presente informe describe la implementación de una biblioteca reusable y general que ofrece la funcionalidad de los métodos LEPP-Delaunay. De esta manera, es posible crear aplicaciones que utilicen dichos métodos sin la necesidad de invertir tiempo de desarrollo en los algoritmos y estructuras de datos asociadas. En otras palabras, el foco del desarrollo puede estar completamente en la aplicación de los métodos LEPP-Delaunay y no en sus detalles de implementación. La biblioteca LEPP-Delaunay fue construida utilizando las estructuras de datos de OpenMesh, proyecto que ofrece una implementación extensible y flexible de la representación de una malla en base a la estructura de datos halfedge. Para mostrar las capacidades de la biblioteca LEPP-Delaunay se implementó una herramienta gráfica para el análisis de mallas que hace uso de la funcionalidad provista por la biblioteca LEPP-Delaunay.

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.

Memoria para optar al título de Ingeniero Civil en Computación / La triangulación de Delaunay es una entidad geométrica con muchas aplicaciones en computación gráfica e ingeniería. Por lo general, su construcción es un problema difícil que a menudo viene acompañado con restricciones geométricas y de calidad. Para facilitar la experimentación de algoritmos relativos al problema de Delaunay, se presenta una herramienta con mejoras en simplicidad, desempeño y robustez frente a otras opciones existentes. En primer lugar, se ofrece una implementación sólida del algoritmo de Delaunay incremental con intercambio de aristas, el cual es un método conocido que aborda el problema agregando cada punto de la triangulación secuencialmente. Esta implementación maneja las estructuras de datos de forma sencilla (triángulos con punteros a sus vecinos), por lo que es fácil de extender. Además, asegura que las triangulaciones siempre quedan bien definidas, anulando cualquier operación que invalide la triangulación de acuerdo con un criterio de robustez sobre los triángulos. En segundo lugar, se implementa un algoritmo que adapta las triangulaciones para satisfacer restricciones en las aristas, el cual funciona por medio de una idea sencilla que reusa conceptos del algoritmo de Delaunay incremental. En cada iteración se localizan los triángulos que intersectan la arista que se quiere respetar y se intercambian las diagonales secuencialmente hasta que sea respetada. Finalmente, el algoritmo Lepp-Centroide desarrollado por la profesora Rivara y coautores permite obtener una triangulación de buena calidad (ángulo mínimo acotado) por medio de la inserción de nuevos puntos. La implementación de esta memoria se comporta como ha sido establecido en estudios teóricos y prácticos previos, lo que significa que se consigue mejorar la calidad de las triangulaciones insertando pocos puntos y con restricciones geométricas menos fuertes.

Ingeniero Civil en Computación / En este trabajo se discute un sistema experimental para resolver ecuaciones diferenciales parciales (EDP) elípticas o parabólicas sobre dominios en 2-D mediante el método de elementos finitos (MEF). La herramienta combina algoritmos de refinamiento y desrefinamiento de triangulaciones conformes sobre dominios generales con bordes curvos en las fronteras e interfaces de medios; el MEF, usando elementos lineales; una estructura de datos adecuada; el uso de estimadores del error cometido en la resolución numérica; una interfaz gráfica sobre XWindows y un lenguaje declarativo para la definición de los problemas. La herramienta fue desarrollada en forma modular, para permitir la incorporación de nuevas opciones, como elementos de grado mayor en el uso del MEF, y utiliza librerías externas, como son, Sparse y SuperLU para la resolución de los sistemas de ecuaciones poco densos, pdraw para visualización de resultados en 3D y GLADE para construcción de la interfaz gráfica; todas estas herramientas corresponden a software de código abierto. La herramienta tiene un uso potencial en una amplia gama de aplicaciones, por ejemplo en cálculo estructural, y mecánica de fluidos y permite al usuario manejar en forma flexible la adaptabilidad, pudiendo definir o modificar a través de la interfaz gráfica, las triangulaciones, nodos, conexiones, moléculas, condiciones de borde y lados curvos. Esta interfaz, también permite al usuario definir o modificar tanto el problema que se desea resolver, como las regiones en las que el usuario desea dirigir ya sea el refinamiento como el desrefinamiento de la triangulación. Los estimadores de error utilizados permiten crear indicadores que dirigen el refinamiento y desrefinamiento en forma adaptativa, para mejorar la solución con la menor interacción del usuario. Con ello solo se debe definir una triangulación inicial conforme que representa una malla gruesa y luego por medio de los mecanismos de refinamiento explícito o los procesos adaptativo, obtener una triangulación que provea de una malla mas fina, que permitirá obtener una solución de mejor calidad. Se ilustra el uso del sistema con problemas de prueba, de solución conocida; se muestra la imagen de la malla inicial del dominio y de algunas iteraciones, la malla y solución asociada. Se concluye que esta herramienta constituye un software general, flexible y sencillo de usar para resolver problemas de EDP sobre dominios en 2-D generales.

Ingeniero Civil en Computación / La Geomorfología fluvial corresponde al estudio de los procesos de formación y sedimentación de los ríos, y de su interacción con el entorno, lo que entrega información sobre la "historia de vida" de un terreno. En este contexto, existen dos elementos de estudio interesantes: las redes de drenaje y las terrazas fluviales. Runnel es un software que tiene por objetivo visualizar y detectar patrones de drenaje y terrazas fluviales sobre terrenos representados por grillas o triangulaciones de éstas. Si bien el funcionamiento de Runnel es correcto, éste tiene un gran problema: el tiempo de ejecución de sus principales algoritmos. A medida que el tamaño del terreno crece, el tiempo de ejecución aumenta considerablemente. Con el fin de mejorar este problema, se decidió paralelizar los algoritmos de detección de redes de drenaje: Peucker, Callaghan, RWFlood y Ángulo Diedro. Al mismo tiempo, se decidió implementar una triangulación simplificada, la cual disminuye el número de triángulos, y en consecuencia, se disminuye el tiempo de ejecución de los algoritmos que usan la triangulación. Para lograr la paralelización se utilizó OpenCL, herramienta que permite la ejecución de un código paralelo tanto en GPU como en CPU de forma indistinguible. Para la triangulación simplificada se utilizó un algoritmo basado en la eliminación de uno de los vértices de aquellos triángulos que cumplen una condición predeterminada. Como resultado de la paralelización se obtuvieron mejoras significativas con los algoritmos de Peucker (speed-up mínimo: 1.19 y speed-up máximo: 13.63), Callaghan (speed-up mínimo: 5.87 y speed-up máximo: 19.82) y Ángulo Diedro (speed-up mínimo: 1.43 y speed-up máximo: 23.53). La triangulación simplificada también entregó mejoras en rendimiento, pero con menor impacto que la paralelización (speed-up mínimo: 1.14 y speed-up máximo: 1.94). El único algoritmo que no resultó en mejoras en su tiempo de ejecución (en la mayoría de los casos de prueba) fue el algoritmo RWFlood (speed-up mínimo: 0.16 y speed-up máximo: 2.93). Junto con el desarrollo de los algoritmos paralelos se adquirió conocimiento sobre las diferencias de rendimiento de una CPU con una GPU. Se tuvo que ahondar en la arquitectura de cada una y reconocer el tipo de problema que cada una puede resolver de manera óptima. Se propone como trabajo futuro solucionar el uso excesivo de la memoria en la triangulación, analizar del impacto de la triangulación simplificada en los terrenos, solucionar el problema del tiempo de ejecución de RWFlood y paralelizar otros algoritmos.

Doctor en Ciencias, Mención Computación / La generación y refinamiento de mallas son temas de gran interés en aplicaciones tales como simulación de fenómenos físicos mediante el uso de los métodos de elementos finitos, en aplicaciones CAD, modelado geométrico y mallas geométricas. Una malla es un conjunto de elementos geométricos (polígonos o poliedros) que no se superponen, los cuales están conectados por medio de vértices, aristas y caras, que se usan para aproximar dominios geométricos. Los algoritmos de refinamiento producen mallas cada vez más finas para discretizar dominios complejos, representar objetos con topologías arbitrarias y también superficies con formas complejas. En esta tesis se estudió la paralelización de algoritmos de refinamiento basados en el concepto de Lepp para sistemas multicore (multinúcleo) y sistemas distribuidos. Se consideraron dos problemas: (1) refinamiento de mallas de buena calidad: aquí dada una malla de entrada de buena calidad, ésta es iterativa y localmente refinada (de acuerdo a un requerimiento externo a la aplicación) para producir una malla final de calidad análoga a la inicial; (2) refinamiento de triangulaciones Delaunay de mala calidad, donde dada una triangulación Delaunay de entrada de mala calidad (con una geometría dada), deseamos producir una triangulación Delaunay de buena calidad y de tamaño óptimo. Algoritmos basados en el concepto de Lepp son algoritmos refinamiento por la arista más larga mejorados donde el refinamiento de cualquier triángulo t tiene asociado un Lepp(t). En el contexto de los sistemas multicore se desarrollaron algoritmos Lepp-bisección multicore eficientes y escalables para el refinamiento de mallas de 2 y 3 dimensiones. También se desarrolló un algoritmo Lepp-Delaunay multicore para la generación de mallas Delaunay de buena calidad. En el contexto de los sistemas de memoria distribuida se desarrolló un algoritmo Lepp-bisección distribuido para el refinamiento de mallas de 2 dimensiones donde la malla inicial es subdividida dentro de un conjunto de submallas (o subparticiones), las cuales son distribuidas entre los procesadores. También se desarrolló una estrategia eficiente para garantizar que se obtiene una malla final válida (conforme) en las interfaces de submallas vecinas. Se realizaron evaluaciones empíricas de los algoritmos paralelos sobre arquitecturas multicore y sistemas de memoria distribuida que muestran que los algoritmos paralelos tienen buen desempeño.

Doctor en Ciencias, Mención Computación / Las técnicas de generación y refinamiento de mallas no estructuradas son usadas para la descomposición de objetos geométricos. Estas técnicas son muy utilizadas en áreas como modelamiento geométrico, computación gráfica, computación científica y aplicaciones de ingeniería, entre otras, lo que les da un interés interdisciplinario. Trabajando con triangulaciones (mallas compuestas por triángulos), el reto es generar una descomposición precisa del objeto geométrico o dominio, y al mismo tiempo satisfacer las restricciones adicionales impuestas por la aplicación, como restricciones en la forma de los elementos, el número de elementos, o la transición entre elementos de diferentes tamaños. Los algoritmos que ofrecen garantías teóricas sobre estos temas son preferidos. Los algoritmos de arista más larga fueron diseñados para el refinamiento iterativo de triangulaciones en aplicaciones de método de elementos finitos adaptativo. Estos algoritmos están basados en la estrategia de propagación por la arista más larga. Comparados a otros algoritmos de refinamiento, los algoritmos de arista más larga rápidamente producen una descomposición del dominio (o de regiones de interés) a través de operaciones locales simples. Las triangulaciones obtenidas presentan buena densidad y la calidad de los triángulos refinados está acotada. El propósito de esta tesis es proporcionar nuevas garantías teóricas para los algoritmos de arista más larga basados en bisección y los algoritmos de arista más larga basados en refinamiento Delaunay, para la generación y el refinamiento de mallas de buena calidad en 2 dimensiones. Nuestro estudio del algoritmo basado en bisección muestra que el algoritmo inserta un número constante de puntos por triángulo refinado, con costo asintóticamente óptimo. También mostramos que durante el proceso de refinamiento el algoritmo mejora la calidad promedio de los triángulos. Obtenemos nuevas cotas para el tamaño de la triangulación refinada y probamos que éste es a lo sumo un factor constante mayor que el tamaño de la triangulación inicial. Esta es la primera prueba completa sobre la complejidad del algoritmo. Seguidamente estudiamos el algoritmo basado en refinamiento Delaunay y su estrategia de inserción de puntos. Demostramos que los puntos insertados por el algoritmo no pueden estar arbitrariamente cerca de puntos existentes, lo que nos permite acotar la longitud de nuevas aristas. Analizamos el mejoramiento de la calidad de triángulos para diversas cotas en el ángulo mínimo, y definimos las propiedades geométricas de los triángulos obtenidos después del refinamiento. Utilizamos las técnicas existentes para el análisis de algoritmos de refinamiento Delaunay para demostrar que el algoritmo produce triangulaciones de tamaño óptimo, con buena densidad de puntos, y con ángulos internos entre 25.66 y 128.68 grados. También estudiamos las propiedades de la propagación en estos algoritmos de arista más larga. Mostramos que el número de triángulos afectados por refinamiento propagado converge rápidamente a aproximadamente dos. Esto demuestra que el refinamiento propagado representa un factor constante en el costo de refinamiento.

No description available.