L'infographie 2D désigne l'ensemble des techniques et méthodes qui permettent de créer, manipuler et représenter des images dans un espace à deux dimensions, et plus spécifiquement à l'aide des ordinateurs. Elle englobe la conception de formes géométriques, la gestion des couleurs, des textures, des ombrages, ainsi que l’animation d’éléments visuels sur un plan fixe. Elle est utilisée en design graphique, dans les jeux vidéo, les interfaces utilisateur ou encore l’illustration. L’infographie 2D repose sur des formats matriciels (bitmap) ou vectoriels selon les besoins de précision et de mise à l’échelle.
Ses fondements mathématiques reposent sur des objets géométriques élémentaires, indispensables à la modélisation et à la manipulation des scènes visuelles. Le point constitue l’unité de base, il est généralement défini par ses coordonnées dans un repère du plan. Le vecteur permet de coder des translations, des orientations, des vitesses, etc. Les droites et segments sont utilisés pour structurer les formes, définir des contours ou tracer des trajectoires. Les courbes, qu’elles soient polynomiales (comme les courbes de Bézier) ou paramétriques, offrent une représentation plus souple des formes complexes. À ces éléments s’ajoutent les transformations géométriques fondamentales (translation, rotation, homothétie, symétrie). Elles sont principalement réalisées grâce au calcul matriciel.
Cet enseignement de volume très limité n'a d'autre ambition que de constituer un socle rudimentaire pour l'étude plus avant des algorithmes de l'infographie. Il est constitué de trois parties :
La représentation d'images sur un écran s'appuie sur l'arsenal géométrique développé durant des millénaires, mais pose des problèmes spécifiques à ce périphérique de sortie, c'est précisément ce qui nous occupe ici. Le tracé d'une droite ou d'un cercle, qui peuvent être considérés comme deux outils atomiques pour composer des images à l'écran, constituent les premiers exemples de ces enjeux algorithmiques.
Les courbes et les surfaces dites de Bézier ont été développées par P. Bézier dans les années 70 pour la création d'éléments de surface chez Renault pour tracer la peau des véhicules, c'est-à-dire la carrosserie. Le principe est relativement simple, on se donne un ensemble de n + 1 points du plan appelées points de contrôle et on cherche à construire une courbe plane inscrite dans l'enveloppe convexe de ces n + 1 points. Pour cela, on introduit le polynômes de Bernstein et on pondère les points de contrôle avec les valeurs des fonctions polynomiales associés. Une courbe de Bézier est alors un ensemble de barycentres. Les courbes \(B\)-splines reprennent le même principe avec beaucoup plus de souplesse.
Je n'ai pas eu le temps de transposer le polycopié en version dynamique, il faudra donc s'en contenter. Les sujets de travaux dirigés et de travaux pratiques sont inclus dans ce document.
Merci de m'indiquer les inévitables inexactitudes, coquilles et probables erreurs qui émaillent ce document.
É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:
\begin{align*} X &:= L \frac{x-x_{\min}}{x_{\max}-x_{\min}}\\ X &:= H \frac{y_{\max} - y}{y_{\max}-y_{\min}} \end{align*}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
\begin{equation} P(X):=a_0+a_1X+\cdots+a_kX^k. \end{equation}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 :
\begin{equation} P(X)=\Big(\big(\ldots(a_k)X + a_{k-1})X + a_{k-2})X + \cdots + a_2\big)X+a_1\Big)X+a_0 \end{equation}L'algorithme de Hörner est implanté 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)
Écrivez 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 xA yA xB yB
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:
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|.
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|.
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
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 M0 = (x0, y0), M1 = (x1, y1), . . ., Mn = (xn, yn) sur la ligne de commande:
bezier p SX SY x0 y0 x1 y1 ... xn yn
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) = Bn,0(u). M0 + Bn,1(u). M1 + Bn,2(u). M2 + . . . + Bn,n(u). Mn
où Bn,p(T) est le pème polynôme de Bernstein d'ordre n:
Bn,p(T) := C(n, p) T p(1 - T)n - pDans un deuxième temps, intégrer ce travail dans un programme plus général qui permet de fixer les points de contrôle en cliquant à la souris dans une fenêtre graphique et qui permette également de déplacer ces points de contrôle en réaffichant la courbe au fur et à mesure des modifications. Modifier le programme pour utiliser la méthode dynamique à l'aide des barycentres successifs.
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
cp votreprojet /home/profs/zanotti/projetsU521
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).
On note \((M_i)_{\in\ab{0}{n}}\) le nuage de points dont on veut calculer l'enveloppe convexe. L'algorithme décrit informellement est le suivant :
L'algorithme complet est donné ici :
ALGORITHME Convexe(M,n):Liste;
DONNEES
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 ← ∅ // initialisation de la pile P
Empiler(M[0], P); // empilement des 3 premiers points
Empiler(M[1], P);
Empiler(M[2], P);
POUR i ∈ [3:n] FAIRE
TQ (⟨under(P), top(P)⟩ > 0) FAIRE
Depiler(P) // point strictement dans l'enveloppe
FTQ
Empiler(M[i], P); // point de l'enveloppe à conserver
FPOUR
RENVOYER P;
FIN