Aquest algorisme s'utilitza per escanejar la conversió d'una línia. Va ser desenvolupat per Bresenham. És un mètode eficaç perquè només implica operacions de suma, restes i multiplicacions de nombres enters. Aquestes operacions es poden realitzar molt ràpidament, de manera que es poden generar línies ràpidament.

En aquest mètode, el següent píxel seleccionat és el que té la menor distància de la línia real.

El mètode funciona de la següent manera:

Suposem un píxel P₁'(x₁',i₁'), a continuació, seleccioneu els píxels posteriors mentre treballem el nostre poder fins a la nit, una posició de píxel a la vegada en la direcció horitzontal cap a P₂'(x₂',i₂').

Una vegada que hi hagi un píxel, escolliu en qualsevol pas

El següent píxel és

marquesina html

1. O el de la seva dreta (límit inferior per a la línia)
2. Un a la part superior dreta i amunt (límit superior per a la línia)

La línia s'aproxima millor per aquells píxels que cauen a la menor distància del camí entre P₁', P₂'.

A tria el següent entre el píxel inferior S i el píxel superior T.
Si s'escull S
Tenim x_i+1=x_i+1 i y_i+1=i_i
Si s'escull T
Tenim x_i+1=x_i+1 i y_i+1=i_i+1

Les coordenades y reals de la línia en x = x_i+1és
y=mx_i+1+b

La distància de S a la línia real en direcció y
s = y-y_i

La distància des de T fins a la línia real en direcció y
t = (y_i+1)-i

Ara considereu la diferència entre aquests 2 valors de distància
s - t

Quan (s-t)<0 ⟹ s < t< p>

El píxel més proper és S

Quan (s-t) ≧0 ⟹ s

El píxel més proper és T

Aquesta diferència és
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Substituint m per i introduint la variable de decisió
d_i=△x (s-t)
d_i=△x (2 (x_i+1)+2b-2y_i-1)
=2△xi_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.y_i+c

On c= 2△y+△x (2b-1)

Podem escriure la variable de decisió d_i+1per a la propera relliscada
d_i+1=2△y.x_i+1-2△x.y_i+1+c
d_i+1-d_i=2△y.(x_i+1-x_i)- 2△x(i_i+1-i_i)

Com que x_(i+1)=x_i+1, tenim
d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(i_i+1-i_i)

Casos especials

Si el píxel escollit es troba al píxel superior T (és a dir, d_i≧0)⟹ i_i+1=i_i+1
d_i+1=d_i+2△y-2△x

Si el píxel escollit es troba al píxel inferior T (és a dir, d_i<0)⟹ y_{i+1=yi
di+1=di+2△i}

Finalment, calculem d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-i₁)+2m-1]

Des de mx₁+b-i_i=0 i m = , tenim
d₁=2△y-△x

Avantatge:

1. Implica només aritmètica de nombres enters, de manera que és senzill.

2. Evita la generació de punts duplicats.

3. Es pot implementar mitjançant maquinari perquè no utilitza multiplicació i divisió.

4. És més ràpid en comparació amb DDA (Digital Differential Analyzer) perquè no implica càlculs de coma flotant com l'algoritme DDA.

Desavantatge:

1. Aquest algorisme només està pensat per al dibuix de línies bàsics. La inicialització no forma part de l'algorisme de línies de Bresenham. Per tant, per dibuixar línies suaus, hauríeu de buscar un algorisme diferent.

Algoritme de línia de Bresenham:

Pas 1: Inicia l'algoritme

Pas 2: Declara la variable x₁,x₂,i₁,i₂,d,i₁,i₂,dx,dy

Pas 3: Introduïu el valor de x₁,i₁,x₂,i₂
On x₁,i₁són les coordenades del punt de partida
I x₂,i₂són les coordenades del punt final

Pas 4: Calcula dx = x₂-x₁
Calcula dy = y₂-i₁
Calcula i₁=2*tu
Calcula i₂=2*(dy-dx)
Calcula d=i₁-dx

Pas 5: Considereu (x, y) com a punt de partida i x_finalcom a valor màxim possible de x.
Si dx<0
Aleshores x = x₂
y = y₂
x_final=x₁
Si dx > 0
Aleshores x = x₁
y = y₁
x_final=x₂

Pas 6: Generar punt a les coordenades (x,y).

Pas 7: Comproveu si s'ha generat una línia sencera.
Si x > = x_final
Atura.

Pas 8: Calcula les coordenades del píxel següent
Si d<0
Aleshores d = d + i₁
Si d ≧ 0
Aleshores d = d + i₂
Increment y = i + 1

Pas 9: Increment x = x + 1

Pas 10: Dibuixa un punt de les últimes coordenades (x, y).

Pas 11: Aneu al pas 7

Pas 12: Final de l'algoritme

etiquetes html

Exemple: La posició inicial i final de la línia són (1, 1) i (8, 5). Troba punts intermedis.

Solució: x₁=1
i₁=1
x₂=8
i₂=5
dx = x₂-x₁=8-1=7
tu=i₂-i₁=5-1=4
jo₁=2* ∆y=2*4=8
jo₂=2*(∆y-∆x)=2*(4-7)=-6
d = I₁-∆x=8-7=1

Programa per implementar l'algoritme de dibuix de línies de Bresenham:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 

Sortida:

Diferencia entre l'algoritme DDA i l'algoritme de línia de Bresenham: