ARNAPOU - Site multi collections

..:: Tracé de droite ::..
(algorithme permettant de tracer une droite 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).

Dans la suite logique du tracé de cercle, j'ai voulu créer un algorithme de tracé de droite.

Il m'a fallu moins de temps pour le trouver que celui pour le cercle. Cet alorithme, de la même manière que le cercle, j'ai appris qu'après coup qu'il portait déjà un nom : celui de son inventeur.

Je n'ai fait que redécouvrir un algorithme existant : celui de Bresenham. Vous pouvez trouver cet alorithme ailleurs sur le net mais sous des formes diverses. Le principe reste le même.

Point 1 (X1, Y1) : en bas à gauche Point 2 (X2, Y2) : en haut à droite Δx=X2-X1 : écart des abscisses Δy=Y2-Y1 : écart des ordonnées

La droite (D2) est la droite théorique tracée entre le point de départ et le point d'arrivée La droite (D1) est la droite parallèle à (D) mais passant par le centre de A La droite (D2) est la droite parallèle à (D) mais passant par le centre de B L'idée est de choisir le point suivant pour lequel l'écart cumulé sera minimal.

Petits calculs :

Equation de la droite (D) :
y=a⋅x+b avec a=ΔyΔx et b=Y1-ΔyΔx⋅X1
d'où (E):y=ΔyΔx⋅x+b

Equation de la droite (D1) :
y'=a⋅x'+b' avec a=ΔyΔx et b'=b+Δ1 et y'=y+1 et x'=x+1
d'où (E1):y+1=ΔyΔx⋅(x+1)+b+Δ1
(E1-E):1=ΔyΔx+Δ1⇒Δ1=1-ΔyΔx

Equation de la droite (D2) :
y'=a⋅x'+b' avec a=ΔyΔx et b'=b+Δ2 et y'=y et x'=x+1
d'où (E2):y=ΔyΔx⋅(x+1)+b+Δ2
(E2-E):0=ΔyΔx+Δ2⇒Δ2=-ΔyΔx

Comme ce qui nous intéresse ce n'est pas la valeur même mais l'ordre de grandeur de Δ1 par rapport à Δ2, on les multiplie par Δx :
Δ'1=Δx-Δy
Δ'2=-Δy

Comme ce n'est pas forcément pratique de comparer des valeurs absolues dans l'algorithme, on ne va pas comparer |Δ'1| avec |Δ'2| mais plutôt |Δ'2|-|Δ'1| avec 0 d'où l'expression 2⋅ΔY-ΔX et les suivantes que vous allez voir ci-dessous.

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

Dans cet algorithme je ne me limite pas au premier quadrant comme vu ci-dessus pour exprimer les formules.

X=X1 Y=Y1 ΔX=|X2-X1| ΔY=|Y2-Y1| Affiche_Pixel(X, Y)
# 1er quadrant Si X1≤X2 et Y1≤Y2 Alors # en dessous 1ere bissectrice Si X2-X1≥Y2-Y1 Alors Δ=2⋅ΔY-ΔX Tant que X<>X2 X=X+1 Si Δ>0 Alors Y=Y+1 Δ=Δ-2⋅ΔX Δ=Δ+2⋅ΔY Affiche_Pixel(X, Y) # au dessus 1ere bissectrice Sinon Δ=2⋅ΔX-ΔY Tant que Y<>Y2 Y=Y+1 Si Δ>0 Alors X=X+1 Δ=Δ-2⋅ΔY Δ=Δ+2⋅ΔX Affiche_Pixel(X, Y)
# 2e quadrant Si X1>X2 et Y1<Y2 Alors # en dessous 2e bissectrice Si X1-X2≥Y2-Y1 Alors Δ=2⋅ΔY-ΔX Tant que X<>X2 X=X-1 Si Δ>0 Alors Y=Y+1 Δ=Δ-2⋅ΔX Δ=Δ+2⋅ΔY Affiche_Pixel(X, Y) # au dessus 2e bissectrice Sinon Δ=2⋅ΔX-ΔY Tant que Y<>Y2 Y=Y+1 Si Δ>0 Alors X=X-1 Δ=Δ-2⋅ΔY Δ=Δ+2⋅ΔX Affiche_Pixel(X, Y)
# 3e quadrant Si X1≥X2 et Y1≥Y2 Alors # en dessous 3e bissectrice Si X1-X2≥Y1-Y2 Alors Δ=2⋅ΔY-ΔX Tant que X<>X2 X=X-1 Si Δ>0 Alors Y=Y-1 Δ=Δ-2⋅ΔX Δ=Δ+2⋅ΔY Affiche_Pixel(X, Y) # au dessus 3e bissectrice Sinon Δ=2⋅ΔX-ΔY Tant que Y<>Y2 Y=Y-1 Si Δ>0 Alors X=X-1 Δ=Δ-2⋅ΔY Δ=Δ+2⋅ΔX Affiche_Pixel(X, Y)
# 4e quadrant Si X1<X2 et Y1>Y2 Alors # en dessous 4e bissectrice Si X2-X1≥Y1-Y2 Alors Δ=2⋅ΔY-ΔX Tant que X<>X2 X=X+1 Si Δ>0 Alors Y=Y-1 Δ=Δ-2⋅ΔX Δ=Δ+2⋅ΔY Affiche_Pixel(X, Y) # au dessus 4e bissectrice Sinon Δ=2⋅ΔX-ΔY Tant que Y<>Y2 Y=Y-1 Si Δ>0 Alors. X=X+1 Δ=Δ-2⋅ΔY Δ=Δ+2⋅ΔX Affiche_Pixel(X, Y)

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 la droite

Sous-programme affichant un pixel

LIGNE PROC ;trace une ligne ;(AX,BX) = point de départ ;(CX,DX) = point d'arrivée pusha cmp ax,cx jb lig0 xchg ax,cx xchg bx,dx lig0: cmp bx,dx jnbe lig00 mov si,cx sub si,ax mov di,dx sub di,bx cmp si,di jb lig2 lig1: mov bp,di shl bp,1 sub bp,si shl si,1 shl di,1 lplg1: cmp ax,cx jnbe finlg call affpixel cmp bp,0 jl lgs1 sub bp,si inc bx lgs1: inc ax add bp,di jmp lplg1 lig2: xchg ax,bx xchg cx,dx xchg si,di mov bp,di shl bp,1 sub bp,si shl si,1 shl di,1 lplg2: cmp ax,cx jnbe finlg xchg ax,bx call affpixel xchg ax,bx cmp bp,0 jl lgs2 sub bp,si inc bx lgs2: inc ax add bp,di jmp lplg2 lig00: mov si,cx sub si,ax mov di,bx sub di,dx cmp si,di jb lig4 lig3: mov bp,di shl bp,1 sub bp,si shl si,1 shl di,1 lplg3: cmp ax,cx jnbe finlg call affpixel cmp bp,0 jl lgs3 sub bp,si dec bx lgs3: inc ax add bp,di jmp lplg3 lig4: xchg ax,bx xchg cx,dx xchg ax,cx xchg bx,dx xchg si,di mov bp,di shl bp,1 sub bp,si shl si,1 shl di,1 lplg4: cmp ax,cx jnbe finlg xchg ax,bx call affpixel xchg ax,bx cmp bp,0 jl lgs4 sub bp,si dec bx lgs4: inc ax add bp,di jmp lplg4 finlg: popa ret LIGNE 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