26 KB
Lab1.zip

ZADATAK VJEŽBE

Osmisliti algoritam iscrtavanja linije na zaslonu računala temeljen na Bresenhamovom postupku. Napraviti demonstracijski program u kojem usporediti učinak razvijenog algoritma i algoritma primijenjenog u programskom paketu u širokoj uporabi (Glut).

KONCEPTUALNO RJEŠENJE

Problem iscrtavanja linije se svodi na odabir točaka na zaslonu koje treba osvijetliti. Bresenhamov postupak zasniva se na praćenju točaka duž one dimenzije koja je dominantnija, uz korigiranje koordinata u drugoj dimenziji praćenjem akumulirane pogreške.

PROGRAMSKO OSTVARENJE

Algoritam koji je korišten je sljedeći (pseudokod):

Neka je (x, y) početna točka, a (xb, yb) završna.
Neka je x0 razlika xb – x, a y0 razlika yb – y.
Pogrešku ćemo evidentirati u varijabli f.

Ako je x-dimenzija linije izrazitija od y-dimenzije, tada:
    Neka je xkorak = sgn (x0)
    Neka je ykorak = (y0) / abs (x0)
    Neka je f = xkorak – 0.5 · sgn (y0)
    Ponavljati sve dok je x različito od xb:
        Ako je predznak pogreške isti kao predznak varijable ykorak:
            Povećati koordinatu y za sgn (y0).
            Korigirati pogrešku f za – sgn (y0).
        Osvijetliti točku (x, y).
        Povećati koordinatu x za vrijednost xkorak.
        Povećati pogrešku f za vrijednost ykorak.

U suprotnom je y-dimenzija linije izrazitija od x-dimenzije, i tada:
    Neka je ykorak = sgn (y0)
    Neka je xkorak = (x0) / abs (y0)
    Neka je f = ykorak – 0.5 · sgn (x0)
    Ponavljati sve dok je y različito od yb:
        Ako je predznak pogreške isti kao predznak varijable xkorak:
            Povećati koordinatu x za sgn (x0).
            Korigirati pogrešku f za – sgn (x0).
        Osvijetliti točku (x, y).
        Povećati koordinatu y za vrijednost ykorak.
        Povećati pogrešku f za vrijednost xkorak.

Napomena: funkcija sgn (x) vraća predznak danog parametra x: –1 ako je broj manji od nule, te 1 u suprotnom.

UPUTE ZA KORIŠTENJE

Program se pokreće bez parametara:

Lab1.exe

Odmah nakon pokretanja, traži se od korisnika da unese početnu točku i završnu točku preko tipkovnice ili mišem:

Čim su određene koordinate obiju točaka, iscrtava se linija koristeći razvijeni algoritam i jedna dodatna linija pomoću već gotovih funkcija iz paketa Glut, 20 točaka iznad prethodne, za usporedbu:

Korisnik zatim može zadati nove koordinate za novu liniju.