Bresenhamin algoritmi

Tietojenkäsittelytieteessä Bresenhamin algoritmi on tehokas tapa rasteroida jana eli piirtää viiva kuvaruudulle. Bresenhamin algoritmiksi kutsutaan kaikkia jananpiirtoalgoritmeja, jotka muistuttavat toiminnaltaan alkuperäistä algoritmia.

Piirtämisen lisäksi janan rasterointi soveltuu muun muassa näkyvyyden ja etenemisen mallintamiseen sekä rasterikuvien ja geometristen muotojen välisten törmäysten havaitsemiseen.

Pelkkien kokonaislukujen käyttö ja sen tuoma numeerinen vakaus erottavat Bresenhamin edukseen muista vastaavista algoritmeista. Sitä voidaan pitää grafiikkaohjelmoinnin alkeisoperaationa.

Algoritmi 

Bresenhamin algoritmi iteroi janan x- ja y-komponenteista pidempää ("leveyskomponenttia") ja korottaa sopivin välein piirtokorkeutta. Sopiva väli ei ole kokonaisluku, joten murtolukua simuloidaan virhemuuttujan avulla. Esimerkissä joka iteraation yhteydessä virhemuuttujaa kasvatetaan korkeuden verran; arvon ylitettyä leveyden piirtokorkeutta nostetaan yhdellä, ja muuttuja palautetaan vähentämällä siitä leveys. On muitakin tapoja toteuttaa virhemuuttuja.

Seuraava pseudokoodi toteuttaa ydinosan Bresenhamin algoritmista. Olkoon s-akseli "leveysakseli" eli joko x- tai y-akseli riippuen siitä, kumpaan akseliin verrattuna jana on loivempi; t-akseli on puolestaan "korkeusakseli". Tarkemmin ilmaistuna valitaan akselit niin, että jana on suoralla t = k s + b, missä k ≤ 1.

Seuraavat muuttujat oletetaan lasketuiksi:
 w: leveys eli janan leveämmän komponentin pituus
 h: korkeus eli janan lyhyemmän komponentin pituus
 w ≥ h
 (s0, t0) ja (s1, t1): janan päätepisteet s- ja t-akseleilla, missä s0 ≤ s1
 
 if t0 < t1
    tstep := 1
 else
    tstep := −1
 virhe := w / 2
 t := t0
 for each s in [s0, s1]
     if s-akseli on x-akseli
         piirrä_piste(x, y)
     else
         piirrä_piste(y, x)
     virhe := virhe + h
     if virhe >= w
         t := t + tstep
         virhe := virhe − w

Virhemuuttuja asetetaan aluksi puoliväliin, jotta lopputulos olisi symmetrinen: ilman sitä esimerkiksi jana (0,0) → (100,1) voisi näyttää hieman vääristyneeltä.

Koordinaatit kuvaavat kuvapisteiden keskikohtia, ei reunoja: Jana (0,0) → (1,1) ei tarkoita janaa yhden kuvapisteen kulmasta kulmaan, vaan janaa kuvapisteen keskustasta toiseen.

Toteutusta voidaan optimoida esimerkiksi laskemalla virhemuuttuja hieman eri tavalla, jolloin silmukassa voidaan käyttää nopeaa kahdella kertomista.

Lähteet 
 Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965.
 Colin Flanagan: The Bresenham Line-Drawing Algorithm (24.7.2007)
 C-kielinen Bresenhamin algoritmi Ed Angelin kirjasta Interactive Computer Graphics: A Top-Down Approach with OpenGL – Fourth Edition (23.1.2008)
  Lauri Savioja: TKK:n kurssin Tietokonegrafiikan perusteet, syksy 2007, luentokalvot: Viivan toteutus (23.1.2008)

Aiheesta muualla 

Algoritmit
Tietokonegrafiikka