INFO821 : Infographie

TPs et TDs

TD1

• Comment dessiner une sphère ? Nous réfléchirons ensemble ... Remarque les sphères de la librairie GLU (un composant d'openGL), ont un axe de symétrie particulier bien visible.

Le corrigé est ici . IL faut surtout regarder sphere.c et les fonctions qu'il utilise dans geometrie.c. Dans le fichier principal ̀td1_sphere.c il y a plein de choses qui pourront vous paraître obscure pour l'instant. Il faut juste regarder la fonction initGLScene()

En compilant vous devriez voir cela, de gauche à droite :

• 80 triangles en divisant les 20 faces d'un icosaedre en 4
• 72 triangles en divisant les 8 faces d'un octaedre en 9
• Version GLUSphere avec 64 triangles (un rectangle = 2 triangles)

Pour compiler ce corrigé, il faut :

• openGL version 1.X ou 2.X (testé avec 2.1).
• SDL 1.2 (librairie pour faire des jeux ...) que l'on utilise pour ouvrir une fenêtre avec le même code sous windows et linux !
• libgc : le GC de Boehm ... pour ne pas faire free(). Si vous n'arrivez pas à l'installer, remplacer GC_malloc et GC_malloc_atomic par malloc, mais il n'y aura pas de libération de la mémoire inutilisée.

TD 2 + Préparation TP

• Dessiner un ruban de Moebius (une bande de papier recollée sur elle même en faisant un demi tour).
• Le relier à un disque avec des courbes de Bézier (la bande n'a qu'un bord).
• Faire une animation pour mieux montrer ce qui se passe.
• Eliminer les arrêtes trop petites.

Voici un corrigé du TD 2, disponible aussi sous forme d'archive tar ... Cet n'est pas tout à fait un corrigé, la raison transpire dans le sujet de TP.

Alternative :

• Une version complètement compatible C90 (d'après gcc -Wall -pedantic -std=c90)
• Une version (C99) avec un GC minimaliste intégré Il reste un warning, que l'on ne peut pas éviter.

Ce corrigé comprends aussi du code utile (et même indispensable) pour le TP1 ...

Consignes générales sur les TPs

• Deux au maximum par groupe, si le nombre est impair, il y aura j'espère un solitaire.
• À partir du TP2 : bonus de 1pt pour tout changement de binôme.
• Les questions ont un nombre de points + un bonus si la question est finie pendant la séance (il faut donc m'appeler !). N'hésitez par à travailler en parallèle pour avoir plus de bonus.
• Je peux enlever des points pour la qualité du code.
• Les questions hors séances sont à rendre au maximum le lundi suivant le TP, avant 14H.
• Le code doit compiler sur ma machine (vous disposerez d'un compte ssh, le même pour tous, pour tester).
• Le programme au démarrage doit indiquer (par affichage sur la console ou via SDL), comment faire pour visualiser le résultat de chaque question (genre "taper 1 pour le voir ce que donne la question 1")
• Des contraintes supplémentaires sont données, avec le malus correspondant en cas de non respoect. C'est à vous d'indiquer si vous pensez que la contrainte a été respectée ou non.

TP 1, Marching cube

Partie 1

Tous ces programmes doivent être testable avec plusieurs fonctions (au moins 5), sélectionnable sans recompiler (-3).

Pour ceux qui ne code pas en C, il n'est pas nécessaire de stocker les triangles dans la structure de donnée avec demi-arêtes. Cela sera utile pour le TP 2. Ceux qui codent en C, doivent le faire, vu que le code est fourni ! (-3) et qu'il faut travailler dessus pour la partie 2.

• Dighotomie (2+0) : écrire une fonction digothomie(point A, point B, double f(point)) qui en supposant que f(A) est négatif et f(B) est positif calcule une solution de l'équation f(M) = 0 (ou presque !) avec M sur le segment [A, B]. Remarque: le fichier vecteur.c contient une fonction calculant le milieu d'un segment.

• Traitement d'un tétraèdre (3+1) : écrire une fonction triangle* test_tetra(point A, point B, point C, point D, double f(point)), qui à partir d'un d'un tétraère extrait zero, un ou deux triangles dont les sommets vérifie f(M) = 0. Le prototype n'est donné qu'à titre indicatif. Vous pouvez faire un tableau pour stocker les sommets par exemple. Il faut orienter les triangles pour que la normale donnée par l'orientation choisie pointe vers les valeurs positives de la fonction f (-1)

• Traitement d'un cube (2+1) : faire une fonction similaire pour un cube en découpant en 6 tétraèdres comme indiqué en cours.

• Marching-cube complet (2+2) : faire un algorithme de marching-cube divisant un cube en N³ petits cubes.

• Optionnel, affichage progressif (3+2) : proposer un affichage pendant le calcul, des interruptions du calcul, zoom, affichage des coordonnées, enfin tout ce que l'on peut vouloir pour débogger. Cette question est là surtout pour donner des points à ceux qui feraient cela par nécessité.

Partie 2, pour ceux qui codent en C (indépendante de la partie 1)

• Pb d'orientation (2+1) : Le code fourni pour la structure avec demi-arête ne peut être utilisé que si la surface est orientable. Donc, pas pour un ruban de Moëbus. Une assertion échoue dans la fonction create_triangle fournie dans ce cas. Pour remédier à cela, il suffit de créer une nouvelle arête lorsque l'arête existe mais n'est "libre", c'est à dire que le pointeur e->next qui devrait être nul ne l'est pas.

• Fuite de mémoire (2+1) : Une arête déjà utilisée par deux triangles de resservira pas : on peut l'éliminer du kd_tree (sans retirer aucun sommet).

• Itération (2+1) : Écrire des fonctions d'itérations similaires à iter_triangle pour les arêtes et les sommets. Si la partie 1 a été faite, tester en calculant pour certaines surfaces F - A + S où F est le nombre de faces (ici des triangles), A le nombre d'arête et S le nombre de sommets. Pour une sphère on doit trouver 2, pour un tore (bouée), on doit trouver 0.

Partie 2, pour ceux qui codent en Java ou autres

• Bonus (?) à partager (par forcéments à parts égales) entre ceux ayant fait le code java initial, disponible au début du TP et qui remplace le code C fourni.

• (4+3) Marche progressive : partir d'un petit cube rencontrant la surface et parcourir la surface au lieu de diviser un grand cube (c'est le vrai marching-cube.

• (2+0) Comment trouver un petit cube rencontrant la surface ... Par recherche aléatoire, d'autres méthodes sont possibles ...

Corrigé

Ce corrigé couvre toutes les questions pour le C ... Sauf la première de la partie 2, qui présente le défaut d'empêcher la détection des bugs d'orientation des triangles.

Deux versions: avec le GC de Böehm et une avec un micro GC que j'ai écrit.

Représentation des objets

Nombres

• Nombres entiers (pb de taille)
• Nombres flottants (plus précisément virgule flottante) (pb de précision) norme IEEE 754
• Nombres à virgule fixe : peu utilisés/disponibles, mais pratique si l'on connait l'ordre de grandeur des nombres. Revient à utiliser des entiers avec une unité bien choisie.

Points

• Tableaux (ou liste)
• Coordonnées cartésiennes :

 * $(x,y)\in \mathbb {R} ^{2}$ dans le plan
 * $(x,y,z)\in \mathbb {R} ^{3}$ dans l'espace
 * Généralisation dans $\mathbb {R^{n}}$

Distinction entre points et vecteurs (direction). Opération sur les vecteurs : addition, multiplication, produits (par un scalaire, scalaire et vectoriel, déterminant), norme.

• Coordonnées projectives :

Idée : ajouter les points à l'infini. Intérêt : simplifie beaucoup de choses (transformation affine, projection, classification des quadriques, ...). Inconvéniant : certaines choses n'ont plus de sens (addition des vecteurs, ...)

 * $(x:y:t)\in \mathbb {P} ^{2}$ dans le plan projectif si $(x,y,t)\neq (0,0,0)$. De plus si $a\neq 0$, $(x:y:t)=(ax:ay:at)$
 * $(x:y:z:t)\in \mathbb {P} ^{3}$ dans l'espace projectif
 * Généralisation dans $\mathbb {P} ^{n}$

Comparaison avec les coordonnées cartésiennes : $(x:y:z:0)$ est le point à l'infini dans la direction (x,y,z) ou (-x:-y:-z). Parfois utile de distinguer $(x:y:z:0)$ de $(-x:-y:-z:0)$. $(x:y:z:t)$ représente le point $(x/t,y/t,z/t)$ si $t\neq 0$. Donc le point de coordonnées cartésiennes $(x,y,z)$ à les coordonnées projectives $(ax:ay:az:a)$ pour tout $a\neq 0$.

• On essaye de ne calculer qu'une fois les coordonnées de chaque point, pour éviter les erreurs d'arrondis (deux fois le même point avec des

coordonnées légèrement différente).

Courbes

• Courbe affine par morceaux : liste ou tableaux de points. Utilisation d'une indirection.
• Courbe paramétrée (droite, cercle).
• Discrétisation à vitesse constante :

 $\delta _{x}={\sqrt {x'^{2}+y'^{2}}}.\delta _{t}\Rightarrow \delta _{t}={\frac {\delta _{x}}{\sqrt {x'^{2}+y'^{2}}}}$

• Discrétisation utilisant la courbure :

 $\delta _{x}=\alpha {\frac {x'y''-x''y'}{(x'^{2}+y'^{2})^{\frac {3}{2}}}}\Rightarrow \delta _{t}=\alpha {\frac {x'y''-x''y'}{(x'^{2}+y'^{2})^{2}}}$

• Courbe de Bézier.

Surfaces

• Liste de triangles
• Liste de Quadrilatères et polygones (attention plan)
• Représentation avancée par demi-arrêtes (code à venir)
• Surfaces implicites (définition, rôle du gradient). Combinaison (max, min, produit, somme).

algorithme du marching-cube.

• Surfaces paramétrées

Triangulation de surfaces implicites Algorithme du marching-cube

• Idée générale
• Découpage du cube en tétrahèdre
• Algorithme

Traitement des triangulations

• Permutation des arrêtes
• Changement de résolution

Utilisation d'OpenGl

• Aperçu du code du TD2 / TP

Bases mathématiques (vues au fur et à mesure)

Coordonnées cartésiennes dans le plan et l'espace

• $(x,y)\in \mathbb {R} ^{2}$ dans le plan
• $(x,y,z)\in \mathbb {R} ^{3}$ dans l'espace
• Généralisation dans $\mathbb {R^{n}}$

Distinction en point et vecteur (direction).

Problèmes de représentation en machine : virgule flottante, virgule fixe, entier ... Tableau ou enregistrement (record).

Opérations sur les vecteurs : sommes, multiplication par un scalaire, produit scalaire et produit vectoriel.

Coordonnées projectives dans le plan et l'espace

Idée : ajouté les points à l'infini. Intérêt : simplifie beaucoup de choses (transformation affine, projection, classification des quadriques, ...)

• $(x:y:t)\in \mathbb {P} ^{2}$ dans le plan projectif si $(x,y,t)\neq (0,0,0)$. De plus si $a\neq 0$, $(x:y:t)=(ax:ay:at)$
• $(x:y:z:t)\in \mathbb {P} ^{3}$ dans l'espace projectif
• Généralisation dans $\mathbb {P} ^{n}$

Comparaison avec les coordonnées cartésiennes : $(x:y:z:0)$ est le point à l'infini dans la direction (x,y,z) ou (-x:-y:-z). Parfois utile de distinguer $(x:y:z:0)$ de $(-x:-y:-z:0)$. $(x:y:z:t)$ représente le point $(x/t,y/t,z/t)$ si $t\neq 0$. Donc le point de coordonnées cartésiennes $(x,y,z)$ à les coordonnées projectives $(ax:ay:az:a)$ pour tout $a$.

Opération sur les vecteurs : attention à la somme !

Équation d'un plan et d'une droite

Donnée d'une droite du plan par un point $(x_{0},y_{0})$ et une direction $(u,v)$. $(-v,u)$ est alors une direction orthgonale (on dit normale à la droite). Équation implicite en cartésien : $\langle (x-x_{0},y-y_{0})\mid (-b,a)\rangle =0$. C'est à dire: $-vx+uy+vx_{0}-uy_{0}=0$. En projectif: $ax+by+ct=0$ (l'équation est homogène).

Donnée d'un plan de l'espace par un point $(x_{0},y_{0},z_{0})$ et une direction normale $(a,b,c)$. Équation implicite en cartésien : $\langle (x-x_{0},y-y_{0},z-z_{0})\mid (a,b,c)\rangle =0$. C'est à dire: $ax+by+cz-ax_{0}-by_{0}-cz_{0}=0$. En projectif: $ax+by+cz+dt=0$ (l'équation est homogène).

Donnée d'une droite de l'espace par un point $(x_{0},y_{0},z_{0})$ et une direction $(u,v,w)$. ...