Infographie et Image Informatique Infographie 2D PDF

livre-scratch.pdf

Avec Scratch la programmation devient un jeu et votre ordinateur un compagnon. À la découverte des algorithmes. Un algorithme est une suite d'instructions

Infographie et Image Informatique Infographie 2D

Le but de l'algorithme de Bresenham est de tracer un segment de droite en l'algorithme et on regarde si la distance entre le centre du cercle et le ...

Algorithmique & programmation en langage C - vol.2 - Archive

Jul 14 2015 concerné (par exemple INF202 pour le cours d'algorithmique et ... l'exercice 2

Mathématiques

Le programme n'est pas un plan de cours et ne contient pas de préconisations pédagogiques 13 créer « à la main » l'algorithme du max est un bon exercice ...

Python au lycée - tome 2

découvrir de nouveaux algorithmes pour trier pour calculer en parallèle

Méthodes robustes en traitement dimage pour la détection et la

et les problèmes qui en découlent l'analyse d'images via des algorithmes de cercle détecté et en particulier

Infographie et Image Informatique Infographie 2D

Le but de l'algorithme de Bresenham est de tracer un segment de droite en l'algorithme et on regarde si la distance entre le centre du cercle et le ...

Cours Fouille de données avancée

1.5 Exercices . 3.5.3 Algorithmes de construction d'arbres de décision . ... Donner des exemples d'application de data mining non vus dans le cours (de ...

Modélisation dobjets 3D par construction incrémentale dun

Jun 17 2005 2.21 L'algorithme d'appariement basé sur des espaces de clusters et des ... `a la vérité terrain au cours des itérations pour les objets.

Infographie et Image Informatique

Gérard-Michel

COCHARD

cochard@u-picardie.fr

Sébastien CHOPLIN

sebastien.choplin@u- picardie.fr

Infographie 2D

Traitements graphiques élémentaires

Tracé d'un segment

Tracé d'un arc de cercle

Fenêtrage

Remplissage et coloriage

Transformations géométriques en 2D

Coordonnées homogènes

Translation

Rotation autour de l'origine

Dilatation

Symétrie

Composition des transformations

Représentation des objets

Courbes paramétriques 2D

Utilisation de courbes cubiques

Courbes d'Hermite

Courbes de Bézier

Courbes B-Splines

Prérequis

l notions basiques d'algèbre linéaire (représentation de systè mes d'équations à l'aide des matrices, produits de matrices). l trigonométrie de niveau 3

ème

Traitements graphiques élémentaires

Tracé d'un segment

Un écran d'ordinateur étant un plan 2D à coordonnées discrè tes (les points ont leurs coordonnées dans un espace fini), il est impossible de tracer un segment de droite de ma nière exacte. Il faut donc trouver une représentation qui soit visuellement la plus proche possible d'un vrai segment de droite. Voici plusieurs possibilités : Parmi toutes ces possibilités, celle qui minimise l'écart avec le vrai segment est obtenue avec l'algorithme de Bresenham défini ci-dessous :

L'algorithme de Bresenham (1965)

Traduction et remaniement de

Le but de l'algorithme de Bresenham est de tracer un segment de droite e n utilisant uniquement les points d'une grille discrète comme dans la figure ci-dessous: Pour ce faire 8 cas sont distingués, suivant la pente de la droite et le sens dans lequel le segment est dessiné. Ces 8 cas divise le plan euclidien en 8 zone appelées octants

L'octant 1

Considérez le tracer d'une droite de pente

m avec

0<=m<=1

sur une grille entre les points (x1,y1) et (x2,y2) tels que x1Après avoir dessinéle point (x,y) , l'algorithme doit faire un compromis entre ce que l'on veut dessiner et ce que la résolution de la grille permet réellement de dessiner . Habituellement le point (x,y) est déjàune erreur, le point réel sur la droite n'étant pas acce ssible sur la grille. Ainsi nous associons une

erreur d'ordonnée eàpour chaque abscisse xcar l'ordonnée réelle devrait être y+e. Cette erreur se

trouvera dans l'intervalle [-0.5,+0.5[.

En passant de

x x+1 , on augmente la valeur de l'ordonnée (mathématique) d'une quant itéégale àla pente de la droite: m . Nous choisirons donc de tracer (x+1,y) si la différence entre cette nouvelle ordonnée et y est inférieure à0,5, c'est àdire si: y+ e +m < y+0.5

Autrement nous tracerons

(x+1,y+1) . En faisant ainsi nous réduisons au minimum l'erreur globale entre le segment de droite mathématique et le tracéde ce segment. L'erreur résultant de ce nouveau point peut maintenant être consid

érécomme le nouvel

e , ceci nous permettra de répéter pour le prochain point sur la droite, celui p our lequel l'abscisse est x+2 La nouvelle valeur de l'erreur peut adopter une de deux valeurs possible s, selon le choix du point tracé. Si (x+1,y) est choisi, la nouvelle valeur de l'erreur est donnée par: e (y+ e +m)-y

Autrement elle est:

e (y+ e +m)-(y+1)

On obtient ainsi l'algorithme suivant:

e 0; y y1 x x1

TantQue

x x2 faire dessiner (x,y) Si ( e m < 0.5 ) alors e e m Sinon y y+1 e e m -1 FinSi x x+1

FinTantQue

Amélioration de l'algorithme pour l'octant 1

Cet algorithme utilise des variables à virgule flottante. Pour évi ter cela (les tests en nombre entiers

étant plus efficaces), en posant

D x x2-x1 D y y2-y1 sachant que m= D y/ D x , on manipule quelque peu l'expression du test en multipliant par 2 et p ar D x pour obtenir: 2 eD x +2 D y D x Toutes les quantités de cette inégalité sont maintenant entiè res.

En posant

e eD x , le test devient: 2( e D y D x Les règles de mise à jour pour l'erreur sur chaque étape peuven t également être adaptées à e e ¬ e + mÛe' ¬ e' + Dy e e m -1

Ûe' ¬ e' + Dy - Dx

L'algorithme avec le test n'utilisant que des nombres entiers est donc: D x x2-x1 D y y2-y1 e 0; y y1 x x1

TantQue

x x2 faire dessiner (x,y)

Si ( 2(

e D y D x ) alors e e D y Sinon y y+1 e e D y D x FinSi x x+1

FinTantQue

Remarques sur l'amélioration de l'algorithme:

n Test en nombre entier seulement, par conséquent plus efficace. n La multiplication par 2 peut être implementée par décalage à gauche. n Cette version est limitée aux pentes dans le premier octant. Voici une implémentation en C++ de l'algorithme de Bresenham pour des segments de droite dans le premier octant: void octant1(Screen &s, unsigned x1, unsigned y1, unsigned x2, unsigned y2, unsigned char colour ) int dx = x2 - x1, dy = y2 - y1, y = y1, eps = 0; for ( int x = x1; x <= x2; x++ ) s.Plot(x,y,colour); eps += dy; if ( (eps << 1) >= dx ) y++; eps -= dx; Cette fonction n'utilise que des nombres entiers positifs, utilise le dé calage à gauche pour la multiplication et élimine des opérations superflues par l'utilisat ion rusée du eps variable. Cette implémentation est inachevée, elle ne vérifie pas que les paramètres correspondent bien au tracage d'un segment de droite dans le premier octant.

Tracé d'un arc de cercle

Par extension de l'algorithme de Bresenham, l'algorithme de Michener répond au problème :

le principe est le même: allumer les pixels qui sont le plus proches du cercle, l'algorithme dépendant

également de la position dans l'octant. Par exemple dans l'octant 1 (ici cela veut dire qu'on va vers le

haut, vers la gauche et la pente de la tangeant étant entre -1 et 0), on diminue x à chaque pas de

l'algorithme et on regarde si la distance entre le centre du cercle et le point (x-1,y) est inférieure à la

distance entre le centre du cercle et (x-1,y+1) (auquel cas on allumera le point (x-1,y) ) algorithme de Michener pour l'octant 1 et pour un cercle de centre (0,0) et de rayon R début // Initialisation x = R ; y = 0 ;

TantQue x>= y faire

Dessiner(x,y)

y = y + 1 ; d1 = |R*R-(x*x+y*y)| ; d2 = |R*R-((x-1)*(x-1)+y*y)| ;

Si d1 > d2 alors

x = x - 1 ; FinSi

FinTantQue

fin

Fenêtrage

Il est commode de distinguer deux types d'espace : l'espace utilisateur qui représente le plan de travail

de ce dernier et qui est indépendant du système de visualisation; l'espace écran qui est évidemment

dépendant du système de visualisation. Entre les deux espaces, une correspondance est établie entre un

rectangle de l'espace utilisateur, appelé fenêtre, et une rectangle de l'espace écran, appelé clôture . Si

fenêtre et clôture ne sont pas homothétiques, on obtient alors un effet de distorsion; si la clôture est

fixe et si la fenêtre est réduite, on a un effet de zoom.

La correspondance entre l'espace utilisateur et l'espace écran implique l'élimination de ce qui est

extérieur à la fenêtre : clipping. Pour sensibiliser au sujet, prenons l'exemple très simple d'un segment

de droite; il peut être soit totalement intérieur à la fenêtre, soit totalement extérieur à la fenêtre, soit

coupant un bord de la fenêtre. Pour distinguer entre les trois cas, une première idée serait de comparer

les coordonnées de chaque point du segment de l'écran avec les coordonnées des sommets de la

clôture; le calcul serait évidemment beaucoup trop long. L'algorithme de Sutherland permet une

meilleure optimisation; l'espace écran est divisé en 9 zones numérotées avec 4 bits, la clôture servant

de base à ce découpage et numérotée 0000. La figure ci-contre montre plusieurs situations où lesquotesdbs_dbs45.pdfusesText_45

[PDF] Infographie et Image Informatique Infographie 2D

Infographie et Image Informatique

Gérard-Michel

COCHARD

Sébastien CHOPLIN

Infographie 2D

Traitements graphiques élémentaires

Tracé d'un segment

Tracé d'un arc de cercle

Fenêtrage

Remplissage et coloriage

Transformations géométriques en 2D

Coordonnées homogènes

Translation

Rotation autour de l'origine

Dilatation

Symétrie

Composition des transformations

Représentation des objets

Courbes paramétriques 2D

Utilisation de courbes cubiques

Courbes d'Hermite

Courbes de Bézier

Courbes B-Splines

Prérequis

ème

Traitements graphiques élémentaires

Tracé d'un segment

L'algorithme de Bresenham (1965)

Traduction et remaniement de

L'octant 1

Considérez le tracer d'une droite de pente

0<=m<=1

En passant de

Autrement nous tracerons

érécomme le nouvel

Autrement elle est:

On obtient ainsi l'algorithme suivant:

TantQue

FinTantQue

Amélioration de l'algorithme pour l'octant 1

étant plus efficaces), en posant

En posant

Ûe' ¬ e' + Dy - Dx

TantQue

Si ( 2(

FinTantQue

Remarques sur l'amélioration de l'algorithme:

Tracé d'un arc de cercle

TantQue x>= y faire

Dessiner(x,y)

Si d1 > d2 alors

FinTantQue

Fenêtrage