Algorithme de tracé d'arc de cercle de Bresenham

Tout d'abord, on peut remarquer que sur une grille de pixels, il existe quatre axes de symétrie au cercle, deux suivant les axes de la matrice, et deux représentant les bissectrices du repère centré sur le cercle. Ainsi, ayant calculé un arc d'un secteur du repère délimité par les axes de symétrie, il suffit d'exploiter la symétrie pour positionner les pixels dans les sept autres octants.

Pour les raisons de symétrie expliquées précédemment, l'algorithme expliqué sera limité au deuxième octant (d'angle compris entre ${\displaystyle {\frac {\pi }{2}}}$ et ${\displaystyle {\frac {\pi }{4}}}$) puis généralisé ensuite. L'algorithme partira donc du point le plus haut du cercle, et descendra jusqu'à la première bissectrice.

Schéma

Ce tracé procède par itération, chaque itération activant un pixel. Imaginons que nous sommes en un pixel P, et qu'il faut placer le pixel suivant. Puisque nous sommes dans le deuxième octant, ce pixel sera le point E ou le point F. La méthode de Bresenham consiste à évaluer si le cercle « idéal » d'équation ${\displaystyle x^{2}+y^{2}-R^{2}=0}$ passe au-dessus ou en dessous du point M, milieu du segment EF pour activer respectivement le pixel E ou le pixel F.

Il faut donc calculer à chaque itération une variable m telle que ${\displaystyle m={x_{M}}^{2}+{y_{M}}^{2}-R^{2}}$. Alors :

• m > 0 ⇒M au-dessus du cercle idéal ⇒ choix de F ⇒ incrémenter x, décrémenter y
• m < 0 ⇒ M au-dessous du cercle idéal ⇒ choix de E ⇒ incrémenter x

Pour optimiser l'algorithme, on calcule la variable m récursivement. On montre que ${\displaystyle 4m=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}}$ (1)

démonstration

Plaçons-nous au point ${\displaystyle P_{i}}$ de coordonnées sur la grille de pixel ${\displaystyle (x_{i};y_{i})}$ et calculons la variable m.

On sait alors que M a pour coordonnées ${\displaystyle (x_{m}=x_{i}+1;y_{m}=y_{i}-0,5)}$.

Donc ${\displaystyle m={x_{M}}^{2}+{y_{M}}^{2}-R^{2}={(x_{i}+1)}^{2}+{(y_{i}-0,5)}^{2}-R^{2}={x_{i}}^{2}+{y_{i}}^{2}+2x_{i}-y_{i}+1,25-R^{2}}$.

Puisqu'on souhaite ne travailler qu'avec des nombres entiers, et puisque seul le signe de m nous intéresse, on multiplie l'équation par 4 et on obtient ${\displaystyle 4m=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}}$.

On va modifier la variable m en fonction du choix du pixel E ou du pixel F. On nommera ${\displaystyle m_{i}}$ l'ancienne valeur de m, et ${\displaystyle m_{i+1}}$ la nouvelle valeur de m.

• On montre que si on choisit E, ${\displaystyle 4m_{i+1}=4m_{i}+8x_{i}+12=4m_{i}+8x_{i+1}+4}$.

Il faut donc incrémenter ${\displaystyle 4m_{i}}$ de ${\displaystyle 8x_{i+1}+4}$.

démonstration

Si on choisit E, alors ${\displaystyle (x_{i+1}=x_{i}+1,y_{i+1}=y_{i})}$.

Or d'après l'équation (1),

${\displaystyle 4m_{i+1}=4{x_{i+1}}^{2}+4{y_{i+1}}^{2}+8x_{i+1}-4y_{i+1}+5-4R^{2}}$,

donc ${\displaystyle 4m_{i+1}=4({x_{i}}^{2}+2x_{i}+1^{2})+4{y_{i}}^{2}+8(x_{i}+1)-4y_{i}+5-4R^{2}}$

d'où ${\displaystyle 4m_{i+1}=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}+8x_{i}+12}$.

En utilisant le fait que ${\displaystyle 4m_{i}=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}}$,

on obtient ${\displaystyle 4m_{i+1}=4m_{i}+8x_{i}+12=4m_{i}+8x_{i+1}+4}$.

• On montre que si on choisit F, ${\displaystyle (x_{i+1}=x_{i}+1,y_{i+1}=y_{i}-1)}$.

Il faut donc incrémenter ${\displaystyle 4m_{i}}$ de ${\displaystyle 8x_{i+1}+4-8y_{i+1}}$.

On en déduit donc le calcul itératif de m : ${\displaystyle 4m_{i+1}=4m_{i}+8x_{i+1}+4-d}$ avec d qui vaut 0 si on choisit E, et ${\displaystyle 8y_{i+1}}$ si on choisit F.

Pour amorcer le calcul itératif, on remarque que ${\displaystyle m_{0}={(1)}^{2}+{(R-0,5)}^{2}-R^{2}}$ donc ${\displaystyle 4m_{0}=5-4R}$.

On a vu précédemment que pour chaque pixel placé la complexité de calcul se réduisait à X additions, Y multiplications et Z comparaisons. L'utilisation de fonctions trigonométriques usuelles ou d'une racine carrée auraient nécessité un coût algorithmique considérable en comparaison.

Illustration des "trous"

On peut également se servir du principe de cet algorithme pour tracer des couronnes et des ellipses.

Si l'on trace des cercles concentriques de rayon de plus en plus grand, on remarque que l'on ne parvient pas à remplir tout le plan : il y a des « trous » . Ce défaut amène à utiliser d'autres méthodes, comme l'algorithme de tracé de cercle d'Andres.