« poprzedni punkt 


5. Wypełnianie

Ważną operacją w grafice 2D jest wypełnianie wnętrza figur. Możliwe są różne warianty wypełniania. Wnętrze może być wypełnione jednolitą barwą, zmienną barwą (wypełnienie tonalne) albo teksturą. Przykłady wypełniania pokazano na rysunku VI.12.

Rys. VI.12. Przykłady wypełniania wnętrza figury: a) ciągłe, b) tonalne, c) teksturą

Spróbujmy teraz zastanowić się jak może wyglądać algorytm wypełniania jednolitą barwą. Zakładamy, że znany jest kontur figury i że jest on zamknięty. Wśród stosowanych metod można wyróżnić dwie grupy: metody przeglądania wierszami oraz metody z punktem początkowym.

W metodach przeglądania wierszami występują dwie fazy. W pierwszej fazie, dla każdego wiersza rastra znajduje się przecięcia z konturami obiektów i ustala się pary punktów przecięcia, między którymi należy dokonać wypełnienia. W drugiej fazie ma miejsce wypełnianie odcinków wyznaczonych w pierwszej fazie. Na rysunku VI.13 pokazano przykładowe linie rastra przecinające wielokąt i zaznaczono punkty przecięć z krawędziami wielokąta. W drugiej fazie zostaną wypełnione odcinki ograniczone przez pary punków P1(1,2), P2(3,4), P3(5,6).

Rys. VI.13. Wyznaczanie odcinków należących do wnętrza wielokąta, które w drugiej fazie algorytmu przeglądania wierszami zostaną wypełnione

Algorytm koncepcyjnie jest prosty i nie stwarza istotnych problemów implementacyjnych w przypadku wielokątów wypukłych, zwłaszcza trójkątów. Przy konkretnej implementacji, dla ustalonej klasy obiektów, trzeba zwracać uwagę na wierzchołki. Na ogół konieczne jest wyróżnienie dwóch klas wierzchołków: takich, dla których dwie stykające się w wierzchołku krawędzie leżą po jednej stronie linii rastra i takie, dla których krawędzie leżą po obu stronach linii rastra (por. rysunek VI.14).

Rys. VI.14. Dwa rodzaje wierzchołków

W grupie metod z punktem początkowym wypełnianie zaczyna się od znanego punktu należącego do wnętrza figury. W jednym z wariantów metody, określanym jako metoda z czterema sąsiadami, w każdym kroku próbuje się wypełnić cztery piksele sąsiednie w stosunku do rozpatrywanego piksela (por. rysunek VI.15 a). Kolejność analizowanych pikseli może być różna, z tym, że zawsze rozpatrywany piksel należy do listy aktywnych pikseli - tych, które leżą na obrzeżu już wypełnionego obszaru. Rozważa się oczywiście wyłącznie punkty należące do wnętrza figury.

Przykładowa kolejność postępowania może być następująca. Od punktu początkowego poruszamy się w lewo wzdłuż wiersza rastra aż do napotkania brzegu obszaru. Następnie w tym samym wierszu poruszamy się w prawo od punktu początkowego aż do napotkania brzegu obszaru. Z kolei przechodzimy do sąsiedniego wiersza i powtarzamy procedurę, zaczynając od punktu leżącego nad punktem początkowym. Powtarzamy to dopóki jest to możliwe. Następnie przechodzimy do wiersza poniżej wiersza, w którym leży punkt początkowy i postępujemy podobnie jak poprzednio. Następnie sprawdzamy stan listy aktywnych pikseli (lista ta jest przez cały czas aktualizowana) i próbujemy kontynuować procedurę od pierwszego piksela znalezionego na liści aktywnych pikseli itd. Na rysunku VI.15 zilustrowano opisany sposób postępowania, pokazując pewien pośredni stan realizacji wypełniania. Na niebiesko zaznaczono punkt początkowy. Zielonym kolorem wyróżniono piksele znajdujące się na liście aktywnych pikseli.

Rys. VI.15. Ilustracja metody wypełniania z punktem początkowym. a) Cztery punkty sąsiednie w stosunku do piksela. b) Wypełnianie od punktu zaznaczonego na niebiesko - etap pośredni

Zauważmy, że algorytm może wypełniać figury zarówno wypukłe jak i niewypukłe.


« poprzedni punkt