Método de nivelación

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

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

El método de conjuntos de niveles ( LSM ) es un marco conceptual para utilizar conjuntos de niveles como herramienta para el análisis numérico de superficies y formas . 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] LSM facilita la realización de cálculos en formas con esquinas agudas y formas que cambian de topología (como al dividirse en dos o desarrollar 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 flotando en el agua.

Una ilustración del método de nivelación

Descripción general

La figura de la derecha ilustra varias ideas sobre el LSM. En la esquina superior izquierda hay una región acotada con un límite que se comporta bien. Debajo de ella, la superficie roja es el gráfico de una función de conjunto de nivel 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 el cual es positivo (interior de la forma) o cero (en el límite). ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

En la fila superior, la topología de la forma cambia a medida que se divide en dos. Es un desafío describir numéricamente esta transformación parametrizando el límite de la forma y siguiendo su evolución. Se puede utilizar un algoritmo para 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, el plano en el que se muestrea la función de conjunto de niveles se traslada hacia arriba, en el que se describe el cambio de topología de la forma. Es menos desafiante trabajar con una forma a través de su función de conjunto de niveles que con ella misma directamente, en cuyo caso un método necesitaría considerar 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) utilizando una función auxiliar , llamada función de conjunto de niveles. La curva se representa como el conjunto de nivel cero de mediante ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$

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

y el método level-set 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 de ella. ^{[2] [3]} ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma }$

La ecuación del conjunto de niveles

Si la curva se mueve en la dirección normal con una velocidad , entonces, por regla de la cadena y diferenciación implícita, se puede determinar 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í, es 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 avanzadas. Los métodos de diferencias finitas simples fallan rápidamente. Los métodos de viento ascendente como el método Godunov se consideran mejores; sin embargo, el método del conjunto de niveles no garantiza la preservación del volumen y la forma del nivel del conjunto 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 esencialmente no oscilatorios (ENO) de alto orden, e incluso entonces, la viabilidad de las simulaciones a largo plazo es cuestionable. Se han desarrollado métodos más avanzados para superar esto; por ejemplo, combinaciones del método de nivelación con partículas marcadoras de seguimiento sugeridas por el campo de velocidad. ^[4]

Ejemplo

Consideremos un círculo unitario en , que se encoge sobre sí mismo a una tasa constante, es decir, cada punto en el límite del círculo se mueve a lo largo de su interior apuntando normalmente a una velocidad fija. El círculo se encogerá y finalmente colapsará hasta quedar 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 colapsará de manera similar hasta un punto. Esto se debe a que esta 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 instantánea de la llama, conocida como ecuación G.
• Se han desarrollado estructuras de datos de conjuntos de niveles para facilitar el uso del método de conjuntos 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 conjunto 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 procesamiento de imágenes , gráficos por computadora , geometría computacional , optimización , dinámica de fluidos computacional y biología computacional .

Véase también

• Diagrama de caja de contorno
• Análisis de cebra
• ecuación g
• Biblioteca de simulación avanzada
• Método del volumen del fluido
• Segmentación de imágenes#Métodos de establecimiento de niveles
• Métodos de límites inmersos
• Métodos estocásticos eulerianos lagrangianos
• 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. Phys. , 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 implícitas dinámicas . 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 artificial y ciencia de los materiales . Cambridge University Press . ISBN 978-0-521-64557-7.
4. Enright, D.; Fedkiw, RP; Ferziger, JH ; Mitchell, I. (2002), "Un método híbrido de conjunto de niveles de partículas para una mejor captura de la interfaz" (PDF) , J. Comput. Phys. , 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 . Lecture Notes in Mathematics. Vol. 771. Springer. 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 conjunto de niveles.
• Página de inicio de Stanley Osher .
• El método de conjunto de niveles. MIT 16.920J / 2.097J / 6.339J. Métodos numéricos para ecuaciones diferenciales parciales por Per-Olof Persson. 8 de marzo de 2005
• Lección 11: El método de conjunto de niveles: MIT 18.086. Métodos matemáticos para ingenieros II por Gilbert Strang