3. Alapvető grafikai algoritmusok

A következőkben az algoritmusoknál raszteres megjelenítőt feltételezünk. Ezeknél a képernyőn megjelenített adatok valamilyen képmátrixba, videómemóriába kerülnek.

  • Ez egy kétdimenziós tömb.

  • A tömbben lévő értékek mutatják, hogy milyen színű legyen az adott képpont.

A jellegzetes geometriai alakzataink folytonosak, a raszterizálás viszont diszkrét és véges. A raszterzilásra tekinthetünk úgy, mint egy mintavételezési folyamatra.

A raszterizálásnál szempont az, hogy

  • a megjelenítés minél gyorsabb tudjon lenni, és

  • a kép minősége minél jobb legyen.

Ezt a kettőt általában nem lehet egyszerre javítani.

Figyelem

A geometriai alakzataink a valóságban nem léteznek.

Gyakorlati szempontból problémát jelent, hogy különböző konvenciók vannak a koordináták megadásához.

  • Geometriai jelölésrendszert feltételezve a vízszintes tengely az \(x\), a függőleges tengely az \(y\). Az \(x\) érték balról-jobbra, az \(y\) érték pedig lenntről felfelé szokott növekedni.

  • Lineáris algebra és numerikus módszerek kapcsán a mátrixot sor és oszlop szerint szokás indexelni.

  • A grafikus megjelenítő eszközöknél az origó a bal felső sarokban szokott lenni. Az \(x\) érték balról-jobbra nő, az \(y\) érték fenntről-lefelé.

Szoktunk beszélni világ, valós és képi koordinátarendszerről. Ezek között az átváltás általában skálázás, tükrözés és eltolás műveletekkel valósítható meg.

Példa

Tegyük fel, hogy a képernyőnk felbontása \(1600 \times 800\). Ezen szeretnénk megjeleníteni az \(\{(x, y) | -5 \leq x < 5, 0 \leq y < 5\}\) halmaz pontjait. Feltételezzük, hogy az origó a képernyő aljának közepén van.

  • Írjuk fel azt a függvényt, amelyik a sík pontjait a képernyő képpontjaihoz rendeli!

\[f(x, y) = (\text{Round}(160 \cdot x + 800), \text{Round}(160 \cdot (5 - y)))\]

  • Írjuk fel azt a függvényt, amelyik a képernyő képpontjait a sik pontjaihoz rendeli!

\[f(x, y) = ((x - 800) / 160, (800 - y) / 160)\]

Megjegyzés

Az átalakításnál kerekítés helyett gyakran csak alsóegészrész vagy a törtrész levágása szerepel.

Rajzoló algoritmusok

Az egyszerűbb elemektől a bonyolultabbak felé kerülnek bemutatásra az algoritmusok.

A képernyőt a következő struktúrával írjuk le:

typedef struct Screen {
  int w;
  int h;
  int data[WIDTH][HEIGHT];
} Screen;

Pontok

A matematikai értelemben vett pontoknak nincs kiterjedésük, így azok megjelenítésével nem érdemes foglalkozni. A gyakorlatban mégis előfordul, úgy mint

  • egy képpont színének átállításával kapott pont,

  • kis méretű négyzet, vagy

  • kis méretű kör.

Egy pontot adott raszteres megjelenítőn a képmátrix megfelelő értékének az átállításával lehet megjeleníteni.

  • A képpontonkénti elérés nem feltétlenül hatékony.

  • A videómemóriához nincs mindig közvetlen hozzáférésünk.

  • Bizonyos rendszerek a pontoknak is definiálnak vastagságot, így gyakorlatilag négyzetként vagy körlapként jelenítik meg azokat.

Egy képpont megadásához az alábbi struktúrát használhatjuk:

typedef struct Point {
  int x;
  int y;
} Point;

\(\rhd\) Hogyan tudunk egy képpontot címezni, hogy ha a képbufferünk egy egydimenziós tömb?

Vízszintes és függőleges vonalak

Vízszintes vonal rajzolása:

void draw_horizontal(Screen* screen, int y, int color) {
  for (int x = 0; x < screen->w; ++x) {
    screen->data[x][y] = color;
  }
}

Függőleges vonal rajzolása:

void draw_vertical(Screen* screen, int x, int color) {
  for (int y = 0; y < screen->h; ++y) {
    screen->data[x][y] = color;
  }
}

Megjegyzés

Az előzőekben feltételeztük, hogy az x és y értékek a képernyő megjelenítési tartományán belül vannak. Ezt a programokban általában ellenőrízni is kell!

\(\rhd\) Hogyan tudjuk ezeket hatékonyan kirajzoltatni, hogy ha a képbufferünk egy egydimenziós tömb?

Téglalapok

A téglalapoknak egy speciális esetéről lesz szó, amelyeknél

  • az oldalak párhuzamosak a tengelyekkel, és

  • a téglalap egész képpontokat fed csak le.

typedef struct Rect {
  int x;
  int y;
  int width;
  int height;
} Rect;

Téglalap rajzolása color színnel:

void draw_rect(Screen* screen, Rect* rect, int color) {
  for (int y = rect->y; y < rect->y + rect->h; ++y) {
    for (int x = rect->x; x < rect->x + rect->w; ++x) {
      screen->data[x][y] = color;
    }
  }
}

Megjegyzés

Az előzőekben több feltételezéssel éltünk.

  • A téglalap teljes egészében a megjeleníthető tartományba esik.

  • A téglalap értékei megfelelőek (nincs például negatív szélesség).

Szakaszok rajzolása, élsimítás

A raszteres képernyő véges, ezért egyenesek helyett inkább csak szakaszok rajzolásáról beszélhetünk.

A szakasz rajzolásához a legegyszerűbb megoldás a DDA (Digital Differential Analyzer).

void draw_line_dda(Screen* screen, Point* a, Point* b, int color) {
  double x, y, dx, dy, step;
  dx = (b->x - a->x);
  dy = (b->y - a->y);
  step = (abs(dx) > abs(dy)) ? abs(dx) : abs(dy);
  dx /= step;
  dy /= step;
  x = a->x;
  y = a->y;
  for (int t = 0; t <= step; ++t) {
    screen->data[(int)x][(int)y];
    x += dx;
    y += dy;
  }
}

A Bresenham algoritmus ennél egy hatékonyabb megoldást ad.

  • Előnye, hogy egész aritmetikát használ.

  • Az elterjedt architektúrákon hatékonyan implementálható.

  • Hardver szintjén elérhető implementációk (pl.: firmware-ben).

Megjegyzés

A következő algoritmus feltételezi, hogy

  • a szakasz az első síknegyedben van, és

  • a rajta áthaladó egyenes \(y = m \cdot x + b\) alakú egyenletében \(0 \leq m < 1\).

void draw_line_bresenham(Screen* screen, Point* a, Point* b, int color) {
  int x, y, dx, dy, diff;
  dx = b->x - a->x;
  dy = b->y - a->y;
  diff = 2 * dy - dx;
  for (x = a->x, y = a->y; x <= b->x; ++x) {
    screen->data[x][y] = color;
    if (diff > 0) {
      ++y;
      diff -= 2 * dx;
    }
    diff += 2 * dy;
  }
}

Példa

Vizsgáljuk meg, hogy milyen pontokat rajzol ki az algoritmus a \((4, 3)\) és \((12, 5)\) pontokat összekötő szakaszon!

dx = 8, dy = 2, diff = -4

x

y

diff

4

3

-4

5

3

0

6

3

4

7

4

-12

8

4

-8

9

4

-4

10

4

0

11

4

4

12

5

-12

Élsimítás (Anti Aliasing)

Háromszög kitöltés

  • Triangle Rasterization

  • Arra törekszünk, hogy éppen csak annyi képpontot jelenítsünk meg, amennyire szükség van.

  • A kitöltött háromszöget megjeleníthetjük úgy, mint közvetlenül egymás alá rajzolt vízszintes szakaszokat. (Megoldható lenne függőlegesekkel is.)

\(\rhd\) Vizsgáljuk meg, hogy mennyi speciális és problémás eset fordulhat elő!

Kör, ellipszis rajzolása

A kört és általánosan az ellipszist is sokszögként közelíthetjük, mint zárt görbét. A probléma így visszavezethető a szakasz rajzolásra.

typedef struct Circle {
  int x;
  int y;
  int radius;
} Circle;

void draw_circle(Screen* screen, Circle* circle, int color) {
  double x_0, y_0, x, y;
  double phi, delta;
  phi = 0;
  delta = 0.01;
  x_0 = circle->radius * cos(phi) + circle->x;
  y_0 = circle->radius * sin(phi) + circle->y;
  while (phi < 2 * M_PI) {
    Point p_0;
    Point p;
    phi += delta;
    x = circle->radius * cos(phi) + circle->x;
    y = circle->radius * sin(phi) + circle->y;
    p_0->x = x_0;
    p_0->y = y_0;
    p->x = x;
    p->y = y;
    draw_line(screen, &p_0, &p, color);
    x_0 = x;
    y_0 = y;
  }
}

\(\rhd\) Hogyan érdemes megválasztani a delta változó értékét?

\(\rhd\) Hogyan lehet az algoritmust ellipszis rajzolásához általánosítani?

  • A Bresenham algoritmus körvonal rajzolására is alkalmas. (Szintén 8 esetet kell megkülönböztetni.)

  • A háromszögekhez hasonlóan egymás alá rajzolt szakaszokként jeleníthetjük meg a kitöltött alakzatot.

  • Az élsimítás problémája itt is felvetődik.

  • A függvénykönyvtárak esetében kör és ellipszis helyett gyakran csak ív (körív, elliptikus ív) rajzolása szerepel, amelyhez szögtartományt is meg lehet adni.

Képelemek vágása

  • A megjelenítéshez használt felületünk (vagy úgy általában térrészünk) véges. Ezt nevezzük viewport-nak.

  • Gyakori eset, hogy az eredményben csak az alakzatok bizonyos része látszik.

  • Az alakzatok megjelenítendő részének meghatározása külön számításokat igényel.

Szakaszmetsző eljárások

  • Danny Cohen, Ivan Sutherland: Cohen-Sutherland algoritmus, 1967

  • You-Dong Liang, Brian A. Barsky: Liang-Barsky algoritmus

Az algoritmus működése:

  • A teret a viewport oldalaival 9 részre vágjuk.

  • Bevezetünk egy bináris kódolást, amely azt mutatja, hogy a viewport-tól milyen irányba vagyunk, például top-bottom-left-right sorrendben.

  • A megjelenítendő térrészhez a 0000 kód fog tartozni.

  • A szakasz végpontjaihoz megállapítjuk a kódokat.

  • Elvégzünk egy bitenkénti vagy műveletet. Hogy ha 0000-t kapunk, akkor a teljes szakasz megjelenítendő

  • egyébként elvégzünk egy bitenkénti és (AND) műveletet. Hogy ha NEM 0000-át kapunk, akkor a szakasz nem látszik.

  • Ha 0000-át kaptunk az AND műveletre, akkor elvégezzük a metszést az OR művelet szerinti bitekhez tartozó oldalakra.

\(\rhd\) Mennyi eset van összesen a végpontok térrészbe esésére vonatkozóan? Vizsgáljunk meg ezek közül néhányat!

Poligonok vágása

Floodfill algoritmus

Az előzőekben olyan algoritmusokat vizsgáltunk, amelyek a koordináták alapján, a matematikai alakzatokat közelítve oldották meg a megjelenítést.

Az adott színnel való kitöltés egy szintén gyakori algoritmus, amely inkább a gráfalgoritmusokhoz sorolható.

Szoftveres eszközök

GUI toolkit-ek

Windows API

GTK

KDE

Java Swing

További függvénykönyvtárak

DOS

HTML5 Canvas API

OpenGL, DirectX, Vulkan

  • 2D-s megjelenítésre is alkalmasak.

  • Később kerülnek még részletezésre.

Esemény- és programvezérelt programozás

Az alkalmazásunk szempontjából eseményeknek tekinthetjük például az alábbiakat:

  • billentyűzet esemény,

  • egér esemény,

  • időzítő esemény,

  • hálózati kérésre adott válasz esemény.

Aszinkron eseményekről van szó.

  • Az eseményvezérelt programozás azt jelenti, hogy a programban végrehajtandó műveleteket bizonyos eseményekhez rendeljük.

  • Programvezérelt esetben a programkódunkban kell azt (szinkron módon) vizsgálni, hogy következett-e be esemény.

#include "app.h"

/**
* Main function
*/
int main(int argc, char* argv[])
{
    App app;

    create_app(&app, 800, 600);
    while (app.is_running) {
        handle_app_events(&app);
        update_app(&app);
        render_app(&app);
    }
    destroy_app(&app);

    return 0;
}

\(\rhd\) Hogy lehetne megoldani a visszatérési hibakód kezelését?

Keretidő

  • A két, egymást követő képkocka kirajzolása között eltelt idő.

  • Jelölhetjük például \(\Delta t\)-vel.

  • Ezt használjuk fel az alkalmazás állapotának a frissítéséhez.

Megjegyzés

Az update és a render műveletek nem minden esetben kell, hogy felváltva kövessék egymást.

MVC modell

  • Modell-Nézet-Vezérlő, Model-View-Controller

  • A programunk aktuális állapotát jelenítjük meg a render végrehajtása során. Egy leképzésről, függvény jellegű kapcsolatról van szó.

  • Esetünkben az eseménykezelő függvény az ami a Controller.

  • Az MVC-nek számos változata, és értelmezése van, például MVP, MVVM.

  • https://en.wikipedia.org/wiki/Model%E2%80%93view%E2%80%93controller

Megjegyzés

Az alkalmazás kódját ezen logika szerint érdemes szervezni. Nem jó, hogy ha keverednek a megjelenítéssel, eseménykezeléssel és az állapottér módosításával kapcsolatos kódrészek.

Interaktív grafikus felületek kialakítása

A programunkban be- és kimenet kezelésére egyaránt szükség van.

A különféle (hardveres vagy grafikus elemekhez kötött) vezérlők segítségével interakcióba tudunk lépni a virtuális terünk elemeivel.

SDL2

Kérdések

  • Milyen problémák megoldásához használjuk az SDL2-őt?

  • Mi a keretidő, és mire használjuk a programokban?

  • Miért szerepeltetünk a függvények többségénél első paraméterként egy struktúra mutatót? Mi ennek a megfelelője más nyelvekben?

  • Mikor kerül megjelenítésre a virtuális tér SDL2 esetében?

  • Milyen események tartoznak az egér kezeléséhez?

  • Milyen események tartoznak a billentyűzet kezeléséhez?

Számítási feladatok

  • Tegyük fel, hogy az \((x, y) \in [-8, 8] \times [-6, 6]\) pontokat szeretnénk megjeleníteni a képernyőn. A képernyő felbontása \(1024 \times 768\).

    • Írja fel azt a függvényt, amelyik a sík pontjaihoz a képernyő képpontjait rendeli!

    • Írja fel azt a függvényt, amelyik a képernyő képpontjaihoz a sík pontjait rendeli!

    • Írjuk fel az előző függvényeket transzformációs mátrixok alakjában!

  • A síkban egy 10 egység sugarú körvonalat 2 egység szélességű vonallal jelenítünk meg. Mennyi az így kapott alakzat területe?

Programozási feladatok

Szakaszok rajzolása

  • Definiáljunk egy szakasz (Line) nevű struktúrát, amelyik tartalmazza a szakasz végpontjait és a kirajzoláshoz használt színt! (A szín lehet index vagy karakter szerint megadott, vagy RGB komponensekkel is. Utóbbi esetben célszerű definiálni egy külön Color struktúrát.)

  • Nézzünk utána, hogy hogyan kezelhető SDL-ben az egéresemény! Kérdezzük le az egérkurzor pozícióját és írassuk ki a szabványos kimenetre!

  • Készítsünk egy szakasz rajzoló programot, amellyel egérkattintással lehet megadni a szakaszok végpontjait! (Feltételezzük, hogy legfeljebb MAX_LINE_COUNT számú szakasz tárolható és jeleníthető meg egyszerre.)

  • Készítsünk egy palettát, ahonnan kattintással kiválasztható az adott szakasz megjelenítéséhez használt színt!

  • Készítsünk egy olyan változatot, melyben a szakaszok helyett beszínezett téglalapok vannak!

Kör közelítése

  • Az examples/circle példában szereplő Circle struktúrát egészítsük ki egy szín attribútummal!

  • A szakasz kirajzolásához használt függvény segítségével készítsünk egy olyan programot, amely a körvonalat szakaszokkal közelíti!

  • Vizsgáljuk meg azon eseteket, amikor a közelítést a felosztáshoz használt lépések számával, a lépések szögével illetve a kirajzolt szakaszok maximális hosszával adhatjuk meg!

  • Készítsünk egy programot, amellyel különböző színű köröket lehet megjeleníteni!

  • Oldjuk meg, hogy az egér segítségével új köröket is meg lehessen adni! (A számukat itt is maximalizálhatjuk, például egy MAX_CIRCLE_COUNT értékkel.)

  • Az egéresemények kezelésével rajzoljunk be egy + vagy x jelet azon körökbe, amely felett van éppen a kurzor. (Egyidejűleg több felett is lehet.)

  • Oldjuk meg, hogy a kirajzolt köröket az egér segítségével lehessen mozgatni!