La generación de mallas es la práctica de crear una malla , una subdivisión de un espacio geométrico continuo en celdas geométricas y topológicas discretas. A menudo, estas celdas forman un complejo simplicial . Por lo general, las celdas dividen el dominio geométrico de entrada. Las celdas de malla se utilizan como aproximaciones locales discretas del dominio más grande. Las mallas se crean mediante algoritmos informáticos, a menudo con guía humana a través de una GUI , según la complejidad del dominio y el tipo de malla deseada. Un objetivo típico es crear una malla que capture con precisión la geometría del dominio de entrada, con celdas de alta calidad (bien formadas) y sin tantas celdas como para hacer que los cálculos posteriores sean intratables. La malla también debe ser fina (tener elementos pequeños) en áreas que son importantes para los cálculos posteriores.
Las mallas se utilizan para renderizar en una pantalla de computadora y para simulación física como el análisis de elementos finitos o la dinámica de fluidos computacional . Las mallas están compuestas de celdas simples como triángulos porque, por ejemplo, sabemos cómo realizar operaciones como cálculos de elementos finitos (ingeniería) o trazado de rayos (gráficos de computadora) en triángulos, pero no sabemos cómo realizar estas operaciones directamente en espacios y formas complicadas como un puente de carretera. Podemos simular la resistencia del puente, o dibujarlo en una pantalla de computadora, realizando cálculos en cada triángulo y calculando las interacciones entre triángulos.
Una distinción importante es entre el mallado estructurado y el no estructurado. En el mallado estructurado, la malla es una red regular, como una matriz, con conectividad implícita entre los elementos. En el mallado no estructurado, los elementos pueden estar conectados entre sí en patrones irregulares y se pueden capturar dominios más complicados. Esta página trata principalmente sobre mallas no estructuradas. Si bien una malla puede ser una triangulación , el proceso de mallado se distingue de la triangulación de conjuntos de puntos en que el mallado incluye la libertad de agregar vértices que no están presentes en la entrada. Los modelos CAD de "facetado" (triangulación) para diseño tienen la misma libertad para agregar vértices, pero el objetivo es representar la forma con precisión utilizando la menor cantidad posible de triángulos y la forma de los triángulos individuales no es importante. Las representaciones de texturas y condiciones de iluminación realistas en gráficos de computadora utilizan mallas en su lugar.
Muchos programas de generación de mallas están acoplados a un sistema CAD que define su entrada y a un software de simulación para obtener su salida. La entrada puede variar mucho, pero las formas más comunes son el modelado de sólidos , el modelado geométrico , NURBS , B-rep , STL o una nube de puntos .
Los términos " generación de malla " , " generación de cuadrícula", " mallado " y " cuadriculado " se utilizan a menudo indistintamente, aunque estrictamente hablando los dos últimos son más amplios y abarcan la mejora de la malla: cambiar la malla con el objetivo de aumentar la velocidad o la precisión de los cálculos numéricos que se realizarán sobre ella. En la representación de gráficos por ordenador y en matemáticas , a veces se hace referencia a una malla como teselación .
Las caras de la malla (celdas, entidades) tienen diferentes nombres según su dimensión y el contexto en el que se utilizará la malla. En elementos finitos, las entidades de la malla de mayor dimensión se denominan "elementos", las "aristas" son 1D y los "nodos" son 0D. Si los elementos son 3D, las entidades 2D son "caras". En geometría computacional, los puntos 0D se denominan vértices. Los tetraedros suelen abreviarse como "tets"; los triángulos son "tris", los cuadriláteros son "quads" y los hexaedros (cubos topológicos) son "hexes".
Muchas técnicas de mallado se basan en los principios de la triangulación de Delaunay , junto con reglas para agregar vértices, como el algoritmo de Ruppert . Una característica distintiva es que se forma una malla gruesa inicial de todo el espacio, luego se agregan vértices y triángulos. Por el contrario, los algoritmos de frente de avance comienzan desde el límite del dominio y agregan elementos de manera incremental que llenan el interior. Las técnicas híbridas hacen ambas cosas. Una clase especial de técnicas de frente de avance crea capas límite delgadas de elementos para el flujo de fluidos. En la generación de malla estructurada, toda la malla es un gráfico de celosía , como una cuadrícula regular de cuadrados. En el mallado estructurado en bloques, el dominio se divide en grandes subregiones, cada una de las cuales es una malla estructurada. Algunos métodos directos comienzan con una malla estructurada en bloques y luego mueven la malla para ajustarse a la entrada; consulte Generación automática de malla hexagonal basada en policubo . Otro método directo es cortar las celdas estructuradas por el límite del dominio; consulte esculpir basado en cubos de marcha .
Algunos tipos de mallas son mucho más difíciles de crear que otros. Las mallas simples tienden a ser más fáciles que las mallas cúbicas. Una categoría importante es la generación de una malla hexagonal que se ajuste a una malla de superficie cuadrática fija; un subárea de investigación es el estudio de la existencia y generación de mallas de pequeñas configuraciones específicas, como el trapezoedro tetragonal . Debido a la dificultad de este problema, se ha estudiado la existencia de mallas hexagonales combinatorias aparte del problema de generar buenas realizaciones geométricas; consulte Técnicas combinatorias para la generación de mallas hexaédricas. Si bien los algoritmos conocidos generan mallas simples con una calidad mínima garantizada, dichas garantías son raras para las mallas cúbicas, y muchas implementaciones populares generan hexágonos invertidos (de adentro hacia afuera) a partir de algunas entradas.
Las mallas se crean a menudo en serie en estaciones de trabajo, incluso cuando los cálculos posteriores sobre la malla se realizarán en paralelo en supercomputadoras. Esto se debe tanto a la limitación de que la mayoría de los generadores de mallas son interactivos como a que el tiempo de ejecución de la generación de mallas suele ser insignificante en comparación con el tiempo del solucionador. Sin embargo, si la malla es demasiado grande para caber en la memoria de una sola máquina en serie, o si la malla debe modificarse (adaptarse) durante la simulación, el mallado se realiza en paralelo.
La generación de la malla mediante métodos algebraicos se basa en la función de interpolación matemática . Se realiza utilizando funciones conocidas en una, dos o tres dimensiones que toman regiones de forma arbitraria. El dominio computacional puede no ser rectangular, pero por el bien de la simplicidad, se toma el dominio como rectangular. La principal ventaja de los métodos es que proporcionan un control explícito de la forma y el espaciado de la malla física. El procedimiento más simple que se puede utilizar para producir una malla computacional ajustada a los límites es la transformación de normalización. [1]
Para una boquilla, con la función descriptiva, la malla se puede generar fácilmente utilizando una división uniforme en la dirección y con incrementos igualmente espaciados en la dirección x , que se describen mediante
donde denota la coordenada y de la pared de la boquilla. Para valores dados de ( , ), los valores de ( , ) se pueden recuperar fácilmente.
Al igual que los métodos algebraicos, los métodos de ecuaciones diferenciales también se utilizan para generar cuadrículas. La ventaja de utilizar las ecuaciones diferenciales parciales (EDP) es que la solución de las ecuaciones generadoras de cuadrículas se puede aprovechar para generar la malla. La construcción de cuadrículas se puede realizar utilizando las tres clases de ecuaciones diferenciales parciales .
Las EDP elípticas generalmente tienen soluciones muy suaves que conducen a contornos suaves. Usando su suavidad como una ventaja, las ecuaciones de Laplace se pueden usar preferiblemente porque el jacobiano resultó ser positivo como resultado del principio de máximo para funciones armónicas . Después del extenso trabajo realizado por Crowley (1962) y Winslow (1966) [2] en EDP mediante la transformación del dominio físico en el plano computacional mientras se mapea utilizando la ecuación de Poisson , Thompson et al. (1974) [3] han trabajado extensamente en EDP elípticas para generar cuadrículas. En los generadores de cuadrícula de Poisson, el mapeo se logra marcando los puntos de cuadrícula deseados en el límite del dominio físico, con la distribución de puntos interior determinada a través de la solución de las ecuaciones escritas a continuación.
donde, son las coordenadas en el dominio computacional, mientras que P y Q son responsables del espaciado de puntos dentro de D. La transformación de las ecuaciones anteriores en el espacio computacional produce un conjunto de dos EDP elípticas de la forma,
dónde
Estos sistemas de ecuaciones se resuelven en el plano computacional sobre una cuadrícula uniformemente espaciada que nos proporciona las coordenadas de cada punto en el espacio físico. La ventaja de utilizar ecuaciones en derivadas parciales elípticas es que la solución asociada a ellas es uniforme y la cuadrícula resultante es uniforme. Sin embargo, la especificación de P y Q se convierte en una tarea difícil, lo que se suma a sus desventajas. Además, la cuadrícula debe calcularse después de cada paso de tiempo, lo que suma tiempo de cálculo. [4]
Este esquema de generación de cuadrículas es generalmente aplicable a problemas con dominios abiertos consistentes con el tipo de EDP que describe el problema físico. La ventaja asociada con las EDP hiperbólicas es que las ecuaciones gobernantes necesitan ser resueltas solo una vez para generar la cuadrícula. La distribución de puntos inicial junto con las condiciones de contorno aproximadas forman la entrada requerida y la solución es luego llevada hacia afuera. Steger y Sorenson (1980) [5] propusieron un método de ortogonalidad de volumen que utiliza EDP hiperbólicas para la generación de mallas. Para un problema 2-D, Considerando que el espacio computacional está dado por , la inversa del jacobiano está dada por,
donde representa el área en el espacio físico para un área dada en el espacio computacional. La segunda ecuación vincula la ortogonalidad de las líneas de la cuadrícula en el límite en el espacio físico, que se puede escribir como
Para que las superficies sean perpendiculares la ecuación se convierte en
El problema asociado con este sistema de ecuaciones es la especificación de . Una mala selección de puede provocar una propagación discontinua y de choque de esta información a lo largo de la malla. Si bien la malla es ortogonal, se genera muy rápidamente, lo que resulta una ventaja con este método.
La técnica de resolución es similar a la de las ecuaciones diferenciales parciales hiperbólicas , ya que se hace avanzar la solución a partir de la superficie de datos inicial que satisface las condiciones de contorno al final. Nakamura (1982) y Edwards (1985) desarrollaron las ideas básicas para la generación de cuadrículas parabólicas. La idea utiliza la ecuación de Laplace o la de Poisson y trata especialmente las partes que controlan el comportamiento elíptico. Los valores iniciales se dan como las coordenadas del punto a lo largo de la superficie y el avance de las soluciones hacia la superficie exterior del objeto que satisface las condiciones de contorno a lo largo de los bordes.
Hasta ahora no se había sugerido el control del espaciado de la cuadrícula. Nakamura y Edwards lograron el control de la cuadrícula utilizando un espaciado no uniforme. La generación de cuadrícula parabólica muestra una ventaja sobre la generación de cuadrícula hiperbólica en el sentido de que no se producen choques ni discontinuidades y la cuadrícula es relativamente uniforme. Sin embargo, las especificaciones de los valores iniciales y la selección del tamaño de paso para controlar los puntos de la cuadrícula requieren mucho tiempo, pero estas técnicas pueden ser efectivas cuando se adquiere familiaridad y experiencia.
Este método incluye una técnica que minimiza la suavidad de la cuadrícula , la ortogonalidad y la variación de volumen. Este método forma una plataforma matemática para resolver problemas de generación de cuadrículas. En este método, se genera una cuadrícula alternativa mediante una nueva malla después de cada iteración y se calcula la velocidad de la cuadrícula utilizando el método de diferencia hacia atrás. Esta técnica es poderosa, pero tiene la desventaja de que se requiere esfuerzo para resolver las ecuaciones relacionadas con la cuadrícula. Se necesita más trabajo para minimizar las integrales que reducirán el tiempo de CPU.
La principal importancia de este esquema es que proporciona un método que generará la cuadrícula automáticamente. Al utilizar este método, las cuadrículas se segmentan en bloques según la superficie del elemento y se proporciona una estructura para garantizar la conectividad adecuada. Para interpretar el flujo de datos se utiliza un solucionador. Cuando se emplea un esquema no estructurado, el interés principal es satisfacer la demanda del usuario y se utiliza un generador de cuadrícula para lograr esta tarea. El almacenamiento de información en el esquema estructurado es de celda a celda en lugar de cuadrícula a cuadrícula y, por lo tanto, se necesita más espacio de memoria. Debido a la ubicación aleatoria de las celdas, la eficiencia del solucionador en el esquema no estructurado es menor en comparación con el esquema estructurado. [6]
Hay algunos puntos que deben tenerse en cuenta al momento de construir la cuadrícula . El punto de cuadrícula con alta resolución crea dificultades tanto para las cuadrículas estructuradas como para las no estructuradas. Por ejemplo, en el caso de la capa límite , el esquema estructurado produce una cuadrícula alargada en la dirección del flujo. Por otro lado, las cuadrículas no estructuradas requieren una mayor densidad de celdas en la capa límite porque la celda debe ser lo más equilátera posible para evitar errores. [7]
Debemos identificar qué información se requiere para identificar la celda y todos los vecinos de la celda en la malla computacional . Podemos elegir ubicar los puntos arbitrarios en cualquier lugar que queramos para la cuadrícula no estructurada. Se utiliza un esquema de inserción de puntos para insertar los puntos de forma independiente y se determina la conectividad de la celda. Esto sugiere que el punto se identifique a medida que se insertan. La lógica para establecer una nueva conectividad se determina una vez que se insertan los puntos. Se necesitan datos que formen el punto de la cuadrícula que identifica la celda de la cuadrícula. A medida que se forma cada celda, se numera y se ordenan los puntos. Además, se necesita la información de la celda vecina.
Un problema al resolver ecuaciones diferenciales parciales utilizando los métodos anteriores es que la cuadrícula se construye y los puntos se distribuyen en el dominio físico antes de que se conozcan los detalles de la solución. Por lo tanto, la cuadrícula puede o no ser la mejor para el problema dado. [8]
Los métodos adaptativos se utilizan para mejorar la precisión de las soluciones. El método adaptativo se conoce como método "h" si se utiliza el refinamiento de la malla, método "r" si el número de puntos de la malla es fijo y no se redistribuye y "p" si se aumenta el orden del esquema de solución en la teoría de elementos finitos. Los problemas multidimensionales que utilizan el esquema de equidistribución se pueden resolver de varias maneras. Los más simples de entender son los generadores de cuadrícula de Poisson con función de control basada en la equidistribución de la función de peso con la difusión establecida como un múltiplo del volumen de celda deseado. El esquema de equidistribución también se puede aplicar al problema no estructurado. El problema es que la conectividad obstaculiza si el movimiento de los puntos de la malla es muy grande.
El flujo constante y el cálculo del flujo con precisión temporal se pueden resolver mediante este método adaptativo. La cuadrícula se refina después de un número predeterminado de iteraciones para adaptarla a un problema de flujo constante. La cuadrícula dejará de ajustarse a los cambios una vez que la solución converja. En casos de precisión temporal, se requiere el acoplamiento de las ecuaciones diferenciales parciales del problema físico y las que describen el movimiento de la cuadrícula.
Por lo general, las celdas son poligonales o poliédricas y forman una malla que divide el dominio. Las clases importantes de elementos bidimensionales incluyen triángulos (símplices) y cuadriláteros (cuadrados topológicos). En tres dimensiones, las celdas más comunes son los tetraedros (símplices) y los hexaedros (cubos topológicos). Las mallas simpliciales pueden ser de cualquier dimensión e incluyen triángulos (2D) y tetraedros (3D) como ejemplos importantes. Las mallas cúbicas son la categoría pandimensional que incluye cuadriláteros (2D) y hexágonos (3D). En 3D, las pirámides de 4 lados y los prismas de 3 lados aparecen en mallas conformes de tipo de celda mixta.
La malla está incrustada en un espacio geométrico que normalmente es bidimensional o tridimensional , aunque a veces la dimensión se incrementa en uno añadiendo la dimensión temporal. Las mallas de dimensiones superiores se utilizan en contextos específicos. Las mallas unidimensionales también son útiles. Una categoría importante son las mallas de superficie, que son mallas 2D incrustadas en 3D para representar una superficie curva.
Los gráficos duales tienen varias funciones en la creación de mallas. Se puede crear una malla poliédrica de diagrama de Voronoi dualizando una malla simple de triangulación de Delaunay . Se puede crear una malla cúbica generando una disposición de superficies y dualizando el gráfico de intersección; véase Continuum de torsión espacial . A veces, tanto la malla primaria como su malla dual se utilizan en la misma simulación; véase Operador de estrella de Hodge . Esto surge de la física que involucra operadores de divergencia y rizo (matemáticas) , como flujo y vorticidad o electricidad y magnetismo , donde una variable vive naturalmente en las caras primarias y su contraparte en las caras duales.
Las mallas tridimensionales creadas para el análisis de elementos finitos deben constar de tetraedros , pirámides , prismas o hexaedros . Las que se utilizan para el método de volumen finito pueden constar de poliedros arbitrarios . Las que se utilizan para los métodos de diferencias finitas consisten en matrices estructuradas por partes de hexaedros conocidas como mallas estructuradas de bloques múltiples. Las pirámides de 4 lados son útiles para conectar conformemente hexágonos a tetetas. Los prismas de 3 lados se utilizan para capas límite que se ajustan a una malla de tetetas del interior lejano del objeto.
Las mallas de superficie son útiles en gráficos de computadora donde las superficies de los objetos reflejan la luz (también dispersión subsuperficial ) y no se necesita una malla 3D completa. Las mallas de superficie también se utilizan para modelar objetos delgados como chapa metálica en la fabricación de automóviles y exteriores de edificios en arquitectura. Las mallas cúbicas de alta dimensión (por ejemplo, 17) son comunes en astrofísica y teoría de cuerdas .
¿Cuál es la definición precisa de una malla? No existe una descripción matemática universalmente aceptada que se aplique en todos los contextos. Sin embargo, algunos objetos matemáticos son claramente mallas: un complejo simplicial es una malla compuesta de símplices. La mayoría de las mallas poliédricas (por ejemplo, cúbicas) son conformes, lo que significa que tienen la estructura de celda de un complejo CW , una generalización de un complejo simplicial . Una malla no necesita ser simplicial porque un subconjunto arbitrario de nodos de una celda no es necesariamente una celda: por ejemplo, tres nodos de un cuadrilátero no definen una celda. Sin embargo, dos celdas se intersecan en celdas: por ejemplo, un cuadrilátero no tiene un nodo en su interior. La intersección de dos celdas puede ser varias celdas: por ejemplo, dos cuadriláteros pueden compartir dos aristas. A veces se prohíbe y rara vez se desea que una intersección sea más de una celda; el objetivo de algunas técnicas de mejora de la malla (por ejemplo, el efecto almohada) es eliminar estas configuraciones. En algunos contextos se hace una distinción entre una malla topológica y una malla geométrica cuya incrustación satisface ciertos criterios de calidad.
Las variantes de malla importantes que no son complejos CW incluyen mallas no conformes donde las celdas no se encuentran estrictamente cara a cara, pero las celdas, no obstante, dividen el dominio. Un ejemplo de esto es un octree , donde una cara de elemento puede dividirse por las caras de elementos adyacentes. Tales mallas son útiles para simulaciones basadas en flujo. En las cuadrículas superpuestas, hay múltiples mallas conformes que se superponen geométricamente y no dividen el dominio; consulte, por ejemplo, Overflow, el solucionador FLOW de cuadrícula OVERset . Los llamados métodos sin malla o sin malla a menudo hacen uso de alguna discretización similar a la malla del dominio y tienen funciones base con soporte de superposición. A veces, se crea una malla local cerca de cada punto de grado de libertad de simulación, y estas mallas pueden superponerse y ser no conformes entre sí.
Las triangulaciones implícitas se basan en un complejo delta: para cada triángulo, las longitudes de sus aristas y un mapa de unión entre las aristas de las caras. (expandir)
Muchas mallas utilizan elementos lineales, donde la asignación del elemento abstracto al elemento realizado es lineal y los bordes de la malla son segmentos rectos. Las asignaciones polinómicas de orden superior son comunes, especialmente las cuadráticas. Un objetivo principal de los elementos de orden superior es representar con mayor precisión el límite del dominio, aunque también tienen ventajas de precisión en el interior de la malla. Una de las motivaciones para las mallas cúbicas es que los elementos cúbicos lineales tienen algunas de las mismas ventajas numéricas que los elementos simpliciales cuadráticos. En la técnica de simulación de análisis isogeométrico , las celdas de la malla que contienen el límite del dominio utilizan la representación CAD directamente en lugar de una aproximación lineal o polinómica.
Mejorar una malla implica cambiar su conectividad discreta, la posición geométrica continua de sus celdas o ambas. Para cambios discretos, para elementos simples, uno intercambia bordes e inserta/elimina nodos. Se realizan los mismos tipos de operaciones para mallas cúbicas (cuadradas/hexagonales), aunque hay menos operaciones posibles y los cambios locales tienen consecuencias globales. Por ejemplo, para una malla hexaédrica, fusionar dos nodos crea celdas que no son hexágonos, pero si se fusionan nodos diagonalmente opuestos en un cuadrilátero y esto se propaga para colapsar una columna completa de hexágonos conectados por caras, entonces todas las celdas restantes seguirán siendo hexágonos. En el refinamiento de malla adaptativo , los elementos se dividen (refinamiento h) en áreas donde la función que se calcula tiene un alto gradiente. Las mallas también se engrosan, eliminando elementos para mayor eficiencia. El método multigrid hace algo similar al refinamiento y engrosamiento para acelerar la resolución numérica, pero sin cambiar realmente la malla.
Para los cambios continuos, se mueven los nodos o se mueven las caras de mayor dimensión modificando el orden polinómico de los elementos. El movimiento de nodos para mejorar la calidad se denomina "suavizado" o "refinamiento r" y el aumento del orden de los elementos se denomina "refinamiento p". Los nodos también se mueven en simulaciones en las que la forma de los objetos cambia con el tiempo. Esto degrada la forma de los elementos. Si el objeto se deforma lo suficiente, se vuelve a mallar todo el objeto y se asigna la solución actual de la malla anterior a la nueva.
El campo es altamente interdisciplinario, con contribuciones encontradas en matemáticas , ciencias de la computación e ingeniería . La I+D de mallado se distingue por un enfoque igual en matemáticas y computación discretas y continuas, como con la geometría computacional , pero en contraste con la teoría de grafos (discreta) y el análisis numérico (continuo). La generación de mallas es engañosamente difícil: es fácil para los humanos ver cómo crear una malla de un objeto dado, pero difícil programar una computadora para que tome buenas decisiones para una entrada arbitraria a priori. Existe una variedad infinita de geometría que se encuentra en la naturaleza y en los objetos hechos por el hombre. Muchos investigadores de generación de mallas fueron los primeros en utilizar mallas. La generación de mallas continúa recibiendo amplia atención, apoyo y financiación porque el tiempo humano para crear una malla eclipsa el tiempo para configurar y resolver el cálculo una vez que la malla está terminada. Esta siempre ha sido la situación desde que se inventaron la simulación numérica y los gráficos de computadora, porque a medida que el hardware de las computadoras y el software de resolución de ecuaciones simples han mejorado, las personas se han sentido atraídas por modelos geométricos más grandes y complejos en un afán por una mayor fidelidad, conocimiento científico y expresión artística.
Las investigaciones sobre mallado se publican en una amplia gama de revistas. Esto se ajusta a la naturaleza interdisciplinaria de la investigación necesaria para avanzar y también a la amplia variedad de aplicaciones que hacen uso de mallas. Cada año aparecen alrededor de 150 publicaciones sobre mallado en 20 revistas, y en cada revista aparecen como máximo 20 publicaciones. No hay ninguna revista cuyo tema principal sea el mallado. Las revistas que publican al menos 10 artículos sobre mallado al año están en negrita.
(Las conferencias cuyo tema principal es el mallado están en negrita ) .
Los talleres cuyo tema principal es la malla están en negrita.
Muchas descripciones de productos comerciales enfatizan la simulación en lugar de la tecnología de malla que la permite.
Estas herramientas generan las mallas particionadas necesarias para el modelado de elementos finitos de múltiples materiales.
Modelos útiles (entradas) y mallas (salidas) para comparar algoritmos de mallado y mallas.
Motores de modelado vinculados con software de generación de mallas para representar la geometría del dominio.
Formatos de archivos (de salida) comunes para describir mallas.
