Brezenhamov linijski algoritam

Brezenhamov linijski algoritam je algoritam računarske grafike koji se koristi za rasterizaciju linije tj. crtanje linije u rasterskom obliku. To podrazumeva da je za liniju zadatu sa dve tačke početnom (x₀, y₀) i krajnjom (x₁, y₁) potrebno odrediti skup piksela koje treba obojiti tako da taj skup piksela predstavlja što bolju aprokcimaciju linije.

Algoritam je razvio Džek Elton Brezenham 1962. u IBM-u. Bio je to jedan od najranijih algoritama računarske grafike. Pošto je linija objekat od izuzetnog značaja za grafiku i često je potrebno vršiti iscrtavanje ogromnog broja linija algoritam za cilj ima efikasnost. Efikasnost se postiže korišćenjem isključivo celobrojne aritmetike čije operacije su znatno jeftinije od operacija u pokretnom zarezu.

Jednostavnost i brzina algoritma čine da je on i danas u širokoj upotrebi. Jednostavnost algoritma omogućava čak i hardversku implementaciju.

Algoritam

Najpre će biti opisan osnovni algoritam za crtanje linija a zatim postepeno uvođena poboljšanja koja vode ka izvođenju Brezenhamovog algoritma.

Podrazumeva se da je linija zadata sa dve tačke, početnom (x₀, y₀) i krajnjom (x₁, y₁) i da važi x₀ < x₁. Takođe, podrazumeva se da je potrebno nacrtati liniju debljine jednog piksela i da je funkcija za crtanje piksela data. Algoritam će biti izložen samo za linije prvog kvadranta za koje važi: $0\leq m={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\leq 1$ tj. da im je koeficient pravca veći od 0 a manji ili jednak 1. Ovaj prostor će biti nazivan prvim oktantom. Ostalih sedam slučajeva obrađuje se simetrično.

Ono što treba naglasiti je da je za linije za koje važi $|m|\leq 1$ u svakoj koloni tj. za svako $x_{0}\leq x\leq x_{1}$ treba označiti tačno jedan piksel. Za ostale linije je potrebno označiti tačno jedan piksel u vrsti.

Algoritam grube sile

Algoritam grube sile za crtanje linije zasniva se na primeni jednačine prave. Jednačina prave kroz dve tačke je:

$y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}.$

Za svako $x=x_{0},...,x_{1}$ računamo vrednost $y$ i tada je potrebno obojiti piksel $(x,\left\lfloor y+0.5\right\rfloor )$.

Ovaj pristup nije dobar jer se vrednost y uvek iznova računa i zbog korišćenja aritmetičkih operacija u pokretnom zarezu.

Inkrementalni algoritam

Vrednost y je moguće računati na osnovu prethodno izračunatih vrednosti.

$y_{i+1}=m*x_{i+1}+B$, gde je B slobodan član

$y_{i+1}=m*(x_{i}+1)+B$

$y_{i+1}=y_{i}+m$

Za svako $x=x_{0},...,x_{1}$ računamo vrednost $y$ i tada je potrebno obojiti piksel $(x,\left\lfloor y+0.5\right\rfloor )$.

Ovaj pristup je dobar jer eliminiše množenje i računanje iz početka vrednosti za y. Međutim, opet je problem rad sa operacijama u pokretnom zarezu pošto je vrednost m realna.

Brezenhamov algoritam

Dosadašnje probleme rešava Brezenhamov algoritam.

Pikseli se sada posmatraju kao čvorovi kvadratne mreže.

Jednačina prave u implicitnom obliku, zapisana kao funkcija od (x,y), je:

$f(x,y)=0=Ax+By+C$, gde su konstante $A=\Delta y,B=-\Delta x,C=(\Delta x)b$

Za tačke na liniji je f(x,y) = 0, za tačke ispod linije je f(x,y) > 0, za tačke iznad linije je f(x,y) < 0.

Pretpostavimo da smo dosli do tačke i koja se nalazi na liniji. Pošto smo u ovom trenutku ograničeni na linije iz prvog oktanka sledeći piksel koji posmatramo će imati x koordinatu x_i+1. Pošto je koeficijent pravca prvog u prvom oktantu veći od 0 a manji od 1 y koordinata sledećeg piksela će biti ili y_i ili y_i+1. Dakle, imamo dve tačke koje su kandidati za odabir i treba da odaberemo onu koja najbolje aproksimira liniju tj. onu koja je najbliža liniji. Tačku sa koordinatama (x_i+1, y_i) označavaćemo kao tačku E (east), a tačku sa koordinatama (x_i+1, y_i+1) kao tačku NE (northeast).

Koju od ove dve tačke treba odabrati određujemo korišćenjem središnje tačke M (midpoint) koja ima koordinate (x_i+1, y_i+½). Ove koordinate uvrštavamo u jednačinu prave:

$d=f(x_{i}+1,y_{i}+{\frac {1}{2}})=Ax_{i}+A+By_{i}+{\frac {1}{2}}B+C$

Ovo je takozvana promenljiva odlučivanja jer na osnovu njenog znaka određujemo koji piksel biramo. Ako je vrednost d manja od 0 znači da je tačka M iznad prave tj. da je prava bliža tački E tako da u tom slučaju bojimo piksel E. Ako je vrednost d veća od nule to znači da je tačka M ispod prave tj. da je prava bliža tački NE i u tom slučaju bojimo piksel NE.

Vrednost promenljive odlučivanja može se računati inkrementalno.

• Ako je u prethodnom koraku odabrana tačka E koordinate sledeće središnje tačke su $M_{E}=(x_{i}+2,y_{i}+{\frac {1}{2}})$ i kada se te koordinate uvrste u jednačinu prave dobijamo novu vrednost funkcije odlučivanja:

$d_{new}=f(x_{i}+2,y_{i}+{\frac {1}{2}})=(Ax_{i}+1)+A+By_{i}+{\frac {1}{2}}B+C$

$d_{new}=d_{old}+A=d_{old}+\Delta y$

• Ako je u prethodnom koraku odabrana tačka NE koordinate sledeće središnje tačke su $M_{NE}=(x_{i}+2,y_{i}+{\frac {3}{2}})$ i kada se te koordinate uvrste u jednačinu prave dobijamo novu vrednost funkcije odlučivanja:

$d_{new}=f(x_{i}+2,y_{i}+{\frac {3}{2}})=(Ax_{i}+1)+A+By_{i}+{\frac {3}{2}}B+C$

$d_{new}=d_{old}+A+B=d_{old}+\Delta y-\Delta x$

Polazni piksel je tačka (x₀, y₀) i on se svakako nalazi na liniji. Početna vrednost promenljive odlučivanja je:

$d_{start}=f(x_{0}+1,y_{0}+{\frac {1}{2}})=Ax_{0}+A+By_{0}+{\frac {1}{2}}B+C=f(x_{0},y_{0})+A+{\frac {1}{2}}B=A+{\frac {1}{2}}B$

Pošto želimo da radimo isključivo sa celim brojevima a za odlučivanje nam je bitan samo znak promenljive odlučivanja ovu vrednost možemo pomnožiti sa 2 pa dobijamo: $d_{start}=2A+B$

Zbog toga se i sve ostale vrednosti množe sa 2:

• ako je odabrana tačka E u prethodnom koraku $d_{new}=d_{old}+2\Delta y$
• ako je odabrana tačka NE $d_{new}=d_{old}+2\Delta y-2\Delta x$

Ovako je ponovo uvedeno množenje, ali pošto je ovo množenje sa 2 ono može biti izvršeno kao šiftovanje ulevo za jednu poziciju tako da ne utiče značajno na smanjenje efikasnosti algoritma. Ovako dobijamo algoritam koji koristi isključivo sabiranje, oduzimanje i šiftovanje.

Implementacija

Prikazana je implementacija u programskom jeziku C. U prvom delu se umesto zamena mesta koordinatama radi pokrivanja svih osam slučajeva vrši određivanje za koje će vrednosti biti menjane koordinate i inicijalizacija promenljive odlučivanja.

void line(int x0, int y0, int x1, int y1) {
 
  int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1; 
  int err = (dx>dy ? dx : -dy) << 1, e2;
 
  for(;;){
    setPixel(x0,y0);
    if (x0==x1 && y0==y1) break;
    e2 = err;
    if (e2 >-dx) { err -= dy; x0 += sx; }
    if (e2 < dy) { err += dx; y0 += sy; }
  }
}

Vidi još

• Sajrus-Bekov algoritam

Literatura

• Janičić, Predrag (2008). Rečunarska grafika (PDF). elektronsko izdanje.