Algorytm Bresenhama

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

Założenia[edytuj | edytuj kod]

  • 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)\leq 1
  • Krzywa musi być nierosnąca albo niemalejąca

Algorytm i jego działanie[edytuj | edytuj kod]

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 Pi+1 przyjmujemy piksel Ti+1, jeżeli d_i < 0, wybieramy piksel Si+1. Wartość d_i = 0 oznacza, że oba piksele leżą w tej samej odległości i arbitralnie przyjmujemy, ze następny piksel to Ti+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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Założenia[edytuj | edytuj kod]

  • 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ółrzednych,
  • Ś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[edytuj | edytuj kod]

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^2b^2\left( \frac{x^2}{a^2}+\frac{y^2}{b^2}-1\right) =b^2x^2+a^2y^2-a^2b^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})
Algorytm Bresenhama.svg

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)
Algorytm Bresenhama 2.svg

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})na podstawie wartości z poprzedniego kroku (d_i), co wymaga 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:

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^2x_{i+1}+b^2=
=d_i+2b^2x_{i+1}+b^2\;

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:

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^2b^2 =
=b^2(x_i+1+1)^2+a^2(y_i -1-\tfrac{1}{2})-a^2b^2 =
=F(x_i+1,y_i-\tfrac{1}{2})+2b^2x_{i + 1}+b^2-2a^2(y_i -\tfrac{1}{2})+a^2 =
=d_i+2b^2x_{i+1}-2a^2y_{i+1}+b^2\;

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

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^2b^2-b^2(x_i + 1)^2-a^2(y_i -\tfrac{1}{2})^2+a^2b^2=
=b^2(x^2_i+x_i+\tfrac{1}{4})+a^2(y^2_i-2y_i+1)-b^2(x^2_i+2x_i+1)-a^2(y^2_i-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})

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:

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^2b^2=\;
=b^2(x_i+1+\tfrac{1}{2})^2+a^2(y_i-1-1)^2-a^2b^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^2x_{i+1} -2a^2y_{i+1}+a^2\;

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:

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^2b^2=\;
=b^2(x_i+\tfrac{1}{2})^2+a^2(y_i-1-1)^2-a^2b^2=\;
=F(x_i+\tfrac{1}{2},y_i-1)-2a^2(y_i-1)+a^2=\;
=d_i-2a^2y_{i+1}+a^2\;

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]