Parallel mesh simplification on a GPU

Abstract

Las mallas geométricas son un potente medio que permite representar fenómenos del mundo real en el mundo digital, y así resolver numéricamente, problemas que no necesariamente poseen una resolución analítica. Sin embargo, el procesamiento de mallas geométricas que almacenan o representan grandes volúmenes de datos, tales como modelamiento de superficies u objetos 3D, se ha vuelto lento o inmanejable al utilizar algoritmos secuenciales para procesarlos. Una de las operaciones realizadas sobre estas mallas es la simplificación, la cual reduce o elimina detalles geométricos y disminuye el uso de memoria de la malla, manteniendo un nivel aceptable de calidad y reteniendo propiedades importantes de ella, tales como preservar su forma original, geometría y topología. Con esto, el resultado de los algoritmos que usan como entrada esta malla simplificada, debiesen obtenerse más rápido, y seguir considerándose válidos y útiles. Este trabajo de tesis propone un algoritmo de simplificación de mallas en paralelo basado en edge-collapse utilizando la GPU, tomando en cuenta varios elementos encontrados durante el proceso de investigación (tales como técnicas de simplificado, métricas de simplificación y algoritmos creados por otros autores). Esta propuesta incluye el uso de una estructura de datos utilizada en la librería Cleap, que almacena datos de la malla redundantemente y puede almacenarse en la memoria de la GPU. Esto es útil, pues los elementos de la malla (vértices, arcos y triángulos) pueden detectar inconsistencias en sus datos (principalmente referencias a elementos eliminados de la malla) luego de una iteración del algoritmo de simplificado sobre la malla, y con esto pueden reparar tales inconsistencias antes de iniciar la siguiente iteración del algoritmo. Los resultados muestran que el algoritmo de simplificación paralelo es hasta 1.000 veces más rápido en promedio que su contraparte secuencial bajo ciertos escenarios y consideraciones, y las mallas resultantes son de calidad similar entre ambas implementaciones. También se presentaron algunos cuellos de botella en algunas etapas, que disminuían el rendimiento del algoritmo como un todo. No pudimos realizar una comparación de nuestro algoritmo con otros algoritmos encontrados durante la revisión bibliográfica, debido a que sus implementaciones no se encontraban disponibles para su uso y/o su descripción para implementarlo por nuestra cuenta era poco clara o tenía ofuscadas etapas clave del algoritmo. Nuestro aporte es un algoritmo de simplificación de mallas en paralelo que funciona en la GPU, que está integrado en una librería que cuenta con implementaciones paralelas de otros algoritmos de refinamiento de mallas (como Triangulaciones de Delaunay y suavizado), y los detalles de su implementación se encuentran disponibles como un proyecto de código abierto. Este trabajo también aporta que se requiere saber para programar en paralelo en la GPU, así como una revisión de los algoritmos, técnicas y detalles encontrados durante la investigación.