Z Wikipedii

Niektóre informacje zawarte w artykule wymagają weryfikacji. Do weryfikacji: wątpliwości co do poprawności (patrz dyskusja)

Algorytm Bresenhama to algorytm służący do rasteryzacji krzywych 2D, czyli do jak najlepszego przybliżenia matematycznych krzywych na siatce pikseli. J. Bresenham w 1965 roku opracował metodę rasteryzacji odcinków, którą następnie przystosowano do rysowania obiektów innego rodzaju (okręgów, 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 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
• = przyrost D_L przy ruchu w lewo (dla odcinka = 0)
• = przyrost D_U przy ruchu w lewo (dla odcinka = 0)
• = przyrost D_L przy ruchu ukośnym (dla odcinka = 0)
• = 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
    • - aktualizacja parametrów pomocniczych
    • - aktualizacja parametrów pomocniczych
  • w przeciwnym razie
    • x: = x + 1 - ruch ukośny
    • y: = y + 1
    • D: = D + D_U - aktualizacja zmiennej decyzyjnej
    • - aktualizacja parametrów pomocniczych
    • - aktualizacja parametrów pomocniczych

[edytuj] Algorytm konwersji odcinka

[edytuj] 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
• Krzywa musi być nierosnąca albo niemalejąca

[edytuj] Algorytm i jego działanie

Załóżmy że krzywa w przedziale [xi, xk] spełnia w/w założenia

Pierwszy piksel stawiamy w punkcie P(xi, yi). 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 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

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 di > 0, to s > t za punkt P_i+1 przyjmujemy piksel T_i+1, jeżeli di < 0, wybieramy piksel S_i+1. Wartość di = 0 oznacza, że oba piksele leżą w tej samej odległości i arbitralnie przyjmujemy, ze następny piksel to T_i+1. Policzmy jeszcze wartość di+1

di+1 = 2dy(xi+1 − x0) − 2dx(yi+1 − y0) + 2dy − dx

oraz różnice di+1 − di

di+1 − di = 2dy(xi+1 − xi) − 2dx(yi+1 − yi)

czyli

di+1 = di + 2dy − 2dx(yi+1 − yi)

gdyż xi+1 = xi + 1. Jeżeli di ­ 0, to yi+1 = yi + 1 (wybieramy piksel Ti+1), co pozwala na uproszczenie obliczeń di+1

di+1 = di + 2(dy − dx)

Analogicznie, gdy di < 0 mamy yi+1 = yi (wybieramy piksel Si+1), i wzór na di+1 ma postać

di+1 = di + 2dy

Z uwagi na rekurencyjną postać wzoru na obliczanie współczynnika di, nazywanego także zmienna decyzyjna, należy jeszcze policzyć wartość początkową d0. Podstawiając xi = x0 oraz yi = y0 do równania

di = 2dy(xi − x0) − 2dx(yi − y0) + 2dy − dx

otrzymujemy wzór na d0

d0 = 2dy − dx

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

[edytuj] Rysowanie odcinka algorytmem Bresenhama

 // x1 , y1 − współrzędne początku odcinka
 // x2 , y2 − współrzędne konca 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);
         }
     }
 }

Rysowanie linii (odcinka) przechodząca przez dwa punkty o współrzędnych P1(x1,y1) i P2(x2,y2) procedura w języku Pascal

 Procedure Linia(x1,y1,x2,y2,Kolor : integer);
 var c,i : integer;
    sx,sy,y,x : real;
  begin
 { if x2<x1 then    {ten warunek nie pozwala rysowac linii 'wygladajacej jak funkcja rosnaca'!!!} 
  begin
   c:=x1;
   x1:=x2;
   x2:=c;
  end;
  if y2<y1 then
  begin
   c:=y2;
   y2:=y1;
   y1:=c;
  end; }
  if (x2-x1)>(y2-y1) then
  begin
    sy:=(y2-y1)/(x2-x1);
    y:=y1;
    for i:=x1 to x2 do 
    begin
      putpixel(i,round(y),Kolor);
      y:=y+sy;
    end;
  end else
  begin
    sx:=(x2-x1)/(y2-y1);
    x:=x1;
    for i:=y1 to y2 do 
    begin
      putpixel(round(x),i,Kolor);
      x:=x+sx;
    end;
  end;
 end;

[edytuj] Algorytm Bresenhama dla okręgu

[edytuj] Założenia

• Rozważamy elipsę w I ćwiartce układu współrzednych,
• Rysowanie elipsy zaczynamy od punktu (0, b),
• W każdym kroku stawiamy symetrycznie 4 punkty elipsy,
• Poczatkową osią wiodacą jest os OX,
• W punkcie zmiany osi wiodącej, współczynnik nachylenia stycznej do elipsy wynosi −1 (tg 135°)

[edytuj] Algorytm i jego działanie

O wyborze piksela decydować będzie wartość funkcji F(x, y) w punkcie środkowym M położonym pomiędzy alternatywnymi pikselami. Gdy osią wiodąca jest OX oblicza się

F (M) = F(xi + 1, yi −1/2)

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

F(M) = F(xi +1/2, yi − 1)

Jeżeli F (M) > 0, to punkt M leży poza elipsa i wybieramy piksel Pi+1 = S. Natomiast, gdy F (M) <= 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel Pi+1 = SE.

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 P0 = (x0, y0) = (0, b)

d0 = F(1, b −1/2)= b²+ a² (−b +1/4)

Jeżeli następnym pikselem jest Pi+1 = E (xi+1 = xi + 1, yi+1 = yi), to wartość zmiennej decyzyjnej wynosi:

di+1=F (xi+1+1,yi+1−1/2)=

b²(xi+1+1)²+a²(yi+1−1/2)²−a²b²=

b²(xi+1+1²+a²(yi−1/2)²-a²b²=

F(xi+1,yi−1/2)+2b*2b(xi+1)+b²=

di+2b²xi+1+b²

Jeżeli następnym pikselem jest Pi+1 = SE (xi+1 = xi+1, yi+1 = yi−1), to wartość zmiennej decyzyjnej wynosi:

di+1=F(xi+1+1,yi+1−1/2)=

b²(xi+1+1)²+a²(yi+1−1/2)²− a²b² =

b²(xi+1+1)²+a²(yi −1−1/2)−a²b² =

F(xi+1,yi−1/2)+2b²(xi + 1)+b²−2a²(yi −1/2)+a² =

di+2b²xi+1−2a²yi+1+b²

Przy zmianie osi wiodącej na OY należy także zmienić wartość zmiennej decyzyjnej. Różnica miedzy „nowa” i „stara” zmienna wynosi:

F(xi+1/2,yi−1)−F(xi+1,yi−1/2)=

b²(xi+1/2)²+a²(yi − 1)²−a²b²−b²(xi + 1)²−a²(yi −1/2)²+a²b²=

b²(x²i+xi+1/4)+a²(y²i−2yi+1)−b²(x2i+2xi+1)−a²)(y²i−yi+1/4)=

b²(xi−2xi+1/4−1)+a²(−2yi+yi+1−1/4)=

b2(−xi−3/4)+a²(−yi+3/4)

Teraz wyliczymy rekurencyjne równania opisujące zmienna decyzyjna, gdy osią wiodąca jest OY . Jeżeli następny piksel jest Pi+1 = SE (xi+1 = xi + 1, yi+1 = yi − 1), to wartość zmiennej decyzyjnej wynosi

di+1=F(xi+1+1/2,yi+1−1)=

b²(xi+1+2)+a²(yi+1−1)²+a²b²=

b²(xi+1+1/2)²+a²(yi−1−1)²+a²b² =

F(xi+1/2,yi−1)+2b²(xi+1)−2a²(yi−1)+a²=

di + 2b²xi+1 −2a²yi+1+a²

Przy wyborze następnego piksela Pi+1 = S (xi+1 = xi, yi+1 = yi−1) wartość zmiennej decyzyjnej wynosi:

di+1=F(xx+1+1/2,yi+1−1)=

b²(xi+1+1/2)²+a²(yi+1−1)²+a²b²=

b²(xi+2)+a²(yi−1−1)+a²b²=

F(xi+1/2,yi−1)−2a2(yi−1)+a²=

di−2a²yi+1+a²

[edytuj] Bibliografia

• J. E. Bresenham, Algorithm for computer control of a digital plotter, IBM Systems Journal, vol. 4, no. 1, 1965

[edytuj] Linki zewnętrzne

• Algorytm Bresenhama