Algorytm Bresenhama

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 , w kolejnym kroku algorytm może zapisać piksel albo (ruch poziomy), albo (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
  • = przyrost D przy ruchu w lewo
  • = przyrost D przy ruchu ukośnym
  • = przyrost przy ruchu w lewo (dla odcinka = 0)
  • = przyrost przy ruchu w lewo (dla odcinka = 0)
  • = przyrost przy ruchu ukośnym (dla odcinka = 0)
  • = przyrost przy ruchu ukośnym (dla odcinka = 0)
  • powtarzaj
    • zapisz piksel
    • jeśli
      • - ruch w lewo
      • - aktualizacja zmiennej decyzyjnej
      • - aktualizacja parametrów pomocniczych
      • - aktualizacja parametrów pomocniczych
    • w przeciwnym razie
      • - ruch ukośny
      • - aktualizacja zmiennej decyzyjnej
      • - aktualizacja parametrów pomocniczych
      • - aktualizacja parametrów pomocniczych

Algorytm konwersji odcinka[edytuj]

Założenia[edytuj]

  • Kąt pomiędzy styczną a osią OX, nie może przekraczać 45 stopni,
    • Jeśli krzywa może zostać opisana funkcją to musi zostać spełniony warunek
  • Krzywa musi być nierosnąca albo niemalejąca

Algorytm i jego działanie[edytuj]

Załóżmy że krzywa w przedziale spełnia ww. założenia

Pierwszy piksel stawiamy w punkcie . Drugi natomiast ogranicza się jedynie do dwóch możliwości: lub . 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

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

oraz różnicę

czyli

gdyż . Jeżeli , to (wybieramy piksel ), co pozwala na uproszczenie obliczeń

Analogicznie, gdy mamy (wybieramy piksel ), i wzór na ma postać

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

otrzymujemy wzór na

Implementacja[edytuj]

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]

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]

Założenia[edytuj]

  • 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]

Przybliżana elipsa ma równanie:

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

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

Algorytm Bresenhama.svg

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

Algorytm Bresenhama 2.svg

Jeżeli to punkt M leży na zewnątrz elipsy i wybieramy piksel . Natomiast, gdy to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel . Algorytm nie wymaga jednak wyliczania każdorazowo wartości funkcji . Jego siła leży w możliwości wyliczania wartości tej funkcji (czyli zmiennej decyzyjnej) w kolejnym kroku na podstawie wartości z poprzedniego kroku co wymaga mniej obliczeń.

Zgodnie z przyjętymi założeniami elipsę zaczynamy rysować w punkcie Ponieważ osią wiodącą jest wówczas OX policzymy wartość zmiennej decyzyjnej d dla piksela startowego

Jeżeli następnym pikselem jest czyli to wartość zmiennej decyzyjnej wynosi:

Jeżeli następnym pikselem jest czyli , to wartość zmiennej decyzyjnej wynosi:

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

Teraz wyliczymy rekurencyjne równania opisujące zmienną decyzyjną, gdy osią wiodącą jest OY . Jeżeli następnym pikselem jest czyli to wartość zmiennej decyzyjnej wynosi:

Przy wyborze następnego piksela czyli wartość zmiennej decyzyjnej wynosi:

Bibliografia[edytuj]

Linki zewnętrzne[edytuj]