Memoria para optar al título de Ingeniero Civil en Computación / Una malla triangular es un modelo de representación de objetos que consiste en un conjunto de vértices, caras (triángulos) y lados (aristas). Estas mallas son muy usadas en computación gráfica y en simulaciones numéricas. Estas mallas pueden no ser suficientemente buenas como para poder realizar cálculos sobre ellas, dado el riesgo de propagar errores, cuando los triángulos que conforman estas mallas son demasiado delgados. Para mejorar/refinar los triángulos que se consideran de mala calidad existen distintos algoritmos, tales como Lepp-Bisección, Lepp-Delaunay o Lepp-Centroide, que hasta ahora solo tienen implementaciones en CPU (ya sean secuenciales o multi-core). El concepto de Lepp (Longest-Edge Propagation Path) consiste en comenzar con un triángulo de la malla, ir hacia el triángulo vecino por su arista más larga sucesivamente, hasta llegar a la última arista más larga que tienen los triángulos en común, llamada arista terminal. El objetivo de esta memoria es diseñar e implementar una solución mixta que usa tanto GPU (parte paralela) y CPU (parte secuencial) para el algoritmo Lepp-Centroide, de tal forma de poder explorar las posibilidades que ofrece la GPU en el mejoramiento y refinamiento de mallas. Para cumplir con este objetivo se implementó la aplicación QLepp2D, la cual consiste en la unión de una biblioteca (QLepp2D-lib) y una interfaz gráfica (QLepp2D-gui) que permiten al usuario cargar una triangulación y mejorarla/refinarla de manera rápida y simple, utilizando el poder que ofrece la biblioteca de OpenCL para paralelizar este procesamiento. QLepp2D-lib está escrita en C++ y OpenCL 1.2. Esta biblioteca puede ser instalada en el sistema y ser usada por otros programas. QLepp2D-gui está escrita usando Qt y utiliza QLepp2D-lib como demostración de la facilidad de uso de esta biblioteca. Adicionalmente, es posible portar la interfaz a distintos idiomas, por lo que es posible utilizarla en distintos sistemas, traduciendo la aplicación de forma automática. Con esta aplicación es posible conseguir el mejoramiento/refinamiento de mallas de triángulos con una velocidad más de 2 veces superior para el procesamiento completo y más de 400 veces superior para el algoritmo del método más rápido, además de demostrar el poder de OpenCL para adaptarse a cualquier dispositivo que posea una implementación disponible. / Proyecto Fondecyt Nº 1181506

Tesis para optar al grado de Magíster en Ciencias, Mención Computación / El modelo cosmológico actual y más aceptado del universo se llama Lambda Cold Dark Matter. Este modelo nos presenta el modelo más simple que proporciona una explicación razonablemente buena de la evidencia observada hasta ahora. El modelo sugiere la existencia de estructuras a gran escala presentes en nuestro universo: Nodos, filamentos, paredes y vacíos. Los vacíos son de gran interés para los astrofísicos ya que su observación sirve como validación para el modelo. Los vacíos son usualmente definidos como regiones de baja densidad en el espacio, con sólo unas pocas galaxias dentro de ellas. En esta tesis, presentamos un estudio del estado actual de los algoritmos de búsqueda de vacíos. Mostramos las diferentes técnicas y enfoques, e intentamos deducir la complejidad algorítmica y el uso de memoria de cada void-finder presentado. Luego mostramos nuestro nuevo algoritmo de búsqueda de vacíos, llamado ORCA. Fue construido usando triangulaciones de Delaunay para encontrar a los vecinos más cercanos de cada punto. Utilizando esto, clasificamos los puntos en tres categorías: Centro, borde y outliers. Los outliers se eliminan como ruido. Clasificamos los triángulos de la triangulación en triángulos de vacíos y centrales. Esto se hace verificando un criterio de distancia, y si los triángulos contienen outliers. Este método nos permite crear un algoritmo de búsqueda de vacíos rápido y robusto. Adicionalmente, se presenta una versión paralela del algoritmo.