Bresenhamov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Bresenhamov algoritem za risanje daljic določi, katere točke v n-dimenzijonalni rasterski mreži, naj bodo narisane, tako da sestavljajo najbližjo aproksimacijo ravni črti med dvema podanima točkama. Uporablja se ga za risanje daljic na računalniški zaslon. Algoritem uporablja preproste operacije kot so celoštevilska seštevanja, odštevanja in premikanje bitov, ki jih zelo hitro izvajajo procesorji v sodobnih računalnikih.

Osnovno idejo Bresenhamovega algoritma prikazujeta spodnji sliki. Slika 1 prikazuje odebeljeno daljico, ki jo želimo narisati. Ker lahko osvetlimo le posamezne piksle, moramo izbrati tiste, ki se daljici najbolj prilegajo. Slika 2 prikazuje najboljšo izbiro.

image:BresenhamSlika3.png


Risanje daljice v prvem oktantu

Rišemo daljico med dvema točkama (x0, y0) in (x1, y1). Za začetek bomo risali v prvem oktantu. Strmina daljice m je omejena med 0 in 1. Strmino daljice izračunamo z: m = \frac{dy}{dx} = \frac{y_1-y_0}{x_1-x_0}.

Nato krčimo metodo risanja linije tako, da vedno, ko riše, poveča x (x povečuje od x0 do x1 s korakom 1). Če narišemo točko pri (x, y), kar pomeni, da "prižgemo" piksel (x, y), ima metoda omejeno območje opcije, kjer lahko postavi naslednjo točko oziroma "prižge" piksel za daljico. Lahko nariše točko pri:

  • (x+1, y) ali
  • (x+1, y+1).

Recimo, da smo na i-tem koraku algoritma. Pravkar smo prižgali piksel (x1, y1). Označimo ta piksel s točko T1. Na spodnji sliki je prikazano, kateri je naslednji piksel, ki se lahko osvetli. Označimo ta piksel s točko T2.

image:BresenhamSlika1.png

Definiramo še napako in jo povežemo z vsako y ordinato. Območje napake bo med -0.5 in 0.5.

Oglejmo si psevdo kodo algoritma:

function daljica(x0, x1, y0, y1) // podani sta začetna in končna točka daljice
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     double napaka := 0
     double deltanapaka := deltay / deltax    //privzemimo, da dx != 0 (daljica ni vertikalna)
     int y := y0
     for x from x0 to x1  //premikamo se po x-osi
         plot(x,y)                         //osvetlimo piksel pri (x, y)
         napaka := napaka + deltanapaka
         if napaka ≥ 0.5 then
             y := y + 1
             napaka := napaka - 1.0

Posplošitev na vse oktante

Zgoraj opisani algoritem deluje samo v prvem oktantu. Bresenhamov algoritem mora delovati v vseh oktantih. Spodnja slika prikazuje, kako je definirana strmina daljic v vsakem oktantu ter relacije med koordinatami.

image:BresenhamSlika2.png

Bresenhamov algoritem mora biti sposoben risati tudi daljice z negativnimi nakloni.

Koda izgleda nekako takole:

 function daljica(x0, x1, y0, y1)
     boolean korak := abs(y1 - y0) > abs(x1 - x0)
     if korak then
         obrni(x0, y0)
         obrni(x1, y1)
     if x0 > x1 then
         obrni(x0, x1)
         obrni(y0, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     double napaka := 0
     double deltanapaka := deltay / deltax
     int y := y0
     if y0 < y1 then ykorak := 1 else ykorak := -1
     for x from x0 to x1
         if korak then plot(y,x) else plot(x,y)
         napaka := napaka + deltanapaka
         if napaka ≥ 0.5 then
             y := y + ykorak
             napaka := napaka - 1.0

Funkcija je sedaj sposobna narisati vse daljice in implementira celoten Bresenhamov algoritem.

Implementacija

Osebna orodja