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ä]
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
[muokkaa | muokkaa wikitekstiä] |
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)
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]
Kuvia tai muita tiedostoja aiheesta Bresenhamin algoritmi Wikimedia Commonsissa
