Sujets des projets
—–
projet C++
Université Pierre et Marie Curie
F. Hecht, R. Chakir
Master II / session 2007/2008
Introduction
Pour tous les projets , il faudra faire un rapport d’une dizaine de pages en Latex.
Ces projets sont à réaliser par binôme, les choix des projets sont faits par les enseignants, une fois le
binôme déclaré.
1 Projets 1,2 & 3 : Elements finis
Vous disposez d’un programme, EF23" (voir [Link]
MPE/[Link] ), résolvant les équations de Poisson par éléments finis P1 Lagrange 2d ou 3d avec
comme solveur un gradient conjugué ou UMFPACK (voir [Link]
ftp/MPE/[Link]).
Pour télécharger et installer les sources 265Ko et grosmaillage 6Mo
curl -O [Link]
curl -O [Link]
tar zxvf [Link]
tar zxvf [Link]
cd EF/libMesh
make install clean
cd ../EF23
make EF2d EF2dMat EF3d
Pour la partie UMFPACK installer UMFPACK (voir le cours dernier cours)
curl -O [Link]
Les 2 premiers projets sont basés sur la modification du le petit programme [Link] (4 pages)
Projet 1 : Calculer des valeurs propres du problème de Poisson en utilisant la bibliothèque ARPACK++
Lire la page [Link] pour les pro-
blèmes de compilations.
Remarque : les valeurs propres du problème de Poisson avec conditions de Dirichlet sur le carré ]0, π[2
sont n2 + m2 et les fonctions propres associés sont sin(nx)sin(my).
1
Mastere II / MPE 2
Projet 2 : Changer le solveur de EF2DUMFPACK par les solveurs de SuperLU, PETSc, et d’autre sol-
veur d’Internet : voir la page [Link]
[Link] afin de comparer les vitesses de résolution.
Projet 3 :Ecrire un outil de visualisation des isosurfaces de la solution avec OpenGL, GLUT, ombrage, trans-
parence et stéréo,
Il faut partir de glplotiso dans
# OpenGL: representation 3D et couleurs
curl -O [Link]
tar zxvf [Link]
cd glplot
# Editer le Makefile pour choisir ou son vos OpenGL/ GLUT
make all
remarque : il faut ajouter -lXi -lXmu a la fin de la variable GLLIBS dans le Makefile pour l’édition
de liens de avec GLUT
2 Projet 4 :Visualisation et optimisation de maillage
Le but de ce projet de visualiser une fonction f du carré ] − 1, 1[2 à valeur dans IR avec une précision de
ε donnée.
Il faut donc construire un maillage telle que l’erreur sur chaque triangle du maillage soit inférieure à ε.
L’algorithme de raffinement de maillage est très simple : il consiste à couper les triangles d’erreur trop
grand en deux parties égales par rapport à une des 3 arêtes en choisissant l’arête qui générera l’erreur
minimal.
Donc l’algorithme est :
1. insérer les triangle avec une erreur trop grande dans la queue
2. tant que la queue n’est pas vide faire :
(a) Prendre le triangle de la queue et découper le triangle en deux en choissisant la bonne arête, et
ajouter les nouveaux triangles dans la queue si nécessaire.
L’erreur sur un triangle K sera définie par :
Z
EK = | f − ΠK ( f )|2
K
Où ΠK ( f ) est la projection L2 (K) de f sur l’espaces P1 (K) des fonctions polynomes de degre 1 de K à
valeur dans R, c’est-à-dire :
Z Z Z
ΠK ( f ) − f = 0; (ΠK ( f ) − f )x = 0 (ΠK ( f ) − f )y = 0
K K K
Et vous utiliserez des formules d’integration pour évaluer les intégrales qui sont définies dans http://
[Link]/format/[Link]/0501496
Programmer l’algorithme precédent pour visualiser les fonctions
f1 (x, y) = x2 + y2
f2 (x, y) = x2 + y3 + tanh(5sin(2(y + x))
avec la bibliothèque GLUT où le paramètre ε peut être changé interactivement, et bien sur il doit être
possible d’afficher ou non le maillage.
Mastere II / MPE 3
3 Projets 5 : Optimisation d’un trajet sur une topographie quelconque
Le principe est d’optimiser le trajet d’un véhicule se déplaçant d’un point à un autre sur un terrain
ayant une topographie quelconque. Cette optimisation devra être réalisée en minimisant deux quantités : la
distance entre le point de départ et le point d’arrivée et la pente (positive et négative) du trajet. Il faudra donc
trouver le chemin optimal pour que le véhicule ait le moins de distance à parcourir et qu’il ait le moins à
monter et descendre possible.
3.1 Discrétisation et graphe
Soit Ω = [a, b]×[c, d] ⊂ R2 le domaine dans lequel le véhicule pourra évoluer. Soit la fonction f : Ω 7→ R
associant à un point X = (x, y) son altitude f (X).
La première étape est la discrétisation de Ω. On se donne deux entiers Nx et Ny et on définit les points
Xi j = (xi , y j ) avec i = 1, ..., Nx et j = 1, ..., Ny . Si on note ∆x = (b − a)/(Nx − 1) et ∆y = (d − c)/(Ny − 1),
on choisira Nx et Ny tels que ∆x ' ∆y. Les points (Xi j )i, j sont les sommets du graphe associé à Ω (on notera
X l’ensemble des sommets (Xi j )i, j du graphe).
On définit ensuite l’ensemble A des arêtes du graphe. Pour cela, on se donne un réel δ > max(∆x, ∆y).
Les arêtes du graphe sont définies par les segments σXn Xm = (Xn , Xm )1≤n,m≤Nx Ny vérifiant 0 < |Xn − Xm | ≤ δ .
Voici deux exemples de graphes obtenus suivant différentes valeurs de δ .
∆y ∆y
δ δ
∆x
∆x
p p
max(∆x, ∆y) < δ < ∆x2 + ∆y2 ∆x2 + ∆y2 ≤ δ < 2 min(∆x, ∆y)
La dernière étape pour la construction du graphe est d’affecter une valeur à chacune des arêtes. Soit
l’arête σXn Xm reliant les points Xn et Xm . La valeur cXn Xm (ou le coût) associée à cette arête sera une fonction
qui dépendra à la fois de la distance |Xn − Xm | ainsi que la valeur absolue de la pente | f (Xm ) − f (Xn )|/|Xn −
Xm |. Le coût cXn Xm pour aller de Xm à Xn (ou bien de manière équivalente de Xn à Xm ) par l’arête σXn Xm sera
d’autant plus grand que la distance entre Xm et Xn sera importante et que la valeur absolue de la pente sera
grande. Par exemple, on pourrait définir le coût ainsi :
|Xn − Xm | | f (Xm ) − f (Xn )|
cXn Xm = α + (1 − α) , 0 ≤ α ≤ 1.
max(∆x, ∆y) |Xn − Xm |
3.2 Détermination du plus court chemin
Soit A ∈ X le point de départ du véhicule et B ∈ X son point d’arrivée. On définit un chemin C allant
de A à B comme une suite de sommets de X C = {A = X0 , X1 , X2 , ..., Xp−1 , Xp = B} tels que pour tout
n = 0, ..., p − 1 on ait σXn Xn+1 ∈ A , c’est-à-dire que tout segment (Xn , Xn+1 ) corresponde à une arête du
p
graphe. On associe au chemin C son coût : cC = ∑n=0 cXn Xn +1 . Le problème d’optimisation du trajet du
véhicule revient donc à trouver le chemin allant de A à B dont le coût est le plus faible. Ce chemin est appelé
le plus court chemin. Pour le déterminer, on utilisera l’algorithme de Dijkstra.
Soit R l’ensemble des sommets restant à visiter et P l’ensemble des sommets déjà parcourus. On définit
aussi d(X) comme le coût du plus court chemin reliant X à A et p(X) le prédécesseur de X dans le plus court
chemin le reliant à A. L’algorithme de Dijkstra :
Mastere II / MPE 4
– Initialisation :
R = X \ {A},
P = {A},
d(A) = 0, d(X) = cAX si σAX ∈ A et d(X) = +∞ sinon.
– Tant que B ∈ / P, Faire :
– Trouver X le sommet réalisant le minimum de d(.) sur R.
– Ajouter X à l’ensemble P.
– Enlever X à l’ensemble R.
– Pour tout Y ∈ R tel que σXY ∈ A , Faire :
– Si d(X) + cXY < d(Y ) Alors d(Y ) = d(X) + cXY , p(Y ) = X ; Fin Si.
– Pour obtenir le plus court chemin reliant A et B, il suffit alors de cheminer à l’envers : on regarde
B, puis on sauvegarde son prédécesseur p(B), puis le prédécesseur de son prédécesseur p(p(B)), ...
jusqu’à arriver à A.
3.3 But du projet
Le but de ce projet est donc de réaliser un programme utilisant GLUT (voir le TP 3) permettant d’afficher
dans une fenêtre graphique où les sommets du graphe correspondront aux pixels de la fenêtre, dont la couleur
sera donnée par la valeur de la topographie en chacuns de ces points. On devra pouvoir visualiser en outre
le plus court chemin entre deux points de la fenêtre obtenu par l’algorithme de Dijkstra. Enfin, les points de
départ et d’arrivée et différents paramètres de la construction du graphe devront pouvoir être modifiés. Par
exemple, différentes topographies pourront être utilisées (collines, vallées, labyrinthes, ...), la valeur de δ
pourra changer et le calcul du coût par arête pourra être choisi de manière à privilégier la distance, la pente,
ou les deux, en prenant par exemple une combinaison convexe de ces quantités dont la pondération pourra
être modifiée par l’utilisateur. Attention, la gestion de la mémoire devra être particulèrement soignée, pour
ne pas avoir à stocker des informations inutiles (matrices creuses ...).
4 Liens
– un support de cours OpenGL (E. Boyer) [Link]
[Link]
– un support de cours Robin Vivian Format PDF [Link]
– Cours OpenGL de l’ESSI par Michel Buffa [Link]
image/
– Advanced Graphics Programming Techniques Using OpenGL [Link]
code/sig99/
u
