Méthode du level-set - Level-set method

Lire les médias

Vidéo de la spirale se propageant par level sets ( courbure flux ) en 2D. LHS montre une solution de niveau zéro. RHS montre le champ scalaire de niveau.

Les méthodes des ensembles de niveaux ( LSM ) sont un cadre conceptuel pour l'utilisation des ensembles de niveaux comme outil d' analyse numérique des surfaces et des formes . L'avantage du modèle level-set est que l'on peut effectuer des calculs numériques impliquant des courbes et des surfaces sur une grille cartésienne fixe sans avoir à paramétrer ces objets (c'est ce qu'on appelle l' approche eulérienne ). De plus, la méthode level-set permet de suivre très facilement les formes qui changent de topologie , par exemple, lorsqu'une forme se divise en deux, développe des trous, ou l'inverse de ces opérations. Tout cela fait de la méthode des niveaux un excellent outil pour modéliser des objets variant dans le temps, comme le gonflage d'un airbag ou une goutte d'huile flottant dans l'eau.

Une illustration de la méthode level-set

La figure de droite illustre plusieurs idées importantes sur la méthode des level-sets. Dans le coin supérieur gauche, nous voyons une forme ; c'est-à-dire une région délimitée avec une frontière bien élevée. En dessous, la surface rouge est le graphique d'une fonction level set déterminant cette forme, et la région bleue plate représente le plan xy . La limite de la forme est alors l'ensemble de niveau zéro de , tandis que la forme elle-même est l'ensemble des points dans le plan pour lesquels est positif (intérieur de la forme) ou zéro (à la limite). ${\style d'affichage \varphi }$${\style d'affichage \varphi }$${\style d'affichage \varphi }$

Dans la rangée du haut, nous voyons la forme changer de topologie en se divisant en deux. Il serait assez difficile de décrire numériquement cette transformation en paramétrant la frontière de la forme et en suivant son évolution. Il faudrait un algorithme capable de détecter le moment où la forme se divise en deux, puis de construire des paramétrisations pour les deux courbes nouvellement obtenues. D'un autre côté, si nous regardons la rangée du bas, nous voyons que la fonction level set s'est simplement traduite vers le bas. C'est un exemple où il peut être beaucoup plus facile de travailler avec une forme via sa fonction de mise à niveau qu'avec la forme directement, où l'utilisation directe de la forme nécessiterait de prendre en compte et de gérer toutes les déformations possibles que la forme pourrait subir.

Ainsi, en deux dimensions, la méthode level-set revient à représenter une courbe fermée (comme la frontière de forme dans notre exemple) à l'aide d'une fonction auxiliaire , appelée fonction level-set. est représenté comme l' ensemble de niveau zéro de par ${\style d'affichage \Gamma }$${\style d'affichage \varphi }$${\style d'affichage \Gamma }$${\style d'affichage \varphi }$

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

et la méthode level-set manipule implicitement , via la fonction . Cette fonction est supposée prendre des valeurs positives à l'intérieur de la région délimitée par la courbe et des valeurs négatives à l'extérieur. ${\style d'affichage \Gamma }$ ${\style d'affichage \varphi }$${\style d'affichage \varphi }$${\style d'affichage \Gamma }$

L'équation des niveaux

Si la courbe se déplace dans la direction normale avec une vitesse , alors la fonction level-set satisfait l' équation level-set${\style d'affichage \Gamma }$${\style d'affichage v}$${\style d'affichage \varphi }$

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

Ici, est la norme euclidienne (désignée habituellement par des barres simples dans les EDP), et c'est le temps. Il s'agit d'une équation aux dérivées partielles , en particulier une équation de Hamilton-Jacobi , et peut être résolue numériquement, par exemple, en utilisant des différences finies sur une grille cartésienne. ${\style d'affichage |\cdot |}$${\style d'affichage t}$

Cependant, la résolution numérique de l'équation des niveaux nécessite des techniques sophistiquées. Les méthodes simples aux différences finies échouent rapidement. Les méthodes ascendantes , telles que la méthode Godounov , s'en sortent mieux ; cependant, la méthode level-set ne garantit pas la conservation du volume et de la forme de la level set dans un champ d'advection qui conserve la forme et la taille, par exemple, un champ de vitesse uniforme ou de rotation. Au lieu de cela, la forme du jeu de niveaux peut être gravement déformée et le jeu de niveaux peut disparaître sur plusieurs pas de temps. Pour cette raison, des schémas aux différences finies d'ordre élevé sont généralement nécessaires, tels que des schémas d'ordre élevé essentiellement non oscillatoires (ENO), et même dans ce cas, la faisabilité de simulations à long terme est discutable. D'autres méthodes sophistiquées pour faire face à cette difficulté ont été développées, par exemple, des combinaisons de la méthode level-set avec des particules marqueurs de traçage advectées par le champ de vitesse.

Exemple

Considérons un cercle unitaire dans , se rétrécissant sur lui-même à une vitesse constante, c'est-à-dire que chaque point sur la frontière du cercle se déplace le long de sa normale pointant vers l'intérieur à une vitesse fixe. Le cercle rétrécira et finira par s'effondrer jusqu'à un point. Si un champ de distance initial est construit (c'est-à-dire une fonction dont la valeur est la distance euclidienne signée à la frontière, intérieur positif, extérieur négatif) sur le cercle initial, le gradient normalisé de ce champ sera la normale du cercle. ${\textstyle \mathbb {R} ^{2}}$

Si le champ a une valeur constante soustraite dans le temps, le niveau zéro (qui était la limite initiale) des nouveaux champs sera également circulaire et s'effondrera de la même manière en un point. Ceci est dû au fait qu'il s'agit effectivement de l'intégration temporelle de l' équation d'Eikonal avec une vitesse de front fixe.

Dans combustion , ce procédé est utilisé pour décrire la surface de flamme instantanée, dite équation G .

Histoire

La méthode level-set a été développée en 1979 par Alain Dervieux, puis popularisée par Stanley Osher et James Sethian . Il est devenu populaire dans de nombreuses disciplines, telles que le traitement d'images , l'infographie , la géométrie computationnelle , l' optimisation , la dynamique des fluides computationnelle et la biologie computationnelle .

Un certain nombre de structures de données level-set ont été développées pour faciliter l'utilisation de la méthode level-set dans les applications informatiques.

Applications

• Dynamique des fluides computationnelle
• La combustion
• Planification de trajectoire
• Optimisation
• Traitement d'image
• Biophysique computationnelle

Dynamique des fluides computationnelle

Pour exécuter un modèle mathématique dans l'interface de deux fluides différents, nous devons adoucir les interactions entre les fluides. Par conséquent, nous devons appliquer une fonction spécifique : la méthode Compact Level Set.

En tant que « spin off », le CompactLSM est un complément du LSM, qui aide à résoudre les équations du LSM. Il peut être utilisé en simulation numérique d'écoulement, par exemple, si l'on travaille avec une discrétisation de l'interface eau-air, compacte au sixième ordre, assure le calcul précis et rapide des équations d'interface (Monteiro 2018).

Le LSM utilise une fonction de distance pour localiser différents fluides. Une fonction distance est celle dont la valeur représente la plus petite distance du point où elle est analysée à l'interface. Cette fonction distance est identifiée par des isolignes (2D) ou des isosurfaces (3D), montrant que les valeurs négatives se réfèrent à l'un des fluides, les valeurs positives se réfèrent à l'autre et la valeur zéro correspond à la position de l'interface.

Mais comment la fonction Heaviside est-elle insérée dans la méthode Compact Level Set ?

Étant donné que la masse spécifique et la viscosité sont discontinues à l'interface, à la fois un problème de diffusion excessive (élargissement de l'interface) et des oscillations numériques sont attendus s'il n'y a pas de traitement adéquat du fluide près de l'interface. Pour minimiser ces problèmes, la méthode Level Set utilise une fonction Heaviside lisse et liée aux cellules qui définit explicitement la position de l'interface (∅ = 0).

La transition dans l'interface est maintenue en douceur, mais avec une épaisseur de l'ordre de grandeur de la taille de la cellule, pour éviter l'introduction de perturbations avec une échelle de longueur égale à celle du maillage, puisque l'interface induit une propriété de saut brusque d'un cellule à la suivante (Unverdi et Tryggvason, 1992). Pour reconstruire les propriétés matérielles de l'écoulement, telles que la masse spécifique et la viscosité, une autre fonction marqueur, I (∅), de type Heaviside est utilisée :

${\displaystyle I(\varphi )={\begin{cases}0,&{\text{if }}\varphi <-\delta \Delta \\[8pt]{\dfrac {1}{2}}\left [1+{\dfrac {\varphi }{\delta \Delta }}+{\dfrac {1}{\pi }}\sin \left({\dfrac {\pi \varphi }{\delta \Delta }} \right)\right],&{\text{if }}|\varphi |\leq \delta \Delta \\[8pt]1,&{\text{if }}\varphi >\delta \Delta \end{ cas}}}$

( 1 )

où δ est un coefficient empirique, généralement égal à 1; 5 et est la discrétisation caractéristique du problème, qui varie selon le phénomène à simuler. La valeur de δ représente une interface avec une épaisseur de trois cellules, et donc δ ô représente la moitié de l'épaisseur de l'interface. Notez que dans cette méthode, l'interface a une épaisseur virtuelle, car elle est représentée par une fonction de lissage. Les propriétés physiques, telles que la masse spécifique et la viscosité cinématique, sont calculées comme suit :

${\displaystyle \rho =(1-I)\rho _{1}+I\rho _{2}\qquad e\qquad v=(1-I)v_{1}+Iv_{2}}$

( 2 )

où ρ ₁ , ρ ₂ , v ₁ et v ₂ sont la masse spécifique et la viscosité cinématique des fluides 1 et 2. L'équation 2 peut être appliquée de manière analogue aux autres propriétés des fluides.

Voir également

Les références

Liens externes

• Voir Ronald Fedkiw de page web académique pour de nombreuses images superbes et des animations montrant comment la méthode des lignes de niveaux peut être utilisé pour modéliser les phénomènes de la vie de réel, comme le feu, l' eau, le tissu, les matériaux de fracturation, etc.
• Multivac est une bibliothèque C++ pour le suivi de front en 2D avec des méthodes level-set.
• La page web de James Sethian sur la méthode level-set.
• La page d'accueil de Stanley Osher .