Algorytm Bresenhama

114 jpg' alt='Algorytm_Bresenhama'>
Algorytm Bresenhama służy do rasteryzacji krzywych płaskich, czyli do jak najlepszego ich obrazowania na siatce pikseli. J. Bresenham w 1965 roku opracował metodę rasteryzacji odcinków którą następnie przystosowano do rysowania teoria_kategorii .php'>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 teoria_kategorii .php'>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 matematyka .php'>stałymi zaś dla okręgu i elipsy wartościami zmieniającymi się z każdym krokiem:Załóżmy że krzywa w matematyka .php'>przedziale spełnia w/w założeniaPierwszy 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 matematyka .php'>stały - jeden piksel. Korzystając z równania kierunkowego prostejpoliczymy 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ędnychPonieważ 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 Pi 1 przyjmujemy piksel Ti 1 jeżeli di < 0, wybieramy piksel Si 1 Wartość di = 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ść di + 1oraz różnicę czyligdyż xi + 1 = xi + 1 Jeżeli di = 0, to yi + 1 = yi + 1 (wybieramy piksel Ti + 1 , co pozwala na uproszczenie obliczeń di + 1Analogicznie, gdy di < 0 mamy yi + 1 = yi (wybieramy piksel Si + 1 , i wzór na di + 1 ma postać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ównaniaotrzymujemy wzór na d0Implementacja 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 linii odcinka przechodząca przez dwa punkty o współrzędnych P1(x1,y1) i P2(x2,y2) procedura w języku PascalPrzybliżana elipsa ma równanie:O wyborze piksela decydować będzie wartość funkcjiw punkcie środkowym M położonym pomiędzy alternatywnymi pikselami. Gdy osią wiodąca jest OX oblicza się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ę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 (di + 1 na podstawie wartości z poprzedniego kroku (di), 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: