KI - SDL - zasłanianie ścian

Gdy rysujemy w przestrzeni obiekt o pełnych ścianach, to musimy rozwiązać problem zasłaniania ścian. W przeciwnym razie obiekt może zostać źle narysowany. Istnieje kilka rozwiązań tego problemu. Pierwsze z nich polega na posortowaniu ścian względem ich odległości od punktu obserwatora, a następnie rysowaniu ich od najdalszej do najbliższej. Wtedy ściany leżące z tyłu zostaną zarysowane ścianami leżącymi z przodu figury.

Dla prostoty umówmy się, że nasze ściany są kwadratami. Ścianę definiujemy za pomocą następujących struktur:

struct vertex3D
{
    double x,y,z;
};

struct vertex2D
{
    Sint32 x,y;
};

struct face3D
{
    int v1,v2,v3,v4;
    Uint32 color;
};

Struktura vertex3D definiuje punkt w przestrzeni trójwymiarowej. Punkt ten posiada trzy współrzędne rzeczywiste x,y,z.

Struktura vertex2D służy do definiowania punktu na powierzchni graficznej, która składa się z pikseli. Piksele posiadają współrzędne całkowite, dlatego w strukturze wykorzystywany jest typ całkowity do przechowywania współrzędnych piksela, który odpowiada rzutowi punktu na powierzchnię graficzną.

Struktura face3D definiuje ścianę. Zawiera ona numery punktów, które tworzą wierzchołki ściany oraz kolor powierzchni ściany. Umawiamy się, że wierzchołki v1...v4 są podane zgodnie z ruchem wskazówek zegara, gdy patrzymy na przód ściany.

Przez odległość ściany do punktu obserwatora będziemy rozumieli odległość jej środka od punktu obserwatora:

Przypominam, że punkt obserwatora leży na ujemnej połówce osi Z w odległości d od środka układu współrzędnych.

Środek ściany kwadratowej wyznaczymy ze wzorów:

gdzie x₁,y₁,z₁ i x₃,y₃,z₃ są odpowiednio współrzędnymi wierzchołków v₁ i v₃.

Mając punkt środka ściany, obliczamy kwadrat odległości do punktu obserwatora wg wzoru (do dalszych obliczeń wystarczy nam kwadrat):

Wzór ten można w prosty sposób wyprowadzić z twierdzenia Pitagorasa jako przekątną równoległoboku, co proponuję dociekliwym.

Odległości liczymy dla wszystkich ścian, a następnie sortujemy te ściany względem malejących odległości - na początku mają się znaleźć ściany najbardziej odległe, a na końcu ściany coraz bliższe punktowi obserwatora. Posortowane ściany rysujemy od najdalszej do najbliższej.

Poniższy program demonstruje tę metodę.

Przykładowa aplikacja

Program wykorzystuje bibliotekę newgfx.

Code::Blocks

// Zasłanianie ścian
// (C)2012 Koło Informatyczne
// I LO w Tarnowie
//-------------------------------

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

const double PI=3.1415926535897;

// Definicja typów danych

struct vertex3D
{
    double x,y,z;
};

struct vertex2D
{
    Sint32 x,y;
};

struct face3D
{
    int v1,v2,v3,v4;
    Uint32 color;
};

// Definicja wierzchołków figury

const int VN = 16;  // Liczba wierzchołków

vertex3D V[] = {{-1,-1,-0.5},{-1,-1,0.5},
                { 0,-1,-0.5},{ 0,-1,0.5},
                { 0, 0,-0.5},{ 0, 0,0.5},
                { 1, 0,-0.5},{ 1, 0,0.5},
                { 1, 1,-0.5},{ 1, 1,0.5},
                { 0, 1,-0.5},{ 0, 1,0.5},
                {-1, 1,-0.5},{-1, 1,0.5},
                {-1, 0,-0.5},{-1, 0,0.5}};

vertex3D VG[VN];

// Definicja ścian figury

const int FN = 14;  // Liczba ścian

face3D F[] ={{ 0, 1, 3, 2,0xffffff},
             { 2, 3, 5, 4,0xff0000},
             { 4, 5, 7, 6,0xffff00},
             { 6, 7, 9, 8,0x00ff00},
             { 9, 8,10,11,0x00ffff},
             {11,10,12,13,0x00ffff},
             {15,14,12,13,0x0000ff},
             { 0, 1,15,14,0x0000ff},
             { 0, 2, 4,14,0x7f00ff},
             {14, 4,10,12,0x7f00ff},
             { 4, 6, 8,10,0x7f00ff},
             { 3, 1,15, 5,0xff007f},
             { 5,15,13,11,0xff007f},
             { 7, 5,11, 9,0xff007f}};

// Tablica współrzędnych ekranowych wierzchołków

vertex2D VE[VN];

// Tworzy macierz jednostkową

void identity(double x[][4])
{
  for(int i = 0; i < 4; i++)
    for(int j = 0; j < 4; j++)
      x[i][j] = i == j ? 1 : 0;
}

// Mnoży macierze X = X x Y

void multiply(double x[][4], double y[][4])
{
    double c[4][4];  // macierz na wynik tymczasowy
    int i,j;

    // mnożymy C = X x Y

    for(i = 0; i < 4; i++)
      for(j = 0; j < 4; j++)
        c[i][j] = x[i][0]*y[0][j] + x[i][1]*y[1][j] + x[i][2]*y[2][j] + x[i][3]*y[3][j];

    // Kopiujemy X = C

    for(i = 0; i < 4; i++)
      for(j = 0; j < 4; j++) x[i][j] = c[i][j];
}

// Dołącza translację do macierzy przekształcenia

void translate(double g[][4], double Tx, double Ty, double Tz)
{
    double t[4][4];

    identity(t);  // tworzymy w t macierz jednostkową

    t[3][0] = Tx; // wstawiamy przesunięcia
    t[3][1] = Ty;
    t[3][2] = Tz;

    multiply(g,t); // dołączamy translację do przekształcenia
}

// Dołącza skalowanie do macierzy przekształcenia

void scale(double g[][4], double Sx, double Sy, double Sz)
{
    double s[4][4];

    identity(s);  // tworzymy w t macierz jednostkową

    s[0][0] = Sx; // wstawiamy skale
    s[1][1] = Sy;
    s[2][2] = Sz;

    multiply(g,s); // dołączamy skalowanie do przekształcenia
}

// Dołącza rotację do macierzy przekształcenia

void rotate_x(double g[][4], double alpha)
{
    double r[4][4],sa,ca;

    sa = sin(alpha);
    ca = cos(alpha);

    identity(r);    // tworzymy w t macierz jednostkową

    r[1][1] =  ca; r[1][2] = sa;
    r[2][1] = -sa; r[2][2] = ca;

    multiply(g,r); // dołączamy obrót do przekształcenia
}

void rotate_y(double g[][4], double alpha)
{
    double r[4][4],sa,ca;

    sa = sin(alpha);
    ca = cos(alpha);

    identity(r);    // tworzymy w t macierz jednostkową

    r[0][0] = ca; r[0][2] = -sa;
    r[2][0] = sa; r[2][2] = ca;

    multiply(g,r); // dołączamy obrót do przekształcenia
}

void rotate_z(double g[][4], double alpha)
{
    double r[4][4],sa,ca;

    sa = sin(alpha);
    ca = cos(alpha);

    identity(r);    // tworzymy w t macierz jednostkową

    r[0][0] =  ca; r[0][1] = sa;
    r[1][0] = -sa; r[1][1] = ca;

    multiply(g,r); // dołączamy obrót do przekształcenia
}

int main(int argc, char *argv[])
{
    int waiting = 1;

    SDL_Surface * screen;

    SDL_Event event;

    double kx = PI, ky = 0, kz = 0;       // Kąty pozycji na elipsie

    double alpha = 0;                     // Kąt obrotu sześcianu

    double sx = 0, sy = 100, sz = 6000;   // Współrzędne środka elipsy

    double rx = 700, ry = 600, rz = 5900; // Promienie elipsy

    double tx,ty,tz;                      // Wektor przesunięcia

    double d = 1000;                      // Punkt obserwatora

    double m;                             // Mnożnik

    SDL_Rect r;                           // Prostokąt wymazywania

    double G[4][4];                       // Macierz przekształcenia

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

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

        // Ustawiamy prostokąt wymazywania

        r.x = r.y = 0;
        r.w = screen->w;
        r.h = screen->h;

        do
        {
            // Obliczamy wektor przesunięcia

            tx = sx + rx * cos(kx);
            ty = sy + ry * sin(ky);
            tz = sz + rz * cos(kz);

            // modyfikujemy kąty

            kx += 0.005;
            ky += 0.0075;
            kz += 0.0125;

            if(kx > PI+PI) kx = 0;
            if(ky > PI+PI) ky = 0;
            if(kz > PI+PI) kz = 0;

            identity(G);           // zerujemy przekształcenie
            scale(G,500,700,900);  // obracamy oś obrotu figury na oś OX
            rotate_z(G,-PI/4);
            rotate_y(G,-PI/4);
            rotate_x(G,-PI/4);
            rotate_x(G,alpha);     // dokonujemy obrotu o kąt alpha
            rotate_x(G,PI/4);      // obracamy oś obrotu do poprzedniego położenia
            rotate_y(G,PI/4);
            rotate_z(G,PI/4);
            translate(G,tx,ty,tz+500); // dołączamy translację, przesuwając obiekt na tor ruchu

            alpha += 0.05; if(alpha > PI+PI) alpha = 0;

            // Obliczamy współrzędne ekranowe

            for(int i = 0; i < VN; i++)
            {
                // wyliczamy współrzędne po przekształceniu

                VG[i].x = G[0][0]*V[i].x + G[1][0]*V[i].y + G[2][0]*V[i].z + G[3][0];
                VG[i].y = G[0][1]*V[i].x + G[1][1]*V[i].y + G[2][1]*V[i].z + G[3][1];
                VG[i].z = G[0][2]*V[i].x + G[1][2]*V[i].y + G[2][2]*V[i].z + G[3][2];

                m = d / (VG[i].z + d);  // obliczamy mnożnik

                VE[i].x = (screen->w >> 1) + m * VG[i].x;
                VE[i].y = (screen->h >> 1) + m * VG[i].y;
            }

            // Tablica odległości ścian

            double FDist[FN];

            // Tablica numerów ścian

            int FNT[FN];

            // Obliczamy odległości ścian

            for(int i = 0; i < FN; i++)
            {
                FNT[i] = i;

                double x,y,z;

                x = (VG[F[i].v1].x + VG[F[i].v3].x) / 2;
                y = (VG[F[i].v1].y + VG[F[i].v3].y) / 2;
                z = (VG[F[i].v1].z + VG[F[i].v3].z) / 2;

                FDist[i] = x*x + y*y + (z+d)*(z+d);
            }

            // Sortujemy ściany wg odległości

            for(int j = 0; j < FN - 1; j++)
            {
                int pmin = j;
                for( int i = j+1; i < FN; i++) if(FDist[i] > FDist[pmin]) pmin = i;

                // Wymieniamy odległości w tablicy FDist[]

                double xd = FDist[pmin];
                FDist[pmin] = FDist[j];
                FDist[j] = xd;

                // Wymieniamy numery ścian w tablicy FNT[]

                int xn = FNT[pmin];
                FNT[pmin] = FNT[j];
                FNT[j] = xn;
            }

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

            // Rysujemy ściany wg kolejności ich numerów w FNT

            for(int i = 0; i < FN; i++)
            {
                Sint32 fig[100];

                // Tworzymy łamaną

                fig[0]  = 5;
                fig[1]  = VE[F[FNT[i]].v1].x;
                fig[2]  = VE[F[FNT[i]].v1].y;
                fig[3]  = VE[F[FNT[i]].v2].x;
                fig[4]  = VE[F[FNT[i]].v2].y;
                fig[5]  = VE[F[FNT[i]].v3].x;
                fig[6]  = VE[F[FNT[i]].v3].y;
                fig[7]  = VE[F[FNT[i]].v4].x;
                fig[8]  = VE[F[FNT[i]].v4].y;
                fig[9]  = VE[F[FNT[i]].v1].x;
                fig[10] = VE[F[FNT[i]].v1].y;
                fig[11] = 0;

                // Łamaną wypełniamy kolorem ściany

                gfxFillPoly(screen,fig,F[FNT[i]].color);
            }

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

            SDL_UpdateRect(screen, 0, 0, 0, 0); // Uaktualniamy ekran

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

            // Wymazujemy szkielet figury

            SDL_FillRect(screen, &r, 0);

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

            // Czekamy na klawisz ESCAPE

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

SDL - Zasłanianie ścian

Przykładowa aplikacja