Study and evaluation of algorithms to generate polygon meshes

Abstract

Actualmente, la diversificación de técnicas de modelado geométrico a través de mallas de polígonos en diferentes ramas científicas como la neurociencia, la ingeniería mecánica y la astrofísica, hace que nos interese su estudio. Las mallas de polígonos permiten modelar geometrías complejas y la simulación de fenómenos complejos o comportamientos de objetos, por lo que también se pueden utilizar en medicina, para extraer descripciones geométricas de imágenes digitales en procesos de resonancia magnética computarizada. Además, los métodos de Elementos Finitos (PFEM) y el método de Elementos Virtuales (VEM) son cada vez más populares hoy en día debido a su flexibilidad en el modelado de dominios complejos, una base matemática importante, eficiencia y precisión en la solución obtenida para algunos problemas complejos. Las mallas de polígonos más utilizadas son las basadas en el diagrama de Voronoi porque se pueden obtener fácilmente a partir de la triangulación de Delaunay. En este trabajo de tesis estudiamos y desarrollamos diferentes enfoques para generar mallas de polígonos y compararlas utilizando diferentes métricas de calidad. Las mallas iniciales se obtienen usando (i) la técnica estándar de quadtree, (ii) usando quadtree con un algoritmo de división de puntos arbitrarios (incluyendo aleatorización) (iii) kd-trees. Los elementos se pueden refinar en puntos de borde arbitrarios hasta que cada elemento cumpla con algunos criterios de calidad especificados por el usuario, sí se generan y comparan mallas que satisfacen los requisitos. Las diferentes estrategias para generar mallas de polígonos se implementaron como una Aplicación Web, desarrollada utilizando tecnologías actuales para los lenguajes Javascript y Typecript, como React y Node.js, con el propósito de lograr una interfaz de usuario interactiva en tiempo real para especificar métricas de calidad y el proceso actual de la malla que se está evaluando. En particular, la aplicación permite ver cómo se comportan el quadtree y el KD-tree en tiempo real en términos de la división del plano y la posterior generación de polígonos más pequeños. La aplicación web se modeló utilizando patrones de diseño para obtener un software fácil de extender al agregar nuevas estrategias para generar mallas iniciales, algoritmos de refinamiento, recorte de polígonos, división de regiones y diferentes métricas de calidad. Esta aplicación está orientada a explorar y evaluar nuevos algoritmos y métricas de calidad pero no a generar implementaciones óptimas con respecto a los tiempos de ejecución. Según los resultados obtenidos en nuestros experimentos, las mallas iniciales generadas por KD-trees se generan más rápidamente que las creadas por quadtrees, obteniendo un menor número de elementos y de mejor calidad. En comparación con Triangle, obtuvimos mejores resultados al refinar dentro de una región elegida por el usuario, obteniendo menos polígonos y un mayor número de puntos. Los resultados muestran ser buenos para la aplicación de simulaciones con métodos matemáticos como VEM, ya que el número de polígonos es menor, pero sigue cumpliendo los criterios de calidad impuestos por el usuario en la región de interés. En cuanto a las métricas, cuando se restringe el área máxima a un número determinado, los polígonos generados por un quadtree utilizando el algoritmo de Splitting Longest Edge obtienen mejores métricas en ER y CR que Triangle. Por otro lado, cuando se utiliza un KD-tree las métricas son todas más bajas en nuestros algoritmos excepto en CR utilizando un refinamiento de quadtree.