Método de ajuste de niveles

Marco conceptual utilizado en el análisis numérico de superficies y formas.

Vídeo de la espiral propagada por conjuntos de niveles (flujo de curvatura) en 2D. La imagen de la izquierda muestra una solución de nivel cero. La imagen de la derecha muestra el campo escalar de nivel establecido.

El método de conjunto de niveles ( LSM ) es un marco conceptual para utilizar conjuntos de niveles como herramienta para el análisis numérico de superficies y formas . Aunque los métodos eulerianos tienen sus usos, como la aproximación de curvas desconocidas, LSM puede realizar cálculos numéricos que involucran curvas y superficies en una cuadrícula cartesiana fija sin tener que parametrizar estos objetos. ^[1] Es importante destacar que LSM facilita la realización de cálculos en formas con esquinas afiladas y formas que cambian de topología (como dividiéndolas en dos o desarrollando agujeros). Estas características hacen que LSM sea eficaz para modelar objetos que varían en el tiempo, como un airbag que se infla o una gota de aceite que flota en el agua.

Una ilustración del método de ajuste de niveles

Descripción general

La figura de la derecha ilustra varias ideas sobre LSM. En la esquina superior izquierda vemos una forma: una región acotada con un límite que se comporta bien. Debajo, la superficie roja es el gráfico de una función de conjunto de niveles que determina esta forma, y ​​la región azul plana representa el plano XY . El límite de la forma es entonces el conjunto de nivel cero de , mientras que la forma en sí es el conjunto de puntos en el plano para los cuales es positivo (interior de la forma) o cero (en el límite). ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

En la fila superior, se puede ver la forma cambiando su topología dividiéndola en dos. Sería difícil describir numéricamente esta transformación parametrizando el límite de la forma y siguiendo su evolución. Se necesitaría un algoritmo para poder detectar el momento en que la forma se divide en dos y luego construir parametrizaciones para las dos curvas recién obtenidas. Sin embargo, en la fila inferior, la función de ajuste de nivel logra este cambio trasladándose hacia abajo. Este es un ejemplo de cuando puede ser más fácil trabajar con una forma a través de su función de conjunto de niveles que con la forma directamente, donde el método necesitaría considerar y manejar todas las posibles deformaciones que podría sufrir la forma.

Por lo tanto, en dos dimensiones, el método de conjunto de niveles equivale a representar una curva cerrada (como el límite de forma en nuestro ejemplo) usando una función auxiliar , llamada función de conjunto de niveles. La curva se representa como el conjunto de nivel cero de por ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$

${\displaystyle \Gamma =\{(x,y)\mid \varphi (x,y)=0\},}$

y el método de conjunto de niveles manipula implícitamente a través de la función . Se supone que esta función toma valores positivos dentro de la región delimitada por la curva y valores negativos fuera. ^{[2] [3]} ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma }$

La ecuación del nivel establecido

Si la curva se mueve en la dirección normal con una velocidad , entonces por regla de la cadena y diferenciación implícita, obtenemos que la función de conjunto de niveles satisface la ecuación de conjunto de niveles ${\displaystyle \Gamma }$ ${\displaystyle v}$ ${\displaystyle \varphi }$

${\displaystyle {\frac {\partial \varphi }{\partial t}}=v|\nabla \varphi |.}$

Aquí, está la norma euclidiana (denotada habitualmente por barras simples en ecuaciones diferenciales parciales) y es el tiempo. Esta es una ecuación diferencial parcial , en particular una ecuación de Hamilton-Jacobi , y se puede resolver numéricamente, por ejemplo, utilizando diferencias finitas en una cuadrícula cartesiana. ^{[2] [3]} ${\displaystyle |\cdot |}$ ${\displaystyle t}$

Sin embargo, la solución numérica de la ecuación del conjunto de niveles puede requerir técnicas complejas. Los métodos simples de diferencias finitas fallan rápidamente. Los métodos de contracorriente , como el método Godunov, se consideran mejores; sin embargo, el método de establecimiento de niveles no garantiza la preservación del volumen y la forma del nivel establecido en un campo de advección que mantiene la forma y el tamaño, por ejemplo, un campo de velocidad uniforme o rotacional . En cambio, la forma del conjunto de niveles puede distorsionarse y el conjunto de niveles puede desaparecer en unos pocos pasos de tiempo. Por lo tanto, a menudo se requieren esquemas de diferencias finitas de alto orden, como los esquemas de alto orden esencialmente no oscilatorios (ENO), e incluso entonces la viabilidad de las simulaciones a largo plazo es cuestionable. Se han desarrollado métodos más complejos para superar esto; por ejemplo, combinaciones del método de nivelación con el seguimiento de partículas marcadoras sugeridas por el campo de velocidad. ^[4]

Ejemplo

Considere un círculo unitario en , que se contrae sobre sí mismo a un ritmo constante, es decir, cada punto en el límite del círculo se mueve a lo largo de su dirección normal hacia el interior a una velocidad fija. El círculo se reducirá y eventualmente colapsará hasta convertirse en un punto. Si se construye un campo de distancia inicial (es decir, una función cuyo valor es la distancia euclidiana con signo al límite, interior positivo, exterior negativo) en el círculo inicial, el gradiente normalizado de este campo será la normal del círculo. ${\textstyle \mathbb {R} ^{2}}$

Si al campo se le resta un valor constante en el tiempo, el nivel cero (que era el límite inicial) de los nuevos campos también será circular y de manera similar colapsará hasta formar un punto. Esto se debe a que ésta es efectivamente la integración temporal de la ecuación de Eikonal con una velocidad de frente fija .

Aplicaciones

• En el modelado matemático de la combustión , el LSM se utiliza para describir la superficie de la llama instantánea, conocida como ecuación G.
• Se han desarrollado estructuras de datos de conjunto de niveles para facilitar el uso del método de conjunto de niveles en aplicaciones informáticas.
• Dinámica de fluidos computacional
• Planificación de trayectoria
• Mejoramiento
• Procesamiento de imágenes
• Biofísica computacional
• Dinámica compleja discreta (visualización del plano de parámetros y del plano dinámico)

Historia

El método de fijación de niveles fue desarrollado en 1979 por Alain Dervieux, ^[5] y posteriormente popularizado por Stanley Osher y James Sethian . Desde entonces, se ha vuelto popular en muchas disciplinas, como el procesamiento de imágenes , los gráficos por computadora , la geometría computacional , la optimización , la dinámica de fluidos computacional y la biología computacional .

Ver también

• diagrama de caja de contorno
• Rayas de cebra (gráficos por computadora)
• Ecuación G
• Biblioteca de simulación avanzada
• Método del volumen de fluido
• Segmentación de imágenes # Métodos de conjunto de niveles
• Método de límite sumergido
• Método estocástico Euleriano-Lagrangiano
• Conjunto de niveles (estructuras de datos)
• Posterización

Referencias

1. Osher, S.; Sethian, JA (1988), "Frentes que se propagan con velocidad dependiente de la curvatura: algoritmos basados ​​en formulaciones de Hamilton-Jacobi" (PDF) , J. Comput. Física. , 79 (1): 12–49, Bibcode :1988JCoPh..79...12O, CiteSeerX  10.1.1.46.1266 , doi :10.1016/0021-9991(88)90002-2, hdl :10338.dmlcz/144762, S2CID  205007680
2. Osher, Stanley J .; Fedkiw, Ronald P. (2002). "Métodos de conjunto de niveles y superficies dinámicas implícitas ". Springer-Verlag . ISBN 978-0-387-95482-0.
3. Sethian, James A. (1999). Métodos de conjunto de niveles y métodos de marcha rápida: interfaces en evolución en geometría computacional, mecánica de fluidos, visión por computadora y ciencia de materiales . Prensa de la Universidad de Cambridge . ISBN 978-0-521-64557-7.
4. Muy bien, D.; Fedkiw, RP; Ferziger, JH ; Mitchell, I. (2002), "Un método híbrido de conjunto de niveles de partículas para una captura de interfaz mejorada" (PDF) , J. Comput. Física. , 183 (1): 83–116, Bibcode :2002JCoPh.183...83E, CiteSeerX 10.1.1.15.910 , doi :10.1006/jcph.2002.7166 
5. Dervieux, A.; Thomasset, F. (1980). "Un método de elementos finitos para la simulación de una inestabilidad de Rayleigh-Taylor". Métodos de aproximación para problemas de Navier-Stokes . Apuntes de conferencias de matemáticas. vol. 771. Saltador. págs. 145-158. doi :10.1007/BFb0086904. ISBN 978-3-540-38550-9.

enlaces externos

• Consulte la página web académica de Ronald Fedkiw para ver muchas imágenes y animaciones que muestran cómo se puede utilizar el método de conjunto de niveles para modelar fenómenos de la vida real.
• Multivac es una biblioteca C++ para seguimiento frontal en 2D con métodos de conjunto de niveles.
• Página web de James Sethian sobre el método de establecimiento de niveles.
• Página de inicio de Stanley Osher .
• El método de establecimiento de niveles. MIT 16.920J / 2.097J / 6.339J. Métodos numéricos para ecuaciones diferenciales parciales de Per-Olof Persson. 8 de marzo de 2005
• Conferencia 11: El método de establecimiento de niveles: MIT 18.086. Métodos matemáticos para ingenieros II por Gilbert Strang