ARNAPOU - Site multi collections

..:: Tracé de cercle ::..
(algorithme permettant de tracer un cercle très basiquement)

Cette page contient des formules mathématiques codées en MATHML (langage normalisé comme le HTML mais pour les formules mathématiques). Internet Explorer 6 ne supporte pas encore ce langage et vous devez installer "MathPlayer" qui est GRATUIT pour voir les formules correctement (c'est un plug-in de IE6 comme Macromedia FlashPlayer qui vous permet de voir du Flash). Vous pouvez le télécharger depuis le site de "Design Science" ou depuis "Arnapou" (1.2 Mo).

Durant mes cours d'assembleur (langage de programmation informatique très bas niveau) de mes études, j'ai voulu réaliser un jeu de puissance 4 en assembleur.

Pour ce programme, le premier problème qui est apparu et le plus intéressant intellectuellement était de pouvoir tracer les jetons, donc des cercles.

Jusque là, vous allez me dire, rien de bien magnifique, mais le challenge c'est qu'en assembleur, je vous déconseille d'utiliser les sinus et cosinus ... puisqu'ils n'existent pas (donc à vous de les créer).

Il est également déconseillé de faire des multiplications classiques et divisions car consommatrices de temps machine. Les seules opérations utilisables à faible coût sont : addition (+), soustraction (-), multiplication ou division par deux (décalage d'1 bit).

Donc je me suis attelé à la tâche avec pour seule aide mon cerveau, une feuille, et un crayon ... après 2 heures de cogitations, j'ai trouvé l'idée, l'ai testé et réalisée... quand vous allez voir par la suite l'algorithme, vous risquez de vous dire que deux heures, c'était bien long pour un truc aussi simple ... mais le plus dur c'était de trouver l'idée elle-même.

Vous trouverez peut-être cet algorithme sous d'autres formes ailleurs car durant l'année suivante, nous avons vu cet algorithme en cours ... et il porte le nom de son inventeur : Bresenham ... mais je garde pour moi la satisfaction de l'avoir développé seul ...

R : rayon du cercle On suppose le Centre du cercle en (0, 0) Point Rose (R, 0) : point de départ de l'algorithme

L'idée est que les points suivent le chemin qui est le plus prêt possible du cercle donc ce qui peut être traduit par :
=> le cercle est le chemin de pixels pour lequel l'écart avec le rayon est minimal

Tout se passe donc par rapport au rayon.

Petits calculs :

Equation du cercle dans le cas parfait :
R2=x2+y2

Equation du cercle dans le cas A ou x'=x-1 et y'=y+1 (cf point A sur graphe) :
R'2=x'2+y'2
R'2=(x-1)2+(y+1)2
R'2=x2-2x+1+y2+2y+1
R'2=x2+y2+2y-2x+2
R'2=R2+2y-2x+2
R'2=R2+ΔR   avec   ΔR=2y-2x+2

Equation du cercle dans le cas B ou x'=x et y'=y+1 (cf point B sur graphe) :
R'2=x'2+y'2
R'2=x2+(y+1)2
R'2=x2+y2+2y+1
R'2=R2+2y+1
R'2=R2+ΔR   avec   ΔR=2y+1

Remarque :
On se limite qu'aux cas A et B car on arrêtera l'algorithme à x=y étant donné que pour les autres points, il suffit de les représenter par symétries.

Conclusion :
On a les deux expressions possibles de ΔR.
Pour tracer le cercle il suffit d'itérer cela en choisissant à chaque fois le ΔR le plus petit.

Cet algorithme a comme syntaxe une syntaxe très basique.
A vous de la traduire dans le language qu'il vous plaira.

Algorithme pour que le cercle puisse être colorié par un programme de coloriage à 4 voisins :

Programme Principal	Sous-Programme Trace_Pixels(X, Y)
Début R= rayon du cercle ΔR=0 X=R Y=0 Trace_Pixels(R, 0) Trace_Pixels(0, R) Tant que X>Y faire Δ1=ΔR+2Y-2X+2 Δ2=ΔR+2Y+1 Si |Δ1|<|Δ2| Alors ΔR=Δ1 Y=Y+1 X=X-1 Sinon ΔR=Δ2 Y=Y+1 Trace_Pixels(X, Y) Trace_Pixels(Y, X) Fin	Début X0= abscisse du centre Y0= ordonnée du centre Affiche_Pixel(X0+X, Y0+Y) Affiche_Pixel(X0+X, Y0-Y) Affiche_Pixel(X0-X, Y0+Y) Affiche_Pixel(X0-X, Y0-Y) Fin

Cet algorithme présente un problème dans le cas où vous voudriez effectuer un coloriage du cercle avec un algorithme à 8 voisins car le cercle n'arrêterait pas le coloriage.

Algorithme pour que le cercle puisse être colorié par un programme de coloriage à 8 voisins :

Programme Principal	Sous-Programme Trace_Pixels(X, Y)
Début R= rayon du cercle ΔR=0 X=R Y=0 Trace_Pixels(R, 0) Trace_Pixels(0, R) Tant que X>Y faire Δ1=ΔR+2Y-2X+2 Δ2=ΔR+2Y+1 Si |Δ1|<|Δ2| Alors ΔR=Δ1 Y=Y+1 Trace_Pixels(X, Y) Trace_Pixels(Y, X) X=X-1 Sinon ΔR=Δ2 Y=Y+1 Trace_Pixels(X, Y) Trace_Pixels(Y, X) Fin	Début X0= abscisse du centre Y0= ordonnée du centre Affiche_Pixel(X0+X, Y0+Y) Affiche_Pixel(X0+X, Y0-Y) Affiche_Pixel(X0-X, Y0+Y) Affiche_Pixel(X0-X, Y0-Y) Fin

La différence avec l'algorithme précédent est le tracé de pixels supplémentaires au milieu de la boucle.

Cette partie est réservée aux connaisseurs ou aux curieux mais je ne ferai pas ici un cours d'assembleur.

Juste pour apaiser la curiosité de certains :

ax, bx, cx, ... : ce sont des registres stockant des valeurs de 16 bits (2 octets)

push : sauve le registre dans la pile pour être restaurée par un pop

mov : copie le registre dans un autre

call : appel d'un sous-programme

cmp : compare des registres pour gérer des conditions

je : 'jump if equal' saut vers une autre instruction si égalité dans la dernière comparaison

add : somme de registres

inc : incrémentation (+1) d'un registre

...

Vous comprenez peut-être maintenant pourquoi éviter les calculs inutiles (multiplications etc ...) est crucial en assembleur : le code est vite lourd à coder même pour un algorithme simple...

Programme affichant le cercle

Sous-programme affichant un pixel

CIRCLE PROC ;trace un cercle de centre (AX,BX) et ;de rayon CX de couleur 'color' pouvant ;être colorié par un algorithme à 4 voisins push ax push bx push cx push si push di push bp mov coordX,ax mov coordY,bx mov ax,cx xor bx,bx call printpixel xchg ax,bx call printpixel xchg ax,bx cmp cx,0 je fcirq1 xor cx,cx deb1q1: cmp ax,bx jb deb2q1 xor bp,bp mov di,ax shl di,1 sub bp,di inc bp mov SI,bx shl SI,1 add SI,bp inc si mov di,bx shl di,1 inc di add SI,cx add di,cx mov err1,SI mov err2,di call abs_SI call abs_DI cmp SI,di jnbe inf1q1 dec ax inc bx mov cx,err1 call printpixel xchg ax,bx call printpixel xchg ax,bx jmp deb1q1 inf1q1: inc bx mov cx,err2 call printpixel xchg ax,bx call printpixel xchg ax,bx jmp deb1q1 deb2q1: xor bp,bp ;sert à rien fcirq1: pop bp pop di pop SI pop cx pop bx pop ax ret CIRCLE ENDP

PRINTPIXEL PROC ;imprime le pixel à l'écran en ;faisant avant une translation push ax push bx push cx push dx mov cx,ax mov dx,bx add ax,coordX add bx,coordY cmp ax,xmax jnbe print2 cmp bx,ymax jnbe print2 call affpixel print2: sub ax,cx sub ax,cx cmp ax,xmax jnbe print3 cmp bx,ymax jnbe print3 call affpixel print3: sub bx,dx sub bx,dx cmp ax,xmax jnbe print4 cmp bx,ymax jnbe print4 call affpixel print4: add ax,cx add ax,cx cmp ax,xmax jnbe print5 cmp bx,ymax jnbe print5 call affpixel print5: pop dx pop cx pop bx pop ax ret PRINTPIXEL ENDP AFFPIXEL PROC ; imprime un pixel de couleur 'color' ; aux coordonnées (AX,BX) push cx push ax push bx push dx mov cx,ax mov dx,bx mov al,color mov bh,pg mov ah,0Ch int 10h ; int bios pop dx pop bx pop ax pop cx ret AFFPIXEL ENDP