Algoritmi za crtanje linija

Sa Wikipedije, slobodne enciklopedije

Geometrijski opis objekta određuje lokaciju i oblik objekta koji će se nalaziti u prikazu. Na primjer kutija je opisana pložajem njenih uglova (vertices), lopta sa pozicijom centra i poluprečnikom, prava linija je definisana dvjema krajnjim tačkama.

Crvenim kružićima je predstavljena stvarna putanja linije, a ono što mi vidimo na raster monitoru je stepenasti efekt „jaggies“ uzrokovan kada se linija generira kao serija pixel pozicija.

Za prikaz linije na monitoru, grafički sistem mora prvo da iscrta krajnje tačke linije u integer koordinatama monitora, te da odredi najbliže piksele duž putanje između krajnjih tačaka. Zatim se boja za liniju učitava u frame buffer na odgovarajućim pixel koordinatama. Čitajući iz frame buffera, video kontroler crta pixele na monitor. Ovaj proces digitalizira liniju u set diskretnih integer pozicija (cjelobrojnih pozicija), koje generalno, samo aproksimiraju stvarnu putanju linije. Izračunate pozicije linije (10.48 , 19.51), na primjer, se konvertuju u pixel pozicije (10 , 21). Zaokruživanje koordinatnih vrijednosti na integer vrijednosti uzrokuje da linija bude iscrtana stepenasto, efekat nazvan „jaggies“ koji vidimo na slici. U grafici se takve pojave opisuju kao aliasing. Efekat je lakše uočljiv na monitorima manjih rezolucija, a jedan od načina poboljšanja je prikazivanje na većim rezolucijama. Efektivnije metode - antialiasing, za glađenje ili peglanje linije se zasnivaju na podešavanju pixel intesiteta duž putanje linije.

• Digitalni diferencijalni analizator - DDA linijski algoritam
• Bresenhamov linijski algoritam