Triangulación automática de polígonos y poliedros

Introducción

Una etapa crítica en la aplicación del método de elementos finitos es la generación de una malla que discretice el dominio a estudiar. En general, las técnicas disponibles para ello tienen limitaciones para proveer soluciones eficientes, confiables y automáticas cuando se trabaja con geometrías complejas: necesitan una cantidad importante de interacción con el usuario y, en muchos casos, la generación de los nodos iniciales no es robusta. Por otra parte, existe una estrecha relación entre la calidad de la solución numérica obtenida por el método de elementos finitos y la calidad de la malla utilizada en el cálculo de dicha solución.

Un enfoque frecuente se basa en la descomposición recursiva de la región a estudiar usando octrees. Mediante esta técnica el volumen es dividido en octantes, que a su vez se dividen recursivamente mientras intersecten el borde del volumen original. La dificultad que presenta este enfoque es la determinación de heurísticas para aproximar el borde del volumen. Este método es también sensitivo al sistema de coordenadas usado al definir la región; una rotación o traslación del sistema de coordenadas (o de la región) puede resultar en una descomposición sustancialmente diferente.

Un segundo tipo de solución está basado en técnicas de avance frontal. Con este enfoque es difícil establecer en forma general cómo los diferentes grupos de tetraedros avanzando desde distintos bordes se unen correctamente en su interior. En este método la construcción de cada tetraedro es computacionalmente más cara comparada con otros enfoques, debido a la necesidad de chequear si el tetraedro está bien formado y determinar si no intersecta los otros frentes.

Un tercer tipo de solución se basa en la generación de puntos en los bordes e interiores de la región para luego construir una malla mediante una triangulación de Delaunay. Las dificultades que presenta este enfoque son la generación apropiada de los puntos adicionales en la región (para lo cual puede ser usado el método octree, con las dificultades descritas anteriormente) y la generación de mallas en regiones no convexas, ya que una triangulación Delaunay define la envoltura convexa de un conjunto de puntos (una discusión al respecto se puede encontrar en [Riv95]).

El objetivo de esta memoria es implementar y testear algoritmos para la generación automática de mallas de triángulos y tetraedros, basados en las ideas introducidas y discutidas en [Riv95]. Con el fin de obtener una triangulación de buena calidad con una mínima densidad de elementos, se utilizan los algoritmos de Delaunay en conjunto con la incorporación sucesiva de puntos en las regiones conflictivas. En el caso de los poliedros, se agrega como paso preliminar la triangulación de las caras del poliedro mediante el algoritmo desarrollado en dos dimensiones.

Objetivos

• Dado un polígono cualquiera, obtener en forma automática una triangulación de buena calidad, con la menor cantidad de elementos posible, que lo represente en forma exacta.
• Dado un poliedro cualquiera, obtener en forma automática una malla de tetraedros de buena calidad, con la menor cantidad de elementos posible, que lo represente en forma exacta.
• Desarrollar herramientas gráficas que permitan la visualización y manipulación de las mallas generadas.

Metodología

• Se estudiarán y evaluarán las aproximaciones previas al problema de la descomposición de sólidos en mallas de tetraedros, principalmente aquellas basadas en octrees. Para ello se usarán las herramientas de visualización construídas previamente.
• Se implementarán y probarán los algoritmos introducidos en [Riv95] y se definirán estrategias adicionales necesarias para su funcionamiento.
• Se implementará un prototipo de generador automático de mallas.
• Se experimentará con los algoritmos y se concluirá sobre su eficacia y eficiencia en la resolución del problema planteado. Se analizarán posibles generalizaciones de ellos y trabajos futuros.

Temario Tentativo

1. Introducción:
   1. Método de Elementos Finitos.
   2. Trabajos anteriores.
   3. Solución propuesta.
2. Algoritmo de Delaunay en 2D y 3D.
3. Triangulación automática de polígonos y poliedros. Descripción de la solución propuesta.
4. Implementación y estructuras de datos.
5. Herramientas de visualización. Interfaz gráfica.
6. Experimentación.
7. Conclusiones

Referencias

[Con94] Contreras, V. Análisis comparativo de algoritmos para la generación automática de mallas de tetraedros usando el método combinado Octree/Delaunay. Memoria de Ingeniería Civil en Computación, U. de Chile, 1994.

[Ino94] Inostroza, P. Ambiente experimental para la generación de mallas en 2D. Memoria de Ingeniería Civil en Computación, U. de Chile, 1994.

[Joe94] Joe, B. Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions, Int. Journal for Numerical Methods in Engineering, vol. 37, 1994.

[Lev91] Levin, C. Generación interactiva de mallas tridimensionales para elementos finitos. Memoria de Ingeniería Civil en Computación, U. de Chile, 1991.

[Gur92] Guersoy, H.N., Patrikalakis, N. An automatic coarse and fine surface mesh generation scheme based on medial axis transform, Engineering with Computers, vol. 8, 1992.

[Riv93] Rivara, M.C. A Discussion on the Triangulation Refinement Problem, En Proc. 5th Canadian Conference on Computational Geometry, 1993.

[Riv95] Rivara, M.C. A new approach for the automatic triangulation of 2D and 3D geometries, Dept. Computer Science, University of Chile, January 1995.

[Rog85] Rogers, Procedural elements for computer graphics, McGraw-Hill, 1985.