Algoritmo para la paralelización en GPU de diagramas de Voronoi

Abstract

En la computación gráfica la cantidad de simulaciones y sus dimensiones ha crecido a lo largo del tiempo. Sus avances en diferentes áreas expresa la necesidad de que los algoritmos que procesan y visualizan la información sean más rápidos y robustos. Una de estas visualizaciones son los diagramas de Voronoi, cuyo objetivo es teselar el espacio a través de polígonos cuyos elementos internos tienen en común un elemento: son más cercanos a ciertos puntos especificados, resolviendo problemas como por ejemplo la ubicación de los puestos de vigilancia en una reserva forestal. Estos diagramas están asociados a otro tipo de grafos llamados Triangulaciones de Delaunay, siendo entre sí grafos duales. Existen varios algoritmos que calculan este último de manera paralela en GPU pero no así de los diagramas de Voronoi, dando pie al objetivo de este trabajo: Diseñar e implementar un nuevo algoritmo paralelo en GPU que permita el cálculo y visualización del diagrama de Voronoi utilizando como base una triangulación de Delaunay. Tras la revisión de los algoritmos dedicados a estos diagramas, se decidió realizar una implementación compatible con la librería CLEAP, que calcula de manera paralela y en GPU una triangulación de Delaunay dada una malla de triángulos cualquiera. Esto hace que sea imprescindible el entendimiento de las estructuras de datos y procesos que la librería lleva a cabo, con el fin de optimizar el tiempo de cálculo del diagrama en cuestión. Dadas las estructuras de datos existentes, se crearon nuevos elementos para almacenar la información relevante a los diagramas de Voronoi. Estas estructuras deben ser capaces de interoperar con los buffers que OpenGL utiliza para la visualización y con los arreglos de datos que CUDA maneja. Junto a esto, los algoritmos implementados deben calcular los vértices y aristas del nuevo diagrama de manera paralela sin que se produzcan pérdidas de información. Los resultados obtenidos fueron positivos, permitiendo a la librería calcular un diagrama de Voronoi agregando a lo más 0.09 segundos de procesamiento adicional (equivalente a un 2% del tiempo total) para mallas de 4.000.000 de puntos, sin alterar el comportamiento previo a la implementación. En conjunto a esto, el tiempo de procesamiento llega a ser 5 veces más rápido que otros algoritmos de similar método en CPU (Qhull). Por otro lado, la nueva implementación aumenta el uso de memoria en un 250%. Comparado con Qhull, el uso de memoria es bastante similar (si solo se considera lo almacenado a nivel de GPU). Se plantea una mejora como trabajo futuro para disminuir esta medición.