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[muokkaa | muokkaa wikitekstiä]

Jana rasteroituna Bresenhamin algoritmin avulla.

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.