Grenoble INP � ENSIMAGÉcole Nationale Supérieure dInformatique et de Mathématiques Appliquées

Rapport de Travaux d'Études et de Recherche

E�ectué au Laboratoire Jean Kuntzmann

Design d'un champ de vecteurs tangents

Allemand-Giorgis Léo2e année � Option MMIS

Laboratoire Jean Kuntzmann Responsable du TER

51 Rue des Mathématiques Hahmann StefanieCampus de Saint Martin d'Hères

38041 Grenoble cedex 09

2 TABLE DES MATIÈRES

Table des matières

1 Introduction 4

1.1 Présentation du sujet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Contexte du travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 La méthode d'interpolation 4

2.1 Présentation de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Les données du problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Le fonctionnement de la méthode . . . . . . . . . . . . . . . . . . . . . . . 5

2.3.1 Création d'une base polaire . . . . . . . . . . . . . . . . . . . . . . 52.3.2 Création d'un lien entre deux facettes . . . . . . . . . . . . . . . . . 52.3.3 Calculs le long de l'arête duale barycentrique . . . . . . . . . . . . . 72.3.4 Calcul du vecteur au point P . . . . . . . . . . . . . . . . . . . . . 7

3 Implémentation 8

3.1 Le programme de départ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.1.1 Description du programme de base . . . . . . . . . . . . . . . . . . 83.1.2 Structure de données des maillages . . . . . . . . . . . . . . . . . . 8

3.2 Conception du code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 Implémentation de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3.1 Contrainte dû à la structure de données . . . . . . . . . . . . . . . 93.3.2 Entrées de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.3 Les problèmes rencontrés . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Résultats données par la méthode 10

4.1 Des succès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2 Les problèmes non résolus . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 Commentaires sur la méthode 12

5.1 Le champ est-il continu ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125.1.1 Dans la facette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125.1.2 Les sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125.1.3 Passage entre deux facettes . . . . . . . . . . . . . . . . . . . . . . 12

5.2 Comportement des lignes de champ . . . . . . . . . . . . . . . . . . . . . . 12

6 Conclusions 13

6.1 Conclusion du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136.2 Conclusion du TER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

TABLE DES MATIÈRES 3

Remerciements

Je voudrais remercier Stefanie Hahmann pour m'avoir accueilli tout au long du TER,pour m'avoir inviter à des conférences et pour m'avoir permis d'assister à une réunion del'équipe IMAGINE.

Je voudrais aussi remercier l'équipe IMAGINE et particulièrement Marie-Paule Canipour nous avoir permis d'assister à une de leur réunion d'équipe.

4 2 LA MÉTHODE D'INTERPOLATION

1 Introduction

1.1 Présentation du sujet

Les domaines de la dynamique des �uides, ou encore la modélisation par des méthodesaux éléments �nis utilisent souvent des méthodes d'interpolation de champs de vecteurs.Par exemple, pour visualiser des champs de vecteurs, on utilise souvent de l'interpolationlinéaire qui possède les avantages d'être très simple et peu coûteuse.

Malheureusement, cette méthode ne permet pas de reproduire la complexité de toutchamp de vecteur. En e�et, les champs ayant des points de singularités qui ne sont pas dupremier ordre ne peuvent pas être représenté. Cela implique un changement dans la topolo-gie du champ de vecteur. Il faut donc trouver d'autres manières de faire une interpolationd'un champ de vecteur.

Une méthode a été trouvé par Wan-Chiu Li, Bruno Vallet, Nicolas Ray et Bruno Lévy.Cette méthode est dé�ni dans Representing Higher-Order Singularities in Vector Fieldsand Piecewise Linear Surfaces. L'idée est de représenter les vecteurs dans chaque facetteen coordonnées polaires et d'utiliser un paramètre donnant le nombre de tour que doit fairele champ de vecteur lorsqu'il va d'un centre de gravité d'une facette au centre de gravitéd'une facette adjacente.

Ce projet a pour but d'implémenter cette méthode d'interpolation dans un programmedéjà existant tournant sous OpenGL.

1.2 Contexte du travail

Le travail a été e�ectué la plupart du temps dans la tour IRMA, le mardi après-midi.J'ai travaillé en collaboration avec Pierre-Luc Manteaux, un autre étudiant de TER, quia aussi travaillé sur une méthode d'interpolation de vecteurs. Un programme nous a étéfournis et nous y avons ajouté nos méthodes d'interpolation et nous avons mis des méthodesde visualisation de champ de vecteurs dur un maillage.

2 La méthode d'interpolation

2.1 Présentation de la méthode

Le principe de la méthode est de faire une interpolation entre les vecteurs aux centresde gravité des facettes. On relie les deux centres de gravité de deux facettes adjacenteset on fait que le vecteur change de manière continue le long de la ligne qui relie les deuxfacettes en faisant varier la norme de façon linéaire et en faisant tourner le vecteur (voir la�gure 1).

2.2 Les données du problèmes 5

Figure 1 � Façon d'interpoler entre A et B (image tirée de la publicationRepresenting Higher-Order Singularities in Vector Fields and Piecewise Linear Surfaces

2.2 Les données du problèmes

Pour appliquer la méthode d'interpolation, nous avons besoin d'un maillage. Si possible,toute arête doit appartenir à deux facettes distinctes. Dans le cas contraire, le résultat nesera pas prévisible.

2.3 Le fonctionnement de la méthode

Nous allons chercher l'interpolation du champ de vecteur en point d'une facette quenous appellerons P . La normale à la facette sera notée n.

2.3.1 Création d'une base polaire

Pour commencer, nous avons besoin d'une base polaire de la facette. Nous allons doncprendre une arête comme première composante de notre base (noté x) et le produit vectorielde x par n nous donnera la deuxième composante.

Un vecteur v de la facette pourra alors être écrit :

v =

(ρ cos θρ sin θ

)

avec ρ = ‖v‖ et(

cos θsin θ

)= v

‖v‖ . Le paramètre θ correspond à un angle que nous prendrons

dans R.

2.3.2 Création d'un lien entre deux facettes

Nous allons créer un lien entre notre facette de départ et une deuxième facette. Pourcela, nous allons chercher l'arête la plus proche du point P. La facette qui contient notrearête et qui est bien sûr di�érente de notre facette de départ sera alors la deuxième facettesur laquelle nous allons travailler.Nous pouvons voir par exemple la �gure 2 où la facette courante est f et la deuxièmefacette sera la facette f ′.

Nous dé�nissons de même qu'à la partie 2.3.1 une base polaire pour f ′.Ensuite, il faut transformer les champs de vecteurs que nous avons au centre de gravitédes facettes en coordonnées polaires. Nous noterons ρ(f) et θ(f) les coordonnées polaires

6 2 LA MÉTHODE D'INTERPOLATION

Figure 2 � Deux facettes et un point P

du vecteur au centre de gravité de la facette f et ρ(f ′) et θ(f ′) les coordonnées polaires duvecteur au centre de gravité de la facette f ′.

L'interpolation des vecteurs se fera le long de la ligne passant par le centre de gravitéde f , le milieu de l'arête commune aux deux facettes et par le centre de gravité de f ′. Cetteligne peut être vue sur la �gure 3. Celle-ci est appelée l'arête duale barycentrique et nousla noterons e.

Figure 3 � La ligne reliant les deux facettes

2.3 Le fonctionnement de la méthode 7

2.3.3 Calculs le long de l'arête duale barycentrique

Les calculs important se feront le long de l'arête duale car c'est sur celle-ci que l'onfera tourner le vecteur. Pour faire ceci, nous allons calculer la di�érence d'angle entre lesextrémités de e :

∆θ(e) = ang(vG,vG′) + θ(f ′)− θ(f) + 2pπ

La fonction ang calcule l'angle entre deux vecteurs et sont résultat appartient à (−π, π]. Leparamètre p est un entier relatif et est appelé période de saut. Ce paramètre sert à choisirla façon dont va être interpolé le champ de vecteur le long de la ligne e.

Ensuite, il faut faire de même pour la di�érence en norme :

∆ρ(e) = ρ(f ′)− ρ(f)

Nous allons maintenant dé�nir un coe�cient α qui correspond au rapport entre lalongueur de e qui est dans la facette f et la longueur totale de la ligne. En appelant M lemilieu de l'arête commune, on a :

α =‖GM‖

‖GM‖+ ‖MG′‖

La dernière dé�nition va être celle du paramètre t qui est la solution de P = (1− t)G+tM .

En�n, nous pouvons faire l'interpolation du champ de vecteur sur la ligne e. Pour cela,il faut calculer l'angle et la norme des vecteurs sur la ligne. On fait une simple interpolationlinéaire. En prenant I un point de la ligne e :

θ(I) = θ(f) + ∆θ(e)αt

et

ρ(I) = ρ(f) + ∆ρ(e)αt

2.3.4 Calcul du vecteur au point P

Pour calculer l'interpolation du vecteur au point P , il faut tout d'abord trouver lesommet de la facette courante le plus proche de P , nous le noterons V . C'est forcément undes sommets de l'arête trouvée dans la partie 2.3.2. On cherche alors le point d'intersectionI entre la droite (PV ) et la ligne e. Le vecteur au point P sera alors le même que celui aupoint I.Nous voyons donc que les vecteurs seront constants le long du segment [V I]. La �gure4 montre l'interpolation du champ au points P et P ′ à partit du calcul au point I. Lesvecteurs en ces deux points sont égaux au vecteur au point I.

8 3 IMPLÉMENTATION

Figure 4 � Interpolation du champ au point P , P ′ et I

3 Implémentation

3.1 Le programme de départ

3.1.1 Description du programme de base

Le programme qui m'a été donné en début de TER permet d'a�cher des maillages enOpenGL (et donc de tourner autour du maillage, de faire des zooms).Il comprend aussi une méthode d'interpolation des champs de vecteurs. La méthode utiliséest une méthode utilisant les vecteurs aux sommets. Soient V1, V2 et V3 les sommets d'unefacette ayant pour vecteurs respectifsv1, v2 et v3. On note P le point de la facette où l'onveut connaître le champ. Il existe α, β et γ tels que P = αV1 + βV2 + γV3, alors :

vP = αv2 + βv2 + γv3

On peut a�cher les lignes de champ qui partent du centre de gravité des facettes et quiutilisent cette méthode d'interpolation.Le programme est écrit en C.

3.1.2 Structure de données des maillages

La structure de données était imposée par le programme initial. Dans cette structure, lesmaillages sont composés de sommets, d'arêtes et de facettes. A chaque sommet correspondun entier qui est son numéro et ses coordonnées dans la base cartésienne de l'espace.Une arête comprend son numéro, les deux numéros des sommets qui la dé�nissent et lesnuméros des deux facettes adjacentes.

3.2 Conception du code 9

Une facette a un numéro, les trois numéros des arêtes qui la composent, les numéros destrois sommets et les coordonnées d'une normale à la facette.Ceci est écrit dans un format nommé .ngb qui n'est pas un format standard. Celui-ci nesera pas détaillé ici.

Ensuite, chaque sommet comporte un champ correspondant au vecteur du champ ence point. Ces vecteurs sont dé�nis dans un �chier .vec.

3.2 Conception du code

Pierre-Luc Manteaux a travaillé avec moi sur l'ajout de nos codes au programme initial.Nous avons choisi de faire chacun deux �chiers contenant notre méthode (un �chier .h etun �chier .c) et de faire un �chier qui contiendrait des outils dont nous aurions besoin toutles deux. Dans ce �chier, nous avons par exemple mis le calcul d'angle entre deux vecteurs.Ensuite, nous avons modi�é le code existant pour intégrer nos programmes pour l'a�chagede lignes de champ.

Nous avons aussi travaillé ensemble sur l'a�chage du champ de vecteur sur le maillage.Nous en avons fait deux : une met des vecteurs un peu partout sur le maillage et l'autrea�che les vecteurs sur les lignes entre les barycentres des facettes et les milieux des arêtes.Cette dernière méthode d'a�chage est très intéressante pour la méthode d'interpolationque j'ai implémentée.

3.3 Implémentation de la méthode

3.3.1 Contrainte dû à la structure de données

La structure de données ne donnant pas le champ de vecteur au centre de gravité maissur les sommets des facettes. J'ai donc choisi de faire une interpolation linéaire pour avoirle vecteur au centre de gravité de la facette.

De plus, le champ que l'on trouve avec l'interpolation linéaire ne se situe pas forcémentdans le plan de la facette. La méthode utilise un champ dans le plan, donc le vecteur estprojeté dans le plan de la facette.

3.3.2 Entrées de la méthode

Dans l'appel de la méthode faisant l'interpolation, il faut donner le paramètre de p(période de saut), le numéro de la face courante, le point où l'on veut faire l'interpolationet les listes de sommets, arêtes et facettes qui composent le maillage. La méthode n'apas vraiment besoin de connaître tout le maillage, elle n'utilise que deux facettes. Mais,soit la recherche de la facette la plus proche du point se faisait dans la méthode, et doncon a besoin du maillage, soit à l'extérieur, mais nous avons préféré que dans l'a�chagegraphique, il n'y ait l'appel que d'une seule fonction pour ne pas compliquer le code.

10 4 RÉSULTATS DONNÉES PAR LA MÉTHODE

3.3.3 Les problèmes rencontrés

Plusieurs problèmes ont été rencontrés pendant l'implémentation :Le plus gros problème est venu de la compréhension du code principal. En e�et, celui-cimanque vraiment de commentaires et est donc di�cilement utilisable rapidement. Un des�chier que j'ai eu à manipuler comprenait dans les 2500 lignes avant que des changementssoient faits. Mais il a très peu de commentairesLa recherche d'une arête ou d'un sommet à partir d'une arête ou d'un sommet n'a pastoujours été évidente. La structure de données n'est pas toujours facile a utilisé dès lorsque l'on doit mêler les trois composantes du maillage.Il y a eu des problèmes avec la structure de données. En e�et, il y a normalement plus dechoses dans la structure de données que ce que j'ai décrit, mais certains champs n'étaientpas remplis.L'intersection de deux droites dans l'espace m'a posé des problèmes : il y a des cas di�érentsà faire car il faut véri�er que les dénominateurs ne sont pas nuls, et j'ai fait des erreursdans les conditions et des échanges de variables. Ces erreurs n'ont pas été faciles à trouver.J'ai eu du mal à comprendre ce qu'est le paramètre α (voir 2.3.3). Il était expliqué grâce àun dessin que je n'avais pas compris au moment de l'implémentation. La première versionne donnait pas la bonne chose.

4 Résultats données par la méthode

4.1 Des succès

Lorsque l'on observe les vecteurs le long des lignes entre les centres de gravité desfacettes et les milieux des arêtes, on voit que le plus souvent ils tournent comme nousle voulons et sur d'autres �gures, on voit que les vecteurs sont constants selon des lignespassant par les sommets. La �gure 5 est un exemple où l'on voit les vecteurs tourner lelong de la ligne.

4.2 Les problèmes non résolus

Il reste plusieurs problèmes :

A certains endroits, les vecteurs sont constant le long de ligne e dans une même facette.Cela semble provenir de l'implémentation de la méthode d'intersection de deux droites. La�gure 6 montre ce problème.

Lorsque les lignes de champs s'approchent des sommets, elles deviennent instables etsortent parfois du maillage.

4.2 Les problèmes non résolus 11

Figure 5 � Exemple où le champ est correct

Figure 6 � Exemple où le champ n'est pas correct

12 5 COMMENTAIRES SUR LA MÉTHODE

5 Commentaires sur la méthode

5.1 Le champ est-il continu ?

5.1.1 Dans la facette

Pour savoir si le champ est continue, il su�t de regarder la continuité sur la ligne e quiest dans une facette. On voit que θ et ρ sont continus le long de la ligne, le champ est donccontinu dans la facette.

5.1.2 Les sommets

Mais il faut se demander comment se comporte le champ au sommet. Le sommet estsur toutes les lignes passant par lui-même et la ligne e. Le champ à un sommet prend donctoutes les valeurs qu'il y a sur la ligne. Comme ces valeurs ne sont pas constantes, le champne peut pas être dé�ni en ce sommet. Le champ n'est donc pas continue aux sommets dumaillage.

5.1.3 Passage entre deux facettes

Les vecteurs étant dans le plan des facettes, le passage ne peut pas être continu si lesfacettes ne sont pas dans le même plan.

Mais on peut dire qu'il y a une sorte de pseudo-continuité puisque sur l'arête entre lesdeux facettes, l'angle et la norme dépendent du vecteur que l'on trouve pour le milieu del'arête. Il faut donc choisir la base polaire de la deuxième facette de façon à ce que lesdeux bases polaires soient égales si les deux facettes sont dans le même plan. Donc pouravoir la base polaire de la seconde facette, on prend la base polaire de la première et on lafait tourner autour de l'arête qui est contenu dans les deux facettes jusqu'à ce que l'on seretrouve dans le plan de la deuxième facette.

5.2 Comportement des lignes de champ

Le programme permet de tracer des lignes de champ qui partent du barycentre. J'ai pualors observer que celle-ci avait tendance à aller vers un des sommet de la facette d'où ellepart.

Ceci est dû au fait que l'on fait tourner le vecteur le long de la ligne. En faisant ceci, ily a des chances qu'à un moment, le vecteur d'un point P de la ligne e soit dirigé vers undes sommets de l'arête la plus proche de P . Comme les vecteurs sont constants le long dusegment entre P et ce sommet, si la ligne de champ arrive sur ce segment, elle sera envoyésur le sommet. De plus, les vecteurs qui sont proches de cette ligne ont tendance à ramenerla ligne de champ vers ce segment.

On peut donc dire que la ligne de champ va souvent se diriger vers un sommet sanschanger de facette.

13

Figure 7 � Comportement des lignes de champ

Un exemple est montré à la �gure 7 où l'on voit bien que la ligne de champ va vers undes sommets de la facette.

6 Conclusions

6.1 Conclusion du projet

Malgré le problème que l'on rencontre, la méthode fonctionne en de nombreux pointsdu maillage. De plus, les deux méthodes d'a�chage du champ de vecteurs donnent un bonrendu. Le code est réutilisable et est commenté.

En changeant un paramètre à l'intérieur du code, il est possible de contrôler la valeurdes paramètres à chaque partie du code. Grâce à cela, il doit être possible de comprendrece qu'il se passe et comment enlever l'erreur.

6.2 Conclusion du TER

Le TER a été une bonne expérience pour moi, j'ai pu découvrir le monde de la rechercheen travaillant dans un des bureau du laboratoire ou encore en assistant à une réunion del'équipe de recherche IMAGINE. J'ai aussi pu voir des présentation de travaux d'étudiantsen thèse dans le domaine des mathématiques appliqués.