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