GKIW Moduł 3

---

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 $y=m\cdot x$. Następnie wyznaczenie wartości $y_i$ dla całkowitych wartości $x_i$ odpowiadających kolejnym kolumnom pikseli. Jeśli teraz przybliżymy współrzędne $y_i$ do wartości całkowitej, to otrzymamy współrzędne dla kolejnych pikseli tworzących odcinek tzn. $y_i=ROUND(m\cdot x_i)$ , gdzie $ROUND()$ 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. $x_{i+1}=x_i+1$ . 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 dx := x2-x1; dy := y2-y1 p1 := 2*dy-dx; p2 := 2*(dy-dx); x := x1; y := y1; xend := x2; set_pixel(x,y); while (x<xend) do begin x := x+1; if (d<0) d := d+p1; else begin d := d+p2; y := y+1; end set_pixel(x,y); end end Algorytm taki wykorzystujący tylko operacje całkowite jest również użyteczny w rozwiązaniach sprzętowych.

---

Niestety korzystanie z rastra również i w przypadku rysowania odcinka może prowadzić do pewnych problemów. Pierwszym jest fakt, że odcinek może nie być symetryczny gdy zamienimy końce startowe. Problem ten wymaga korekty podejmowania decyzji dla d=0 w zależności od wzrostu lub spadku wartości współrzędnych. Poważniejszym problemem jest zmiana jasności. Oba odcinki na rysunku składają się z 7 punktów. Tylko że odcinek po przekątnej rastra jest $\sqrt{2}$ razy dłuższy od odcinka poziomego. Jest to problem związany ze skończoną rozdzielczością rastra i podobnie jak usuwanie wrażenia schodków odcinka rozwiązuje się go zmieniając barwy pikseli sąsiednich.

---

Na podobnej zasadzie jak rysowanie odcinka, Bresenham opracował algorytm rysowania łuku okręgu. Oczywiście zmieniają się w tym przypadku warunki wyboru pikseli, ale algorytm ten również wykorzystuje tylko operacje na liczbach całkowitych. Przy okazji rysowania okręgu warto zwrócić uwagę na parametr charakteryzujący proporcje boków rastra pikseli w pionie i w poziomie, czyli aspekt. Jeśli proporcje rozdzielczości dla kart graficznych 1024x768 wynoszą 4:3, natomiast 1280x1024 wynoszą 5:4, to jeśli chcemy wyświetlić takie obrazy na tym samym monitorze, to proporcje trzeba przeliczyć także w odległości między pikselami. Inaczej narysowany okrąg albo w jednym albo w drugim przypadku będzie miał kształt elipsy.

---

Wypełnianie obszaru jest drugim po rysowaniu odcinka lub łuku, najczęściej występującym problemem związanym z prymitywami. Zadanie dla szczególnych przypadków (np. dla prostokąta) jest zadaniem trywialnym. Natomiast w ogólnym przypadku algorytm powinien pracować poprawnie dla dowolnego wielokąta (także wklęsłego), również dla wielokątów z „dziurami”.

---

Analogicznym zadaniem do wypełniania obszaru jest zmiana barwy w danym obszarze. Zadania są równoważne. Algorytm rozwiązujący jedno z nich może posłużyć do rozwiązania drugiego.

---

Można zauważyć, że jeśli wybierzemy jeden punkt, który jest wewnątrz wypełnianego obszaru, to punkt sąsiedni będzie również punktem wewnątrz albo będzie punktem brzegowym. Wypełnianie przez spójność zakłada znajomość punktu startowego (tzw. „ziarna”) wewnątrz obszaru. Punkt ten jest wypełniany, a następnie startując z niego wypełniamy punkty sąsiednie (jeśli oczywiście istnieją – jeśli nie są już wypełnione, ani nie są punktami granicznymi obszaru). Jednocześnie punkty sąsiednie stają się wyjściowymi dla wypełniania w następnym kroku. Procedura ta jest powtarzana dopóki można wskazać punkty wyjściowe (niewypełnione) wewnątrz obszaru. Warto zwrócić tutaj uwagę na problem sąsiedztwa i konieczność dostosowania do niego kształtu brzegu. Można wyróżnić dwa przypadki. Gdy ruchy po mapie pikseli mogą odbywać się analogicznie do ruchów wieży po szachownicy – wtedy piksel ma 4 sąsiadów – siatka jest czterospójna. Gdy dodamy do tego jeszcze ruchy na ukos (odpowiada to kierunkom ruchów hetmana w szachach), to piksel ma 8 sąsiadów – siatka jest ośmiospójna. Czytelnik może przeanalizować jak powinien wyglądać rozkład pikseli brzegu dla obu przypadków aby stanowił on figurę zamkniętą z punktu widzenia możliwości ruchu. Algorytm wypełniania przez spójność dla siatki czterospójnej. Przyjęto: c_b – barwa brzegu, c_f – barwa wypełnienia procedure wypełnij1(x,y) begin set_pixel(x,y,c_f); if (barwa(x-1,y) inna niż c_b i inna niż c_f) wypełnij1(x-1,y); if (barwa(x+1,y) inna niż c_b i inna niż c_f) wypełnij1(x+1,y); if (barwa(x,y-1) inna niż c_b i inna niż c_f) wypełnij1(x,y-1); if (barwa(x,y+1) inna niż c_b i inna niż c_f) wypełnij1(x,y+1); end Czytelnik może zaproponować korektę obejmującą siatkę ośmiospójną. Zaproponowana postać algorytmu wypełniania przez spójność jest algorytmem rekurencyjnym. Daje to łatwość opisu ale także problemy realizacyjne. Z tego powodu znane są wersje niniejszego algorytmu w postaci nierekurencyjnej. Algorytm wypełniania przez spójność jest czasem nazywany algorytmem przez sianie (punkt startowy jest „ziarnem”).

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---