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
• $D{D}_{L_L}$ = przyrost $D_L$ przy ruchu w lewo (dla odcinka = 0)
• $D{D}_{U_L}$ = przyrost $D_U$ przy ruchu w lewo (dla odcinka = 0)
• $D{D}_{L_U}$ = przyrost $D_L$ przy ruchu ukośnym (dla odcinka = 0)
• $D{D}_{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+D{D}_{L_L}$ – aktualizacja parametrów pomocniczych
    • $D_U:=D_U+D{D}_{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+D{D}_{L_U}$ – aktualizacja parametrów pomocniczych
    • $D_U:=D_U+D{D}_{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^{\prime }(x)⩽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=\frac{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=\frac{dy}{dx}(x_i+1-x_o)-(y_i-y_o)$

$t=(y_i+1-y_o)-\frac{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(\frac{x^2}{a^2}+\frac{y^2}{b^2}-1)=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-\frac{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+\frac{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)⩽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-\frac{1}{2})=b^2+a^2(-b+\frac{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{array}{cc}{d}_{i+1}& =F(x_{i+1}+1,y_{i+1}-\frac{1}{2})\\ & =b^2(x_{i+1}+1{)}^2+a^2(y_{i+1}-\frac{1}{2}{)}^2-a^2{b}^2\\ & =b^2(x_i+1+1{)}^2+a^2(y_i-\frac{1}{2}{)}^2-a^2{b}^2\\ & =F(x_i+1,y_i-\frac{1}{2})+2b^2{x}_{i+1}+b^2\\ & =d_i+2b^2{x}_{i+1}+b^2\end{array}$

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{array}{cc}{d}_{i+1}& =F(x_{i+1}+1,y_{i+1}-\frac{1}{2})\\ & =b^2(x_{i+1}+1{)}^2+a^2(y_{i+1}-\frac{1}{2}{)}^2-a^2{b}^2\\ & =b^2(x_i+1+1{)}^2+a^2(y_i-1-\frac{1}{2})-a^2{b}^2\\ & =F(x_i+1,y_i-\frac{1}{2})+2b^2{x}_{i+1}+b^2-2a^2(y_i-\frac{1}{2})+a^2\\ & =d_i+2b^2{x}_{i+1}-2a^2{y}_{i+1}+b^2\end{array}$

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{array}{cc}& F(x_i+\frac{1}{2},y_i-1)-F(x_{i+1},y_i-\frac{1}{2})\\ =& b^2(x_i+\frac{1}{2}{)}^2+a^2(y_i-1{)}^2-a^2{b}^2-b^2(x_i+1{)}^2-a^2(y_i-\frac{1}{2}{)}^2+a^2{b}^2\\ =& b^2(x_i^2+x_i+\frac{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+\frac{1}{4})\\ =& b^2(x_i-2x_i+\frac{1}{4}-1)+a^2(-2y_i+y_i+1-\frac{1}{4})\\ =& b^2(-x_i-\frac{3}{4})+a^2(-y_i+\frac{3}{4})\end{array}$

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{array}{cc}{d}_{i+1}& =F(x_{i+1}+\frac{1}{2},y_{i+1}-1)\\ & =b^2(x_{i+1}+\frac{1}{2}{)}^2+a^2(y_{i+1}-1{)}^2-a^2{b}^2\\ & =b^2(x_i+1+\frac{1}{2}{)}^2+a^2(y_i-1-1{)}^2-a^2{b}^2\\ & =F(x_i+\frac{1}{2},y_i-1)+2b^2(x_i+\frac{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{array}$

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{array}{cc}{d}_{i+1}& =F(x_{i+1}+\frac{1}{2},y_{i+1}-1)\\ & =b^2(x_{i+1}+\frac{1}{2}{)}^2+a^2(y_{i+1}-1{)}^2-a^2{b}^2\\ & =b^2(x_i+\frac{1}{2}{)}^2+a^2(y_i-1-1{)}^2-a^2{b}^2\\ & =F(x_i+\frac{1}{2},y_i-1)-2a^2(y_i-1)+a^2\\ & =d_i-2a^2{y}_{i+1}+a^2\end{array}$

Bibliografia

• Szablon:Cytuj pismo
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:Cytuj stronę