Grafika komputerowa: wypełnianie obszarów

Operacje wypełniania wymagają intensywnych działań na pikselach, dlatego zastosujemy zamiast tekstury powierzchnię graficzną SDL_Surface. Powierzchnia taka jest przechowywana w pamięci głównej i mikroprocesor ma do niej bezpośredni dostęp. Zasadę pracy z powierzchnią graficzną SDL_Surface ilustruje poniższy przykład:

C++

// Powierzchnia graficzna 1
//-------------------------

#include <SDL.h>
#include <iostream>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  SDL_Rect rect = {W_W/2-W_W/4,W_H/2-W_H/4,W_W/2,W_H/2};

  // Rysujemy prostokąt
  SDL_LockSurface(s);
  SDL_SetRenderDrawColor(r,255,0,0,255);
  SDL_RenderDrawRect(r,&rect);
  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Opiszmy użyte w programie elementy:

SDL_Init(...)	Inicjalizacja biblioteki SDL.
SDL_Window * w = SDL_CreateWindow(...)	Tworzymy okno i zapisujemy informację o nim w strukturze SDL_Window.
SDL_Surface * s = SDL_GetWindowSurface(w)	W strukturze SDL_Surface zapisujemy informację o powierzchni graficznej okna, która jest tworzona w pamięci RAM dostępnej dla mikroprocesora.
SDL_Renderer * r = SDL_CreateSoftwareRenderer(s)	Tworzymy programowy kontekst graficzny. Dzięki niemu będziemy mogli stosować z powierzchnią SDL_Surface poznane polecenia graficzne w sposób identyczny jak dla tekstury akceleratora, jedynie szybkość będzie mniejsza, ale to w naszym przypadku nie ma znaczenia.
SDL_Rect rect	Tworzymy strukturę rect wykorzystywaną do narysowania prostokąta na powierzchni SDL_Surface
SDL_LockSurface(s)	Blokujemy dostęp do powierzchni innym procesom – nie wszystkie powierzchnie wymagają blokowania, tutaj jest to robione na zapas.
SDL_SetRenderDrawColor(...) SDL_RenderDrawRect(...)	Polecenia graficzne dla kontekstu, ustawiamy kolor czerwony i rysujemy w tym kolorze prostokąt.
SDL_UnlockSurface(s)	Zwalniamy blokadę powierzchni
SDL_UpdateWindowSurface(w)	Treść powierzchni SDL_Surface przesyłamy do bufora ekranu.

Pozostała część programu jest taka sama jak w poprzednich programach: czekamy w pętli na zdarzenie SDL_QUIT, po czym zamykamy kontekst z oknem i kończymy działanie programu.

Potrzebujemy jeszcze funkcji, która odczyta piksel z zadanej pozycji na powierzchni SDL_Surface. Piksel będzie zwracany w postaci 32-bitowego kodu. Nie analizujemy formatu piksela, zatem otrzymany kod może być różny na różnych platformach, jednakże nie będzie to miało znaczenia. Podobną funkcję opisaliśmy w rozdziale o pikselach.

C++

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela bez przezroczystości
  return color & ((s->format->Amask)^-1);
}

Poniższy program rysuje 100 linii w kolorze białym, po czym w pętli co 1 sekundę odczytuje kolejne piksele powierzchni SDL_Surface i jeśli są różne od tła (kolor czarny o kodzie 0), to zmienia ich kolor na przypadkowy kolor różny od czarnego.

C++

// Powierzchnia graficzna 2
//-------------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela bez przezroczystości
  return color & ((s->format->Amask)^-1);
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy 100 przypadkowych linii
  SDL_LockSurface(s);
  SDL_SetRenderDrawColor(r,255,255,255,255);
  for(int i = 0; i < 100; i++)
    SDL_RenderDrawLine(r,rand() % W_W,rand() % W_H,rand() % W_W,rand() % W_H);
  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Animacja
  SDL_Event event;
  int x, y, c = 100;
  while(1)
  {
    if(!--c)
    {
      SDL_LockSurface(s);
      for(x = 0; x < W_W; x++)
        for(y = 0; y < W_H; y++)
          if(ReadPixel(s,x,y))
          {
             SDL_SetRenderDrawColor(r,1+rand()%256,1+rand()%256,1+rand()%256,255);
             SDL_RenderDrawPoint(r,x,y);
          }
      SDL_UnlockSurface(s);
      SDL_UpdateWindowSurface(w);
      c = 100;
    }
    else SDL_Delay(10);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Kolejna funkcja tworzy kod koloru piksela na podstawie jego składowych kolorów:

C++

// Funkcja zwraca kod koloru piksela dla danej powierzchni graficznej
//-------------------------------------------------------------------
Uint32 PixelColor(SDL_Surface * s, Uint8 r,  Uint8 g,  Uint8 b)
{
  Uint32 color;

  // Obliczamy kod piksela
  color  = (r << s->format->Rshift) & (s->format->Rmask);
  color |= (g << s->format->Gshift) & (s->format->Gmask);
  color |= (b << s->format->Bshift) & (s->format->Bmask);
  return color;
}

I ostatnia funkcja umieszcza na powierzchni graficznej piksel bez sprawdzania prostokąta obcinającego (sprawdzenie to będzie wykonywane w innym miejscu):

C++

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

Na początek: podrozdziału strony

W SDL możemy ograniczyć powierzchnię graficzną do prostokąta, wewnątrz którego będą wykonywane operacje graficzne. Prostokąt taki nazywamy prostokątem obcinającym (ang. clipping rectangle). Powierzchnia graficzna SDL_Surface posiada taki prostokąt. Początkowo obejmuje on całą powierzchnię graficzną, lecz możesz to łatwo zmienić za pomocą funkcji:

SDL_SetClipRect(s,r)
s – wskaźnik struktury SDL_Surface
r – wskaźnik nowego prostokąta obcinającego

Poniższy program tworzy nowy prostokąt obcinający, po czym rysuje 1000 białych punktów na powierzchni graficznej okna. Punkty pojawią się tylko wewnątrz prostokąta obcinającego. Animacja powoduje zmianę kolorów punktów na kolory losowe.

C++

// Powierzchnia graficzna 3
//-------------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Zmieniamy prostokąt obcinający
  SDL_Rect cr = {W_W/8,W_H/8,W_W-W_W/4,W_H-W_H/4};
  SDL_SetClipRect(s,&cr);

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy 100 przypadkowych linii
  SDL_LockSurface(s);
  SDL_SetRenderDrawColor(r,255,255,255,255);
  for(int i = 0; i < 10000; i++)
    SDL_RenderDrawPoint(r,rand() % W_W,rand() % W_H);
  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Animacja
  SDL_Event event;
  int x,y,c=100;
  int xs,ys,xe,ye; // Granice prostokąta obcinającego

  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w;
  ye = ys + s->clip_rect.h;
  while(1)
  {
    if(!--c)
    {
      SDL_LockSurface(s);
      for(x = xs; x < xe; x++)
        for(y = ys; y < ye; y++)
          if(ReadPixel(s,x,y))
          {
             SDL_SetRenderDrawColor(r,1+rand()%256,1+rand()%256,1+rand()%256,255);
             SDL_RenderDrawPoint(r,x,y);
          }
      SDL_UnlockSurface(s);
      SDL_UpdateWindowSurface(w);
      c = 100;
    }
    else SDL_Delay(10);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Kolejny program przykładowy wykorzystuje funkcje zapisu piksela do utworzenia efektu kalejdoskopu:

C++

// Powierzchnia graficzna 4
//-------------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Zmieniamy prostokąt obcinający
  SDL_Rect cr = {0,0,W_W/2,W_H/2};
  SDL_SetClipRect(s,&cr);

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy 200 przypadkowych linii w różnych kolorach
  SDL_LockSurface(s);
  for(int i = 0; i < 200; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    SDL_RenderDrawLine(r,rand()%W_W,rand()%W_H,rand()%W_W,rand()%W_H);
  }

  // Tworzymy lustrzane odbicia
  for(int x = 0; x < W_W / 2; x++)
    for(int y = 0; y < W_H / 2; y++)
    {
       Uint32 pc = ReadPixel(s,x,y);
       WritePixel(s,W_W-x-1,y,pc);
       WritePixel(s,x,W_H-y-1,pc);
       WritePixel(s,W_W-x-1,W_H-y-1,pc);
    }
  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

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 obszarem cztero-spójnym (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.

Obszar jest obszarem ośmio-spójnym (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).

→

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.

Tego typu algorytmy można zrealizować jako rekurencyjne lub stosowe.

Rekurencyjny, czterospójny algorytm wypełniania konturowego

void BoundaryFill(s,x,y,cc,fc);

s	–	powierzchnia SDL_Surface
x, y	–	współrzędne ziarna wypełnienia.
cc	–	kolor konturu obejmującego obszar wypełniany
fc	–	kolor wypełnienia

Wyjście

Wypełnienie kolorem fc obszaru ograniczonego konturem w kolorze cc 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.

Zmienne pomocnicze

xs,ys,xe,ye	–	współrzędne prostokąta obcinającego
pc	–	kolor piksela

Lista kroków

K01: xs ← s->clip.x ; obliczamy współrzędne wierzchołków prostokąta obcinającego

K02: ys ← s->clip.y

K03: xe ← xs + s->clip.w-1

K04: ye ← ys + s->clip.h-1

K05: Jeśli (x< xs) lub (x>xe)
lub (y<ys) lub (y>ye),
to zakończ ; sprawdzamy, czy ziarno jest wewnątrz prostokąta obcinającego

K06: pc ← ReadPixel(s,x,y) ; pobieramy kolor piksela na pozycji x,y

K07: Jeśli (pc = cc) lub (pc = fc),
to zakończ ; natrafiliśmy na już ustawiony punkt lub kontur

K08: WritePixel(s,x,y,fc) ; wypełniamy ziarno kolorem wypełnienia

K09: BoundaryFill(s,x-1,y,cc,fc) ; rekurencyjnie siejemy w 4 kierunkach

K10: BoundaryFill(s,x,y-1,cc,fc)

K11: BoundaryFill(s,x+1,y,cc,fc)

K12: BoundaryFill(s,x,y+1,cc,fc)

K13: Zakończ

Poniższy program rysuje na obrzeżach powierzchni graficznej okna małe prostokąty w kolorze białym, po czym wypełnia powierzchnię kolorem czerwonym za pomocą powyższego algorytmu.

Uwaga: Algorytm rekurencyjny jest bardzo pamięciożerny i nie uda ci się uruchomić tego programu z normalnymi ustawieniami kompilatora. Musisz koniecznie zwiększyć rozmiar stosu, który standardowo jest zbyt mały i dochodzi do jego przepełnienia (alternatywą jest użycie bardzo małego okna, np. o wymiarach 160 x 120). W tym celu w Code Blocks wybierz z menu opcję:

Project → Build Options

Ukaże się okno opcji kompilacyjnych:

Wybierz w nim zakładkę Linker settings i w polu Other linker options dopisz na końcu:

-Wl,--stack,2000000

Ważne są przecinki. Opcja ta zwiększa rozmiar stosu dla aplikacji do 2GB – z takimi wartościami program powinien zadziałać, gdyby jednak się wciąż wieszał, to spróbuj zwiększyć liczbę końcową:

Zatwierdź okno kliknięciem w OK, następnie z menu wybierz Build → Rebuild (Ctrl+F11) i uruchom program.

C++

// Wypełnianie 1
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

// Funkcja zwraca kod koloru piksela dla danej powierzchni graficznej
//-------------------------------------------------------------------
Uint32 PixelColor(SDL_Surface * s, Uint8 r,  Uint8 g,  Uint8 b)
{
  Uint32 color;

  // Obliczamy kod piksela
  color  = (r << s->format->Rshift) & (s->format->Rmask);
  color |= (g << s->format->Gshift) & (s->format->Gmask);
  color |= (b << s->format->Bshift) & (s->format->Bmask);
  return color;
}

// Rekurencyjna funkcja wypełniania konturowego, czterospójnego
//-------------------------------------------------------------
void BoundaryFill(SDL_Surface * s, int x, int y, Uint32 cc, Uint32 fc)
{
  int xs,ys,xe,ye;
  Uint32 pc;
  // Wyznaczamy granice prostokąta obcinającego
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;
  // Sprawdzamy, czy ziarno jest wewnątrz prostokata.
  // Jeśli nie, to kończymy
  if((x < xs) || (x > xe) || (y < ys) || (y > ye)) return;
  // Czytamy kod piksela na pozycji ziarna
  pc = ReadPixel(s,x,y);
  // Musi się różnić od cc i fc, aby kontynuować
  if((pc == cc) || (pc == fc)) return;
  // Stawiamy ziarno
  WritePixel(s,x,y,fc);
  //Rekurencyjnie siejemy w 4 kierunkach
  BoundaryFill(s,x-1,y,cc,fc);
  BoundaryFill(s,x,y-1,cc,fc);
  BoundaryFill(s,x+1,y,cc,fc);
  BoundaryFill(s,x,y+1,cc,fc);
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  SDL_Rect rect;
  rect.w = W_W / 8;
  rect.h = W_H / 8;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy po 16 prostokątów przy każdej krawędzi okna
  SDL_LockSurface(s);
  SDL_SetRenderDrawColor(r,255,255,255,255);
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % W_W;
    rect.y = rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = W_W - rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % W_W;
    rect.y = W_H - rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  // Wypełniamy od środka okna kolorem czerwonym
  BoundaryFill(s, W_W/2,W_H/2,PixelColor(s,255,255,255),PixelColor(s,255,0,0));

  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Zamiast rekurencji możemy wykorzystać strukturę stosu, która charakteryzuje się tym, iż dane są odczytywane w kolejności odwrotnej do ich wstawiania:

Stos (ang. stack) jest sekwencyjną strukturą danych. Najprościej możemy go sobie wyobrazić jako stos książek na biurku. Nowe książki układamy na szczycie stosu (ang. stack top), wtedy stos rośnie w górę:

Ze stosu pobieramy książki znajdujące się na samej górze, wtedy stos maleje. Zwróć uwagę, że książki zawsze zdejmujesz ze stosu w kolejności odwrotnej do ich umieszczania – jako pierwszą zdejmiesz ostatnią książkę na stosie:

Wracając do świata komputerów, stos jest taką strukturą danych, z której odczytujemy elementy w kolejności odwrotnej do ich wstawiania. Struktura ta nosi nazwę LIFO (ang. Last In – First Out – wszedł ostatni, a wyszedł pierwszy).

Rozróżniamy następujące operacje dla stosu:

Sprawdzenie, czy stos jest pusty – operacja empty zwraca true, jeśli stos nie zawiera żadnego elementu, w przeciwnym razie zwraca false
Odczyt szczytu stosu – operacja top zwraca element (zwykle jest to wskaźnik) znajdujący się na szczycie stosu, sam element pozostaje wciąż na stosie.
Zapis na stos – operacja push umieszcza na szczycie stosu nowy element.
Usunięcie ze stosu – operacja pop usuwa ze szczytu stosu znajdujący się tam element.

Stos zrealizujemy za pomocą biblioteki STL, którą mamy pod ręką w C++. Biblioteka STL jest biblioteką funkcji szablonowych. Stos otrzymamy przez dołączenie do programu pliku nagłówkowego:

#include <stack>

Następnie musimy utworzyć zmienną stosu oraz określić, co na tym stosie będziemy umieszczać:

stack<int> stos;

Taka definicja tworzy zmienną stosu o nazwie stos, a na tym stosie będzie można umieszczać liczby całkowite typu int. Zmienna jest klasą i posiada funkcje składowe, z których najważniejsze to

stos.empty()	–	zwraca true, jeśli na stosie nic nie ma, czyli stos jest pusty.
stos.top()	–	zwraca odwołanie do elementu na szczycie stosu.
stos.push(v)	–	umieszcza na szczycie stosu nową wartość v.
stos.pop()	–	usuwa wartość przechowywaną na szczycie stosu.

W porównaniu z algorytmem rekurencyjnym, algorytm stosowy jest bardziej oszczędny pamięciowo.

Stosowy, czterospójny algorytm wypełniania konturowego

void BoundaryFill(s,x,y,cc,fc);

s	–	powierzchnia SDL_Surface
x, y	–	współrzędne ziarna wypełnienia.
cc	–	kolor konturu obejmującego obszar wypełniany
fc	–	kolor wypełnienia

Wyjście

Wypełnienie kolorem fc obszaru ograniczonego konturem w kolorze cc 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.

Zmienne pomocnicze

q	–	stos
xs,ys,xe,ye	–	współrzędne prostokąta obcinającego
pc	–	kolor piksela

Lista kroków

K01:	xs ← s->clip.x	; obliczamy współrzędne wierzchołków prostokąta obcinającego
K02:	ys ← s->clip.y
K03:	xe ← xs + s->clip.w - 1
K04:	ye ← ys + s->clip.h - 1
K05:	Twórz stos q
K06:	Umieść na szczycie stosu x i y
K07:	Dopóki stos nie jest pusty, wykonuj kroki K08...K16
K08:	Pobierz ze stosu x i y	; pobieramy współrzędne ziarna wypełniania
K09:	Jeśli (x<xs) lub (x >xe) lub (y<ys) lub (y>ye), to wykonaj kolejny obieg pętli K07	; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania
K10:	pc = kolor piksela x,y
K11:	Jeśli (pc = cc) lub (pc=fc), to wykonaj kolejny obieg pętli K07	; natrafiliśmy na kontur lub już wypełniony piksel, nie przetwarzamy
K12:	Ustaw kolor piksela x,y na fc	; piksel kolorujemy na kolor wypełnienia
K13:	Umieść na stosie x-1 i y	; na stos przesyłamy współrzędne czterech sąsiednich pikseli
K14:	Umieść na stosie x i y-1
K15:	Umieść na stosie x +1 i y
K16:	Umieść na stosie x i y+1
K17:	Zakończ

Poniższy program realizuje opisany algorytm. Działa on identycznie jak poprzedni. Tutaj nie musisz już modyfikować opcji linkera, ponieważ stos tworzony jest w pamięci danych, a tej jest zwykle pod dostatkiem na współczesnych komputerach.

C++

// Wypełnianie 2
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stack>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

// Funkcja zwraca kod koloru piksela dla danej powierzchni graficznej
//-------------------------------------------------------------------
Uint32 PixelColor(SDL_Surface * s, Uint8 r,  Uint8 g,  Uint8 b)
{
  Uint32 color;

  // Obliczamy kod piksela
  color  = (r << s->format->Rshift) & (s->format->Rmask);
  color |= (g << s->format->Gshift) & (s->format->Gmask);
  color |= (b << s->format->Bshift) & (s->format->Bmask);
  return color;
}

// Stosowa funkcja wypełniania konturowego, czterospójnego
//-------------------------------------------------------------
void BoundaryFill(SDL_Surface * s, int x, int y, Uint32 cc, Uint32 fc)
{
  int xs,ys,xe,ye;
  Uint32 pc;
  stack<int> q; // Stos

  // Wyznaczamy granice prostokąta obcinającego
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;

  // Umieszczamy na stosie współrzędne ziarna
  // i wchodzimy w pętlę
  q.push(x); q.push(y);
  while(!q.empty())
  {
    // Pobieramy współrzędne w kolejności odwrotnej
    y = q.top(); q.pop();
    x = q.top(); q.pop();

    // Sprawdzamy, czy są wewnątrz prostokąta obcinającego
    if((x<xs)||(x>xe)||(y<ys)||(y>ye)) continue; // Następny obieg pętli

    // Pobieramy kolor piksela
    pc = ReadPixel(s,x,y);

    // Jeśli jest to kolor konturu lub wypełnienia, następny obieg
    if((pc==cc)||(pc==fc)) continue;

    // Piksel wypełniamy kolorem fc
    WritePixel(s,x,y,fc);

    // Na stos idą współrzędne sąsiednich punktów
    q.push(x-1); q.push(y);
    q.push(x); q.push(y-1);
    q.push(x+1); q.push(y);
    q.push(x); q.push(y+1);
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  SDL_Rect rect;
  rect.w = W_W / 8;
  rect.h = W_H / 8;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy po 16 prostokątów przy każdej krawędzi okna
  SDL_LockSurface(s);
  SDL_SetRenderDrawColor(r,255,255,255,255);
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % W_W;
    rect.y = rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = W_W - rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    rect.x = rand() % W_W;
    rect.y = W_H - rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  // Wypełniamy od środka okna kolorem czerwonym
  BoundaryFill(s, W_W/2,W_H/2,PixelColor(s,255,255,255),PixelColor(s,255,0,0));

  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Drugi rodzaj wypełnienia, wypełnienie powodziowe, działa na podobnych zasadach, jedyna różnica występuje przy sprawdzaniu koloru piksela. Na początku algorytm odczytuje kolor ziarna i zapamiętuje go. Następnie wypełnia obszar o tym kolorze, pomijając piksele o innych kolorach. Z powodu pamięciożerności pominiemy wersję rekurencyjną i skupimy się na wersji stosowej.

Stosowy algorytm cztero-spójnego wypełniania powodziowego

void FloodFill(s,x,y,fc)

s	–	Powierzchnia SDL_Surface
x, y	–	współrzędne ziarna wypełnienia. Ziarno musi się zawierać w prostokącie obcinającym clip.
fc	–	kolor wypełnienia

Wyjście

Wypełnienie kolorem fc 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.
xs,ys	–	współrzędne lewego górnego narożnika prostokąta obcinania
xe,ye	–	współrzędne prawego dolnego narożnika prostokąta obcinania
sc	–	kolor ziarna

Lista kroków

K01:	xs ← s->clip.x	; obliczamy współrzędne wierzchołków prostokąta obcinającego
K02:	ys ← s->clip.y
K03:	xe ← xs + s->clip.w-1
K04:	ye ← ys + s->clip.h-1
K05:	sc ← kolor piksela na pozycji x,y	; odczytujemy kolor ziarna wypełnienia, wg którego będziemy śledzić piksele
K06:	Twórz stos
K07:	Umieść na szczycie stosu x i y
K08:	Dopóki stos nie jest pusty, wykonuj kroki K09...K16
K09:	Pobierz ze stosu x i y	; pobieramy współrzędne ziarna wypełniania
K10:	Jeśli (x<xs) lub (x>xe) lub (y<ys) lub (y>ye), to wykonaj kolejny obieg pętli K08	; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania
K11:	Jeśli kolor piksela x,y ≠ sc, to wykonaj kolejny obieg pętli K08	; natrafiliśmy na kolor brzegu obszaru, piksela nie przetwarzamy
K12:	Ustaw kolor piksela x,y na fc	; piksel kolorujemy na kolor wypełnienia
K13:	Umieść na stosie x i y - 1	; na stos przesyłamy współrzędne czterech sąsiednich pikseli
K14:	Umieść na stosie x + 1 i y
K15:	Umieść na stosie x i y + 1
K16:	Umieść na stosie x - 1 i y
K17:	Zakończ

Na podstawie algorytmu tworzymy przykładowy program. W tej wersji prostokąty brzegowe mają różne kolory.

C++

// Wypełnianie 3
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stack>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

// Funkcja zwraca kod koloru piksela dla danej powierzchni graficznej
//-------------------------------------------------------------------
Uint32 PixelColor(SDL_Surface * s, Uint8 r,  Uint8 g,  Uint8 b)
{
  Uint32 color;

  // Obliczamy kod piksela
  color  = (r << s->format->Rshift) & (s->format->Rmask);
  color |= (g << s->format->Gshift) & (s->format->Gmask);
  color |= (b << s->format->Bshift) & (s->format->Bmask);
  return color;
}

// Stosowa funkcja wypełniania powodziowego, czterospójnego
//-------------------------------------------------------------
void FloodFill(SDL_Surface * s, int x, int y, Uint32 fc)
{
  int xs,ys,xe,ye;
  Uint32 sc;
  stack<int> q; // Stos

  // Wyznaczamy granice prostokąta obcinającego
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;
  // Pobieramy kolor ziarna
  sc = ReadPixel(s,x,y);

  // Umieszczamy na stosie współrzędne ziarna
  // i wchodzimy w pętlę
  q.push(x); q.push(y);

  while(!q.empty())
  {
    // Pobieramy współrzędne w kolejności odwrotnej
    y = q.top(); q.pop();
    x = q.top(); q.pop();
    // Sprawdzamy, czy są wewnątrz prostokąta obcinającego
    if((x<xs)||(x>xe)||(y<ys)||(y>ye)) continue; // Następny obieg pętli

    // Sprawdzamy kolor piksela za kolorem ziarna.
    // Jeśli jest różny od sc, nie przetwarzamy dalej, następny obieg
    if(sc != ReadPixel(s,x,y)) continue;

    // Piksel wypełniamy kolorem fc
    WritePixel(s,x,y,fc);

    // Na stos idą współrzędne sąsiednich punktów
    q.push(x-1); q.push(y);
    q.push(x); q.push(y-1);
    q.push(x+1); q.push(y);
    q.push(x); q.push(y+1);
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  SDL_Rect rect;
  rect.w = W_W / 8;
  rect.h = W_H / 8;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy po 16 prostokątów przy każdej krawędzi okna
  SDL_LockSurface(s);
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % W_W;
    rect.y = rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = W_W - rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % W_W;
    rect.y = W_H - rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  // Wypełniamy od środka okna kolorem czerwonym
  FloodFill(s, W_W/2,W_H/2,PixelColor(s,255,0,0));

  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Jeśli chcesz zobaczyć animowaną wersję, uruchom poniższy program. Uwaga: zdarzenia są obsługiwane dopiero po zakończeniu wypełniania. Uzbrój się w cierpliwość.

C++

// Wypełnianie 4
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stack>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

SDL_Window * w;

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(SDL_Surface * s, int x, int y)
{
  // Obliczamy adres piksela
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;

  Uint32 color = *addr;
  // Zwracamy kod koloru piksela
  return color & ((s->format->Amask)^-1);
}

// Funkcja zapisuje piksel na pozycji x,y
//---------------------------------------
void WritePixel(SDL_Surface * s, int x, int y, Uint32 color)
{
  Uint32 * addr;

  // Obliczamy adres piksela
  addr = (Uint32 *)s->pixels + x + y * s->w;

  // Zapisujemy kolor piksela
  * addr = color;
}

// Funkcja zwraca kod koloru piksela dla danej powierzchni graficznej
//-------------------------------------------------------------------
Uint32 PixelColor(SDL_Surface * s, Uint8 r,  Uint8 g,  Uint8 b)
{
  Uint32 color;

  // Obliczamy kod piksela
  color  = (r << s->format->Rshift) & (s->format->Rmask);
  color |= (g << s->format->Gshift) & (s->format->Gmask);
  color |= (b << s->format->Bshift) & (s->format->Bmask);
  return color;
}

// Stosowa funkcja wypełniania powodziowego, czterospójnego
//-------------------------------------------------------------
void FloodFill(SDL_Surface * s, int x, int y, Uint32 fc)
{
  int xs,ys,xe,ye;
  Uint32 sc;
  stack<int> q; // Stos

  // Wyznaczamy granice prostokąta obcinającego
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;
  // Pobieramy kolor ziarna
  sc = ReadPixel(s,x,y);

  // Umieszczamy na stosie współrzędne ziarna
  // i wchodzimy w pętlę
  q.push(x); q.push(y);

  while(!q.empty())
  {
    // Pobieramy współrzędne w kolejności odwrotnej
    y = q.top(); q.pop();
    x = q.top(); q.pop();
    // Sprawdzamy, czy są wewnątrz prostokąta obcinającego
    if((x<xs)||(x>xe)||(y<ys)||(y>ye)) continue; // Następny obieg pętli

    // Sprawdzamy kolor piksela za kolorem ziarna.
    // Jeśli jest różny od sc, nie przetwarzamy dalej, następny obieg
    if(sc != ReadPixel(s,x,y)) continue;

    // Piksel wypełniamy kolorem fc
    WritePixel(s,x,y,fc);

    // Uaktualniamy okno na ekranie
    SDL_UnlockSurface(s);
    SDL_UpdateWindowSurface(w);
    SDL_LockSurface(s);

    // Na stos idą współrzędne sąsiednich punktów
    q.push(x-1); q.push(y);
    q.push(x); q.push(y-1);
    q.push(x+1); q.push(y);
    q.push(x); q.push(y+1);
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  w = SDL_CreateWindow("Powierzchnia graficzna", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy powierzchnię graficzną okna
  SDL_Surface * s = SDL_GetWindowSurface(w);

  // Tworzymy programowy kontekst graficzny
  SDL_Renderer * r = SDL_CreateSoftwareRenderer(s);
  if(!r)
  {
     cout << "SDL_CreateSoftwareRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  SDL_Rect rect;
  rect.w = W_W / 8;
  rect.h = W_H / 8;

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Rysujemy po 16 prostokątów przy każdej krawędzi okna
  SDL_LockSurface(s);
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % W_W;
    rect.y = rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = W_W - rand() % (W_W / 8);
    rect.y = rand() % W_H;
    SDL_RenderDrawRect(r,&rect);
  }
  for(int i = 0; i < 16; i++)
  {
    SDL_SetRenderDrawColor(r,rand()%256,rand()%256,rand()%256,255);
    rect.x = rand() % W_W;
    rect.y = W_H - rand() % (W_H / 8);
    SDL_RenderDrawRect(r,&rect);
  }
  // Wypełniamy od środka okna kolorem czerwonym
  FloodFill(s, W_W/2,W_H/2,PixelColor(s,255,0,0));

  SDL_UnlockSurface(s);

  // Uaktualniamy okno na ekranie
  SDL_UpdateWindowSurface(w);

  // Czekamy na zamknięcie okna
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Wypełnianie obszarów

Dostęp do pikseli

Prostokąt obcinający

Wypełnianie obszarów ograniczonych

Rekurencyjny, czterospójny algorytm wypełniania konturowego

void BoundaryFill(s,x,y,cc,fc);

Wyjście

Zmienne pomocnicze

Lista kroków

Stosowy, czterospójny algorytm wypełniania konturowego

void BoundaryFill(s,x,y,cc,fc);

Wyjście

Zmienne pomocnicze

Lista kroków

Stosowy algorytm cztero-spójnego wypełniania powodziowego

void FloodFill(s,x,y,fc)

Wyjście

Zmienne pomocnicze

Lista kroków