Wymagane jest zapoznanie się z następującymi podrozdziałami:
P019 - Pierwszy program dla Windows
OL031 - Instalacja biblioteki SDL w środowisku Dev-C++
OL032 - Inicjalizacja biblioteki SDL
OL033 - Powierzchnie graficzne w SDL
OL034 - Przygotowanie plików własnej biblioteki graficznej
OL035 - Rysowanie po powierzchni graficznej
OL036 - algorytm Bresenhama rysowania odcinka
OL037 - obcinanie grafiki do prostokąta
UWAGA!!!Bieżące opracowanie NIE JEST KURSEM programowania biblioteki SDL. Są to materiały przeznaczone do zajęć na kole informatycznym w I LO w Tarnowie.
Przed pracą z tym rozdziałem utwórz w środowisku Dev-C++ nowy projekt SDL i dołącz do niego pliki SDL_gfx.cpp oraz SDL_gfx.h. Jeśli nie przeczytałeś zalecanych rozdziałów, koniecznie zrób to, a wszystko stanie się jasne. W przeciwnym razie odpuść sobie również ten rozdział. Opis funkcji bibliotecznych znajdziesz w podsumowaniu SDL004.
Artykuł nie jest już rozwijany
Grafika komputerowa nie składa się tylko z linii. Bardzo często musimy wypełniać różne obszary określonym kolorem. Istnieje wiele algorytmów wypełniania (ang. fill) na powierzchni rastrowej (tj. powierzchni graficznej zbudowanej z pikseli). Tutaj przeanalizujemy kilka z nich. Algorytmy wypełniania odczytują zawartość pikseli na powierzchni graficznej, aby określić, czy dany piksel należy ustawić na zadany kolor, czy też jest on granicą wypełnianego obszaru. Dlatego musimy posiadać funkcję zwracającą kod piksela na zadanych współrzędnych x ,y. Struktura funkcji gfxGetPixel() jest praktycznie identyczna do funkcji gfxPlot(). Różnica polega jedynie na tym, iż gfxGetPixel() nie zapala piksela, lecz odczytuje jego kod koloru z wyliczonego adresu w buforze ekranu.
UWAGA: Poniższy kod funkcji gfxGetPixel() dopisz do końca pliku SDL_gfx.cpp.
// gfxGetPixel() odczytuje 32 bitowy kod piksela // screen - wskaźnik struktury SDL_Surface // x,y - współrzędne piksela //------------------------------------------------------------------ Uint32 gfxGetPixel(SDL_Surface * screen, Sint32 x, Sint32 y) { return * ((Uint32 *)screen->pixels + y * screen->w + x); }UWAGA: Na końcu pliku nagłówkowego SDL_gfx.h dopisz:
Uint32 gfxGetPixel(SDL_Surface * screen, Sint32 x, Sint32 y);Poniższy program testowy dzieli ekran na cztery równe ćwiartki. W pierwszej ćwiartce rysuje 25 linii na losowych współrzędnych. Następnie odczytuje kolejne piksele z tej ćwiartki i umieszcza je w odpowiedni sposób w pozostałych ćwiartkach, co w wyniku daje efekt kalejdoskopu.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P015 - odczyt pikseli //---------------------- #include <windows.h> #include <SDL/SDL_gfx.h> #include <time.h> // do inicjalizacji generatora pseudolosowego const int SCRX = 320; // stałe określające szerokość i wysokość const int SCRY = 240; // ekranu w pikselach int main(int argc, char *argv[]) { if(SDL_Init(SDL_INIT_VIDEO)) { MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK); exit(-1); } atexit(SDL_Quit); SDL_Surface * screen; if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) { MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK); exit(-1); } if(SDL_MUSTLOCK(screen)) if(SDL_LockSurface(screen) < 0) { MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK); exit(-1); } // inicjujemy generator liczb pseudolosowych srand((unsigned)time(NULL)); // obliczamy współrzędne środka ekranu Sint32 x = screen->w >> 1; Sint32 y = screen->h >> 1; // W pierwszej ćwiartce ekranu rysujemy 25 przypadkowych linii for(int i = 0; i < 25; i++) { Sint32 x1 = rand() % x; Sint32 y1 = rand() % y; Sint32 x2 = rand() % x; Sint32 y2 = rand() % y; Uint32 color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256); gfxLine(screen, x1, y1, x2, y2, color); } // Odczytujemy kolejne piksele z pierwszej ćwiartki i zapisujemy je w pozostałych // ćwiardkach odpowiednio odbijając w pionie i poziomie for(int i = 0; i < x; i++) for(int j = 0; j < y; j++) { Uint32 color = gfxGetPixel(screen, i, j); // odczytujemy piksel z 1 ćwiartki ekranu gfxPlot(screen, screen->w - i - 1, j, color); // kopiujemy do 2 ćwiartki gfxPlot(screen, screen->w - i - 1, screen->h - j - 1, color); // kopiujemy do 3 ćwiartki gfxPlot(screen, i, screen->h - j - 1, color); // kopiujemy do 4 ćwiartki } if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK); return 0; }
W bibliotece SDL istnieje już funkcja wypełniająca zadany obszar prostokątny pikselami w wybranym kolorze. Opisaliśmy ją w rozdziale OL035.
int SDL_FillRect(SDL_Surface * dst, SDL_Rect * dstrect, Uint32 color);Powtórzmy. Parametry wywołania SDL_FillRect() są następujące:
dst - wskazuje strukturę SDL_Surface z powierzchnią graficzną, po której chcemy rysować. Jeśli na powierzchni jest zdefiniowany prostokąt obcinania, to prostokąt wypełniający pojawi się tylko wewnątrz prostokąta obcinania, w obszarze wspólnym. Powierzchnia graficzna może być dowolnego typu, niekoniecznie 32-bitowa. dstrect - wskazuje strukturę SDL_Rect definiującą prostokątny obszar do wypełnienia kolorem na powierzchni graficznej dst. Jeśli wskaźnik ma wartość NULL, to wypełniona zostanie cała powierzchnia graficzna (patrz wyżej - prostokąt obcinania). color - 32 bitowy kolor punktu. Kod piksela musi być kompatybilny z formatem graficznym powierzchni. Dla dowolnej powierzchni można go uzyskać przy pomocy wywołania funkcji biblioteki SDL: Uint32 SDL_MapRGB(SDL_PixelFormat *fmt, Uint8 r, Uint8 g, Uint8 b);
fmt - wskazuje strukturę SDL_PixelFormat definiującą format pikseli. Można tutaj podać zawartość pola format struktury SDL_Surface, po której chcemy rysować. r,g,b - składowe kolorów bazowych: r - czerwony, g - zielony i b - niebieski Jak widzimy, funkcja SDL_FillRect() automatycznie reaguje na prostokąt obcinający, umieszczony w polu clip_rect struktury SDL_Surface, której wskaźnik jest pierwszym argumentem funkcji. Poniższy program testuje tę funkcję razem z funkcją gfxClipRectangle(), która rysuje prostokątne ramki. Definiuje on na ekranie prostokąt obcinający, a następnie rysuje 100 wypełnionych ramek, obciętych do prostokąta.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P016 - wypełnianie prostokątów //------------------------------- #include <windows.h> #include <SDL/SDL_gfx.h> #include <time.h> // do inicjalizacji generatora pseudolosowego const int SCRX = 320; // stałe określające szerokość i wysokość const int SCRY = 240; // ekranu w pikselach int main(int argc, char *argv[]) { if(SDL_Init(SDL_INIT_VIDEO)) { MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK); exit(-1); } atexit(SDL_Quit); SDL_Surface * screen; if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) { MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK); exit(-1); } if(SDL_MUSTLOCK(screen)) if(SDL_LockSurface(screen) < 0) { MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK); exit(-1); } // inicjujemy generator liczb pseudolosowych srand((unsigned)time(NULL)); // tworzymy prostokąt obcinania oraz prostokąt wypełniania SDL_Rect * clip = new SDL_Rect; SDL_Rect * fill = new SDL_Rect; // ustawiamy prostokąt obcinania clip->x = screen->w >> 3; // 1/8 szerokości ekranu clip->y = screen->h >> 3; // 1/8 wysokości ekranu clip->w = screen->w - (screen->w >> 2); clip->h = screen->h - (screen->h >> 2); // Rysujemy żółtą ramkę na krawędzi prostokąta gfxRectangle(screen, clip, 0xffff00); // pomniejszamy prostokąt obcinający clip->x++; clip->y++; clip->w -= 2; clip->h -= 2; // ustawiamy na ekranie obcinanie do prostokąta clip SDL_SetClipRect(screen, clip); // w prostokącie clip rysujemy 100 ramek wypełnionych różnymi kolorami for(int i = 0; i < 100; i++) { fill->x = rand() % ((screen->w >> 1) + (screen->w >> 2)); fill->y = rand() % ((screen->h >> 1) + (screen->h >> 2)); fill->w = 10 + rand() % (screen->w >> 2); fill->h = 10 + rand() % (screen->h >> 2); SDL_FillRect(screen, fill, ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256)); gfxClipRectangle(screen, fill, ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256)); } if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK); return 0; }
W ogólnym przypadku obszar do wypełnienia jest ograniczony linią oraz prostokątem obcinającym i posiada nieregularny kształt. Zadaniem algorytmu wypełniającego jest znalezienie wszystkich pikseli leżących wewnątrz tego obszaru i pokolorowanie ich na zadany kolor.
Na początek podamy kilka ważnych definicji.
Obszar jest cztero-spójny (ang. four-way connected region), jeśli zawarte w nim piksele posiadają ten sam kolor oraz do każdego z nich można dotrzeć poruszając się po pikselach tego obszaru tylko w 4 kierunkach - góra, dół, prawo, lewo. Poniższy rysunek przedstawia obszar cztero-spójny (zielone piksele) oraz drogi dojścia (żółta linia) do każdego z nich. Zwróć uwagę na podobieństwo do grafów, jeśli piksele potraktujemy jako węzły, a drogi dojścia jako krawędzie!
Obszar jest ośmio-spójny (ang. eigth-way connected region), jeśli dodatkowo zezwolimy na drogi przekątne. Wtedy do pikseli obszaru możemy przechodzić na 8 sposobów.
Linia ograniczająca obszar może być cztero- lub ośmio-spójna (podany przez nas algorytm Bresenhama tworzy linie ośmiospójne).
![]() |
![]() |
Zwróć uwagę, iż obszar ośmio-spójny musi być otoczony linią cztero-spójną (w przeciwnym razie "wycieknie" w kierunkach ukośnych), natomiast obszar cztero-spójny można otoczyć linią ośmio-spójną (rysunek po prawej stronie). Zrozumienie tego prostego faktu ma bardzo istotne znaczenie przy doborze odpowiednich algorytmów wypełniających.
Istnieją dwa rodzaje sposobów wypełniania ograniczonych obszarów:
Wypełnianie konturowe (ang boundary-fill) - wszystkie piksele zawarte wewnątrz konturu (zamkniętej linii zbudowanej z pikseli o tym samym kolorze) zostają pokolorowane na ten sam kolor wypełnienia. Zawartość objętego konturem obszaru nie jest istotna (patrz poniżej). Nie może on jedynie zawierać pikseli o kolorze wypełnienia.
Wypełnianie powodziowe (ang. floodfill) - wszystkie piksele spójne (tzn. przyległe w 4 lub 8 kierunkach) do piksela startowego i posiadające ten sam co on kolor zostaną pokolorowane na nowy kolor wypełnienia. Wynika z tego, iż wypełniany obszar musi posiadać przed operacją jednolity kolor. Natomiast obszary przyległe mogą posiadać kolory dowolne, ale różne od koloru wypełnianego obszaru.
![]() |
![]() |
Piksel, od którego rozpoczynamy wypełnianie obszaru nazywamy ziarnem wypełnienia (ang. fill seed). Musi on znajdować się wewnątrz wypełnianego obszaru. Pozostałe piksele znajdujemy wykorzystując cztero- lub ośmio-spójność. Opisane poniżej algorytmy należą do grupy algorytmów wypełniania przez sianie (ang. seed fill algorithm) . Wewnątrz wypełnianego obszaru umieszczamy ziarno wypełnienia, a następnie próbujemy je propagować (siać) w czterech lub ośmiu kierunkach w zależności od rodzaju spójności wypełnianego obszaru. Jeśli ziarno trafi na podatny grunt, to wypełnia go kolorem i próbuje dalej się propagować w czterech lub ośmiu kierunkach. W ten sposób cały obszar zostanie zamalowany określonym kolorem. W zależności od warunków akceptacji ziarna otrzymamy algorytm wypełnienia konturowego - ziarno sieje się tylko na pikselu o kolorze różnym od koloru konturu, lub algorytm wypełnienia powodziowego - ziarno sieje się tylko na pikselu o kolorze pierwszego ziarna. Poniżej prezentujemy oba algorytmy wypełniające wraz z odpowiednimi programami testowymi.
Algorytm cztero-spójnego wypełniania konturowego
Wejście
x, y - współrzędne ziarna wypełnienia. Ziarno musi się zawierać w prostokącie obcinającym clip. ccolor - kolor konturu obejmującego obszar wypełniany fcolor - kolor wypełnienia clip - prostokąt obcinający Wyjście
Wypełnienie kolorem fcolor obszaru ograniczonego konturem w kolorze ccolor i obejmującego punkt x,y. Jeśli obszar rozpościera się poza prostokąt obcinający, to wypełnienie ograniczy się tylko do prostokąta obcinania.
Zmienne pomocnicze
q - stos przechowujący współrzędne punktów. cx1,cy1 - współrzędne lewego górnego narożnika prostokąta obcinania cx2,cy2 - współrzędne prawego dolnego narożnika prostokąta obcinania pcolor - kolor piksela Lista kroków
K01: cx1 ← clip.x ; obliczamy współrzędne wierzchołków prostokąta obcinającego K02: cy1 ← clip.y K03: cx2 ← cx1 + clip.w - 1 K04: cy2 ← cy1 + clip.h - 1 K05: Wyzeruj stos q K06: Umieść na szczycie stosu x i y K07: Dopóki stos q nie jest pusty, wykonuj kroki K08...K20 K08: Pobierz ze stosu x i y ; pobieramy współrzędne ziarna wypełniania K09: Jeżeli x < cx1, wykonaj kolejny obieg pętli K07 ; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania K10: Jeżeli x > cx2, wykonaj kolejny obieg pętli K07 ; jeśli nie, punktu x,y nie przetwarzamy dalej w pętli K11: Jeżeli y < cy1, wykonaj kolejny obieg pętli K07 K12: Jeżeli y > cy2, wykonaj kolejny obieg pętli K07 K13: pcolor = kolor piksela x,y K14: Jeżeli pcolor = ccolor, wykonaj kolejny obieg pętli K07 ; natrafiliśmy na kontur, nie przetwarzamy K15: Jeżeli pcolor = fcolor, wykonaj kolejny obieg pętli K07 ; natrafiliśmy na punkt już wypełniony, nie przetwarzamy K16: Ustaw kolor piksela x,y na fcolor ; piksel kolorujemy na kolor wypełnienia K17: Umieść na stosie x i y - 1 ; na stos przesyłamy współrzędne czterech sąsiednich pikseli K18: Umieść na stosie x + 1 i y K19: Umieść na stosie x i y + 1 K20: Umieść na stosie x - 1 i y K21: Zakończ Algorytm ośmio-spójnego wypełniania konturowego jest praktycznie identyczny. Różnica polega jedynie na tym, iż na stosie dodatkowo umieszczamy w pętli współrzędne pikseli leżących na kierunkach przekątnych.
Na podstawie powyższego algorytmu napiszemy prosty program testowy, który rysuje kilka ramek oraz okręgów na powierzchni graficznej, a następnie rozpoczyna wypełnianie obszaru począwszy od środka ekranu. Wypełnianie jest specjalnie spowolnione, aby można było je wygodnie obserwować.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P017 - wypełnianie konturowe //----------------------------- #include <windows.h> #include <SDL/SDL_gfx.h> #include <math.h> // funkcje sin, cos i sqrt #include <time.h> // do inicjalizacji generatora pseudolosowego #include <stack> // używamy STL do implementacji stosu using namespace std; // potrzebne dla STL! const int SCRX = 320; // stałe określające szerokość i wysokość const int SCRY = 240; // ekranu w pikselach int main(int argc, char *argv[]) { if(SDL_Init(SDL_INIT_VIDEO)) { MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK); exit(-1); } atexit(SDL_Quit); SDL_Surface * screen; if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) { MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK); exit(-1); } if(SDL_MUSTLOCK(screen)) if(SDL_LockSurface(screen) < 0) { MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK); exit(-1); } // inicjujemy generator liczb pseudolosowych srand((unsigned)time(NULL)); // wyznaczamy środek ekranu Sint32 x = screen->w >> 1; Sint32 y = screen->h >> 1; // rysujemy 20 losowych ramek, tak aby nie przykrywały środka ekranu // ramki są zawsze 4-spójne SDL_Rect * r = new SDL_Rect; for(int i = 0; i < 20; i++) { do { r->x = rand() % screen->w; r->y = rand() % screen->h; r->w = rand() % (screen->w >> 3) + 4; r->h = rand() % (screen->h >> 3) + 4; }while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h)); gfxClipRectangle(screen, r, 0xffff00); } // rysujemy 20 losowych okręgów, tak aby nie przykrywały środka // okręgi są 8-spójne Sint32 xs, ys, rs; for(int i = 0; i < 20; i++) { do { xs = rand() % screen->w; ys = rand() % screen->h; rs = rand() % (screen->w >> 3) + 4; }while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs); gfxMoveTo(xs + rs, ys); for(int j = 1; j < 51; j++) gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)), lround(ys + rs * sin(6.2831 * j / 50)), 0xffff00); } if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); // tutaj umieszczamy algorytm wypełniania Uint32 ccolor = 0xffff00; // kolor konturu Uint32 fcolor = 0xff0000; // kolor wypełnienia Uint32 pcolor; // kolor piksela stack<Sint32> q; // stos Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego // obliczamy prostokąt obcinający cx1 = cy1 = 10; cx2 = screen->w - 10; cy2 = screen->h - 10; q.push(x); q.push(y); while(!q.empty()) { y = q.top(); q.pop(); // pobieramy ze stosu x i y x = q.top(); q.pop(); // jeśli x,y jest w prostokącie obcinającym, przetwarzamy punkt if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2)) { // pobieramy kolor piksela na pozycji x,y if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); pcolor = gfxGetPixel(screen, x, y); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); // jeśli ma on kolor konturu lub wypełnienia, nie przetwarzamy go if((pcolor == ccolor) || (pcolor == fcolor)) continue; // wypełniamy piksel kolorem wypełnienia if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); gfxPlot(screen, x, y, fcolor); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); // uaktualniamy ekran. Aby przyspieszyć, użyj SDL_UpdateRect(screen, x, y, 1, 1) SDL_UpdateRect(screen, 0, 0, 0, 0); // na stosie umieszczamy współrzędne czterech sąsiednich pikseli q.push(x); q.push(y - 1); q.push(x + 1); q.push(y); q.push(x); q.push(y + 1); q.push(x - 1); q.push(y); } } MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK); return 0; }
Sprawdź co się stanie, jeśli w powyższym programie zmienisz kolory ramek lub kolory okręgów. Wyjaśnij zachowanie się algorytmu.
Algorytm cztero-spójnego wypełniania powodziowego
Wejście
x, y - współrzędne ziarna wypełnienia. Ziarno musi się zawierać w prostokącie obcinającym clip. fcolor - kolor wypełnienia clip - prostokąt obcinający Wyjście
Wypełnienie kolorem fcolor obszaru o kolorze ziarna z pozycji x,y. Jeśli obszar rozpościera się poza prostokąt obcinający, to wypełnienie ograniczy się tylko do prostokąta obcinania.
Zmienne pomocnicze
q - stos przechowujący współrzędne punktów. cx1,cy1 - współrzędne lewego górnego narożnika prostokąta obcinania cx2,cy2 - współrzędne prawego dolnego narożnika prostokąta obcinania scolor - kolor ziarna Lista kroków
K01: cx1 ← clip.x ; obliczamy współrzędne wierzchołków prostokąta obcinającego K02: cy1 ← clip.y K03: cx2 ← cx1 + clip.w - 1 K04: cy2 ← cy1 + clip.h - 1 K05: scolor ← kolor piksela na pozycji x,y ; odczytujemy kolor ziarna wypełnienia, wg którego będziemy śledzić piksele K06: Wyzeruj stos q K07: Umieść na szczycie stosu x i y K08: Dopóki stos q nie jest pusty, wykonuj kroki K09...K19 K09: Pobierz ze stosu x i y ; pobieramy współrzędne ziarna wypełniania K10: Jeżeli x < cx1, wykonaj kolejny obieg pętli K08 ; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania K11: Jeżeli x > cx2, wykonaj kolejny obieg pętli K08 ; jeśli nie, punktu x,y nie przetwarzamy dalej w pętli K12: Jeżeli y < cy1, wykonaj kolejny obieg pętli K08 K13: Jeżeli y > cy2, wykonaj kolejny obieg pętli K08 K14: Jeżeli kolor piksela x,y ≠ scolor, wykonaj kolejny obieg pętli K08 ; natrafiliśmy na kolor brzegu obszaru, piksela nie przetwarzamy K15: Ustaw kolor piksela x,y na fcolor ; piksel kolorujemy na kolor wypełnienia K16: Umieść na stosie x i y - 1 ; na stos przesyłamy współrzędne czterech sąsiednich pikseli K17: Umieść na stosie x + 1 i y K18: Umieść na stosie x i y + 1 K19: Umieść na stosie x - 1 i y K20: Zakończ Algorytm jest bardzo podobny do poprzedniego algorytmu wypełniania konturowego. Różnice leżą jedynie w warunkach sprawdzania kolorów wypełnianych pikseli. W algorytmie konturowym piksel nie mógł być w kolorze konturu oraz bieżącego wypełnienia. W algorytmie wypełniania obszaru piksel musi być w kolorze pierwszego ziarna.
Na podstawie powyższego algorytmu napiszemy prosty program testowy, który rysuje w różnych kolorach kilka ramek oraz okręgów na powierzchni graficznej, a następnie rozpoczyna wypełnianie obszaru począwszy od środka ekranu. Wypełnianie jest specjalnie spowolnione, aby można było je obserwować.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P018 - wypełnianie powodziowe //------------------------------ #include <windows.h> #include <SDL/SDL_gfx.h> #include <math.h> // funkcje sin, cos i sqrt #include <time.h> // do inicjalizacji generatora pseudolosowego #include <stack> // używamy STL do implementacji stosu using namespace std; // potrzebne dla STL! const int SCRX = 320; // stałe określające szerokość i wysokość const int SCRY = 240; // ekranu w pikselach int main(int argc, char *argv[]) { if(SDL_Init(SDL_INIT_VIDEO)) { MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK); exit(-1); } atexit(SDL_Quit); SDL_Surface * screen; if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) { MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK); exit(-1); } if(SDL_MUSTLOCK(screen)) if(SDL_LockSurface(screen) < 0) { MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK); exit(-1); } // inicjujemy generator liczb pseudolosowych srand((unsigned)time(NULL)); // wyznaczamy środek ekranu Sint32 x = screen->w >> 1; Sint32 y = screen->h >> 1; // rysujemy 20 losowych ramek w różnych kolorach, tak aby nie przykrywały środka ekranu // ramki są zawsze 4-spójne SDL_Rect * r = new SDL_Rect; Uint32 color; for(int i = 0; i < 20; i++) { do { r->x = rand() % screen->w; r->y = rand() % screen->h; r->w = rand() % (screen->w >> 3) + 4; r->h = rand() % (screen->h >> 3) + 4; } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h)); color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256); gfxClipRectangle(screen, r, color); } // rysujemy 20 losowych okręgów w różnych kolorach, tak aby nie przykrywały środka // okręgi są 8-spójne Sint32 xs, ys, rs; for(int i = 0; i < 20; i++) { do { xs = rand() % screen->w; ys = rand() % screen->h; rs = rand() % (screen->w >> 3) + 4; } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs); color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256); gfxMoveTo(xs + rs, ys); for(int j = 1; j < 51; j++) gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)), lround(ys + rs * sin(6.2831 * j / 50)), color); } if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); // tutaj umieszczamy algorytm wypełniania Uint32 scolor; // kolor ziarna Uint32 fcolor = 0xff0000; // kolor wypełnienia Uint32 pcolor; // kolor piksela stack<Sint32> q; // stos Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego // obliczamy prostokąt obcinający cx1 = cy1 = 10; cx2 = screen->w - 10; cy2 = screen->h - 10; if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); scolor = gfxGetPixel(screen, x, y); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); q.push(x); q.push(y); while(!q.empty()) { y = q.top(); q.pop(); // pobieramy ze stosu x i y x = q.top(); q.pop(); if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2)) { if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); pcolor = gfxGetPixel(screen, x, y); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); if(pcolor != scolor) continue; if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); gfxPlot(screen, x, y, fcolor); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); q.push(x); q.push(y - 1); q.push(x + 1); q.push(y); q.push(x); q.push(y + 1); q.push(x - 1); q.push(y); } } MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK); return 0; }
Zwróć uwagę na różnicę w działaniu algorytmu wypełnienia konturowego i powodziowego. Wypełnienie szuka konturu w zadanym kolorze, który ogranicza wypełniany obszar. Wszystkie inne kolory są zamalowywane kolorem wypełnienia. Natomiast wypełnienie powodziowe wypełnia tylko obszar tego samego koloru. Jeśli natrafi w nim na piksele w innym kolorze, to pozostawia je nienaruszone.
Sprawdź co się stanie, jeśli zamiast stosu użyjesz struktury kolejki jednokierunkowej - nowe elementy odkładamy na koniec listy, a pobieramy z początku listy - efekt jest bardzo ciekawy i pouczający. Eksperymentuj z podanymi przykładami, np. umieszczaj na stosie tylko niektórych sąsiadów ziarna - jak wpłynie to na sposób wypełniania obszaru?
Jeśli interesują cię wariackie sposoby wypełniania, to sprawdź działanie poniższego programu:
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P019 - wypełnianie zwariowane //------------------------------ #include <windows.h> #include <SDL/SDL_gfx.h> #include <math.h> // funkcje sin, cos i sqrt #include <time.h> // do inicjalizacji generatora pseudolosowego #include <stack> // używamy STL do implementacji stosu using namespace std; // potrzebne dla STL! const int SCRX = 320; // stałe określające szerokość i wysokość const int SCRY = 240; // ekranu w pikselach int main(int argc, char *argv[]) { if(SDL_Init(SDL_INIT_VIDEO)) { MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK); exit(-1); } atexit(SDL_Quit); SDL_Surface * screen; if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) { MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK); exit(-1); } if(SDL_MUSTLOCK(screen)) if(SDL_LockSurface(screen) < 0) { MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK); exit(-1); } // inicjujemy generator liczb pseudolosowych srand((unsigned)time(NULL)); // wyznaczamy środek ekranu Sint32 x = screen->w >> 1; Sint32 y = screen->h >> 1; // rysujemy 20 losowych ramek w różnych kolorach, tak aby nie przykrywały środka ekranu // ramki są zawsze 4-spójne SDL_Rect * r = new SDL_Rect; Uint32 color; for(int i = 0; i < 20; i++) { do { r->x = rand() % screen->w; r->y = rand() % screen->h; r->w = rand() % (screen->w >> 3) + 4; r->h = rand() % (screen->h >> 3) + 4; } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h)); color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256); gfxClipRectangle(screen, r, color); } // rysujemy 20 losowych okręgów w różnych kolorach, tak aby nie przykrywały środka // okręgi są 8-spójne Sint32 xs, ys, rs; for(int i = 0; i < 20; i++) { do { xs = rand() % screen->w; ys = rand() % screen->h; rs = rand() % (screen->w >> 3) + 4; } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs); color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256); gfxMoveTo(xs + rs, ys); for(int j = 1; j < 51; j++) gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)), lround(ys + rs * sin(6.2831 * j / 50)), color); } if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); // tutaj umieszczamy algorytm wypełniania Uint32 scolor; // kolor ziarna Uint32 fcolor = 0xff0000; // kolor wypełnienia Uint32 pcolor; // kolor piksela stack<Sint32> q; // stos Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego // obliczamy prostokąt obcinający cx1 = cy1 = 10; cx2 = screen->w - 10; cy2 = screen->h - 10; if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); scolor = gfxGetPixel(screen, x, y); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); q.push(x); q.push(y); while(!q.empty()) { y = q.top(); q.pop(); // pobieramy ze stosu x i y x = q.top(); q.pop(); if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2)) { if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); pcolor = gfxGetPixel(screen, x, y); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); if(pcolor != scolor) continue; if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen); gfxPlot(screen, x, y, fcolor); if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen); SDL_UpdateRect(screen, 0, 0, 0, 0); switch(rand() % 4) { case 0: q.push(x); q.push(y - 1); q.push(x + 1); q.push(y); q.push(x); q.push(y + 1); q.push(x - 1); q.push(y); break; case 1: q.push(x + 1); q.push(y); q.push(x - 1); q.push(y); q.push(x); q.push(y + 1); q.push(x); q.push(y - 1); break; case 2: q.push(x); q.push(y + 1); q.push(x); q.push(y - 1); q.push(x - 1); q.push(y); q.push(x + 1); q.push(y); break; case 3: q.push(x - 1); q.push(y); q.push(x + 1); q.push(y); q.push(x); q.push(y - 1); q.push(x); q.push(y + 1); break; } } } MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK); return 0; }
![]() | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe