Du pixel au trait

par · Publié · Mis à jour

Les écrans numériques, les imprimantes, les machines-outil possèdent des axes à pas discrets : la géométrie y est représentée par des points (appelés pixels pour les écrans).

En 1962, Jack E. Bresenham, a développé un algorithme qui détermine quels sont les points d’un plan discret qui doivent être tracés afin de former une approximation de segment de droite entre deux points donnés.

Il s’agit d’un des premiers algorithmes découverts dans le domaine de la synthèse d’image.

Plus tard, en 1977, il développa un nouvel algorithme pour tracer des arcs de cercle discrets, sans utiliser de fonction sinus ni racine carrée !

Afin de bien visualiser les pixels, sans avoir besoin de loupe, nous utiliserons le programme de base suivant, utilisant la bibliothèque Python Tkinter :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Import des noms du module
from tkinter import *

W, H = 13, 7 # Dimensions du plan discret
E = 20 # Taille en pixels écran des "pixels" du plan discret
e = 1 # Épaisseur en pixels écran entre les "pixels" du plan discret

# Création d'un objet "fenêtre"
fenetre = Tk()
fenetre.geometry(str(W*E)+'x'+str(H*E))
fenetre.resizable(0, 0)
fenetre.title("Bresenham")

canvas = Canvas(fenetre)
canvas.pack()

# Une grille :
for x in range(W+1):
    canvas.create_line(x*E, 0, x*E, H*E, fill="#d0d0d0", width = 2*e)
for y in range(H+1):
    canvas.create_line(0, y*E, W*E, y*E, fill="#d0d0d0", width = 2*e)

# Fonction de tracé de "pixel"
def afficher_pixel(x, y):
    canvas.create_rectangle((x-1)*E+e, (y-1)*E+e, x*E-e, y*E-e, fill = "black", width = 0)

# Fonctions de tracé du segment idéal
def afficher_ligne(x0, y0, x1, y1):
    canvas.create_line(x0*E-E/2, y0*E-E/2, x1*E-E/2, y1*E-E/2, fill = "red", width = 5)

# Fonctions de tracé de segment :
# ..........................

# Démarrage de la boucle Tkinter (à laisser à la fin !!!)
fenetre.mainloop()

Tracé de segment

Explication de l’algorithme de base dans le premier octant

La ligne est tracée entre deux points (x1, y1) et (x2, y2), où chaque paire indique la colonne et la rangée, respectivement, croissant vers la droite et le bas.

Dans un premier temps, on supposera que le segment se trouve dans le premier octant :

  • il descend vers le bas et la droite,
  • la distance horizontale \(x_2-x_1\) excède la distance verticale \(y_2-y_1\) (le segment a une pente inférieure ou égale à 1).

Rappel : l’origine d’un plan discret en informatique (écran, imprimante, …) se trouve en haut à gauche !

Notre but est, pour chaque colonne \(x\) entre \(x_1\) et \(x_2\), d’identifier la rangée \(y\) dans cette colonne qui est la plus proche du segment idéal.

La pente du segment s’exprime :

\(a=\frac{y_2-y_1}{x_2-x_1}\)

Ainsi, pour chaque colonne \(x\), on détermine la rangée \(y\) du pixel le plus proche de l’ordonnée exacte du point d’abscisse \(x\) par :

\(y=\lfloor( a\left(x-x_1\right)+y_1+0,5\rfloor)\)

Implémenter en Python une fonction segment1(x1, y1, x2, y2)  permettant de tracer un segment discret dans le premier octant.
Estimer le coût de cet algorithme en fonction de \(dx=x_2-x_1\) (on considèrera que chaque opération sur un réel coute 2 et qu’une affectation coute 1)

Optimisation de l’algorithme

Le calcul explicite de la valeur \(y\) pour chaque colonne \(x\) est coûteux (1 multiplication, 3 sommes et un arrondi sur des flottants).

On se propose de progresser sur le segment par incrémentation : à chaque pas de \(x\), on augmente \(y\) de la valeur \(a\). Si \(x\) augmente à chaque itération, \(y\) n’augmente que si l’erreur \(y-a\left(x-x_1\right)+y_1\) est supérieure à \(0,5\).

Pour éviter de calculer l’erreur de manière absolue à chaque itération, on introduit la variable \(e\) définie comme l’erreur relative : la distance verticale entre la valeur \(y\) courante et l’ordonnée exacte de la droite à l’abscisse \(x\) courante. Au départ cette valeur d’erreur \(e\) est nulle et chaque fois qu’on incrémente \(x\), on augmente la valeur d’erreur par la valeur de pente \(a\). A chaque fois que l’erreur dépasse \(0,5\), le segment discret est devenu plus proche du segment réel, aussi on ajoute \(1\) à \(y\) en retranchant simultanément \(1\) à l’erreur \(e\).

Implémenter en Python une fonction segment2(x1, y1, x2, y2)  avec cette nouvelle méthode.
Estimer le coût de cet algorithme en fonction de \(dx=x_2-x_1\) (on considèrera que chaque opération sur un entier coute 1)
Il subsiste encore de nombreux calculs portant sur des flottants, plus couteux que des calculs sur des entiers. Pour remédier à cela, on peut constater que \(a=\frac{dy}{dx}\) est un nombre rationnel. L’idée consiste à manipuler \(e\times dx\) (qui restera un entier) au lieu de \(e\).
Cette méthode doit permettre de ne plus réaliser que des opérations sur des nombres entiers.
Implémenter en Python une fonction segment3(x1, y1, x2, y2), comme une évolution de l’algorithme précédent, puis estimer son coût.
Reprendre l’algorithme, de sorte d’obtenir, par simplification et réductions de variable, un coût minimum.

 

Tracé d’arc de cercle

Comme pour le segment, il est possible de construire un arc de cercle dans un seul octant, puis de déduire le reste du cercle par symétries.

Nous choisissons le deuxième octant : l’algorithme partira du bas du cercle en direction de la droite, si bien qu’il reviendra encore à incrémenter \(x\) à chaque itération, et de ne décrémenter \(y\) que pour rester le plus près possible du cercle idéal.

Pour un cercle de rayon \(r\) et de centre \((x_C,y_C)\), notons \(x\) et \(y\) les coordonnées relatives à son centre des pixels qui doivent le constituer, c’est à dire tels que \(x^2+y^2-r^2\) soit minimum.

Ainsi pour déterminer les coordonnées du pixel « suivant » le pixel de coordonnées \((x, y)\), il suffira de déterminer si le cercle idéal passe au dessus ou au dessous d’un point \(M\), de coordonnées \((x_M, y_M)=(x+1, y-0.5)\), ce qui revient à évaluer le signe d’une variable \(m=x_M^2+y_M^2-r^2\).

Pour tracer le cercle de centre \((x_C,y_C)\), il suffira d’ajouter \(x_C\) et \(y_C\) aux coordonnées relatives \(x\) et \(y\).

Implémenter une fonction arc_cercle1(xc, yc, r)  utilisant la méthode décrite plus haut.

Comme pour le cas des segments, il est possible d’optimiser cet algorithme. Pour cela, il faut réaliser le moins d’opérations possible à l’intérieur de la boucle, en calculant \(m\) de manière « récursive ».

Et pour les mêmes raisons qu’auparavant, il faudra veiller à ne faire que des opérations sur des entiers.

Voici ce que propose Bresenham : à partir d’un pixel \(P_i(x_i,y_i)\) précédemment calculé :

  • on exprime \(4m_i\) en fonction de \(x_i\), \(y_i\) et \(r\).
  • on détermine \(4m_{i+1}\) en fonction de \(x_i\), \(y_i\) et \(4m_i\), pour chacun des 2 cas (pixels) \(P_{i+1}\) envisageables.
  • on réalise un changement de variable : \(4m\) redevient \(m\).
Implémenter la fonction arc_cercle2(xc, yc, r), version optimisée de la fonction précédente.

 

Source : https://fr.wikipedia.org/wiki/Algorithme_de_tracé_d’arc_de_cercle_de_Bresenham

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *