GKIW Moduł 3
Z Studia Informatyczne
|
|
Tworzenie obrazu na monitorze lub urządzeniu drukującym wymaga wypełnienia wybranego obszaru pikseli określonymi barwami w taki sposób, aby powstał zamierzony rysunek. Korzystając z edytora graficznego wybieramy pewne obiekty podstawowe – tak zwane prymitywy (np. odcinek) i żądamy narysowania ich w określonym miejscu. Nie zastanawiamy się w tym momencie nad tym, że żądanie to, z pozoru bardzo proste, wymaga rozwiązanie wielu problemów geometrycznych oraz opracowania skutecznych i szybkich algorytmów. I to bez względu na to czy będzie to realizowane przez odpowiednią bibliotekę czy tez sprzętowo przez kartę graficzną |
|
Jednym z podstawowych problemów tego typu jest zadanie narysowania odcinka na mapie pikseli. Najprostszym rozwiązaniem wydaje się poprowadzenie prostej przez końce odcinka i opisanie jej równaniem . Następnie wyznaczenie wartości dla całkowitych wartości odpowiadających kolejnym kolumnom pikseli. Jeśli teraz przybliżymy współrzędne do wartości całkowitej, to otrzymamy współrzędne dla kolejnych pikseli tworzących odcinek tzn. , gdzie jest operacją zaokrąglania do najbliższej wartości całkowitej. Tak skonstruowany algorytm przyrostowy ma podstawową wadę. Wymaga operacji zmiennopozycyjnych (mnożenia, dodawania, zaokrąglania). |
|
Rozwiązanie oparte w całości na arytmetyce stałopozycyjnej zaproponował Bresenham w 1965 roku. Jest to algorytm przyrostowy, w którym jedna współrzędna np. x wzrasta w każdym kroku o 1, tzn. . Bez zmniejszania ogólności można przyjąć, że wystarczy opracować algorytm dla nachylenia odcinka od 0 do 1. (Jest to 1/8 układu współrzędnych. Dla innych wartości można bowiem odpowiednio zamienić zmienne lub znaki przed nimi.) Wzrost y w takim przypadku zależy od wyboru piksela (S lub T), który jest bliżej teoretycznej prostej. O wyborze decyduje zmienna kontrolna d, która jest uaktualniana w każdym kroku. |
|
Pełny algorytm Bresenhama dla x2>x1, y2>y1, 0<m<1 wyglądałby tak:
procedure Bresline (x1,x2, y2,y2,) begin
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
