Le cours

Les documents

Travaux pratiques

Transformation d'un nuage de points d'une fenêtre d'observation vers l'espace écran.
écrivez un programme convert qui convertit une séquence de points du plan euclidien en une séquence de points de la fenêtre écran.  Les paramètres de la ligne de commande sont au nombre de 7:

% xmin xmax ymin ymax H L fichier

Les 4 premiers paramètres sont les coordonnées des deux points A et B (respectivement coin inférieur gauche et supérieur droit) qui définissent la fenêtre d'observation dans le plan euclidien, les deux paramètres suivants sont la hauteur et la largeur de la fenêtre écran et le dernier est le nom du fichier qui contient les points à afficher. Ces points sont stockés sous forme de couples de type double (un couple par ligne du fichier) et les termes du couple sont simplement séparés par un espace. Le programme doit donc boucler sur l'ensemble des points du fichier (si le nom du fichier est absent, le fichier est l'entrée standard pour permettre de cascader les commandes avec le pipe |). Utilisez la transformation calculée en TD à partir de la matrice dans l'espace projectif, si (x, y) désigne l'un des couples du fichier d'entrée, les coordonnées (X, Y) de son image dans l'espace écran sont données par:

X = L(x - x_min) / (x_max - x_min)
Y = H(y_maxy) / (y_max - y_min)

Pour tester votre transformation, vous écrirez un second programme poly qui renvoie sur la sortie standard une séquence de points du plan formatés de la même façon que pour le fichier d'entrée du programme convert. Ces points seront définis par une courbe polynomiale dont les coefficients seront passés en paramètres. Plus précisément, si le polynôme est donné par l'expression

P(X) := a₀ + a₁X + . . . + a_kX^k

Il y aura k + 4 paramètres sur la ligne de commande:

% xmin xmax nbpoints a0 a1 ...

Les 2 premiers paramètres xmin et xmax définissent l'intervalle sur lequel on veut évaluer la fonction polynomiale, nbpoints désigne le nombre de couples qu'il faudra calculer et les termes suivants correspondent aux coefficients du polynôme considéré. L'échantillonnage de l'intervalle sera uniforme. Pour évaluer une fonction polynomiale, on utilisera la factorisation de Hörner qui permettra d'écrire un algorithme de complexité linéaire:

P(X) = a₀ + X(a₁ + X(a₂ + X(a₃ + . . . (a_{k - 1} + X a_k)))

La méthode de Hörner est implantée en langage C de la manière suivante:

double eval_poly(double *P, double x, unsigned char k){
    unsigned char i = 0;
    double y = 0;
    for (i = 0; i <= k; i++)
         y = x * y + P[k - i];
    return y;

Pour afficher la courbe, vous utiliserez la bibliothèque cng. Les chemins sont :

/usr/local/lib/libcng.a (bibliothèque)
/usr/local/include/cng.h (headers)
/usr/local/src/CNG_v0.2 (Makefile et exemples)

Tracé d'un segment de droite à l'aide de l'algorithme de Bresenham.
Ecrivez un programme bresenham en langage C qui trace le segment [A,B] à l'aide de l'algorithme de Bresenham dans une fenêtre écran dimensionnée automatiquement à partir des coordonnées entières (x_A,y_A) et (x_B,y_B) des points A et B. Les paramètres de la ligne de commande seront

%bresenham x_A y_A x_B y_B

Modifiez votre programme pour faire de l'antialiasing. On note B (resp. T) le pixel en-dessous du pixel L (resp. au dessus du pixel H). On considère la droite orientée (LH). Trois cas se présentent:

1. la droite (AB) passe entre les centres des pixels L et H et les distances algébriques HI et LI satisfont HI < 0 et LI > 0; On allume L et H avec pour intensités respectives |HI| et 1 - |HI|.

2. la droite (AB) passe au-dessus du centre du pixel H et les distances algébriques HI et LI satisfont HI > 0 et LI > 0; On allume H et T avec pour intensités respectives 1 - |HI| et |HI|.

3. la droite (AB) passe en-dessous du centre du pixel Let les distances algébriques HI et LI satisfont HI < 0 et LI < 0.On allume L et H avec pour intensités respectives 1 - |LI| et |LI|.

Pour tracer les segments qui ne sont pas dans le premier octant, calculez les 7 symétries qui permettent de ramener la situation au bon octant.

PS. On définit la luminance Y d'un pixel à partir de son codage RVB par la pondération suivante correspondant à la sensibilité de l'œil aux trois couleurs primaires:  Y = 0.30 R + 0.59V + 0.11 B

Tracé d'une courbe de Bézier.
L'objectif est d'écrire un programme qui trace des courbes de Bézier. Le programme récupère le nombre p de points à tracer dans la fenêtre écran, la dimension horizontale SX et verticale SY de la fenêtre écran ainsi que les n + 1 points de contrôle M₀ = (x₀, y₀), M₁ = (x₁, y₁), . . ., M_n = (x_n, y_n) sur la ligne de commande:

% bezier p SX SY x₀ y₀ x₁ y₁ ... x_n y_n

Pour réaliser le tracé, vous utiliserez la méthode directe, i.e. celle qui consiste à manipuler les polynômes de Bernstein et à les évaluer avec la factorisation de Hörner. On rappelle que le point générique de la courbe de Bézier M(u), u ∈ [0, 1] est défini par la fonction polynomiale

M(u) = B_n,0(u). M₀ + B_n,1(u). M₁ + B_n,2(u). M₂ + . . . + B_n,n(u). M_n

où B_n,p(T) est le pème polynôme de Bernstein d'ordre n:

B_n,p(T) := C(n, p) T ^p(1 - T)^{n - p}

Projet

L'objectif du projet est de développer une (petite) application pour traiter des images 2D avec la bibliothèque cng. Le principe général consiste à ouvrir une fenêtre graphique 800x600 par exemple, et garder une bande horizontale ou verticale pour contenir les outils dans la liste ci-dessous.

Pour m'éviter de chercher les infos, le projet devra impérativement être placé dans le répertoire

Le fichier exécutable s'appelera pix2D, le répertoire devra inclure un fichier LisezMoi qui contiendra toutes les informations nécessaires à l'utilisation de votre programme. Vos programmes doivent être commentés. Il faudra également inclure les fichiers TestBresenham et TestMichener qui contiendront l'étude pratique de la complexité de ces algorithmes comparativement aux tracés empiriques (utilisez le profiler gprof et tracez les courbes de complexité avec Gnuplot ou avec votre propre logiciel).

Liste des outils à implanter

1. Table des couleurs: permet de sélectionner la couleur du tracé et du remplissage s'il y a lieu (il faut conserver la possibilité de ne pas remplir).
   
2. Tracé de lignes brisées avec l'algorithme de Brensenham antialiasé: à chaque clic de souris, on trace le segment entre le dernier point et le nouveau.
3. Tracé de cercles avec l'algorithme de Michener antialiasé: le premier clic correspond au centre du cercle, le second au rayon. Eventuellement, proposer une couleur de remplissage.
4. Tracé de parallélogrammes: utiliser bresenham sur les 4 segments.
   
5. Tracé de polygones convexes avec l'algorithme de détection de l'enveloppe polygonale convexe: Chaque clic de souris définit un sommet du polygone. Une fois tous les sommets validés, on détermine l'enveloppe polygonale avec l'algo vu en cours.
6. Tracé de courbes de Bézier avec la méthode des polynômes de Bernstein et la méthode itérative
7. Tracé de courbes de Bézier quadratiques passant par les points de contrôles (noeuds de jonction)
8. Tracé de courbes B-splines uniformes (le vecteur noeud u_0,u₁,...,u_n+m+1est tel que |u_i+1-u_i|= cte).
9. Coloriage d'une zone avec le pot de peinture: implanter l'algorithme récursif et colorier les pixels à une distance inférieure à un seuil fixé par l'utilisateur. Faites différents essais de distance dans l'espace RVB.
10. Remplissage d'un polygone convexe: utiliser l'algorithme avec les listes.
11. Pour les plus courageux: implanter la lecture et l'écriture des images dans des fichiers au format gif ou jpeg. Pour info: en jpeg, il y a une simple transformée en cosinus discret (c'est la transformée de Fourier simplifiée  sur R) et un codage de Huffman déjà traité et programmé en cours d'algorithmique de licence.

Algorithme de calcul de l'enveloppe convexe d'un ensemble de n + 1 points
On note (M_i)_{i ∈ [0,n]} les points dont on veut calculer l'enveloppe convexe.

1. On réindexe les points: M₀ est le point qui a la plus petite abscisse parmi les points qui ont la plus petite ordonnée.
2. Les points suivants M₁, M₂, ..., M_n sont choisis de manière à ce que la suite des angles formé par la demi-droite horizontale positive [M₀x) issue de M₀ et le segment [M₀M_i] pour i ∈ [1,n] soit croissante. Si plusieurs points donnent le même angle, on ne conserve que celui qui est le plus éloigné de M₀, les autres sont éliminés.
3. On crée une pile P sur laquelle on empile successivement les trois premiers points M₀, M₁ et M₂.
On définit deux fonctions top(P) et under(P) qui renvoient respectivement le point au sommet de la pile P et celui juste en dessous (sans la modifier). On note ⟨ABC⟩ l'angle formé par les segments [BA] et [BC] (angle positif s'il suit le sens trigonométrique, négatif sinon).
4. On termine:

   Pour i ∈ [3,n] Faire
       TantQue ⟨under(P),top(P),M_i⟩ > 0 Faire
           Depiler(P)
       FTantQue
       Empiler(M_i,P)
   FPour

La pile P contient alors l'enveloppe convexe des points dans le sens trigonométrique.

algorithme CONVEXE(M,n):Liste;
données
   n: entier;     
   M[0,n]: tableau de n + 1 points;
variables
   P: liste de points du plan;
   i: entier; 
debut
   M[0] ← PPO(M)  // PPO cherche le point de plus petite ordonnee
   Ordonner(M)  // cf. explications.
   P ← ∅  // on initialise la pile P
   empiler(M[0],P);  // on y empile les trois premiers points
   empiler(M[1],P);
   empiler(M[2],P);
   POUR i ∈ [3:n] FAIRE  
      TQ (angle(under(P),top(P)) > 0) FAIRE
         depiler(P)
      FTQ 
      empiler(M[i],P);
   FPOUR
   retourner P;
fin.

Sujets d'examen

1. 2010-2011. Session 1 et Session 2
2. 2005-2006. Session 1
3. 2003-2004. Session 1 et Session 2
4. 2002-2003. Session 1 et Session 2
5. 2001-2002. Session 1 et Session 2
6. 2000-2001. Session 1 et Session 2
7. 1999-2000. Session 1 et Session 2
8. 1998-1999. Session 1 et Session 2
9. 1997-1998. Session 1 et Session 2