SDL - Przekształcenia na płaszczyźnie

Mnożenie macierzy

W przekształceniach geometrycznych na płaszczyźnie oraz w przestrzeni trójwymiarowej intensywnie korzysta się z mnożenia macierzy. Macierz jest tablicą dwuwymiarową, która składa się z n wierszy i m kolumn:

 

  A[0][0] A[0][1] A[0][2] A[0][3]
A3 x 4 =  A[1][0] A[1][1] A[1][2] A[1][3]
  A[2][0] A[2][1] A[2][2] A[2][3]

 

Jeśli n = m, to mówimy, że macierz jest macierzą kwadratową:

 

  A[0][0] A[0][1] A[0][2]
A3 x 3 =  A[1][0] A[1][1] A[1][2]
  A[2][0] A[2][1] A[2][2]

 

Jeśli macierz składa się z jednego wiersza, to mówimy, że jest wektorem wierszowym:

 

A1 x 4 =  A[0] A[1] A[2] A[3]

 

Jeśli macierz składa się z jednej kolumny, to mówimy, że jest wektorem kolumnowym:

 

  A[0]
A3 x 1 =  A[1]
  A[2]

Zasada mnożenia dwóch macierzy A i B jest następująca:

 

Mamy dwie macierze: Am x n i Bn x o, gdzie m - liczba wierszy A, n - liczba kolumn A oraz wierszy B, o - liczba kolumn B.

Zauważ, że macierze A i B nie muszą posiadać takich samych rozmiarów. Jednakże macierz B musi posiadać tyle samo wierszy ile macierz A ma kolumn. Wynikiem mnożenia tych macierzy będzie:

 

Am x n x Bn x o = Cm x o

 

Zasadę obliczania kolejnych elementów macierzy wynikowej C przedstawimy na prostym przykładzie:

 

  a00 a01 a02
A3 x 3 =  a10 a11 a12
  a20 a21 a22

 

  b00 b01 b02
B3 x 3 =  b10 b11 b12
  b20 b21 b22

 

Ustawiamy odpowiednio obie macierze:

 

        b00 b01 b02
      B = b10 b11 b12
        b20 b21 b22
  a00 a01 a02 c00 c01 c02
A =  a10 a11 a12 c10 c11 c12
  a20 a12 a22 c20 c21 c22

 

Wartość elementu c00 macierzy wynikowej C obliczamy jako sumę iloczynów poszczególnych wyrazów z wiersza 0 macierzy A przez wyrazy z kolumny 0 macierzy B:

 

        b00 b01 b02
      B = b10 b11 b12
        b20 b21 b22
  a00 a01 a02 c00 c01 c02
A =  a10 a11 a12 c10 c11 c12
  a20 a12 a22 c20 c21 c22

 

c00 = a00 x b00 + a01 x b10 + a02 x b20

 

Kolejne wyrazy obliczamy podobnie: cij = suma iloczynów wyrazów z i-tego wiersza A przez wyrazy z j-tej kolumny B:

 

        b00 b01 b02
      B = b10 b11 b12
        b20 b21 b22
  a00 a01 a02 c00 c01 c02
A =  a10 a11 a12 c10 c11 c12
  a20 a12 a22 c20 c21 c22

 

c01 = a00 x b01 + a01 x b11 + a02 x b21

 

        b00 b01 b02
      B = b10 b11 b12
        b20 b21 b22
  a00 a01 a02 c00 c01 c02
A =  a10 a11 a12 c10 c11 c12
  a20 a12 a22 c20 c21 c22

 

c00 = a00 x b00 + a01 x b10 + a02 x b20

...

Macierz jednostkowa jest macierzą kwadratową, której główna przekątna zawiera wyrazy o wartości 1, a wszystkie pozostałe wyrazy mają wartość 0:

 

  1 0 0
I =  0 1 0
  0 0 1

 

Iloczyn macierzy jednostkowej przez dowolną macierz (o odpowiednich wymiarach) daje tę samą macierz:

 

I x A = A

 

Translacja o wektor T

Mamy dany punkt P(x,y).  Punkt reprezentujemy w postaci wektora wierszowego:

 

P = [x y 1]

 

Chcemy otrzymać punkt P', który jest obrazem punktu P po przesunięciu o wektor T(Tx,Ty), gdzie Tx jest przesunięciem w osi x, a Ty jest przesunięciem w osi y.

 

Translacja

 

Tworzymy macierz translacji T:

 

  1 0 0
T =  0 1 0
  Tx Ty 1

 

Wektor punktu P' otrzymamy ze wzoru: P' = P x T

 

        1 0 0
      T = 0 1 0
        Tx Ty 1
P =   x   y   1 x' y' 1

 

x' = x • 1 + y • 0 + 1 • Tx = x + Tx

y' = x • 0 + y • 1 + 1 • Ty = y + Ty

 

Zwróć uwagę, iż nie musimy liczyć całego wektora P'. Wystarczą tylko wartości x' i y', które nam będą potrzebne do rysowania po powierzchni graficznej.

 

Rotacja

Dany jest punkt P(x,y). Chcemy otrzymać obraz tego punktu P' przy obrocie o kąt φ:

 

Rotacja

 

Oś obrotu znajduje się w środku układu współrzędnych.

Tworzymy wektor P = [x y 1].

Tworzymy macierz rotacji:

 

  cosφ sinφ 0
R =  -sinφ cosφ 0
  0 0 1

 

i znów: P' = P x R

 

        cosφ sinφ 0
      R = -sinφ cosφ 0
        0 0 1
P =   x   y   1 x' y' 1

 

x' = x • cosφ + y • (-sinφ) + 1 • 0 = x • cosφ - y • sinφ

y' = x • sinφ + y • cosφ + 1 • 0 = x • sinφ + y • cosφ

 

Tutaj również wystarczy wyliczyć jedynie x' oraz y'.

 

Skalowanie

Skalowanie (ang. scaling) względem osi układu współrzędnych polega na przemnożeniu współrzędnych x i y każdego wierzchołka przez współczynniki skali w osi OX - sx i w osi OY - sy, które nie muszą być równe - wtedy obiekt zostanie rozciągnięty lub ściśnięty względem wybranej osi.

Skalowanie

 

Tworzymy wektor P = [x y 1].

Tworzymy macierz skalowania:

 

  Sx 0 0
S =  0 Sy 0
  0 0 1

 

P' = P x S

 

        Sx 0 0
      S = 0 Sy 0
        0 0 1
P =   x   y   1 x' y' 1

 

x' = x • Sx + y • 0 + 1 • 0 = x • Sx

y' = x • 0 + y • Sy + 1 • 0 = y • Sy

 

Składanie przekształceń

Przekształcenia geometryczne można w prosty sposób składać, uzyskując przekształcenie złożone. Na przykład obrót wokół punktu o współrzędnych xr,yr uzyskamy przesuwając obiekt o wektor -xr -yr, następnie dokonując obrotu o wymagany kąt i ponownie przesuwając o wektor xr yr. Co więcej możemy wcześniej przygotować macierz takiego przekształcenia mnożąc kolejne macierze przekształceń cząstkowych:

 

T1 - macierz przesunięcia o -xr -yr
R - macierz obrotu
T2 - macierz przesunięcia o xr yr

G = T1 x R x T2 - macierz przekształcenia całkowitego.

 

Reprezentacja figur płaskich

Obiekt będzie zbudowany z listy łamanych. Zasady tworzenia tej listy są następujące:

Każda łamana rozpoczyna się od liczby określającej liczbę wierzchołków. Jeśli liczba ta ma wartość 0, to oznacza to koniec listy łamanych. Za liczbą wierzchołków następują pary współrzędnych określających położenie wierzchołka na płaszczyźnie.

Przykład:

3 12 1 14 5 1 1 2 5 3 4 7 0

Ten obiekt składa się z dwóch łamanych:

 3  12 1 14 5 1 1       2  5 3 4 7     0

Pierwsza łamana posiada trzy wierzchołki: (12,1), (14,5) i (1,1).
Druga łamana posiada tylko dwa wierzchołki: (5,3) i (4,7).
Ostatnie zero oznacza koniec listy łamanych.

Listę łamanych można utworzyć w tablicy o odpowiedniej wielkości. Na przykład tak:

  Sint32 obj[] = {3, 12, 1, 14, 5, 1, 1, 2, 5, 3, 4, 7, 0};

Program

Program wykorzystuje bibliotekę newgfx.

 

Code::Blocks
// Przekształcenia na płaszczyźnie
// (C)2012 Koło Informatyczne
// I LO w Tarnowie
//-------------------------------

#include "newgfx.h"
#include <cmath>
#include <ctime>

// Funkcja tworzy macierz jednostkową

void Identity(double x[][3])
{
    int i,j;

    for(i = 0; i < 3; i++)
      for(j = 0; j < 3; j++)
        x[i][j] = (i == j) ? 1 : 0;
}

// A = A x B

void Multiply(double a[][3], double b[][3])
{
    double c[3][3];
    int i,j;

    for(i = 0; i < 3; i++)
      for(j = 0; j < 3; j++)
        c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j] + a[i][2]*b[2][j];

    for(i = 0; i < 3; i++)
      for(j = 0; j < 3; j++) a[i][j] = c[i][j];
}

// Dodaje do przekształcenia translację
// g[][] - macierz przekształcenia
// Tx - przesunięcie w osi x
// Ty - przesunięcie w osi y

void Translation(double g[][3], double Tx, double Ty)
{
    double t[3][3];

    Identity(t);   // tworzymy w t macierz jednostkową
    t[2][0] = Tx;  // dodajemy przesunięcie
    t[2][1] = Ty;
    Multiply(g,t); // dodajemy translację do przekształcenia
}

// Dodaje do przekształcenia rotację
// g[][] - macierz przekształcenia
// alfa - kąt w radianach

void Rotation(double g[][3], double alfa)
{
    double r[3][3],sa;

    sa = sin(alfa);
    Identity(r);   // tworzymy w r macierz jednostkową
    r[0][0] = r[1][1] = cos(alfa);
    r[0][1] = sa;
    r[1][0] = -sa;
    Multiply(g,r); // dodajemy rotację do przekształcenia
}

// Skalowanie
// g[][] - macierz przekształcenia
// Sxy - współczynnik skali na obu osiach

void Scaling(double g[][3], double Sxy)
{
    double s[3][3];

    Identity(s);   // tworzymy w s macierz jednostkową
    s[0][0] = s[1][1] = Sxy;
    Multiply(g,s); // dołączamy skalowanie do przekształcenia
}

// Oblicza współrzędne punktów po przekształceniu
// g[][] - macierz przekształcenia
// f - łamana źródłowa
// d - łamana docelowa

void Transformation(double g[][3],Sint32 * f, Sint32 * d)
{
    Sint32 licznik,i;
    double x,y;

    do
    {
        licznik = * d++ = * f++;  // odczytujemy liczbę punktów

        for(i = 0; i < licznik; i++)
        {
            x = * f++;    // odczytujemy współrzędne punktu
            y = * f++;

            // obliczamy współrzędne przekształcone i umieszczamy je
            // w łamanej docelowej na miejscu x i y

            * d++ = round(g[0][0]*x + g[1][0]*y + g[2][0]); // x'
            * d++ = round(g[0][1]*x + g[1][1]*y + g[2][1]); // y'
        }
    } while(licznik);
}

int main(int argc, char *argv[])
{
    int waiting = 1;
    int x,y,dx,dy,dr,dg,db;
    double alpha,da,scale,ds,G[3][3];
    Uint32 r,g,b;

    Sint32 f[] = {5,-60,-60, 60,-60, 60, 60,-60, 60,-60,-60,
                  4,  0,-40, 40, 40,-40, 40,  0,-40,
                  4,-40,-40,-20,-40,-40,  0,-40,-40,
                  4, 20,-40, 40,-40, 40,  0, 20,-40,
                  0};
    Sint32 d[100]; // figura docelowa - musi mieć co najmniej tyle samo elementów co f

    SDL_Surface * screen;
    SDL_Event event;

    const double DPI = 6.28318530717958;

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

    if(!SDL_Init(SDL_INIT_VIDEO))
    {
        atexit(SDL_Quit);

        screen = SDL_SetVideoMode(1024, 768, 32, SDL_HWSURFACE | SDL_FULLSCREEN);

        x = y = 1;
        dx = (1 + rand() % 3) * (1 - 2 * (rand() % 2));
        dy = (1 + rand() % 3) * (1 - 2 * (rand() % 2));
        alpha = 0;
        da = 0.03;   // zmiana kata przy każdym kadrze animacji
        scale = 1;
        ds = 0.01;   // zmiana skali
        r = 0; g = 0; b = 0;
        dr = 2; dg = 3; db = 5;

        do
        {
            SDL_Delay(16);

            Identity(G);           // tworzymy macierz przekształcenia
            Scaling(G,scale);      // dodajemy skalowanie
            Rotation(G,alpha);     // dodajemy obrót
            Translation(G,x,y);    // dodajemy przesunięcie

            Transformation(G,f,d); // wyznaczamy łamaną po transformacji

            if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);

            gfxFillPoly(screen,d,(r << 16) | (g << 8) | b);

            if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

            SDL_UpdateRect(screen, 0, 0, 0, 0);

            if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);

            gfxFillPoly(screen,d,0); // wymazujemy figurę z ekranu

            if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

            // modyfikujemy parametry ruchu dla następnego kadru

            x += dx;
            y += dy;
            if((x <= 0) || (x > screen->w)) dx = -dx;
            if((y <= 0) || (y > screen->h)) dy = -dy;

            alpha += da;
            if(alpha >= DPI) alpha = 0;

            scale *= 1 + ds;
            if((scale < 0.3) || (scale > 6)) ds = -ds;

            if(r + dr > 255) dr = -dr;
            if(g + dg > 255) dg = -dg;
            if(b + db > 255) db = -db;

            r += dr;
            g += dg;
            b += db;

            // sprawdzamy, czy nie naciśnięto ESC - jeśli tak, kończymy.

            if (SDL_PollEvent(&event))
                if ((event.type == SDL_QUIT) ||
                   ((event.type == SDL_KEYDOWN) &&
                    (event.key.keysym.sym == SDLK_ESCAPE))) waiting = 0;
        } while(waiting);
    }

    return 0;
}

 



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.