Algorytm Bresenhama

Algorytm Bresenhama służy do rasteryzacji krzywych płaskich, czyli do jak najlepszego ich obrazowania na siatce pikseli. Jack Bresenham w 1965 roku opracował metodę rasteryzacji odcinków, którą następnie przystosowano do rysowania obiektów innego rodzaju (okręgów czy elips).

Siła algorytmu tkwi w prostocie; koszt postawienia jednego piksela to porównanie i jedno dodawanie (dla odcinków) lub porównanie i dwa dodawania (dla okręgów i elips), ponadto algorytm wykonuje obliczenia na liczbach całkowitych, które są bardzo szybkie na wszystkich mikroprocesorach.

Metoda pozwala w bardzo prosty sposób wybierać, które piksele leżą najbliżej rasteryzowanego obiektu (np. odcinka). Zakładając, że poprzednio algorytm zapisał piksel o współrzędnych $(x,y),$ w kolejnym kroku algorytm może zapisać piksel albo $(x+1,y)$ (ruch poziomy), albo $(x+1,y+1)$ (ruch ukośny) – wybór determinuje znak tzw. zmiennej decyzyjnej, której wartość jest po każdym kroku aktualizowana. Aktualizacja polega na dodaniu pewnych wartości, będących w przypadku odcinka stałymi, zaś dla okręgu i elipsy wartościami zmieniającymi się z każdym krokiem:

• D = zmienna decyzyjna
• $D_{L}$ = przyrost D przy ruchu w lewo
• $D_{U}$ = przyrost D przy ruchu ukośnym
• $DD_{L_{L}}$ = przyrost $D_{L}$ przy ruchu w lewo (dla odcinka = 0)
• $DD_{U_{L}}$ = przyrost $D_{U}$ przy ruchu w lewo (dla odcinka = 0)
• $DD_{L_{U}}$ = przyrost $D_{L}$ przy ruchu ukośnym (dla odcinka = 0)
• $DD_{U_{U}}$ = przyrost $D_{U}$ przy ruchu ukośnym (dla odcinka = 0)
• powtarzaj
  • zapisz piksel $(x,y)$
  • jeśli $D>0$
    • $x:=x+1$ – ruch w lewo
    • $D:=D+D_{L}$ – aktualizacja zmiennej decyzyjnej
    • $D_{L}:=D_{L}+DD_{L_{L}}$ – aktualizacja parametrów pomocniczych
    • $D_{U}:=D_{U}+DD_{U_{L}}$ – aktualizacja parametrów pomocniczych
  • w przeciwnym razie
    • $x:=x+1$ – ruch ukośny
    • $y:=y+1$
    • $D:=D+D_{U}$ – aktualizacja zmiennej decyzyjnej
    • $D_{L}:=D_{L}+DD_{L_{U}}$ – aktualizacja parametrów pomocniczych
    • $D_{U}:=D_{U}+DD_{U_{U}}$ – aktualizacja parametrów pomocniczych

Algorytm konwersji odcinka

Założenia

• Kąt pomiędzy styczną a osią OX, nie może przekraczać 45 stopni,
  • Jeśli krzywa może zostać opisana funkcją $y=f(x)$ to musi zostać spełniony warunek $0<f'(x)\leqslant 1$
• Krzywa musi być nierosnąca albo niemalejąca

Algorytm i jego działanie

Załóżmy, że krzywa w przedziale $[x_{i},x_{k}]$ spełnia ww. założenia

Pierwszy piksel stawiamy w punkcie $P(x_{i},y_{i}).$ Drugi natomiast ogranicza się jedynie do dwóch możliwości: $S_{i+1}=(x_{i}+1,y_{i})$ lub $T_{i+1}=(x_{i}+1,y_{i}+1).$ Przyrost w kierunku osi OX (osi wiodącej) jest stały – jeden piksel. Korzystając z równania kierunkowego prostej

$y={\tfrac {dy}{dx}}(x-x_{o})+y_{o}$

policzymy w jakiej odległości znajdują się powyższe piksele od punktu przecięcia łączącego je odcinka z prostą przebiegającą w rzeczywistym układzie współrzędnych

$s={\tfrac {dy}{dx}}(x_{i}+1-x_{o})-(y_{i}-y_{o})$

$t=(y_{i}+1-y_{o})-{\tfrac {dy}{dx}}(x_{i}+1-x_{o})$

$d_{i}=dx(s-t)=2dy(x_{i}-x_{o})-2dx(y_{i}-y_{o})+2dy-dx$

Ponieważ dx > 0, di określa, która z odległości s i t jest większa. Jeżeli $d_{i}>0,$ to s > t za punkt P_i+1 przyjmujemy piksel T_i+1, jeżeli $d_{i}<0,$ wybieramy piksel S_i+1. Wartość $d_{i}=0$ oznacza, że oba piksele leżą w tej samej odległości i arbitralnie przyjmujemy, że następny piksel to T_i+1. Policzmy jeszcze wartość $d_{i+1}$

$d_{i+1}=2dy(x_{i+1}-x_{0})-2dx(y_{i+1}-y_{0})+2dy-dx$

oraz różnicę $d_{i+1}-d_{i}$

$d_{i+1}-d_{i}=2dy(x_{i+1}-x_{i})-2dx(y_{i+1}-y_{i})$

czyli

$d_{i+1}=d_{i}+2dy-2dx(y_{i+1}-y_{i})$

gdyż $x_{i+1}=x_{i}+1.$

Jeżeli $d_{i}=0,$ to $y_{i+1}=y_{i}+1$ (wybieramy piksel $T_{i+1}$), co pozwala na uproszczenie obliczeń $d_{i+1}$

$d_{i+1}=d_{i}+2(dy-dx)$

Analogicznie, gdy $d_{i}<0$ mamy $y_{i+1}=y_{i}$ (wybieramy piksel $S_{i+1}$), i wzór na $d_{i+1}$ ma postać

$d_{i+1}=d_{i}+2dy$

Z uwagi na rekurencyjną postać wzoru na obliczanie współczynnika $d_{i},$ nazywanego także zmienna decyzyjna, należy jeszcze policzyć wartość początkową $d_{0}.$ Podstawiając $x_{i}=x_{0}$ oraz $y_{i}=y_{0}$ do równania

$d_{i}=2dy(x_{i}-x_{0})-2dx(y_{i}-y_{0})+2dy-dx$

otrzymujemy wzór na $d_{0}$

$d_{0}=2dy-dx$

Implementacja

Implementacja algorytmu Bresenhama musi oczywiście uwzględniać inne możliwe położenia odcinka względem osi OX. Jednak w każdej sytuacji można zastosować opisany wyżej schemat, w razie potrzeby traktując oś OY jako oś wiodącą

Rysowanie odcinka algorytmem Bresenhama

Procedura w języku C:

 // x1 , y1 - współrzędne początku odcinka
 // x2 , y2 - współrzędne końca odcinka
 void BresenhamLine(const int x1, const int y1, const int x2, const int y2)
 {
     // zmienne pomocnicze
     int d, dx, dy, ai, bi, xi, yi;
     int x = x1, y = y1;
     // ustalenie kierunku rysowania
     if (x1 < x2)
     {
         xi = 1;
         dx = x2 - x1;
     }
     else
     {
         xi = -1;
         dx = x1 - x2;
     }
     // ustalenie kierunku rysowania
     if (y1 < y2)
     {
         yi = 1;
         dy = y2 - y1;
     }
     else
     {
         yi = -1;
         dy = y1 - y2;
     }
     // pierwszy piksel
     glVertex2i(x, y);
     // oś wiodąca OX
     if (dx > dy)
     {
         ai = (dy - dx) * 2;
         bi = dy * 2;
         d = bi - dx;
         // pętla po kolejnych x
         while (x != x2)
         {
             // test współczynnika
             if (d >= 0)
             {
                 x += xi;
                 y += yi;
                 d += ai;
             }
             else
             {
                 d += bi;
                 x += xi;
             }
             glVertex2i(x, y);
         }
     }
     // oś wiodąca OY
     else
     {
         ai = ( dx - dy ) * 2;
         bi = dx * 2;
         d = bi - dy;
         // pętla po kolejnych y
         while (y != y2)
         {
             // test współczynnika
             if (d >= 0)
             {
                 x += xi;
                 y += yi;
                 d += ai;
             }
             else
             {
                 d += bi;
                 y += yi;
             }
             glVertex2i(x, y);
         }
     }
 }

Algorytm Bresenhama dla elipsy

Założenia

• Elipsa ma osie zgodne z osiami układu współrzędnych,
• Półosie elipsy mają długości a (wzdłuż osi OX) i b (wzdłuż OY),
• Rozważamy elipsę w I ćwiartce układu współrzędnych,
• Środkiem symetrii elipsy jest środek układu współrzędnych,
• Rysowanie elipsy zaczynamy od punktu (0, b),
• W każdym kroku stawiamy symetrycznie 4 punkty elipsy,
• Początkową osią wiodacą jest oś OX,
• W punkcie zmiany osi wiodącej, współczynnik nachylenia stycznej do elipsy wynosi -1 (tg 135°)

Algorytm i jego działanie

Przybliżana elipsa ma równanie:

${\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}-1=0$

O wyborze piksela decydować będzie wartość funkcji

$F(x,y)=a^{2}b^{2}\left({\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}-1\right)=b^{2}x^{2}+a^{2}y^{2}-a^{2}b^{2}$

w punkcie środkowym M położonym pomiędzy alternatywnymi pikselami. Gdy osią wiodąca jest OX oblicza się

$F(M)=F(x_{i}+1,y_{i}-{\tfrac {1}{2}})$

Jeżeli F (M) > 0, to punkt M leży na zewnątrz elipsy i wybieramy piksel $P_{i+1}=SE.$ Natomiast, gdy F (M)⇐ 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel $P_{i+1}=E.$ Gdy osią wiodąca jest OY oblicza się

$F(M)=F(x_{i}+{\tfrac {1}{2}},y_{i}-1)$

Jeżeli $F(M)>0,$ to punkt M leży na zewnątrz elipsy i wybieramy piksel $P_{i+1}=S.$ Natomiast, gdy $F(M)\leqslant 0,$ to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel $P_{i+1}=SE.$ Algorytm nie wymaga jednak wyliczania każdorazowo wartości funkcji $F(M).$ Jego siła leży w możliwości wyliczania wartości tej funkcji (czyli zmiennej decyzyjnej) w kolejnym kroku $(d_{i+1})$ mniej obliczeń.

Zgodnie z przyjętymi założeniami elipsę zaczynamy rysować w punkcie $(0,b).$ Ponieważ osią wiodącą jest wówczas OX policzymy wartość zmiennej decyzyjnej d dla piksela startowego $P_{0}=(x_{0},y_{0})=(0,b)$

$d_{0}=F(1,b-{\tfrac {1}{2}})=b^{2}+a^{2}(-b+{\tfrac {1}{4}})$

Jeżeli następnym pikselem jest $P_{i+1}=E,$ czyli $x_{i+1}=x_{i}+1,y_{i+1}=y_{i},$ to wartość zmiennej decyzyjnej wynosi:

${\begin{aligned}d_{i+1}&=F(x_{i+1}+1,y_{i+1}-{\tfrac {1}{2}})\\&=b^{2}(x_{i+1}+1)^{2}+a^{2}(y_{i+1}-{\tfrac {1}{2}})^{2}-a^{2}b^{2}\\&=b^{2}(x_{i}+1+1)^{2}+a^{2}(y_{i}-{\tfrac {1}{2}})^{2}-a^{2}b^{2}\\&=F(x_{i}+1,y_{i}-{\tfrac {1}{2}})+2b^{2}x_{i+1}+b^{2}\\&=d_{i}+2b^{2}x_{i+1}+b^{2}\end{aligned}}$

Jeżeli następnym pikselem jest $P_{i+1}=SE,$ czyli $x_{i+1}=x_{i}+1,y_{i+1}=y_{i}-1,$ to wartość zmiennej decyzyjnej wynosi:

${\begin{aligned}d_{i+1}&=F(x_{i+1}+1,y_{i+1}-{\tfrac {1}{2}})\\&=b^{2}(x_{i+1}+1)^{2}+a^{2}(y_{i+1}-{\tfrac {1}{2}})^{2}-a^{2}b^{2}\\&=b^{2}(x_{i}+1+1)^{2}+a^{2}(y_{i}-1-{\tfrac {1}{2}})-a^{2}b^{2}\\&=F(x_{i}+1,y_{i}-{\tfrac {1}{2}})+2b^{2}x_{i+1}+b^{2}-2a^{2}(y_{i}-{\tfrac {1}{2}})+a^{2}\\&=d_{i}+2b^{2}x_{i+1}-2a^{2}y_{i+1}+b^{2}\end{aligned}}$

Przy zmianie osi wiodącej na OY należy także zmienić wartość zmiennej decyzyjnej. Różnica między „nową” i „starą” zmienną wynosi:

${\begin{aligned}&F(x_{i}+{\tfrac {1}{2}},y_{i}-1)-F(x_{i+1},y_{i}-{\tfrac {1}{2}})\\={}&b^{2}(x_{i}+{\tfrac {1}{2}})^{2}+a^{2}(y_{i}-1)^{2}-a^{2}b^{2}-b^{2}(x_{i}+1)^{2}-a^{2}(y_{i}-{\tfrac {1}{2}})^{2}+a^{2}b^{2}\\={}&b^{2}(x_{i}^{2}+x_{i}+{\tfrac {1}{4}})+a^{2}(y_{i}^{2}-2y_{i}+1)-b^{2}(x_{i}^{2}+2x_{i}+1)-a^{2}(y_{i}^{2}-y_{i}+{\tfrac {1}{4}})\\={}&b^{2}(x_{i}-2x_{i}+{\tfrac {1}{4}}-1)+a^{2}(-2y_{i}+y_{i}+1-{\tfrac {1}{4}})\\={}&b^{2}(-x_{i}-{\tfrac {3}{4}})+a^{2}(-y_{i}+{\tfrac {3}{4}})\end{aligned}}$

Teraz wyliczymy rekurencyjne równania opisujące zmienną decyzyjną, gdy osią wiodącą jest OY. Jeżeli następnym pikselem jest $P_{i+1}=SE,$ czyli $x_{i+1}=x_{i}+1,y_{i+1}=y_{i}-1,$ to wartość zmiennej decyzyjnej wynosi:

${\begin{aligned}d_{i+1}&=F(x_{i+1}+{\tfrac {1}{2}},y_{i+1}-1)\\&=b^{2}(x_{i+1}+{\tfrac {1}{2}})^{2}+a^{2}(y_{i+1}-1)^{2}-a^{2}b^{2}\\&=b^{2}(x_{i}+1+{\tfrac {1}{2}})^{2}+a^{2}(y_{i}-1-1)^{2}-a^{2}b^{2}\\&=F(x_{i}+{\tfrac {1}{2}},y_{i}-1)+2b^{2}(x_{i}+{\tfrac {1}{2}})-2a^{2}(y_{i}-1)+a^{2}+b^{2}\\&=d_{i}+2b^{2}x_{i+1}-2a^{2}y_{i+1}+a^{2}\end{aligned}}$

Przy wyborze następnego piksela $P_{i+1}=S,$ czyli $x_{i+1}=x_{i},y_{i+1}=y_{i}-1,$ wartość zmiennej decyzyjnej wynosi:

${\begin{aligned}d_{i+1}&=F(x_{i+1}+{\tfrac {1}{2}},y_{i+1}-1)\\&=b^{2}(x_{i+1}+{\tfrac {1}{2}})^{2}+a^{2}(y_{i+1}-1)^{2}-a^{2}b^{2}\\&=b^{2}(x_{i}+{\tfrac {1}{2}})^{2}+a^{2}(y_{i}-1-1)^{2}-a^{2}b^{2}\\&=F(x_{i}+{\tfrac {1}{2}},y_{i}-1)-2a^{2}(y_{i}-1)+a^{2}\\&=d_{i}-2a^{2}y_{i+1}+a^{2}\end{aligned}}$

Bibliografia

• J.E. Bresenham. Algorithm for computer control of a digital plotter. „IBM Systems Journal”. 4 (1), 1965. [zarchiwizowane z adresu 2008-05-28]. (ang.). brak numeru strony
• Michał Jankowski: Elementy grafiki komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, s. 27–34. ISBN 83-204-1326-5.

Linki zewnętrzne

• Algorytm Bresenhama. wm.ite.pl. [zarchiwizowane z tego adresu (2017-11-12)].