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
(s₀, t₀) ja (s₁, t₁): janan päätepisteet s- ja t-akseleilla, missä s₀ ≤ s₁

if t₀ < t₁
   tstep := 1
else
   tstep := −1
virhe := w / 2
t := t₀
for each s in [s₀, s₁]
    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

Tähän artikkeliin tai sen osaan on merkitty lähteitä, mutta niihin ei viitata.
Älä poista mallinetta ennen kuin viitteet on lisätty. Voit auttaa Wikipediaa lisäämällä artikkelille asianmukaisia viitteitä. Lähteettömät tiedot voidaan kyseenalaistaa tai poistaa.

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^{[vanhentunut linkki]} (23.1.2008)