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 ${\displaystyle (x,y),}$ w kolejnym kroku algorytm może zapisać piksel albo ${\displaystyle (x+1,y)}$ (ruch poziomy), albo ${\displaystyle (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
• ${\displaystyle D_{L}}$ = przyrost D przy ruchu w lewo
• ${\displaystyle D_{U}}$ = przyrost D przy ruchu ukośnym
• ${\displaystyle DD_{L_{L}}}$ = przyrost ${\displaystyle D_{L}}$ przy ruchu w lewo (dla odcinka = 0)
• ${\displaystyle DD_{U_{L}}}$ = przyrost ${\displaystyle D_{U}}$ przy ruchu w lewo (dla odcinka = 0)
• ${\displaystyle DD_{L_{U}}}$ = przyrost ${\displaystyle D_{L}}$ przy ruchu ukośnym (dla odcinka = 0)
• ${\displaystyle DD_{U_{U}}}$ = przyrost ${\displaystyle D_{U}}$ przy ruchu ukośnym (dla odcinka = 0)
• powtarzaj
  • zapisz piksel ${\displaystyle (x,y)}$
  • jeśli ${\displaystyle D>0}$
    • ${\displaystyle x:=x+1}$ – ruch w lewo
    • ${\displaystyle D:=D+D_{L}}$ – aktualizacja zmiennej decyzyjnej
    • ${\displaystyle D_{L}:=D_{L}+DD_{L_{L}}}$ – aktualizacja parametrów pomocniczych
    • ${\displaystyle D_{U}:=D_{U}+DD_{U_{L}}}$ – aktualizacja parametrów pomocniczych
  • w przeciwnym razie
    • ${\displaystyle x:=x+1}$ – ruch ukośny
    • ${\displaystyle y:=y+1}$
    • ${\displaystyle D:=D+D_{U}}$ – aktualizacja zmiennej decyzyjnej
    • ${\displaystyle D_{L}:=D_{L}+DD_{L_{U}}}$ – aktualizacja parametrów pomocniczych
    • ${\displaystyle D_{U}:=D_{U}+DD_{U_{U}}}$ – aktualizacja parametrów pomocniczych