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 / 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.

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.