Пређи на садржај

Брезенхамов линијски алгоритам

С Википедије, слободне енциклопедије

Брезенхамов линијски алгоритам је алгоритам рачунарске графике који се користи за растеризацију линије тј. цртање линије у растерском облику. То подразумева да је за линију задату са две тачке почетном (x0, y0) и крајњом (x1, y1) потребно одредити скуп пиксела које треба обојити тако да тај скуп пиксела представља што бољу апрокцимацију линије.

Алгоритам је развио Џек Елтон Брезенхам 1962. у IBM-у. Био је то један од најранијих алгоритама рачунарске графике. Пошто је линија објекат од изузетног значаја за графику и често је потребно вршити исцртавање огромног броја линија алгоритам за циљ има ефикасност. Ефикасност се постиже коришћењем искључиво целобројне аритметике чије операције су знатно јефтиније од операција у покретном зарезу.

Једноставност и брзина алгоритма чине да је он и данас у широкој употреби. Једноставност алгоритма омогућава чак и хардверску имплементацију.

Алгоритам

[уреди | уреди извор]

Најпре ће бити описан основни алгоритам за цртање линија а затим постепено увођена побољшања која воде ка извођењу Брезенхамовог алгоритма.

Подразумева се да је линија задата са две тачке, почетном (x0, y0) и крајњом (x1, y1) и да важи x0 < x1. Такође, подразумева се да је потребно нацртати линију дебљине једног пиксела и да је функција за цртање пиксела дата. Алгоритам ће бити изложен само за линије првог квадранта за које важи: тј. да им је коефициент правца већи од 0 а мањи или једнак 1. Овај простор ће бити називан првим октантом. Осталих седам случајева обрађује се симетрично.

Оно што треба нагласити је да је за линије за које важи у свакој колони тј. за свако треба означити тачно један пиксел. За остале линије је потребно означити тачно један пиксел у врсти.

Алгоритам грубе силе

[уреди | уреди извор]

Алгоритам грубе силе за цртање линије заснива се на примени једначине праве. Једначина праве кроз две тачке је:

За свако рачунамо вредност и тада је потребно обојити пиксел .

Овај приступ није добар јер се вредност y увек изнова рачуна и због коришћења аритметичких операција у покретном зарезу.

Инкрементални алгоритам

[уреди | уреди извор]

Вредност y је могуће рачунати на основу претходно израчунатих вредности.

, где је B слободан члан

За свако рачунамо вредност и тада је потребно обојити пиксел .

Овај приступ је добар јер елиминише множење и рачунање из почетка вредности за y. Међутим, опет је проблем рад са операцијама у покретном зарезу пошто је вредност m реална.

Брезенхамов алгоритам

[уреди | уреди извор]

Досадашње проблеме решава Брезенхамов алгоритам.

Пиксели се сада посматрају као чворови квадратне мреже.

Једначина праве у имплицитном облику, записана као функција од (x,y), је:

, где су константе

За тачке на линији је f(x,y) = 0, за тачке испод линије је f(x,y) > 0, за тачке изнад линије је f(x,y) < 0.

Претпоставимо да смо досли до тачке i која се налази на линији. Пошто смо у овом тренутку ограничени на линије из првог октанка следећи пиксел који посматрамо ће имати x координату xi+1. Пошто је коефицијент правца првог у првом октанту већи од 0 а мањи од 1 y координата следећег пиксела ће бити или yi или yi+1. Дакле, имамо две тачке које су кандидати за одабир и треба да одаберемо ону која најбоље апроксимира линију тј. ону која је најближа линији. Тачку са координатама (xi+1, yi) означаваћемо као тачку Е (east), а тачку са координатама (xi+1, yi+1) као тачку NE (northeast).

Коју од ове две тачке треба одабрати одређујемо коришћењем средишње тачке М (midpoint) која има координате (xi+1, yi+½). Ове координате уврштавамо у једначину праве:

Ово је такозвана променљива одлучивања јер на основу њеног знака одређујемо који пиксел бирамо. Ако је вредност d мања од 0 значи да је тачка М изнад праве тј. да је права ближа тачки Е тако да у том случају бојимо пиксел Е. Ако је вредност d већа од нуле то значи да је тачка М испод праве тј. да је права ближа тачки NE и у том случају бојимо пиксел NE.

Вредност променљиве одлучивања може се рачунати инкрементално.

  • Ако је у претходном кораку одабрана тачка Е координате следеће средишње тачке су и када се те координате уврсте у једначину праве добијамо нову вредност функције одлучивања:
  • Ако је у претходном кораку одабрана тачка NЕ координате следеће средишње тачке су и када се те координате уврсте у једначину праве добијамо нову вредност функције одлучивања:

Полазни пиксел је тачка (x0, y0) и он се свакако налази на линији. Почетна вредност променљиве одлучивања је:

Пошто желимо да радимо искључиво са целим бројевима а за одлучивање нам је битан само знак променљиве одлучивања ову вредност можемо помножити са 2 па добијамо:

Због тога се и све остале вредности множе са 2:

  • ако је одабрана тачка Е у претходном кораку
  • ако је одабрана тачка NЕ

Овако је поново уведено множење, али пошто је ово множење са 2 оно може бити извршено као шифтовање улево за једну позицију тако да не утиче значајно на смањење ефикасности алгоритма. Овако добијамо алгоритам који користи искључиво сабирање, одузимање и шифтовање.

Имплементација

[уреди | уреди извор]

Приказана је имплементација у програмском језику C[1]. У првом делу се уместо замена места координатама ради покривања свих осам случајева врши одређивање за које ће вредности бити мењане координате и иницијализација променљиве одлучивања.

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; }
  }
}

Литература

[уреди | уреди извор]

Референце

[уреди | уреди извор]