Pixels

Vidéo ■ partie 9.1. Pixels

Vidéo ■ partie 9.2. Tracé d'un segment - Algorithme de Bresenham
Vidéo ■ partie 9.3. Anticrénelage
Vidéo ■ partie 9.4. Tracé d'un cercle
Vidéo ■ partie 9.5. Colorier
Vidéo ■ partie 9.6. Animation 2D
Comment tracer, pixel par pixel, les figures géométriques de base ?

1. Pixels

1.1. L’unité d’affichage

Le pixel est l’unité élémentaire d’affichage graphique numérique. Son abréviation est « px ». Le plus souvent
le pixel est assimilé à un carré (ce sera le cas dans ce cours), mais peut aussi parfois être un rectangle.

Un pixel peut être noir ou blanc, mais aussi en couleur (le plus souvent obtenue par l’addition des couleurs
de trois sous-pixels : un rouge, un vert, un bleu). La taille d’un pixel est généralement inférieure à 1 mm,
elle dépend du type d’écran. Plus la taille d’un pixel est petite, plus la résolution est bonne. Une autre unité
de mesure de la résolution est le nombre de pixels par pouce, abrégé par « ppp » (ou ppi pour pixels per
inch). Comme son nom l’indique, il s’agit de compter combien de pixels on peut juxtaposer sur une longueur
d’un pouce (1 pouce = 25,4 mm). L’équivalent dans le monde de l’impression est le dpi (dots per inch).
Voici quelques exemples approximatifs :

Type d’écran Taille du pixel (mm) Résolution (ppp)

Télévision 0.5 50
Ordinateur portable 0.17 150
Téléphone 0.05 500

1 2π
L’œil humain a une acuité d’environ 1 minute d’arc (c’est-à-dire 1/60 de degré, soit θ = 60 360 ≃ 0.00029
radian). Ainsi à une distance d, l’œil distingue des pixels d’une taille ℓ ≃ dθ (avec ℓ et d en mètre et θ en
radian).
PIXELS 2

d θ

Ainsi en regardant un écran à 20 cm de distance, augmenter la résolution au-delà de 400 ppp ne permet de
ressentir une amélioration. Il faut alors mieux concentrer ses efforts sur la qualité de l’image (vitesse de
rafraîchissement, couleurs, rayonnements. . .) et sur l’énergie (consommation, encre électronique. . .).

Un pixel n’est pas vraiment un petit carré ! Dans ce cours nous assimilerons un pixel à un (petit) carré.
Cependant la réalité est plus compliquée. Un écran est composé d’une grille de sources lumineuses, appelées
des sous-pixels. Chaque source illumine une petite zone qui n’est pas nécessairement un carré (cela peut
être un disque ou un rectangle). Chaque source est souvent d’une seule couleur parmi rouge/vert/bleu,
mais son intensité peut varier. Il n’y a donc physiquement aucun carré dans ce processus ! Sur la photo
ci-dessous on pourrait regrouper trois sous-pixels superposés et appeler le petit carré correspondant un
pixel, en lui attribuant la couleur résultant des trois sous-pixels. Il est plus juste de dire que les pixels sont
un échantillonnage (relevé en des points d’une grille) du signal lumineux produit par l’écran.

Les sous-pixels d’un écran de téléphone portable (photo Wikimedia).

1.2. Écran
La taille d’un écran est le couple (largeur, hauteur) exprimé en pixels, habituellement notée sous la forme
largeur × hauteur. Le résultat du produit correspond au nombre total de pixels de l’écran.

hauteur

largeur

Le rapport d’image est le quotient de la largeur par la hauteur :

largeur
rapport d’image = .
hauteur
Par exemple, pour un écran de taille 1024 × 768, cela signifie que chaque ligne contient 1 024 pixels et que
chaque colonne contient 728 pixels. Le rapport d’image est
1024 4
r= = ≃ 1.33.
768 3
PIXELS 3

Nom du format largeur hauteur rapport (fraction) ratio (approché)

VGA 640 480 4/3 1.33
HD720 1280 720 16/9 1.77
HD1080 1920 1080 16/9 1.77
WUXGA 1920 1200 16/10 1.60
4K 3840 2160 16/9 1.77
8K 7680 4320 16/9 1.77
Image format Cinémascope 1024 430 2.38

Le repère des pixels sur un écran a son axe des « y » dirigé vers le bas, contrairement à l’usage en mathéma-
tiques (que l’on suivra dans cet ouvrage). Ainsi le pixel en haut à gauche a pour coordonnées (0, 0).
x
(0, 0)

2. Tracé de droites et de cercles

2.1. Tracé élémentaire d’un segment

Le but est de tracer un segment composé de pixels entre deux points P1 (x 1 , y1 ) et P2 (x 2 , y2 ). Nous supposons
que ces points ont des coordonnées entières (x 1 , y1 , x 2 , y2 ∈ Z) et qu’un pixel est un carré de côté 1 centré
en un couple d’entier (i, j).

P2 P2

P1 P1

L’idée naturelle est de calculer une équation de la droite (P1 P2 ). Une équation réduite est y = αx + β où α
est la pente et β l’ordonnée à l’origine. On va préférer écrire l’équation sous la forme :
y = α(x − x 1 ) + y1
∆y y2 − y1
où (x 1 , y1 ) est un point de la droite et la pente se calcule par α = ∆x = x 2 −x 1 .

.
P2

∆y

P1. ∆x
PIXELS 4

∆y
Hypothèse. On suppose x 1 < x 2 , y1 < y2 et α = ∆x ⩽ 1.
Autrement dit, on trace un segment ayant une pente comprise entre 0 et 1, c’est-à-dire l’angle formé entre
une horizontale et le segment est compris entre 0° et 45°. Les autres situations s’obtiennent par symétrie et
ne seront pas détaillées ici.
Les pixels à colorier ont pour abscisses successives i = x 1 , x 1 + 1, . . . , x 2 . L’ordonnée réelle correspondant à
l’abscisse i est y = α(i − x 1 ) + y1 mais nous voulons une coordonnée entière qui s’obtient par un arrondi :

j = arrondi(α(i − x 1 ) + y1 )

Remarque : si ⌊x⌋ désigne la partie entière d’un réel x (obtenue par une commande floor(x) en Python
par exemple) alors :
arrondi(x) = ⌊x + 21 ⌋
Pour minimiser les opérations on remarque que lorsque l’on passe de l’abscisse x à l’abscisse x + 1 alors
l’ordonnée passe de y à y + α.

y +α .
α

y . 1

x x +1

Algorithme (Algorithme du tracé élémentaire).

Entrée : des entiers x 1 , y1 , x 2 , y2 vérifiant l’hypothèse.
Sortie : le tracé des pixels reliant (x 1 , y1 ) à (x 2 , y2 ).
y −y
• Calculer α = x 22 −x 11 .
• Poser i = x 1 .
• Poser y = y1 .
• Tant que i ⩽ x 2 :
— j = arrondi( y)
— afficher le pixel (i, j)
— i = i+1
— y = y +α

Exemple.
On souhaite tracer le segment reliant P1 (0, 0) et P2 (8, 3). On calcule :
∆y y2 − y1 3
α= = = = 0.375.
∆x x2 − x1 8
PIXELS 5

Voici les valeurs lorsqu’on applique l’algorithme :

i y j
0 0 0
1 0.375 0
2 0.75 1
3 1.125 1
4 1.5 2
5 1.875 2
6 2.25 2
7 2.625 3
8 3.0 3
Ce qui donne :

3
P2
2

0
P1
0 1 2 3 4 5 6 7 8

Noter que les calculs se font avec des nombres réels et sont donc assez lents.

2.2. Algorithme de Bresenham

Objectif : trouver un algorithme plus rapide que l’algorithme élémentaire en ne faisant que des calculs sur
des entiers. Le résultat est équivalent à l’algorithme précédent mais beaucoup plus rapide.
Voici quelques tracés.

7
P2
6

2 2
P2
1 1

0 0
P1 P1
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9

4
P2
3

0
P1
0 1 2 3 4 5 6 7 8 9 10 11
PIXELS 6

Algorithme (Algorithme de Bresenham).

Entrée : des entiers x 1 , y1 , x 2 , y2 vérifiant l’hypothèse.
Sortie : le tracé des pixels reliant (x 1 , y1 ) à (x 2 , y2 ).
• Calculer p = 2∆ y = 2( y2 − y1 ).
• Calculer m = 2∆ y − 2∆x = 2( y2 − y1 ) − 2(x 2 − x 1 ).
• Poser d = 2∆ y − ∆x = 2( y2 − y1 ) − (x 2 − x 1 ).
• Poser i = x 1 et j = y1 .
• Tant que i ⩽ x 2 :
— afficher le pixel (i, j)
— si d < 0 :
— d =d+p
— sinon :
— j = j+1
— d =d+m
— i = i+1

Noter que p, m sont des constantes entières avec p > 0 et m < 0 ; d est le « défaut », c’est une variable qui
détermine s’il faut prendre le pixel juste à côté ou bien s’il faut monter d’un cran. Le défaut est alors mis
à jour en lui ajoutant selon le cas une valeur fixe p > 0 ou m < 0 (si d < 0, le nouveau défaut d + p a
augmenté ; si d ⩾ 0, le nouveau défaut d + m a diminué car m < 0).

+m
+p

d d

Cas d < 0. Cas d ⩾ 0.

Noter qu’en plus les opérations sur les entiers sont élémentaires : ce sont des additions et un test de positivité.

Exemple.
On souhaite tracer le segment reliant P1 (0, 0) et P2 (8, 5). On calcule :
p = 10 m = −6 d0 = 2
Voici les valeurs lorsqu’on applique l’algorithme :
nouvelle
i j d monter ?
valeur de d
0 0 2 oui −4
1 1 −4 non 6
2 1 6 oui 0
3 2 0 oui −6
4 3 −6 non 4
5 3 4 oui −2
6 4 −2 non 8
7 4 8 oui 2
8 5
PIXELS 7

5
P2
4

0
P1
0 1 2 3 4 5 6 7 8

Preuve. Justifions que l’algorithme est correct.

• Équation de la droite à coefficients entiers. Nous avons vu qu’une équation de la droite (P1 P2 ) est
∆y
y = ∆x (x − x 1 ) + y1 avec ∆x = x 2 − x 1 et ∆ y = y2 − y1 . En multipliant cette équation par l’entier ∆x
on obtient l’équation :
(∆ y)x − (∆x) y − (∆ y)x 1 + (∆x) y1 = 0
c’est-à-dire une équation a x + b y + c = 0 avec a, b, c qui sont tous les trois des entiers.
Ainsi on définit la fonction :
E(x, y) = a x + b y + c
où a = ∆ y, b = −∆x, c = −(∆ y)x 1 + (∆x) y1 . Cette fonction détermine l’écart du point (x, y) par
rapport à la droite (P1 P2 ) :
— si E(x, y) = 0, le point (x, y) appartient à la droite,
— si E(x, y) < 0, le point (x, y) est situé au-dessus de la droite,
— si E(x, y) > 0, le point (x, y) est situé en-dessous de la droite.
• Monter ou pas ? Centrons en P(x k , yk ) un pixel déjà correctement colorié. Quels choix avons-nous pour
colorier le pixel suivant ? Dans tous les cas le pixel suivant sera sur la colonne d’abscisse x k + 1. Mais
son ordonnée sera soit yk + 1 (point A), soit yk (point B).

.
A(x k + 1, yk + 1)
.
A(x k + 1, yk + 1)

.
P(x k , yk )
.
B(x k + 1, yk )
.
P(x k , yk )
.
B(x k + 1, yk )

Cas Dk < 0. Cas Dk ⩾ 0.

Nous allons utiliser notre fonction d’écart E. Noter que l’on a toujours E(A) ⩽ 0 et E(B) > 0. On choisit
entre A et B celui qui est le plus proche de la droite réelle, c’est-à-dire celui qui a le plus petit écart |E(A)|
ou |E(B)| (en valeur absolue). Pour savoir lequel choisir on définit le défaut par
D(P) = E(A) + E(B).
On retient :
Si D(P) ⩽ 0 alors on choisit B, si D(P) > 0 alors on choisit A.
En effet, si D(P) ⩽ 0 alors E(A) + E(B) ⩽ 0 donc E(B) ⩽ −E(A) mais comme E(A) ⩽ 0 et E(B) > 0 alors
on a bien |E(B)| ⩽ |E(A)|.
PIXELS 8

• Calcul du défaut. Calculons Dk le défaut au point P(x k , yk ) :

Dk = D(x k , yk ) = E(A) + E(B) = E(x k + 1, yk + 1) + E(x k + 1, yk )
= a(x k + 1) + b( yk + 1) + c + a(x k + 1) + b yk + c
= 2a x k + 2b yk + 2a + b + 2c
En particulier D0 le défaut au point initial (x 1 , y1 ) est :
D0 = 2a x 1 + 2b y1 + 2a + b + 2c
= 2(a x 1 + b y1 + c) + 2a + b (⋆)
= 2a + b
= 2∆ y − ∆x
À la ligne (⋆) on a utilisé le fait que le point initial (x 1 , y1 ) est exactement sur la droite, donc a x 1 +b y1 +c =
0.
• Formule de récurrence du défaut.
Nous allons maintenant trouver la relation qui lie le défaut d’un pixel Dk au défaut du pixel suivant
Dk+1 . On part toujours du point P(x k , yk ), on a déjà calculé Dk . Le calcul de Dk+1 dépend du choix A ou
B pour le pixel d’abscisse x k+1 .

.
A′

.
A
.
B′
.
A′

.
P
.P
.
B
.
B′

Cas A. Cas B.
Cas du choix A (cas Dk ⩾ 0). Le pixel suivant a pour abscisse x k + 2 et pour ordonnée soit yk + 2 (A′ ),
soit yk + 1 (B ′ ).

.
A′ (x k + 2, yk + 2)

. .
A(x k + 1, yk + 1) B ′ (x k + 2, yk + 1)

.
P(x k , yk )

Cas A.
Calculons alors le défaut :
Dk+1 = E(A′ ) + E(B ′ ) = E(x k + 2, yk + 2) + E(x k + 2, yk + 1)
= a(x k + 2) + b( yk + 2) + c + a(x k + 2) + b( yk + 1) + c
= 2a x k + 2b yk + 4a + 3b + 2c
= Dk + 2a + 2b
PIXELS 9

Ainsi en posant m = 2a + 2b = 2∆ y − 2∆x, on obtient la formule de récurrence :

Dk+1 = Dk + m.
Cas du choix B (cas Dk < 0). Le pixel suivant a pour abscisse x k + 2 et pour ordonnée soit yk + 1 (A′ ),
soit yk (B ′ ).

.
A′ (x k + 2, yk + 1)

.
P(x k , yk )
.
B(x k + 1, yk )
.
B ′ (x k + 2, yk )

Cas B.
Calculons alors le défaut :
Dk+1 = E(A′ ) + E(B ′ ) = E(x k + 2, yk + 1) + E(x k + 2, yk )
= a(x k + 2) + b( yk + 1) + c + a(x k + 2) + b yk + c
= 2a x k + 2b yk + 4a + b + 2c
= Dk + 2a
Ainsi en posant p = 2a = 2∆ y, on obtient la formule de récurrence :
Dk+1 = Dk + p.
Conclusion : on sait calculer Dk+1 qui permet de choisir entre A′ et B ′ . Ainsi à partir de D0 et par les
formules de récurrence ci-dessus on calcule la suite des défauts Dk et on sait donc s’il faut monter le
pixel d’un cran ou pas.

2.3. Anticrénelage (antialiasing)

Le tracé d’un segment est nécessairement une approximation d’un tracé de droite, qui présente des défauts de
visualisation appelée « crénelage ». On remédie à cette imperfection à l’aide d’un anticrénelage (antialiasing)
qui colorie aussi le pixel laissé de côté (le pixel A ou B écarté dans les algorithmes précédents).

Avec anticrénelage Sans anticrénelage

PIXELS 10

De près le rendu n’est pas impressionnant mais de loin l’amélioration est sensible.
Nous allons expliquer un algorithme simple pour dessiner un segment avec anticrénelage. Nous avons donc
deux pixels l’un au-dessus de l’autre à colorier : le pixel A et le pixel B. Comment répartir 100% de couleur
entre ces deux pixels ?
Commençons par expliquer une analogie issue de la physique. Considérons deux masses ponctuelles liées
entre elles : mA centrée en A et mB centrée en B. Lorsque l’on regarde ce système d’assez loin on peut le
considérer comme un système formé d’une seule masse ponctuelle : la masse totale est m = mA + mB et est
centrée au centre de gravité G. Ce centre de gravité G est défini par la relation :
ℓA mA = ℓB mB
où ℓA = AG et ℓB = BG.

.
A
.G
.
B
.
G
mB
mA
mA + mB

ℓA ℓB
.
A
.
G
.
B

mA mB

Reprenons cette idée : nous répartissons une masse totale m = 1 (100% de la couleur) centrée exactement
sur la droite réelle en G entre deux points A et B.
Notons (x, y) le point G de la droite réelle. Soit alors :
j = ⌊ y⌋ et ℓ = y − ⌊ y⌋
PIXELS 11

respectivement la partie entière et la partie fractionnaire de y. La distance BG est ℓ et la distance AG est 1−ℓ
(car AB = 1). Ainsi pour que les couleurs satisfassent la formule du centre de gravité il faut choisir mA = ℓ et
mB = 1 − ℓ comme intensité de couleur respectivement pour A et B car on a alors bien (1 − ℓ)ℓ = ℓ(1 − ℓ).
On adapte l’algorithme du tracé élémentaire pour y ajouter l’anticrénelage.

Algorithme (Algorithme d’anticrénelage).

Entrée : des entiers x 1 , y1 , x 2 , y2 vérifiant l’hypothèse.
Sortie : le tracé des pixels reliant (x 1 , y1 ) à (x 2 , y2 ).
y −y
• Calculer α = x 22 −x 11 .
• Poser i = x 1 .
• Poser y = y1 .
• Tant que i ⩽ x 2 :
— j = ⌊ y⌋
— ℓ = y − ⌊ y⌋
— afficher le pixel (i, j) avec l’intensité de couleur 1 − ℓ
— afficher le pixel (i, j + 1) avec l’intensité de couleur ℓ
— i = i+1
— y = y +α

2.4. Tracé d’un cercle

On souhaite tracer un cercle de rayon r centré en (x 0 , y0 ). Ce cercle a pour équation :
(x − x 0 )2 + ( y − y0 )2 = r 2 .
Pour cela on va se contenter de tracer l’arc de cercle compris entre 90° et 45°. Le reste s’obtiendra par
symétrie.

Voici quelques exemples.

PIXELS 12

Voici l’algorithme du tracé de l’arc de cercle de type Bresenham car il n’utilise que des entiers. Le point de
départ est le point (0, r) (point le plus haut du cercle).

Algorithme (Algorithme de tracé de cercle).

Entrée : des entiers x 0 , y0 pour le centre et un entier r pour le rayon.
Sortie : le tracé d’un arc du cercle centré en (x 0 , y0 ) de rayon r.
• Poser i = 0.
• Poser j = r.
• Poser d = 3 − 2r.
• Tant que i ⩽ j :
— afficher le pixel (x 0 + i, y0 + j)
— si d < 0 :
— d = d + 4i + 6
— sinon :
— d = d + 4i − 4 j + 10
— j = j−1
— i = i+1

Sur la portion tracée (de 90◦ à 45◦ ) il y a exactement un pixel pour chaque i. Pour obtenir le cercle complet,
en plus du pixel en (x 0 + i, y0 + j), il faut afficher par symétrie les pixels en (x 0 + j, y0 + i), (x 0 − i, y0 + j),
(x 0 − j, y0 + i) (x 0 + i, y0 − j), (x 0 + j, y0 − i), (x 0 − i, y0 − j), (x 0 − j, y0 − i).
Preuve. La preuve est similaire à celle de l’algorithme du tracé d’un segment de Bresenham.
• Équation du cercle.
On suppose que le cercle est centré à l’origine : (x 0 , y0 ) = (0, 0). Un cercle quelconque s’obtiendrait par
translation. Soit la fonction d’écart :
E(x, y) = x 2 + y 2 − r 2
PIXELS 13

Si E(x, y) = 0 le point (x, y) est sur le cercle, si E(x, y) > 0 le point est à l’extérieur, si E(x, y) < 0 le
point est à l’intérieur.
y

. . .
E(x, y) = 0

E(x, y) > 0
E(x, y) < 0

• Descendre ou pas ?
Pour un pixel centré en P déjà tracé, nous devons choisir pour le pixel suivant entre A et B. On choisit le
point le plus proche du cercle, c’est-à-dire le minimum entre |E(A)| ou |E(B)|. On définit le défaut par
D(P) = E(A) + E(B)
et on a :
Si D(P) < 0 alors on choisit A, si D(P) ⩾ 0 alors on choisit B.

.
P(x k , yk )
.
A(x k + 1, yk )
.
P(x k , yk )
.
A(x k + 1, yk )

.
B(x k + 1, yk − 1)
.
B(x k + 1, yk − 1)

Cas Dk < 0. Cas Dk ⩾ 0.

• Calcul du défaut. Calculons Dk le défaut au point P(x k , yk ) :
Dk = D(x k , yk ) = E(A) + E(B) = E(x k + 1, yk ) + E(x k + 1, yk − 1)
= (x k + 1)2 + yk2 − r 2 + (x k + 1)2 + ( yk − 1)2 − r 2
= 2x k2 + 2 yk2 + 4x k − 2 yk + 3 − 2r 2
En particulier D0 le défaut au point initial (0, r) vaut :
D0 = 3 − 2r.
• Formule de récurrence du défaut.
On part du point P(x k , yk ), connaissant Dk on calcule Dk+1 en fonction du choix A ou B pour le pixel
d’abscisse x k+1 .

.P
.A
.A′
.P

.B′
.
B
.
A′
Cas A.

.
B′

Cas B.
PIXELS 14

Cas du choix A (cas Dk < 0). Le pixel suivant a pour abscisse x k + 2 et pour ordonnée soit yk (A′ ), soit
yk − 1 (B ′ ).

.
P(x k , yk )
.
A(x k + 1, yk )
.
A′ (x k + 2, yk )

.
B ′ (x k + 2, yk − 1)

Cas A.
Le défaut se calcule ainsi :
Dk+1 = E(A′ ) + E(B ′ ) = E(x k + 2, yk ) + E(x k + 2, yk − 1)
= (x k + 2)2 + yk2 − r 2 + (x k + 2)2 + ( yk − 1)2 − r 2
= Dk + 4x k + 6
Cas du choix B (cas Dk ⩾ 0). Le pixel suivant a pour abscisse x k + 2 et pour ordonnée soit yk − 1 (A′ ),
soit yk − 2 (B ′ ).

.
P(x k , yk )

. .
B(x k + 1, yk − 1) A′ (x k + 2, yk − 1)

.
B ′ (x k + 2, yk − 1)

Cas B.

Dk+1 = E(A′ ) + E(B ′ ) = E(x k + 2, yk − 1) + E(x k + 2, yk − 2)

= (x k + 2)2 + ( yk − 1)2 − r 2 + (x k + 2)2 + ( yk − 2)2 − r 2
= Dk + 4x k − 4 yk + 10
Conclusion : on sait calculer Dk+1 qui permet de choisir entre A′ et B ′ .

3. Colorier

3.1. Colorier par diffusion

Objectif. On considère une image formée par exemple de pixels noirs et blancs. On souhaite colorier en gris
une zone de l’image. Pour cela, on part d’un pixel initial (la graine, seed) et il faut colorier en gris toute la
zone de pixels blancs contenant la graine et bordée par des pixels noirs.

graine
PIXELS 15

Principe. On part de la graine, qu’on colorie en gris. Pour chacun de ses quatre pixels voisins (gauche, bas,
droite, haut), si c’est un pixel blanc, on applique le processus à partir de ce nouveau pixel.
Ci-dessous la graine et ses quatre voisins.

Mise en œuvre. Ce procédé peut être traduit en algorithmes par différentes méthodes : algorithme récursif,
algorithme avec une pile ou algorithme avec une file. Dans tous les cas ce sont des algorithmes qui utilisent
beaucoup de mémoire afin de stocker les pixels en attente d’être traités. On choisit un algorithme avec file
(queue ou fifo, first in, first out) un peu moins gourmand en mémoire que les autres choix.

Algorithme (Algorithme de remplissage par diffusion (flood fill)).

Entrée : un tableau de pixels noirs ou blancs, un pixel initial (x 0 , y0 ) (la graine)
Sortie : un tableau de pixels noirs, blancs ou gris
• file = [(x 0 , y0 )]
• Tant que la file n’est pas vide :
— prendre (x, y) un élément de file (et le retirer de la file)
— si (x, y) est un pixel blanc :
— le colorier en gris,
— ajouter à la file les quatre voisins (x − 1, y), (x, y + 1), (x + 1, y), (x, y − 1).

Quelques étapes du processus :

3.2. Colorier par balayage

Le coloriage par balayage en un peu plus performant au niveau de la mémoire car il colorie une portion de
ligne avant d’ajouter les pixels au-dessus ou en-dessous dans la file d’attente.

Algorithme (Algorithme de balayage (scan fill)).

Entrée : un tableau de pixels noirs ou blancs, un pixel initial (x 0 , y0 ) (la graine)
Sortie : un tableau de pixels noirs, blancs ou gris
• file = [(x 0 , y0 )]
• Tant que la file n’est pas vide :
— prendre (x, y) un élément de file (et le retirer de la file)
— poser x min = x − 1
— tant que (x min , y) est un pixel blanc :
— le colorier en gris,
— faire x min = x min − 1.
— poser x max = x
— tant que (x max , y) est un pixel blanc :
— le colorier en gris,
— faire x max = x max + 1.
— Pour chaque x ′ entre x min + 1 et x max − 1 :
PIXELS 16

— si (x ′ , y + 1) est un pixel blanc, l’ajouter à la file,

— si (x ′ , y − 1) est un pixel blanc, l’ajouter à la file.

Ci-dessous la graine et les premières lignes.

Quelques étapes plus avancées :

4. Animation
Nous expliquons quelques principes liés à l’animation des images. Les premiers dessins animés étaient basés
sur des calques : une image fixe pour le calque de l’arrière-plan, un calque pour le premier plan avec par
exemple un personnage à redessiner de nombreuses fois afin de simuler le mouvement et éventuellement
des calques intermédiaires. On retrouvait aussi cette technique au cinéma où certains arrières-plans étaient
peints.

4.1. Perspective atmosphérique

Voyons comment la technique des calques permet de simuler un paysage.
La perspective atmosphérique est une façon de représenter l’éloignement des différents plans ou calques
par des teintes plus claires, des contrastes moins élevés et des couleurs plus grises (la saturation diminue).
Cela reflète des phénomènes physiques réels, certaines particules de l’atmosphère (molécules d’air, goutte-
lettes d’eau, fumées. . .) diffractent la lumière (particulièrement les longueurs d’ondes plus courtes comme
le bleu).

Il existe un modèle de couleurs HSV (Hue/Saturation/Value : Teinte/Saturation/Luminosité) pour lequel il

suffit donc de changer le paramètre de saturation.
Ci-dessous les couleurs obtenues pour (h, s, b) avec h = 0.66, b = 0.8 et la saturation s variant de 0 à 1.
PIXELS 17

0%

10 %

19 %

39 %

60 %

80 %

100 %

4.2. La 2.5D
Comme son nom le suggère, la 2.5D est un ensemble des techniques d’animation qui permettent de simuler
une scène 3D. C’est le cas de beaucoup de jeux vidéos de stratégie où le point de vue du joueur est au-dessus
du plateau de jeu. Les objets représentés en perspective (par exemple ci-dessous les immeubles) sont des
petites images 2D pré-dessinées. C’est une technique efficace mais qui nécessite de fixer ou de limiter
fortement le choix de la vue du joueur.

SimCity 2000 (images : Wikipedia)

4.3. Principe de l’animation 2D

Vous le savez, on simule le mouvement à l’écran par un succession rapide d’images. Ainsi les pixels ne
se déplacent pas, mais seule leur couleur change. Le cerveau humain, entraîné par les objets réels en
mouvement, reconstitue un déplacement à partir d’images fixes.

Pour réaliser de petits jeux animés, les modules de Pygame de Python sont très sympas. On explique ci-dessous
les principes de l’animation 2D en suivant la philosophie de Pygame.
Animation 1D.
Commençons par une animation très élémentaire en une seule dimension. Les objets en jeu sont :
• fond qui est l’image d’arrière-plan représentée ici par une liste de 0,
PIXELS 18

• un entier p qui représente la position d’un personnage, ce personnage est représenté par un 1,
• ecran qui est l’image finale affichée, et sera donc une juxtaposition de 0 et de 1.
Les étapes de l’animation sont les suivantes :
• Initialisation. On initialise ecran avec l’image d’arrière-plan fond :
0000000000
On définit une position de départ, par exemple p = 3.
• Affichage. Par ecran[p] = 1 on affiche le personnage :
0001000000
• Déplacement.
— Effacer le personnage. ecran[p] = 0
— Changer la position. p = p + 1.
— Réafficher le personnage. ecran[p] = 1
En répétant le déplacement on obtient, successivement :
0001000000
0000100000
0000010000
0000001000
0000000100

Animation 2D.
Le principe est similaire, il nous faut une image de fond, une image à afficher pour l’objet à déplacer.
L’affichage à l’écran correspond à affecter des valeurs à la mémoire graphique (screen buffer) ; on représente
ici l’écran comme une image.

Écran Arrière-plan Personnage

L’opération fondamentale est la copie rapide ou blit (pour bit-block transfer) qui consiste à copier les données
d’une image dans la mémoire graphique. Concrètement cela signifie copier une image et l’afficher à l’écran
à une position donnée (figure (a)) ou bien copier seulement une partie d’une image (figure (b)).

(a) Copie d’une image

Image & position

blit

Écran avant Écran après

PIXELS 19

(b) Copie d’une sous-image

Sous-image

blit

Écran avant Écran après

Le second cas de figure nous sert à effacer le personnage avant de le déplacer, plus exactement on copie à
l’écran la portion de l’arrière-plan à la place qu’occupait le personnage.
Le processus de l’animation est alors le même que précédemment :
• (a) Initialisation. On initialise ecran avec l’image d’arrière-plan fond :
• (b) Affichage. On affiche le personnage à une position donnée.
• Déplacement. (À répéter)
— (c) Effacement du personnage. Pour cela on copie la portion de l’arrière-plan correspondant à l’empla-
cement qu’occupe le personnage.
— (d) Affichage du personnage à sa nouvelle position.
La vitesse du mouvement est contrôlée par la longueur du déplacement et la durée de la pause entre deux
répétitions.

Écran

(a)

Arrière-plan

(b)

Image

(c)

(d)