Algorytm Bresenhama

Algorytm Bresenhama

Algorytm Bresenhama jest wykorzystywany do rasteryzacji krzywych płaskich, co oznacza, że umożliwia ich jak najlepsze odwzorowanie na siatce pikseli. W 1965 roku Jack Bresenham stworzył metodę rasteryzacji odcinków, która później została zaadaptowana do rysowania innych obiektów, takich jak okręgi i elipsy.

Główna moc algorytmu wynika z jego prostoty; koszt umieszczenia jednego piksela to zaledwie jedno porównanie i jedno dodawanie (w przypadku odcinków) lub jedno porównanie i dwa dodania (dla okręgów i elips). Dodatkowo, algorytm operuje na liczbach całkowitych, co czyni obliczenia bardzo szybkim procesem na wszystkich mikroprocesorach.

Metoda ta pozwala w prosty sposób określić, które piksele są najbliżej rasteryzowanego obiektu (np. odcinka). Zakładając, że wcześniej 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 zależy od wartości tzw. zmiennej decyzyjnej, której wartość jest aktualizowana po każdym kroku. Aktualizacja polega na dodaniu odpowiednich wartości, które są stałe w przypadku odcinka, natomiast dla okręgu i elipsy zmieniają się z każdym krokiem:

D = zmienna decyzyjna

• D_L = przyrost D przy ruchu w lewo
• D_U = przyrost D przy ruchu ukośnym
• DD_LL = przyrost D_L przy ruchu w lewo (dla odcinka = 0)
• DD_UL = przyrost D_U przy ruchu w lewo (dla odcinka = 0)
• DD_LU = przyrost D_L przy ruchu ukośnym (dla odcinka = 0)
• DD_UU = przyrost D_U przy ruchu ukośnym (dla odcinka = 0)

Powtarzaj

zapisz piksel

(x, y)

jeśli D > 0, to

• x := x + 1 – ruch w lewo
• D := D + D_L – aktualizacja zmiennej decyzyjnej
• D_L := D_L + DD_LL – aktualizacja parametrów pomocniczych
• D_U := D_U + DD_UL – aktualizacja parametrów pomocniczych

w przeciwnym razie

• x := x + 1 – ruch ukośny
• y := y + 1
• D := D + D_U – aktualizacja zmiennej decyzyjnej
• D_L := D_L + DD_LU – aktualizacja parametrów pomocniczych
• D_U := D_U + DD_UU – aktualizacja parametrów pomocniczych

Algorytm konwersji odcinka

Założenia

Kąt pomiędzy styczną a osią OX nie może przekraczać 45 stopni.

Jeśli krzywa może być opisana funkcją

y = f(x) to musi być spełniony warunek 0 < f'(x) ≤ 1.

Krzywa musi być nierosnąca albo niemalejąca.

Algorytm i jego działanie

Załóżmy, że krzywa w przedziale [x_i, x_k] spełnia powyższe założenia. Pierwszy piksel stawiamy w punkcie P(x_i, y_i).

Drugi piksel ogranicza się do dwóch możliwości:

• S_i+1 = (x_i + 1, y_i)
• 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

y = (dy/dx)(x – x_o) + y_o 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

s = (dy/dx)(x_i + 1 – x_o) – (y_i – y_o)

t = (y_i + 1 – y_o) – (dy/dx)(x_i + 1 – x_o)

d_i = dx(s – t) = 2dy(x_i – x_o) – 2dx(y_i – y_o) + 2dy – dx

Jeżeli d_i > 0, to s > t, za punkt P_i+1 przyjmujemy piksel T_i+1, jeżeli d_i < 0, to wybieramy piksel S_i+1. Wartość d_i = 0 oznacza, że oba piksele leżą w tej samej odległości i arbitralnie przyjmujemy, że następny piksel to T_i+1.

Obliczamy jeszcze wartość d_i+1 oraz różnicę d_i+1 – d_i.

Na końcu uzyskujemy wzór na d_i+1 = d_i + 2dy – 2dx(y_i+1 – y_i).

W przypadku d_i = 0, y_i+1 = y_i + 1 (wybieramy piksel T_i+1).

W przypadku d_i < 0, y_i+1 = y_i (wybieramy piksel S_i+1).

Implementacja

Implementacja algorytmu Bresenhama musi uwzględniać różne możliwe położenia odcinka względem osi OX. W każdej sytuacji można zastosować opisany wyżej schemat, traktując oś OY jako oś wiodącą.

Rysowanie odcinka algorytmem Bresenhama
Procedura w języku C:

Algorytm Bresenhama dla elipsy

Założenia

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), oraz rozważamy elipsę w I ćwiartce układu współrzędnych. Środkiem symetrii elipsy jest środek układu współrzędnych. Rysowanie elipsy zaczynamy od punktu (0, b), a w każdym kroku stawiamy symetrycznie 4 punkty elipsy. Początkową osią wiodącą jest oś OX, a w punkcie zmiany osi wiodącej, współczynnik nachylenia stycznej do elipsy wynosi -1 (tg 135°).

Algorytm i jego działanie

Przybliżana elipsa ma równanie:

x²/a² + y²/b² – 1 = 0.

O wyborze piksela decyduje wartość funkcji F(x, y) = b²x² + a²y² – a²b².

W punkcie środkowym M, położonym pomiędzy alternatywnymi pikselami, gdy osią wiodącą jest OX, oblicza się F(M) = F(x_i + 1, y_i – 1/2). Jeżeli F(M) > 0, to punkt M leży na zewnątrz elipsy i wybieramy piksel P_i+1 = SE, natomiast gdy F(M) ≤ 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel P_i+1 = E.

Kiedy osią wiodącą jest OY, oblicza się F(M) = F(x_i + 1/2, y_i – 1). Jeżeli F(M) > 0, to punkt M leży na zewnątrz elipsy i wybieramy piksel P_i+1 = S, natomiast gdy F(M) ≤ 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel P_i+1 = SE.

Algorytm nie wymaga wyliczania każdorazowo wartości funkcji F(M). Jego siła leży w możliwości wyliczania wartości tej funkcji (czyli zmiennej decyzyjnej) w kolejnym kroku (d_i+1) z mniejszą ilością obliczeń.

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 P₀ = (0, b).

d₀ = F(1, b – 1/2) = b² + a²(-b + 1/4).

Jeżeli następnym pikselem jest P_i+1 = E, to wartość zmiennej decyzyjnej wynosi d_i+1 = d_i + 2b²x_i+1 + b².

Jeżeli następnym pikselem jest P_i+1 = S, to wartość zmiennej decyzyjnej wynosi d_i+1 = d_i – 2a²y_i+1 + a².

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

F(x_i + 1/2, y_i – 1) – F(x_i+1, y_i – 1/2).

Teraz wyliczymy rekurencyjne równania opisujące zmienną decyzyjną, gdy osią wiodącą jest OY.

Jeżeli następnym pikselem jest P_i+1 = S, to wartość zmiennej decyzyjnej wynosi:

d_i+1 = F(x_i+1 + 1/2, y_i+1 – 1) = d_i – 2a²y_i+1 + a².

Jeżeli następny piksel to P_i+1 = S, to również d_i+1 = d_i + 2b² – 2a²y_i+1 + a².

Bibliografia

J.E. Bresenham. Algorithm for computer control of a digital plotter. „IBM Systems Journal”. 4 (1), 1965. [zarchiwizowane z adresu 2008-05-28]. (ang.). brak numeru strony

Michał Jankowski: Elementy grafiki komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, s. 27–34. ISBN 83-204-1326-5.

Linki zewnętrzne

Algorytm Bresenhama. wm.ite.pl. [zarchiwizowane z tego adresu (2017-11-12)].