Estructuras de datos tipo grafo en los algoritmos por refinamiento y desrefinamiento basados en la bisección por el lado mayor. Aplicaciones

Abstract

Los algoritmos de generación de mallas han sido objeto de numerosas investigaciones en los últimos años, Estos algoritmos constituyen herramientas básicas en los métodos numéricos, así como en la industria gráfica, como gráficos por ordenador, diseño y modelado de sólidos en entornos de Simulación en Ciencias y Tecnología. En los algoritmos de refinamiento y desrefinamiento de mallas es crucial disponer de una buena estructura de datos que haga eficiente su ejecución. Ello se debe a las complejas operaciones que surgen en la partición de elementos, lo cual se acentúa cuando la dimensión del problema aumenta y la cantidad de elementos crece rápidamente. En esta Tesis se presenta una nueva estructura de datos basada en grafos que de forma natural se ajusta a los algoritmos de refinamiento y desrefinamiento basados en el esqueleto. Además se estudian y demuestran propiedades matemáticas y computacionales de dicha estructura de datos y de la partición en cuatro triángulos por el lado mayor. Asimismo, se proporcionan versiones nuevas de los algoritmos de refinamiento en dimensión dos y tres y del algoritmo de desrefinamiento en dimensión dos. Se muestran aplicaciones a modelos digitales del terreno y generalización de terrenos, niveles de detalle en gráficos por ordenador y VRML, y se presenta la incorporación del algoritmo de refinamiento en 2D a un código de elementos finitos comercial con el que, a modo de ejemplo, se resuelve un problema elíptico no lineal.