Serwis Edukacyjny
Nauczycieli
w I-LO w Tarnowie

Do strony głównej I LO w Tarnowie

Materiały dla uczniów liceum

  Wyjście       Spis treści       Poprzedni       Następny  

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

logo

Autor artykułu: mgr Jerzy Wałaszek

 

 

SDL2

Wypełnianie obszarów algorytmem Smitha

Rozdziały:
    Instalacja
    Typy danych
    Grafika rastrowa
    Okno
    Kontekst graficzny
    Punkty
    Odcinki
    Figury
    Algorytm Bresenhama
    Wypełnianie figur
    Wypełnianie obszarów
    Wypełnianie obszarów algorytmem Smitha
    Przezroczystość
    Zdarzenia

     Interfejs SDL2 wg nazw
     Interfejs SDL2 wg kategorii
W rozdziale:
Pojęcia wstępne
Znajdowanie segmentów
Przeszukiwanie segmentów
Algorytm Smitha

 

Pojęcia wstępne

Zaprezentowane w poprzednim rozdziale algorytmy wypełniania konturowego (ang. boundary fill) i wypełniania powodziowego (ang. flood fill) posiadają istotne wady. Przy dużych powierzchniach stos może rozrastać się znacznie w pamięci i nie jest on efektywnie wykorzystywany - współrzędne tych samych pikseli mogą być wielokrotnie umieszczane na stosie prowadząc do pustych przebiegów głównej pętli algorytmu. Z tego powodu opracowano bardziej efektywne rozwiązania problemu wypełniania obszarów. Jednym z nich jest popularny algorytm Smitha.

Podstawowym ulepszeniem algorytmu wypełniania jest w przypadku algorytmu Smitha operowanie segmentami pikseli, a nie pojedynczymi pikselami. Przez segment będziemy rozumieli zbiór przyległych pikseli tworzących poziomy odcinek na powierzchni graficznej:

Segment definiujemy trójką (x,y,len), gdzie x i y oznaczają współrzędne początku segmentu, a len oznacza długość, czyli liczbę pikseli wchodzących w skład segmentu. Na przykład trójka (5,6,5) oznacza segment rozpoczynający się od piksela (5,6) i zawierający 5 pikseli. O przynależności pikseli do segmentu decyduje rodzaj wypełniania. Dla wypełniania konturowego (ang. boundary fill) segment będą tworzyły przyległe piksele ograniczone z obu stron albo brzegiem prostokąta obcinania, albo pikselami w kolorze konturu. W tym przypadku kolor pikseli w segmencie nie ma znaczenia - musi być tylko różny od koloru konturu oraz koloru wypełnienia:

 

Przy wypełnianiu powodziowym (ang. flood fill) wszystkie piksele wchodzące w skład segmentu muszą posiadać ten sam kolor, różny od koloru wypełniania. Segment jest z obu stron ograniczony pikselami w innych kolorach lub prostokątem obcinającym (ang. clipping rectangle).

Pierwszym problemem, który musimy rozwiązać, jest znajdowanie maksymalnego segmentu pikseli, jeśli dane są współrzędne dowolnego piksela wchodzącego w skład segmentu. Problem rozwiązujemy przesuwając się po pikselach segmentu od początkowego punktu w lewo i prawo dopóki jest to możliwe, czyli do momentu, gdy natrafimy na ograniczenie - inny kolor piksela lub krawędź prostokąta obcinającego.

 

Znajdowanie segmentów

Poniżej prezentujemy dwie wersje algorytmu funkcji findSegment() - dla wypełniania konturowego oraz dla wypełniania powodziowego. Znaleziony segment jako trójka (x,y,len) zostaje umieszczony na stosie i będzie użyty we właściwym algorytmie.

Wypełnianie konturowe

int FindBSegment(s,x,y,cc,q,xs,xe)

s  – powierzchnia SDL_Surface
x, y  –  współrzędne piksela w segmencie
cc  – kolor konturu obejmującego obszar wypełniany
q  – stos
xs,xe  –  współrzędne x prostokąta obcinającego

Wyjście

Umieszczenie na stosie q trójki definiującej segment. Funkcja jako wartość zwraca współrzędną x2 + 1, czyli pierwszą pozycję na osi X, od której może rozpocząć się nowy segment.

Zmienne pomocnicze

x2  – współrzędna prawego końca segmentu

Lista kroków

K01: x2 ← x ; ustawiamy koniec segmentu
K02:     x ← x - 1 ; próbujemy rozszerzyć segment w lewo
K03:     Jeśli x ≥ xs i kolor piksela x,y ≠ cc, idź do K02 ; dopóki nie natrafimy na krawędź prostokąta obcinającego lub kontur
K04: x ← x + 1 ; poszliśmy za daleko, cofamy się. W x początek segmentu
K05:     x2 ← x2 + 1 ; próbujemy rozszerzyć segment w prawo
K06:     Jeśli x2 ≤ xe i kolor piksela x2,y ≠ cc, idź do K05 ; dopóki nie natrafimy na krawędź prostokąta obcinającego lub kontur
K07: Umieść na stosie x, y, x2 - x ; trójkę definiującą segment umieszczamy na stosie
K08: Zwróć (x2 + 1) i zakończ algorytm  

Wypełnianie powodziowe

int FindFSegment(s,x,y,rc,q,xs,xe)

s  – powierzchnia SDL_Surface
x, y  –  współrzędne piksela w segmencie
rc  – kolor wypełnianego obszaru
q  – stos
xs,xe  –  współrzędne x prostokąta obcinającego

Wyjście

Umieszczenie na stosie q trójki definiującej segment. Funkcja jako wartość zwraca współrzędną x2 + 1, czyli pierwszą pozycję na osi X, od której może rozpocząć się nowy segment.

Zmienne pomocnicze

x2  – współrzędna prawego końca segmentu

Lista kroków

K01: x2 ← x ; ustawiamy koniec segmentu
K02:     x ← x - 1 ; próbujemy rozszerzyć segment w lewo
K03:     Jeśli x ≥ xs i kolor piksela x,y = rc, idź do K02 ; dopóki nie natrafimy na krawędź prostokąta obcinającego lub inny kolor
K04: x ← x + 1 ; poszliśmy za daleko, cofamy się. W x początek segmentu
K05:     x2 ← x2 + 1 ; próbujemy rozszerzyć segment w prawo
K06:     Jeśli x2 ≤ xe i kolor piksela x2,y = rc, idź do K05 ; dopóki nie natrafimy na krawędź prostokąta obcinania lub inny kolor
K07: Umieść na stosie x1, y1, x2 - x ; trójkę definiującą segment umieszczamy na stosie
K08: Zwróć (x2 + 1) i zakończ algorytm  

Zwróć uwagę, iż oba algorytmy różnią się tylko w krokach K03 oraz K06, gdzie sprawdzamy warunek przynależności nowego piksela do wyznaczanego segmentu.

 

Przeszukiwanie segmentów

Drugi problem istotny dla algorytmu Smitha polega na wyznaczaniu wszystkich segmentów przyległych od góry i od dołu do danego segmentu i umieszczeniu ich na stosie.

W celu rozwiązania tego problemu przeglądamy kolejne piksele leżące ponad i poniżej danego segmentu. Jeśli natrafimy na piksel, który może należeć do nowego segmentu (np. dla wypełnienia konturowego piksel nie posiada ani koloru konturu, ani koloru wypełnienia), uruchamiamy funkcję FindSegment() ze współrzędnymi tego piksela. Funkcja wyznaczy współrzędne początku nowego segmentu oraz zwróci jego długość - dodatkowo tę trójkę umieści na stosie. Wykorzystujemy długość wyznaczonego segmentu, aby przesunąć się o odpowiednią ilość pikseli wzdłuż podstawowego segmentu - przesuwamy się o jeden piksel więcej w prawo niż wynosi współrzędna końca znalezionego segmentu. Operację kontynuujemy aż do przejścia przez cały segment. Poniżej przedstawiamy algorytm funkcji SearchSegment() dla obu typów wypełnień:

Wypełnienie konturowe

void SearchBSegment(s,x,y,len,cc,fc,q,xs,xe)

s  – powierzchnia SDL_Surface
x, y  – współrzędne początku segmentu do przeszukania
len  – długość przeszukiwanego segmentu
cc  – kolor konturu
fc  – kolor wypełnienia
q  –  stos
xs,xe  –  współrzędne x prostokąta obcinającego

Wyjście

Umieszczenie na stosie q wszystkich segmentów stycznych z danym segmentem.

Zmienne pomocnicze

x2  –  współrzędna prawego końca segmentu
pc  –  kolor piksela

Lista kroków

K01: x2 ← x + len - 1 ; wyznaczamy koniec segmentu
K02: Dopóki x ≤ x2: wykonuj kroki K03...K06 ; skanujemy segment bazowy
K03:     pc ← kolor piksela na pozycji x,y ; odczytujemy kolor piksela
K04:     Jeśli pc = fc, to x ← x + 2 i kontynuuj pętlę ; przeskakujemy obszar już wypełniony + piksel konturu
K05:     Jeśli pc = cc, to x ← x + 1 i kontynuuj pętlę ; przeskakujemy piksel konturu
K06:     x ← FindBSegment(s,x,y,cc,q,xs,xe) ; przeskakujemy znaleziony segment i umieszczamy go na stosie
K07: Zakończ

Wypełnianie powodziowe

void SearchFSegment(s,x,y,len,rc,fc,q,xs,xe)

s  – powierzchnia SDL_Surface
x, y  – współrzędne początku segmentu do przeszukania
len  – długość przeszukiwanego segmentu
rc  – kolor wypełnianego obszaru
fc  – kolor wypełnienia
q  –  stos
xs,xe  –  współrzędne x prostokąta obcinającego

Wyjście

Umieszczenie na stosie q wszystkich segmentów stycznych z danym segmentem.

Zmienne pomocnicze

x2  –  współrzędna prawego końca segmentu
pc  –  kolor piksela

Lista kroków

K01: x2 ← x + len - 1 ; wyznaczamy koniec segmentu
K02: Dopóki x ≤ x2: wykonuj kroki K03...K06 ; skanujemy segment bazowy
K03:     pc ← kolor piksela na pozycji x,y ; odczytujemy kolor piksela
K04:     Jeśli pc = fc, to x ← x + 2 i kontynuuj pętlę ; przeskakujemy obszar już wypełniony + piksel konturu
K05:     Jeśli pc ≠ rc, to x ← x + 1 i kontynuuj pętlę ; przeskakujemy piksel granicy
K06:     x ← FindFSegment(s,x,y,cc,q,xs,xe) ; przeskakujemy znaleziony segment i umieszczamy go na stosie
K07: Zakończ

 

 

Algorytm Smitha

Wykorzystamy teraz poprzednie cztery funkcje segmentowe do napisania algorytmu wypełniania.

Algorytm Smitha dla wypełniania konturowego

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

s  – powierzchnia SDL_Surface
x, y  –  współrzędne ziarna, od którego rozpocznie się wypełnianie obszaru
cc  – kolor konturu, który ogranicza wypełniany obszar
fc  – kolor wypełnienia

Wyjście

Wypełnia kolorem fc obszar ograniczony ośmiospójną linią konturu w kolorze cc oraz prostokątem obcinającym.

Zmienne pomocnicze

q  – stos
len  – długość przetwarzanych segmentów
xs,ys,xe,ye  –  współrzędne prostokąta obcinającego

Lista kroków

K01: xs ← s->clip.x ; obliczamy prostokąt obcinający
K02: ys ← s->clip.y  
K03: xe ← xs + s->clip.w - 1  
K04: ye ← ys + s->clip.h - 1  
K05: FindBSegment(s,x,y,cc,q,xs,xe) ; znajdujemy pierwszy segment i umieszczamy go na stosie
K06: Dopóki stos q zawiera dane, wykonuj kroki K07...K10  
K07:     Pobierz ze stosu x,y,len ; pobieramy segment ze stosu
K08:     Wypełnij segment kolorem fb ; faktyczne wypełnianie obszaru kolorem fcolor
K09:     Jeśli y > ys, to SearchBSegment(s,x,y-1,len,cc,fc,q,xs,xe) ; przeszukujemy górę segmentu umieszczając na stosie znalezione segmenty
K10:     Jeśli y < ye, to SearchBSegment(s,x,y+1,len,cc,fc,q,xs,xe) ; przeszukujemy dół segmentu umieszczając na stosie znalezione segmenty
K11: Zakończ  

Poniżej jest przykładowy program z implementacją algorytmu Smitha. Program jest identyczny jak w poprzednim rozdziale, zmieniono jedynie algorytm wypełniający

 

// Wypełnianie konturowe algorytmem Smitha
//----------------------------------------

#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;

// Aby zmniejszyć ilość przekazywanych argumentów
// do funkcji, wspólne zmienne tworzymy jako globalne
SDL_Window * w;   // Okno
SDL_Surface * s;  // Powierzchnia graficzna okna
stack<int> q;     // Stos
int xs,ys,xe,ye;  // Prostokąt obcinający
Uint32 cc,fc;     // Kolory konturu i wypełnienia

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(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(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(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;
}

// Funkcja znajduje segment
//-------------------------
int FindBSegment(int x, int y)
{
  int x2;

  x2 = x;  // x2 reprezentuje koniec segmentu
  do
    x--;   // próbujemy rozszerzyć segment w lewo
  while((x >= xs) && (ReadPixel(x,y) != cc));
  x++;
  do
    x2++;  // próbujemy rozszerzyć segment w prawo
  while((x2 <= xe) && (ReadPixel(x2,y) != cc));
  q.push(x); q.push(y); q.push(x2-x); // segment na stos
  return x2 + 1;
}

// Funkcja wyszukuje segmenty
//---------------------------
void SearchBSegment(int x, int y, int len)
{
  int x2;
  Uint32 pc;

  x2 = x + len - 1;  // koniec segmentu
  while(x <= x2)     // skanujemy segment
  {
    pc = ReadPixel(x,y);
    if(pc == fc)
    {
      x += 2;
      continue;
    }
    if(pc == cc)
    {
      x++;
      continue;
    }
    x = FindBSegment(x,y);
  }
}

// Rysuje segment w kolorze fc
//----------------------------
void DrawSegment(int x, int y, int len)
{
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;
  while(len--) *(addr++) = fc;
}

// Wypełnianie konturowe
//----------------------
void BoundaryFill(int x, int y)
{
  int len;

  // Obliczamy aktualny prostokąt obcinający
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;

  // Znajdujemy pierwszy segment i umieszczamy go na stosie
  FindBSegment(x,y);
  while(!q.empty())
  {
     // Pobieramy segment ze stosu w odwrotnej kolejności
     len = q.top(); q.pop();
     y   = q.top(); q.pop();
     x   = q.top(); q.pop();

     // Wypełniamy segment kolorem fb
     DrawSegment(x,y,len);

     // Znajdujemy segmenty powyżej i poniżej i umieszczamy je na stosie
     if(y > ys) SearchBSegment(x,y-1,len);
     if(y < ye) SearchBSegment(x,y+1,len);
  }
}

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
  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);
  }

  // Ustalamy kolory konturu i wypełnienia
  cc = PixelColor(255,255,255); // Kontur biały
  fc = PixelColor(0,127,0);     // Wypełnienie zielone dla odmiany

  // Wypełniamy od środka
  BoundaryFill(W_W/2,W_H/2);

  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;
}

 

Algorytm Smitha dla wypełniania powodziowego

FloodFill(s,x,y,cc,fc)

s  – powierzchnia SDL_Surface
x, y  –  współrzędne ziarna, od którego rozpocznie się wypełnianie obszaru
fc  – kolor wypełnienia

Wyjście

Wypełnia kolorem fc obszar ograniczony ośmiospójnymi obszarami i liniami w kolorach różnych od koloru obszaru oraz prostokątem obcinającym.

Zmienne pomocnicze

q  – stos
len  – długość przetwarzanych segmentów
rc  – kolor wypełnianego obszaru
xs,ys,xe,ye  –  współrzędne prostokąta obcinającego

Lista kroków

K01: xs ← s->clip.x ; obliczamy prostokąt obcinający
K02: ys ← s->clip.y  
K03: xe ← xs + s->clip.w - 1  
K04: ye ← ys + s->clip.h - 1  
K05: rc ← kolor piksela x,y ; pobieramy kolor ziarna
K06: FindFSegment(s,x,y,cc,q,xs,xe) ; znajdujemy pierwszy segment i umieszczamy go na stosie
K07: Dopóki stos q zawiera dane, wykonuj kroki K08...K11  
K08:     Pobierz ze stosu x,y,len ; pobieramy segment ze stosu
K09:     Wypełnij segment kolorem fb ; faktyczne wypełnianie obszaru kolorem fcolor
K10:     Jeśli y > ys, to SearchFSegment(s,x,y-1,len,rc,fc,q,xs,xe) ; przeszukujemy górę segmentu umieszczając na stosie znalezione segmenty
K11:     Jeśli y < ye, to SearchFSegment(s,x,y+1,len,rc,fc,q,xs,xe) ; przeszukujemy dół segmentu umieszczając na stosie znalezione segmenty
K12: Zakończ  

 

Przykładowy program.

 

// Wypełnianie powodziowe algorytmem Smitha
//-----------------------------------------

#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;

// Aby zmniejszyć ilość przekazywanych argumentów
// do funkcji, wspólne zmienne tworzymy jako globalne
SDL_Window * w;   // Okno
SDL_Surface * s;  // Powierzchnia graficzna okna
stack<int> q;     // Stos
int xs,ys,xe,ye;  // Prostokąt obcinający
Uint32 rc,fc;     // Kolory ziarna i wypełnienia

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(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(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(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;
}

// Funkcja znajduje segment
//-------------------------
int FindFSegment(int x, int y)
{
  int x2;

  x2 = x;  // x2 reprezentuje koniec segmentu
  do
    x--;   // próbujemy rozszerzyć segment w lewo
  while((x >= xs) && (ReadPixel(x,y) == rc));
  x++;
  do
    x2++;  // próbujemy rozszerzyć segment w prawo
  while((x2 <= xe) && (ReadPixel(x2,y) == rc));
  q.push(x); q.push(y); q.push(x2-x); // segment na stos
  return x2 + 1;
}

// Funkcja wyszukuje segmenty
//---------------------------
void SearchFSegment(int x, int y, int len)
{
  int x2;
  Uint32 pc;

  x2 = x + len - 1;  // koniec segmentu
  while(x <= x2)     // skanujemy segment
  {
    pc = ReadPixel(x,y);
    if(pc == fc)
    {
      x += 2;
      continue;
    }
    if(pc != rc)
    {
      x++;
      continue;
    }
    x = FindFSegment(x,y);
  }
}

// Rysuje segment w kolorze fc
//----------------------------
void DrawSegment(int x, int y, int len)
{
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;
  while(len--) *(addr++) = fc;
}

// Wypełnianie powodziowe
//-----------------------
void FloodFill(int x, int y)
{
  int len;

  // Obliczamy aktualny prostokąt obcinający
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;

  // Zapamiętujemy kolor ziarna
  rc = ReadPixel(x,y);

  // Znajdujemy pierwszy segment i umieszczamy go na stosie
  FindFSegment(x,y);
  while(!q.empty())
  {
     // Pobieramy segment ze stosu w odwrotnej kolejności
     len = q.top(); q.pop();
     y   = q.top(); q.pop();
     x   = q.top(); q.pop();

     // Wypełniamy segment kolorem fb
     DrawSegment(x,y,len);

     // Znajdujemy segmenty powyżej i poniżej i umieszczamy je na stosie
     if(y > ys) SearchFSegment(x,y-1,len);
     if(y < ye) SearchFSegment(x,y+1,len);
  }
}

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
  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);
  }

  // Ustalamy kolor wypełnienia
  fc = PixelColor(0,0,255);     // Wypełnienie niebieskie dla odmiany

  // Wypełniamy od środka
  FloodFill(W_W/2,W_H/2);

  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;
}

 

Wersja animowana. W kodzie specjalnie dodałem opóźnienie, gdyż algorytm działa zbyt szybko.

 

// Wypełnianie powodziowe algorytmem Smitha
//----------------------------------------

#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;

// Aby zmniejszyć ilość przekazywanych argumentów
// do funkcji, wspólne zmienne tworzymy jako globalne
SDL_Window * w;   // Okno
SDL_Surface * s;  // Powierzchnia graficzna okna
stack<int> q;     // Stos
int xs,ys,xe,ye;  // Prostokąt obcinający
Uint32 rc,fc;     // Kolory ziarna i wypełnienia

// Funkcja odczytuje kolor piksela na pozycji x,y
//------------------------------------------------
Uint32 ReadPixel(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(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(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;
}

// Funkcja znajduje segment
//-------------------------
int FindFSegment(int x, int y)
{
  int x2;

  x2 = x;  // x2 reprezentuje koniec segmentu
  do
    x--;   // próbujemy rozszerzyć segment w lewo
  while((x >= xs) && (ReadPixel(x,y) == rc));
  x++;
  do
    x2++;  // próbujemy rozszerzyć segment w prawo
  while((x2 <= xe) && (ReadPixel(x2,y) == rc));
  q.push(x); q.push(y); q.push(x2-x); // segment na stos
  return x2 + 1;
}

// Funkcja wyszukuje segmenty
//---------------------------
void SearchFSegment(int x, int y, int len)
{
  int x2;
  Uint32 pc;

  x2 = x + len - 1;  // koniec segmentu
  while(x <= x2)     // skanujemy segment
  {
    pc = ReadPixel(x,y);
    if(pc == fc)
    {
      x += 2;
      continue;
    }
    if(pc != rc)
    {
      x++;
      continue;
    }
    x = FindFSegment(x,y);
  }
}

// Rysuje segment w kolorze fc
//----------------------------
void DrawSegment(int x, int y, int len)
{
  Uint32 * addr = (Uint32 *)s->pixels + x + y * s->w;
  while(len--) *(addr++) = fc;
}

// Wypełnianie powodziowe
//-----------------------
void FloodFill(int x, int y)
{
  int len;

  // Obliczamy aktualny prostokąt obcinający
  xs = s->clip_rect.x;
  ys = s->clip_rect.y;
  xe = xs + s->clip_rect.w - 1;
  ye = ys + s->clip_rect.h - 1;

  // Zapamiętujemy kolor ziarna
  rc = ReadPixel(x,y);

  // Znajdujemy pierwszy segment i umieszczamy go na stosie
  FindFSegment(x,y);
  while(!q.empty())
  {
     // Pobieramy segment ze stosu w odwrotnej kolejności
     len = q.top(); q.pop();
     y   = q.top(); q.pop();
     x   = q.top(); q.pop();

     // Wypełniamy segment kolorem fb
     DrawSegment(x,y,len);

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

     // Opóźnienie, aby lepiej widzieć
     SDL_Delay(25);

     // Znajdujemy segmenty powyżej i poniżej i umieszczamy je na stosie
     if(y > ys) SearchFSegment(x,y-1,len);
     if(y < ye) SearchFSegment(x,y+1,len);
  }
}

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
  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);
  }

  // Ustalamy kolor wypełnienia
  fc = PixelColor(0,0,255);     // Wypełnienie niebieskie dla odmiany

  // Wypełniamy od środka
  FloodFill(W_W/2,W_H/2);

  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;
}

 

 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2019 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.