Wypełnianie wielokątów

Powrót do spisu treści

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
OL038 - podstawowe algorytmy wypełniania obszarów
OL039 - algorytm Smitha
OL040 - praca w środowisku sterowanym zdarzeniami
OL041 - czcionka bitmapowa
OL042 - czcionka wektorowa
OL043 - przyciski poleceń

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 SDL010.

 

Artykuł w PRZEBUDOWIE


SDL

Wypełnianie wielokątów jest operacją bardzo często stosowaną w grafice komputerowej, szczególnie w grafice trójwymiarowej. Dzięki niej otrzymujemy realistyczne obrazy przedmiotów, które posiadają ściany, a nie jedynie obrysy:

Siatka i ściany        

Znanych jest wiele różnych metod wypełniania wielokątów. Jedna z bardziej popularnych to wypełnianie wielokąta przez skanowanie liniami poziomymi (ang. scan linie polygon fill). Zasada jest bardzo prosta. Mamy dany wielokąt, który składa się z ciągu łamanych - opis tworzenia takiego wielokąta znajdziesz w artykule OL051. Wielokąt przecinamy liniami równoległymi do osi OX o współrzędnych yi rosnących od ymin do ymax, gdzie ymin i ymax jest zakresem współrzędnych y wierzchołków łamanej.

Linia skanująca i wielokąt

Obliczamy punkty przecięcia linii skanującej z krawędziami wielokąta. Obliczone punkty sortujemy rosnąco: x1, x2, x3 i x4. Kolejne pary punktów łączymy liniami poziomymi:

Wypełnianie

Zatem pierwsze podejście do konstrukcji algorytmu będzie następujące (specjalnie pomijamy specyfikację wejścia i wyjścia, gdyż nie jest to jeszcze gotowy algorytm):

K01: Na podstawie listy łamanych skonstruuj listę krawędzi wielokąta
K02: Przeglądnij listę krawędzi i wyznacz ymin i ymax
K03: Dla y = ymin, ymin+1,...,ymax wykonuj kroki K04...K06
K04:     Wyznacz X - zbiór współrzędnych x punktów przecięcia krawędzi z listy z linią skanującą y
K05:     Posortuj rosnąco zbiór X
K06:     Kolejne pary punktów ze zbioru X połącz linią poziomą na wysokości y.
K07: Zakończ

Na pozór wszystko wygląda OK. Jednakże musimy rozważyć kilka przypadków szczególnych.

Krawędź pozioma

Mamy problem. Jeśli linia skanująca przechodzi przez krawędź poziomą, to jak wyznaczyć punkt przecięcia? Przecież spełniają go wszystkie punkty x od początku do końca krawędzi?

Krawędź pozioma

Umawiamy się - na liście krawędzi wielokąta nie umieszczamy krawędzi poziomych, czyli takich, dla których zachodzi równość współrzędnych y punktu początkowego i końcowego.

Linia skanująca przecina wierzchołek wielokąta

Wierzchołek łączy dwie krawędzie, zatem na współrzędnej x wierzchołka otrzymamy dwa punkty przecięcia linii skanującej - po jednym dla każdej z krawędzi. Poniższy rysunek przedstawia możliwe przypadki:

Rodzaje wierzchołków

Pierwszy wierzchołek jest stalaktytem - obie złączone w nim krawędzie są powyżej linii skanującej. Do zbioru X zostaną wprowadzone dwa punkty x1 i x2 o równej wartości. Jak widać nie stanowi to problemu Linia pozioma od x1 do x2 będzie pojedynczym punktem.

Drugi wierzchołek jest stalagmitem - obie złączone w nim krawędzie leżą poniżej linii skanującej. Do zbioru X będą wstawione dwie współrzędne x4 i x5. To również nie stanowi problemu. Linie poziome x3-x4 oraz x5-x6 są prawidłowe.

Trzeci wierzchołek wprowadza problem - otrzymamy dwie współrzędne x6 i x7. Algorytm narysuje złą linię od x7 do x8. Nie narysuje za to właściwej linii od x8 do x9.  I dodatkowo zostanie współrzędna x9, z którą nie wiadomo co zrobić. Wniosek może być tylko jeden - w przypadku wierzchołka nie będącego stalaktytem ani stalagmitem należy do zbioru X wprowadzać tylko jedną współrzędną x. Technicznie można to zrealizować przez wyrzucanie krawędzi, gdy linia skanująca osiągnie współrzędną y jej dolnego końca. Jednakże przy takim podejściu nie będą rysowane dolne krawędzie obszaru oraz punkt końcowy stalaktytu - w sumie jest to nawet pożądane, ponieważ przy wielu przyległych wielokątach unikamy powtórnego rysowania linii na liniach już narysowanych, co w niektórych przypadkach może nawet prowadzić do błędów w grafice.

Nasz algorytm możemy teraz nieco usprawnić:

K01: Dla kolejnych krawędzi wielokąta wykonuj kroki K02...K04
K02:     Jeśli krawędź jest pozioma, pomiń ją i przejdź do następnej krawędzi
K03:     Dodaj krawędź do listy krawędzi
K04: Na podstawie listy krawędzi wyznacz ymin i ymax
K05: Dla y = ymin, ymin+1,...,ymax wykonuj kroki K07...K09
K06:     Wyznaczaj punkty przecięcia linii skanującej z kolejnymi krawędziami, pomijając krawędzie,
    w których linia skanująca przechodzi przez dolny wierzchołek. Wyznaczone punkty umieszczaj
    w zbiorze X.
K07:     Posortuj rosnąco zbiór X
K08:     Kolejne pary współrzędnych ze zbioru X połącz linią poziomą na wysokości y, przy czym
    lewą współrzędną x zaokrąglij w górę, prawą zaokrąglij w dół.
K09: Zakończ

Podział krawędzi

Na obecnym etapie naszego algorytmu wyznaczanie punktów przecięcia linii skanującej wymaga sprawdzenia wszystkich krawędzi wielokąta. Jeśli krawędzi tych jest dużo, może to być dosyć kosztowne. Ale przecież linia skanująca nie przecina wszystkich krawędzi:

Rodzaje krawędzi

Linia skanująca porusza się w dół (oś OY jest skierowana w dół na powierzchni graficznej). Kolorem niebieskim zaznaczyliśmy krawędzie wielokąta, które algorytm już przetworzył (dla przejrzystości na rysunku nie ma wypełnienia). Do tych krawędzi w algorytmie już nigdy nie wrócimy, zatem nie ma sensu ich dalej sprawdzać na punkty przecięcia z linią skanującą.

Kolorem zielonym zaznaczyliśmy krawędzie, do których algorytm jeszcze nie doszedł - tych krawędzi też nie musimy sprawdzać.

Pozostają krawędzie zaznaczone kolorem czerwonym - to krawędzie, które aktualnie przecina linia skanująca. Nazwiemy je krawędziami aktywnymi. Kandydatami na krawędzie aktywne są tylko krawędzie zielone. Krawędź staje się aktywna, gdy linia skanująca osiąga jej górny koniec (o mniejszej współrzędnej y), a przestaje być aktywna, gdy linia skanująca osiąga dolny koniec (punkt końcowy o większej współrzędnej y).

Wynika z tego, iż powinniśmy dla każdej krawędzi zapamiętać współrzędne y dolnego i górnego końca.

Narzucającym się rozwiązaniem jest stworzenie dwóch list:

W trakcie skanowania pobieramy z LK wszystkie krawędzie, których punkt początkowy (górny) ma współrzędną y równą współrzędnej y linii skanującej i wstawiamy je do LKA. Z kolei z LKA wyrzucamy wszystkie krawędzie, dla których punkt dolny ma współrzędną y równą współrzędnej y linii skanującej - te krawędzie zostały już przeskanowane.

Wyznaczanie współrzędnej x punktu przecięcia krawędzi z linią skanującą

Kolejna optymalizacja dotyczy wyznaczania punktów przecięcia linii skanującej z krawędzią aktywną. Możemy oczywiście wykorzystać do tego celu wzory matematyczne:

Punkt przecięcia

Jeśli x1 = x2, to krawędź jest pionowa i zawsze x = x1.

Jeśli y = y1, to linia skanująca osiągnęła pierwszy punkt krawędzi i x = x1.

W pozostałych przypadkach wykorzystujemy prostą proporcję:

x - x1  =  x2 - x1
y - y1 y2 - y1
x = x1 +  x2 - x1  (y - y1)
y2 - y1

Jednakże takie podejście wymaga wykonywania dużej liczby obliczeń. A przecież możemy wykorzystać bardzo proste spostrzeżenie:

Jeśli pewna krawędź jest przecinana przez linię skanującą o współrzędnej y, to zapewne będzie również przecinana przez następną linię skanującą o współrzędnej y + 1. Przy umieszczaniu krawędzi na liście LK wystarczy wyliczyć stały przyrost dx dla kolejnych wartości y linii skanującej:

dx =   x2 - x1
y2 - y1

Kolejną wartość współrzędnej x przecięcia linii skanującej z krawędzią otrzymamy ze wzoru:

xi+1 = xi + dx

Możemy teraz określić pożądaną postać danych dla elementów list LK i LKA:

Element listy LK powinien zawierać współrzędne y punktu początkowego i końcowego krawędzi oraz współrzędną x punktu początkowego i przyrost dx dla danej krawędzi.

Element listy LKA powinien zawierać współrzędną y punktu końcowego krawędzi, aktualną współrzędną x punktu przecięcia krawędzi z linią skanującą oraz przyrost dx.

Ograniczanie listy krawędzi

Ostatnie usprawnienie dotyczy wybierania elementów list LK i LKA. Aby uniknąć przeglądania całej listy od początku do końca, elementy powinny być posortowane:

Lista LK jest posortowana rosnąco względem współrzędnych y punktów początkowych krawędzi - wtedy wybór elementów dla listy LKA sprowadza się do sprawdzania i przenoszenia początkowych elementów listy LK do LKA, jeśli współrzędna y linii skanującej jest równa współrzędnej y punktu początkowego krawędzi w LK.

Lista LKA jest posortowana rosnąco względem współrzędnych y punktów końcowych krawędzi - wtedy z listy LKA usuwamy początkowe elementy, o współrzędnej y punktu końcowego mniejszej od współrzędnej y linii skanującej - krawędzie już przeskanowane.

Sortowanie obu list może być wykonywane już na etapie wstawiania do nich nowych krawędzi. Od zastosowanego algorytmu sortującego zależy klasa złożoności operacji wypełniania wielokąta.

Ponieważ wielokąt będzie rysowany wewnątrz prostokąta obcinającego, to listę LK można ograniczyć tylko do krawędzi, które wpadają w poziomy pas prostokąta obcinania (krawędzie zielone na poniższym rysunku):

Pas obcinania

Krawędzie przecinające brzeg pasu obcinania obcinamy do fragmentów leżących wewnątrz tego pasa:

Obcięty wielokąt

Listę krawędzi LK można posortować w czasie O(n) algorytmem sortowania kubełkowego, który tutaj szczególnie się nadaje z uwagi na ograniczoną liczbę wartości współrzędnych y punktów początkowych krawędzi - szerokość pasa obcinania jest ograniczona wysokością w pionie powierzchni graficznej - praktycznie do 1024 wartości.

Pełny algorytm wypełniania wielokąta przez skanowanie liniami poziomymi

Wejście

F  -  lista łamanych, które definiują wielokąt. Łamane powinny tworzyć figurę zamkniętą.
color  - kolor wypełnienia
clip  - prostokąt obcinania.

Wyjście

Wypełnienie obszaru wewnątrz wielokąta pikselami o zadanym kolorze

Dane pomocnicze

x1,x2  -  współrzędne x punktów początkowego i końcowego krawędzi
y1,y1  - współrzędne y punktów początkowego i końcowego krawędzi
ymin  - minimalna wartość współrzędnych y punktów tworzących wielokąt
ymax  - maksymalna wartość punktów tworzących wielokąt
LK  -  tablica kubełków o wartościach równych kolejnym współrzędnym od ymin do ymax.
Każdy kubełek jest listą krawędzi, których górny punkt posiada współrzędną y równą wartości kubełka.
Element E listy zawiera następujące dane:
    y - współrzędna y punktów początkowego i końcowego krawędzi
    x - współrzędna x punktu początkowego
    dx - przyrost x dla kolejnych y tej krawędzi
LKA  - lista krawędzi aktywnych. Każdy element E zawiera:
    y - współrzędną y punktu końcowego
    x  - aktualną współrzędną x punktu przecięcia z linią skanującą
    dx - przyrost x dla kolejnych y

Lista kroków

K01: Utwórz tablicę pustych kubełków LK o rozmiarze równym wysokości prostokąta obcinania clip ; pierwszy kubełek LK[0] odnosi się do y = clip.y
K02: ymin ← clip.y + clip.h ; ustawiamy wartości początkowe zakresu y
K03: ymax ← clip.y  
K04: Dopóki istnieją nieprzetworzone krawędzie w F, wykonuj kroki K05...K19 ; przechodzimy przez kolejne krawędzie wielokąta
K05:     Wyznacz współrzędne punktu początkowego x1,y1 oraz końcowego x2,y2 krawędzi.  
K07:     Jeśli (y1 < clip.y) i (y2 < clip.y), przejdź do następnego obiegu pętli K04 ; pomijamy krawędzie leżące pod pasem obcinania
K08:     Jeśli (y1 ≥ clip.y + clip.h) i (y2 ≥ clip.y + clip.h), przejdź do następnego obiegu pętli K04 ; oraz nad pasem obcinania
K09:     Twórz element listy E.  
K10:     Jeśli ymin > y1, to ymin ← y1 ; ustalamy wstępne minimum
K11:     Jeśli ymax < y2, to ymax ← y2 ; i maksimum dla y
K12:     E.x ← x1 ; współrzędna początkowa x
K13:
    E.dx ←   x2 - x1
y2 - y1
; przyrost x dla kolejnych y
K14:     Jeśli y1 ≥ clip.y, przejdź do kroku K15 ; sprawdzamy, czy krawędź rozpoczyna się pod pasem obcinania
K15:     E.x ← E.x + E.dx • (clip.y - y1) ; jeśli tak, obliczamy dla niej nowy punkt startowy x
K16:     y1 ← clip.y ; przesuwamy współrzędną y punktu początkowego krawędzi
K17:     Jeśli y2 ≥ clip.y + clip.h, to y2 ← clip.y + clip.h ; obcinamy krawędź wybiegającą poza pas obcinania
K18:     E.y ← y2  
K19:     Jeśli y1 ≠ y2, wstaw E do kubełka LK[y1 - clip.y] ; umieszczamy nie poziomą krawędź we właściwym kubełku
K20: Utwórz pustą listę LKA  
K21: Jeśli ymin < clip.y, to ymin ← clip.y ; korygujemy zakres y
K22: Jeśli ymax > clip.y + clip.h - 1, ymax ← clip.y + clip.h - 1  
K23 Dla y = ymin,ymin+1,...,ymax wykonuj kroki K24...K31 ; przebiegamy zakres współrzędnych y linią skanującą
K24:     Usuń z listy LKA wszystkie krawędzie, dla których E.y = y ; usuwamy krawędzie przeskanowane
K25:     Jeśli kubełek LK[y - clip.y] jest pusty, przejdź do kroku K28  
K26:     Posortuj kubełek LK[y - clip.y] wg E.x. ; przenosimy krawędzie aktywne z LK do LKA
K27:     Scal zawartość kubełka LK[y - clip.y] z listą LKA ; przenosimy do LKA krawędzie, które osiągnęła linia skanująca
K28:     Połącz linią w kolorze color na wysokości y współrzędne x kolejnych par
    elementów listy LKA. Lewą współrzędną zaokrąglij w górę, prawą zaokrąglij w dół
; wypełniamy linią
K29:     Dla każdego elementu listy LKA oblicz nowe E.x ← E.x + E.dx ; wyznaczamy współrzędną punktu przecięcia dla y + 1
K30:     Posortuj listę LKA względem rosnących współrzędnych E.x jej elementów  
K31: Zakończ  

Na podstawie opisanego powyżej algorytmu utworzymy funkcję biblioteczną. Utwórz nowy projekt SDL. Załaduj do niego pliki SDL_gfx.h i SDL_gfx.cpp - opis w podsumowaniu SDL010.

Na końcu pliku SDL_gfx.h dopisz prototyp funkcji:


void gfxFillPoly(SDL_Surface * s, Sint32 * f, Uint32 color);

Funkcja posiada następujące parametry:

s  -  wskaźnik struktury SDL_Surface.
f  - wskaźnik listy łamanych, która definiuje prostokąt
color  - kolor wypełnienia

Na końcu pliku SDL_gfx.cpp dopisz definicję nowej funkcji:


// Wypełnia zadany wielokąt podanym kolorem
// s     - wskaźnik struktury SDL_Surface
// f     - wskaźnik listy łamanych
// color - kolor wypełnienia
//-----------------------------------------

// Element list LK i LKA
//----------------------

typedef struct
{
  Sint32 y;
  double x, dx;
} LKElement;

// Funkcja służy do porównań elementów list LK i LKA
//--------------------------------------------------

bool CompareLKElements(LKElement a, LKElement b)
{
   return a.x < b.x;    
}

void gfxFillPoly(SDL_Surface * s, Sint32 * f, Uint32 color)
{
  list<LKElement> LK[s->clip_rect.h];  // tablica kubełków
  list<LKElement> LKA;                 // lista krawędzi aktywnych

  Sint32 y1clip = s->clip_rect.y;
  Sint32 y2clip = y1clip + s->clip_rect.h - 1;
  Sint32 ymax   = y1clip;
  Sint32 ymin   = y2clip;
  Sint32 xp, xk, yp, yk, x1, x2, y1, y2, y, plen;

  while(plen = * f++)
  {
    xp = * f++; yp = * f++;
    while(--plen)
    {
      xk = * f++; yk = * f++;            
      if(yp > yk)
      {
        x1 = xk; y1 = yk; x2 = xp; y2 = yp;
      }
      else
      {
        x1 = xp; y1 = yp; x2 = xk; y2 = yk;
      }
      if(((y1 >= y1clip) || (y2 >= y1clip)) && ((y1 <= y2clip) || (y2 <= y2clip)))
      {
        LKElement E;
        if(ymin > y1) ymin = y1;
        if(ymax < y2) ymax = y2;
        E.x  = x1;
        E.dx = (x2 - x1) / (double)(y2 - y1);
        if(y1 < y1clip)
        {
          E.x += E.dx * (y1clip - y1);
          y1 = y1clip;      
        }
        E.y = y2;
        if(y1 != y2) LK[y1 - y1clip].push_front(E);
      }
      xp = xk; yp = yk;
    }              
  }

  if(ymin < y1clip) ymin = y1clip;
  if(ymax > y2clip) ymax = y2clip;
  
  for(y = ymin; y <= ymax; y++)
  {
    list<LKElement>::iterator i = LKA.begin();
    while(i != LKA.end()) if(i->y == y) i = LKA.erase(i); else i++;
    if(LK[y - y1clip].size())
    {
      LK[y - y1clip].sort(CompareLKElements);
      LKA.merge(LK[y - y1clip],CompareLKElements);
    }

    bool selector = false;

    for(list<LKElement>::iterator i = LKA.begin(); i != LKA.end(); i++)
    {
      if(selector)
      {
        x2 = (Sint32)floor(i->x);
        gfxClipHLine(s, x1, y, color, x2 - x1 + 1);
      }
      else x1 = (Sint32)ceil(i->x);
      selector = !selector;
      i->x += i->dx;
    }
    LKA.sort(CompareLKElements);
  }
  LKA.clear();
}

Poniżej mamy małą modyfikację programu testowego z poprzednich zajęć, który prezentuje różne transformacje geometryczne - tym razem figury są wypełnione różnymi kolorami dzięki nowej funkcji. Przed uruchomieniem programu skopiuj do katalogu projektowego czcionkę vecprop9x12.fnt.


// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P041 - Transformacje geometryczne z wypełnianiem wielokątów
//------------------------------------------------------------

#include <SDL/SDL_gfx.h>
#include <SDL/SDL_gui.h>
#include <time.h>

const int SCRX = 640;      // stałe określające szerokość i wysokość
const int SCRY = 480;      // ekranu w pikselach

SDL_Surface * screen;
gfxFont     * font = gfxOpenFont("vecprop9x12.fnt");

//------------------------------------------
// Funkcje obsługujące poszczególne animacje
//------------------------------------------

void (* action)();         // wskaźnik funkcji

Sint32 figure[] = {11,0,20,20,0,40,0,40,20,60,20,60,40,50,50,50,60,20,60,0,40,0,20,0};

char * t[] = {"Transformacje geometryczne"," Translacja "," Rotacja "," Skalowanie ",
              " Jednokładność "," Powinowactwo "," Ścinanie "," Zakończ "};

// Ustala prostokąt obcinania dla animacji
// i kasuje ekran - włącza blokadę
//----------------------------------------

void SetClip()
{
  SDL_Rect r;
  
  r.x = 0; r.y = font->h + 8; r.h = screen->h - font->h - 8; r.w = screen->w;
  
  SDL_SetClipRect(screen,&r);
  
  if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);

  SDL_FillRect(screen, &(screen->clip_rect), 0);  
}

// Odtwarza prostokąt obcinania
//-----------------------------

void RestoreClip(int i)
{
  gfxDrawText(screen, font, t[i], (screen->w >> 1) - (gfxTextLength(font, t[i]) >> 1),
              screen->clip_rect.y + 8, 0x00ff00, -1);
  SDL_Rect r;
  
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

  SDL_UpdateRect(screen, screen->clip_rect.x, screen->clip_rect.y,
                 screen->clip_rect.w, screen->clip_rect.h);    

  r.x = 0; r.y = 0; r.h = screen->h; r.w = screen->w;
  
  SDL_SetClipRect(screen, &r);
}

// Translacja
//-----------

const int MAXF = 100;

double Tx[MAXF],Ty[MAXF],dx[MAXF],dy[MAXF];
int    si[MAXF];

void InitTransI(int i)
{
  int xp,yp,xk,yk;
  si[i] = 300 + rand() % 1000;
  switch(rand() % 4)
  {
    case 0:
      xp = rand() % (screen->w + 120) - 60;
      xk = rand() % (screen->w + 120) - 60;
      yp = -60;
      yk = screen->h + 60;
      break;
    case 1:
      xp = rand() % (screen->w + 120) - 60;
      xk = rand() % (screen->w + 120) - 60;
      yk = -60;
      yp = screen->h + 30;
      break;
    case 2:
      yp = rand() % (screen->h + 120) - 60;
      yk = rand() % (screen->h + 120) - 60;
      xp = -60;
      xk = screen->w + 60;
      break;
    case 3:
      yp = rand() % (screen->h + 120) - 60;
      yk = rand() % (screen->h + 120) - 60;
      xk = -60;
      xp = screen->w + 60;
      break;
  }
  Tx[i] = xp; Ty[i] = yp;
  dx[i] = (xk - Tx[i]) / si[i];
  dy[i] = (yk - Ty[i]) / si[i];
}

void InitTrans()
{
  for(int i = 0; i < MAXF; i++) InitTransI(i);     
}

void Trans()
{ 
  SetClip();

  for(int i = 0; i < MAXF; i++)
  {
    if(!si[i]) InitTransI(i);
    si[i]--;
    Tx[i] += dx[i];
    Ty[i] += dy[i];
    double * T = gfx2DTrans(Tx[i], Ty[i]);
    Sint32 * F = gfx2DCopyPoly(figure);
    gfx2DTransform(F, T);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    delete [] T;
    delete [] F;
  }
  RestoreClip(1);
}

// Rotacja
//-----------

double phi[MAXF], dphi[MAXF];

void InitRot()
{
  for(int i = 0; i < MAXF; i++)
  {
    Tx[i] = rand() % (screen->w);
    Ty[i] = rand() & (screen->h);
    phi[i] = 0;
    dphi[i] = 1 / (double)(200 + rand() % 200);
  }
}

void Rot()
{
  SetClip(); 

  for(int i = 0; i < MAXF; i++)
  {
    phi[i] += dphi[i];
    if(phi[i] > 6.2831853) phi[i] -= 6.2831853;
    double * T1 = gfx2DTrans(Tx[i] - (screen->w >> 1), Ty[i] - (screen->h >> 1));
    double * R  = gfx2DRot(phi[i]);
    double * T2 = gfx2DTrans((screen->w >> 1),(screen->h >> 1));
    double * E  = gfxMMul(3, 3, 3, T1, R);
    double * G  = gfxMMul(3, 3, 3, E, T2);
    Sint32 * F  = gfx2DCopyPoly(figure);
    gfx2DTransform(F, G);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    delete [] T1;
    delete [] R;
    delete [] T2;
    delete [] E;
    delete [] F;
    delete [] G;
  }
  
  gfxLine(screen, screen->w >> 1, (screen->h >> 1) - 5,
                  screen->w >> 1, (screen->h >> 1) + 5, 0xff0000);
  gfxLine(screen, (screen->w >> 1) - 5, screen->h >> 1,
                  (screen->w >> 1) + 5, screen->h >> 1, 0xff0000);
                  
  RestoreClip(2);
}

// Skalowanie
//-----------

double Sx[MAXF], Sy[MAXF], dSx[MAXF], dSy[MAXF];

void InitScale()
{
  for(int i = 0; i < MAXF; i++)
  {
    Tx[i] = rand() % (screen->w);
    Ty[i] = rand() & (screen->h);
    Sx[i] = 0.5; dSx[i] = 1 / (double)(200 + rand() % 200);
    Sy[i] = 0.5; dSy[i] = 1 / (double)(200 + rand() % 200);
  }
}

void Scale()
{
  SetClip();

  for(int i = 0; i < MAXF; i++)
  {
    if((Sx[i] < -2) || (Sx[i] > 2)) dSx[i] = - dSx[i];
    if((Sy[i] < -2) || (Sy[i] > 2)) dSy[i] = - dSy[i];
    Sx[i] += dSx[i];
    Sy[i] += dSy[i];    
    double * T1 = gfx2DTrans(-30, -30);
    double * S  = gfx2DScale(Sx[i], Sy[i]);
    double * T2 = gfx2DTrans(Tx[i] + 30, Ty[i] + 30);
    double * E  = gfxMMul(3, 3, 3, T1, S);
    double * G  = gfxMMul(3, 3, 3, E, T2);
    Sint32 * F  = gfx2DCopyPoly(figure);
    gfx2DTransform(F, G);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    delete [] T1;
    delete [] S;
    delete [] T2;
    delete [] E;
    delete [] F;
    delete [] G;
  }
                  
  RestoreClip(3);
}

// Jednokładność
//-----------

double kH[MAXF], dkH[MAXF];

void InitHomoth()
{
  for(int i = 0; i < MAXF; i++)
  {
    Tx[i] = rand() % (screen->w);
    Ty[i] = rand() & (screen->h);
    kH[i] = 1; dkH[i] = 1 / (double)(200 + rand() % 200);
  }     
}

void Homoth()
{
  SetClip();

  for(int i = 0; i < MAXF; i++)
  {
    if((kH[i] < -2) || (kH[i] > 2)) dkH[i] = - dkH[i];
    kH[i] += dkH[i];
    double * T  = gfx2DTrans(Tx[i], Ty[i]);    
    double * H  = gfx2DHomoth(screen->w >> 1, screen->h >> 1, kH[i]);
    double * G  = gfxMMul(3, 3, 3, T, H);
    Sint32 * F  = gfx2DCopyPoly(figure);
    gfx2DTransform(F, G);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    gfxLine(screen, screen->w >> 1, (screen->h >> 1) - 5,
                    screen->w >> 1, (screen->h >> 1) + 5, 0xff0000);
    gfxLine(screen, (screen->w >> 1) - 5, screen->h >> 1,
                    (screen->w >> 1) + 5, screen->h >> 1, 0xff0000);
    delete [] T;
    delete [] H;
    delete [] G;
    delete [] F;
  }
                  
  RestoreClip(4);   
}

// Powinowactwo
//-------------

void Affine()
{
  SetClip();

  for(int i = 0; i < MAXF; i++)
  {
    if((kH[i] < -2) || (kH[i] > 2)) dkH[i] = - dkH[i];
    kH[i] += dkH[i];
    double * T = gfx2DTrans(Tx[i], Ty[i]);    
    double * A = gfx2DAffine(-screen->h + 1, screen->w - 1, 0, kH[i]);
    double * G = gfxMMul(3, 3, 3, T, A);
    Sint32 * F = gfx2DCopyPoly(figure);
    gfx2DTransform(F, G);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    gfxClipLine(screen, 0,0,screen->w - 1, screen->h - 1, 0xff0000);
    delete [] T;
    delete [] A;
    delete [] G;
    delete [] F;
  }
                  
  RestoreClip(5);
}

// Ścinanie
//---------

double kx[MAXF], dkx[MAXF], ky[MAXF], dky[MAXF];

void InitShear()
{
  for(int i = 0; i < MAXF; i++)
  {
    Tx[i] = rand() % (screen->w);
    Ty[i] = rand() % (screen->h);
    kx[i] = 0; dkx[i] = 1 / (double)(200 + rand() % 200);
    ky[i] = 0; dky[i] = 1 / (double)(200 + rand() % 200);
  } 
}

void Shear()
{
  SetClip();

  for(int i = 0; i < MAXF; i++)
  {
    if((kx[i] < -2) || (kx[i] > 2)) dkx[i] = - dkx[i];
    if((ky[i] < -2) || (ky[i] > 2)) dky[i] = - dky[i];
    kx[i] += dkx[i];
    ky[i] += dky[i];
    double * S = gfx2DShear(kx[i], ky[i]);
    double * T = gfx2DTrans(Tx[i], Ty[i]);
    double * G = gfxMMul(3, 3, 3, S, T);
    Sint32 * F = gfx2DCopyPoly(figure);
    gfx2DTransform(F, G);
    gfxFillPoly(screen, F, 0x007000 ^ 0x03ff00 * i);
    gfx2DDrawPoly(screen, F, 0xffff00);
    delete [] T;
    delete [] S;
    delete [] G;
    delete [] F;
  }

  RestoreClip(6); 
}

// Funkcja obsługująca przyciski
//------------------------------

void bfn(gfxGUIObject * sender)
{
  switch(sender->tag)
  {
    case 1: InitTrans();  action = Trans;  break;
    case 2: InitRot();    action = Rot;    break;
    case 3: InitScale();  action = Scale;  break;
    case 4: InitHomoth(); action = Homoth; break;
    case 5: InitHomoth(); action = Affine; break;
    case 6: InitShear();  action = Shear;  break;
    case 7: exit(0);
  }
}

//***********************
// *** Program główny ***
//***********************

int main(int argc, char * argv[])
{
  
// Tablica siedmiu wskaźników do przycisków

  gfxButton * b[7];
  
  if(SDL_Init(SDL_INIT_VIDEO)) exit(-1);

  atexit(SDL_Quit);
  
  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE))) exit(-1);

  SDL_WM_SetCaption(t[0], ""); 
    
// Tworzymy przyciski akcji

  SDL_Rect r;

  r.x = r.y = r.w = 0;
  r.h = font->h + 8;
    
  for(int i = 1; i <= 7; i++)
  {
    b[i] = new gfxButton(i, true, screen, font, &r, t[i], bfn);
    r.x += gfxTextLength(font, t[i]) + 4;
  }
   
// Inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// Inicjujemy animacje

  InitTrans();
  action = Trans;
  
// Obsługujemy zdarzenia

  SDL_Event event;
  
  bool running = true;  
  while(running)
  {
    SDL_Delay(1);
    (* action)(); // wywołujemy funkcję obsługi animacji
    while(SDL_PollEvent(&event))
    {
      bool eventfree;
      for(int i = 1; i <= 7; i++)
        if(!(eventfree = b[i]->DoEvents(&event))) break;
      if(eventfree && (event.type == SDL_QUIT))
      {
        running = false;
        break;
      }
    }
  }
  
// zamykamy czcionkę

  gfxCloseFont(font);

// Usuwamy przyciski

  for(int i = 1; i <= 7; i++) delete b[i];
  return 0;
}

Efekt działania programu


Podsumowanie



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.