następny punkt »


1. Odcinki

Na początku zajmiemy się problemem tworzenia odcinka na zasadzie składania go z punktów dostępnych w rastrze.

Zacznijmy od przedstawienia problemu. Zadanie polega na narysowaniu odcinka o znanych współrzędnych początku i końca. Na rysunku VI.1 a pokazano wygląd odcinka do jakiego jesteśmy przyzwyczajeni i jaki możemy uzyskać na papierze, korzystając z ołówka i linijki. Na rysunku VI.1 b pokazano wygląd tego samego odcinka narysowanego na bazie rastra. Oczywiście w tym przykładzie specjalnie została wybrana bardzo mała rozdzielczość rastra, po to żeby dobrze pokazać problem. Ponadto, wybór pikseli wchodzących w skład odcinka był dosyć arbitralny.

Rys. VI.1. Idealny wygląd odcinka (a); odcinek narysowany na rastrze (b)

Zastanówmy się wobec tego nad algorytmem, który umożliwi wybieranie pikseli dla odcinka o zadanych współrzędnych początku i końca. Przyjmijmy, że z naszym rastrem związany jest układ współrzędnych x, y. Wiadomo, że jeżeli znane są współrzędne końców odcinka, to można znaleźć równanie prostej, na której ten odcinek leży. Pamiętamy, że równanie takie ma postać

gdzie m jest współczynnikiem określającym nachylenie prostej i a α jest kątem nachylenia prostej. Znając równanie prostej możemy dalej postępować następująco. Dla kolejnej kolumny rastra o współrzędnej xi można wyznaczyć z równania prostej wartość współrzędnej yi punktu leżącego na prostej. Następnie można znaleźć najbliższy punkt rastra w kolumnie xi. Wyjaśnia to rysunek VI.2. Procedurę należy powtarzać dla każdej kolumny w zakresie zmian współrzędnej x dla odcinka.

Rys. VI.2. Wyznaczanie kolejnych pikseli przy korzystaniu z równania linii

Metoda jest prosta. Jednak dla wyznaczenia kolejnego piksela trzeba wykonać operację mnożenia, dodawania i zaokrąglenia. Liczbę wykonywanych operacji można zmniejszyć jeżeli zauważy się, że przy stałym nachyleniu linii i stałym odstępie między kolumnami pikseli równym 1 wartość yi+1 w kolejnej kolumnie xi+1 można obliczyć dodając do wartości yi stały przyrost Δy = m. Korzystając z zależności:

yi+1= yi + m

dla obliczenia kolejnego piksela trzeba wykonać jedno dodawania i zaokrąglanie. Oszczędzamy wobec tego jedno mnożenie. Jeżeli weźmiemy pod uwagę, że przy tworzeniu jednego obrazu trzeba często narysować kilkadziesiąt odcinków i dla każdego z nich trzeba obliczyć kilkadziesiąt pikseli, to okaże się, że oszczędność w sensie liczby wykonywanych obliczeń staje się znacząca. A pamiętamy, że czas jaki mamy na obliczenie kolejnego obrazu jest zawsze bardzo krótki. Algorytm w przedstawionej wersji jest określany jako algorytm DDA.

Zauważmy, że opisany sposób postępowania jest słuszny przy założeniu, że nachylenie odcinka jest mniejsze od 45º. Przy kątach większych od 45º i mniejszych od 90º trzeba wprowadziæ modyfikację polegającą na tym, że teraz wyznaczane będą piksele w kolejnych wierszach, a nie w kolejnych kolumnach tak jak poprzednio. Gdyby tej zmiany nie wprowadzić liczba pikseli tworzących odcinek mogłaby być zbyt mała. Ilustruje to rysunek VI.3.

Rys. VI.3. Odcinek o nachyleniu większym od 45º. a) Zestaw pikseli przy wybieraniu według kolumn - wariant niepoprawny. b) Zestaw pikseli przy wybieraniu według wierszy - wariant poprawny

Okazuje się, że można jeszcze zmniejszyć czas obliczeń przy rysowaniu odcinka dodając wymóg, by wykonywane były tylko obliczenia stałopozycyjne, a nie zmiennopozycyjne jak to ma miejsce w algorytmie DDA. Odpowiedni algorytm został opracowany przez Bresenhama.

Zanim podamy pełny algorytm Bresenhama spróbujmy zobaczyć jak wyglądało rozumowanie, które doprowadziło do końcowej postaci algorytmu. Zakładamy, że nachylenie odcinka jest mniejsze od 45º (czyli 0 < m <1). Załóżmy, że został już znaleziony piksel w kolumnie xi i mamy znaleźć piksel w następnej kolumnie xi+1. Można zauważyć, że wybór ogranicza się tylko do dwóch pikseli: tego leżącego w tym samym wierszu i tego w wierszu powyżej (zobacz rysunek VI.4.). Pozostaje więc znalezienie prostego kryterium, które pozwoli wybrać piksel przy jak najmniejszym nakładzie obliczeniowym. Bresenham zaproponował, żeby takie kryterium skonstruować wykorzystując różnicę odległości (D1 - D2) rozważanych pikseli od punktu leżącego na rzeczywistym odcinku (por. rysunek VI.4). Można zauważyć, że badając znak tej różnicy można wybrać piksel. Przy znaku minus będzie to górny piksel, przy znaku plus dolny piksel.

Rys. VI.4. Ilustracja toku rozumowania Bresenhama. Na zielono zaznaczono piksele między którymi należy dokonać wyboru w kolejnej kolumnie

Ostatecznie algorytm podany przez Bresenhama ma następującą postać.

  1. Znając współrzędne końców odcinka należy wybrać koniec odcinka o mniejszej współrzędnej x. (Ponieważ algorytm nie zawsze daje ten sam wynik przy rozpoczynaniu od różnych końców odcinka, przyjęto za zasadę, że zawsze zaczyna się od tego końca, dla którego współrzędna x jest mniejsza). Wybrany punkt (x0,y0) jest pierwszym punktem rysowanego odcinka.


  2. Obliczyć pomocnicze wielkości:
  3. Δx = x2 - x1, Δy = y2 - y1, a = 2Δy, b = 2Δy - 2Δx

    oraz wartość początkową pomocniczego parametru decyzyjnego jako

    p0 = 2Δy - Δx.

  4. Dla kolejnych kolumn o współrzędnych xk, zaczynając od k = 0 należy sprawdzić znak wartości pomocniczego parametru pk.
  5. W przypadku gdy pk < 0 następny piksel ma współrzędne (xk+1, yk) i nowa wartość parametru decyzyjnego jest określana z zależności pk+1 = pk + a.

    W przeciwnym przypadku następny punkt ma współrzędne (xk+1, yk+1) i nowa wartość parametru decyzyjnego jest określana z zależności pk+1 = pk + b.

  6. Krok 3 jest powtarzany dopóki nie dojdziemy do końca odcinka.

Zauważmy, że w każdym kroku, w celu wyznaczenia kolejnego piksela musimy wykonać tylko jedno dodawanie całkowitoliczbowe.

Przykład

Korzystając z metody Bresenhama znaleźć kolejne piksele dla odcinka o współrzędnych końców (2,2), (8,5).

  1. Wybieramy pierwszy punkt odcinka. Jest to punkt (2,2).

  2. Obliczamy pomocnicze wielkości

    Δx = 8 - 2 = 6 Δy = 5 - 2 = 3 a = 2 * 3 = 6 b = 6 - 12 = -6

    p0 = 2Δy - Δx = 6 - 6 = 0

  3. Wyznaczamy kolejne piksele
  4. Ponieważ p0 = 0, to następny piksel ma współrzędne (3,3) i

    p1 = p0 + b = 0 - 6 = -6

    Ponieważ p1 < 0, to następny piksel ma współrzędne (4,3) i

    p2 = p1 + a = -6 + 6 = 0

    Ponieważ p2 = 0, to następny piksel ma współrzędne (5,4) i

    p3 = p2 + b = 0 - 6 = -6

    itd. Cały odcinek pokazano na rysunku VI.5.

    Rys. VI.5. Przykład działania algorytmu Bresenhama


 następny punkt »