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 ${\displaystyle (x,y),}$ w kolejnym kroku algorytm może zapisać piksel albo ${\displaystyle (x+1,y)}$ (ruch poziomy), albo ${\displaystyle (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
• ${\displaystyle D_{L}}$ = przyrost D przy ruchu w lewo
• ${\displaystyle D_{U}}$ = przyrost D przy ruchu ukośnym
• ${\displaystyle DD_{L_{L}}}$ = przyrost ${\displaystyle D_{L}}$ przy ruchu w lewo (dla odcinka = 0)
• ${\displaystyle DD_{U_{L}}}$ = przyrost ${\displaystyle D_{U}}$ przy ruchu w lewo (dla odcinka = 0)
• ${\displaystyle DD_{L_{U}}}$ = przyrost ${\displaystyle D_{L}}$ przy ruchu ukośnym (dla odcinka = 0)
• ${\displaystyle DD_{U_{U}}}$ = przyrost ${\displaystyle D_{U}}$ przy ruchu ukośnym (dla odcinka = 0)
• powtarzaj
  • zapisz piksel ${\displaystyle (x,y)}$
  • jeśli ${\displaystyle D>0}$
    • ${\displaystyle x:=x+1}$ – ruch w lewo
    • ${\displaystyle D:=D+D_{L}}$ – aktualizacja zmiennej decyzyjnej
    • ${\displaystyle D_{L}:=D_{L}+DD_{L_{L}}}$ – aktualizacja parametrów pomocniczych
    • ${\displaystyle D_{U}:=D_{U}+DD_{U_{L}}}$ – aktualizacja parametrów pomocniczych
  • w przeciwnym razie
    • ${\displaystyle x:=x+1}$ – ruch ukośny
    • ${\displaystyle y:=y+1}$
    • ${\displaystyle D:=D+D_{U}}$ – aktualizacja zmiennej decyzyjnej
    • ${\displaystyle D_{L}:=D_{L}+DD_{L_{U}}}$ – aktualizacja parametrów pomocniczych
    • ${\displaystyle 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ą ${\displaystyle y=f(x)}$ to musi zostać spełniony warunek ${\displaystyle 0<f'(x)\leqslant 1}$
• Krzywa musi być nierosnąca albo niemalejąca

Algorytm i jego działanie

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

Pierwszy piksel stawiamy w punkcie ${\displaystyle P(x_{i},y_{i}).}$ Drugi natomiast ogranicza się jedynie do dwóch możliwości: ${\displaystyle S_{i+1}=(x_{i}+1,y_{i})}$ lub ${\displaystyle 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

${\displaystyle 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

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

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

${\displaystyle 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 ${\displaystyle d_{i}>0,}$ to s > t za punkt P_i+1 przyjmujemy piksel T_i+1, jeżeli ${\displaystyle d_{i}<0,}$ wybieramy piksel S_i+1. Wartość ${\displaystyle 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ść ${\displaystyle d_{i+1}}$

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

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

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

czyli

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

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

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

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

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

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

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

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

otrzymujemy wzór na ${\displaystyle d_{0}}$

${\displaystyle 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:

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

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

${\displaystyle 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ę

${\displaystyle 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 ${\displaystyle P_{i+1}=SE.}$ Natomiast, gdy F (M)⇐ 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel ${\displaystyle P_{i+1}=E.}$ Gdy osią wiodąca jest OY oblicza się

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle P_{i+1}=SE,}$ czyli ${\displaystyle x_{i+1}=x_{i}+1,y_{i+1}=y_{i}-1,}$ to wartość zmiennej decyzyjnej wynosi:

${\displaystyle {\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:

${\displaystyle {\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 ${\displaystyle P_{i+1}=SE,}$ czyli ${\displaystyle x_{i+1}=x_{i}+1,y_{i+1}=y_{i}-1,}$ to wartość zmiennej decyzyjnej wynosi:

${\displaystyle {\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 ${\displaystyle P_{i+1}=S,}$ czyli ${\displaystyle x_{i+1}=x_{i},y_{i+1}=y_{i}-1,}$ wartość zmiennej decyzyjnej wynosi:

${\displaystyle {\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)].