Számítógépes grafika házi feladat tutorial

Tartalomjegyzék

1 Előszó
2 Az OpenGL és GLUT alapjai
- 2.1 Az OpenGL
- 2.2 A GLUT
3 Az első házihoz szükséges elmélet
4 A második házihoz szükséges elmélet
5 A harmadik házihoz szükséges elmélet
6 Utóhang

Előszó

Ez a segédlet a házikhoz kellő ötletek és OpenGL függvények működését hivatott elmagyarázni. Az elméletbe csak olyan mélységig megy bele, hogy a házidat meg tudd írni, de nem olyan mélységig, hogy a védésen, vagy vizsgán feltett kérdések mindegyikére válaszolni tudj. Arra ott vannak a hivatalos források: az előadásdiák, a sünis könyv, és - sokak számára meglepő - de maga az előadás is. Amiben ez a összefoglaló más az előbb említett forrásoktól, az az, hogy ez sokkal tömörebb és lényegre törőbb, mindenhol megpróbálja felhívni a figyelmed a tipikus hibákra, illetve tartalmaz több ezer sornyi kipróbálható példaprogramot. Ezek a programok azért érhetőek el forráskóddal együtt, hogy könnyen ki tudd próbálni őket, részekre tudd bontani, apró módosításokat is ki tudj rajta próbálni, egyszóval azért vannak itt, hogy a megértést segítsék. Nem azért, hogy ezekből oldd meg a feladatodat. Én megbízok bennetek, de ha ezzel visszaéltek, le fogom szedni a példaprogramokat.

Az oldalról kódot a saját házidba átemelni TILOS! Más házijába lehet, oda csak nem ajánlott. Még ha pár sornyi kódról is van szó, akkor is inkább gépeld be magadnak, addig is gyakorolsz... (nem csak gépelni). Meg persze nem is érdemes másolni, mert csak borzolod vele a plágiumkereső idegeit.

Az OpenGL és GLUT alapjai

Az OpenGL

Az OpenGL egyszerű térbeli alakzatok (primitívek), pl.: pontok, vonalak, háromszögek rajzolására specializálódott.
- Ezekből az építőkockákból csodákat lehet művelni, a mai számítógépes játékok nagyrészt hárszömszögek rajzolásából építkeznek.
- A primitíveket nagyon sokféleképpen és nagyon hatékonyan lehet az OpenGL-lel kirajzolni, de ezen kívül semmi mást nem tud, nem tud képet betölteni, árnyékokat számolni, de még egy kocka kirajzolásához is "küzdeni" kell.
- A hatékonyság növelése érdekében az OpenGL a videókártyát is használja a rajzoláshoz.
- Egy rajzolófüggvény viselkedése több száz paramétertől függ, persze nem kell az összeset függvény argumentumként átadni, ehelyett az OpenGL egy állapotgép-en alapszik.
  - Ha valamit átállítasz (pl. a rajzolószínt), akkor az onnantól kezdve minden rajzolás-hívást befolyásol.
A legtöbb OpenGL függvényt több különböző típusú paraméterrel is meg lehet hívni, viszont az OpenGL egy C könyvtár, amiben nincs függvény overload. Ennek kiküszöbélésére a függvények neve Hungarian Notation szerűen a név végén tartalmaz pár karaktert, ami a paraméterekre utal, pl.: 3f - 3 db float, 2iv - 2 elemű int vector (azaz pointer egy tetszőleges memóriaterületre, ahol 2 db int van egymás után)
- pl.: glVertex3f()
Az OpenGL elnevezési konvenciója:
- A függvények neve mindig kisbetűvel kezdődik, a gl, glu vagy glut szavakkal, attól függően hogy melyik függvénykönyvtárban található a függvény
- Ha több szóból áll, azokat egybeírjuk, és a szavakat nagy betűvel kezdjük (camelCase).
  - pl.: glDrawElementsInstancedBaseVertexBaseInstance() - amúgy ez a leghosszabb nevű OpenGL függvény, de a tárgyból nincs rá szükség.
A grafikában a lebegőpontos számokkal float alakban szeretünk dolgozni. A double-el nem az a gond, hogy kétszer annyi helyet foglal, hanem hogy a double pontosságú műveletvégzés sokkal lassabb, mint ha megelégednénk a float által elvárt pontossággal. Ez az oka annak, hogy a videókártyák, kb 2011-ig csak floatokkal tudtak számolni (double-el csak szoftveresen emulálva, nagyjából 25-ször olyan lassan). Az OpenGL-nek az a verziója, amit a tárgyban kell használni (1.1), csak floatokkal tud dolgozni a videókártyán, ami azt jelenti, hogy ha double-t adsz neki, attól nem csak, hogy nem lesz pontosabb, de még plusz munkát is adsz neki ezzel, mert neki vissza kell kasztolni a számot floattá, és ez a kasztolás nagyon nincs ingyen. A floatok használatának egy további előnye, hogy az x86 processzorok 4 db float műveletet tudnak egyszerre elvégezni SSE-vel. Ez az oka annak, hogy a tárgyból a legtöbb függvénynek csak a floatot váró alakját lehet használni, például a glVertex3f-et lehet, de a glVertex3d-t nem.
Az OpenGL RGB színskálán állítja elő a képet, és neki is RGB értéket kell adni, ha egy színt akarunk leírni. A grafikában általában nem a megszokott komponensenként egy byte-on (0, 255) specifikáljuk a színeket. Ezzel alapvetően az baj, hogy a színhez tartozó fényerősség csak nagyon kis tartományon változhat, ahhoz képest amekkora különbségek a valóságban előfordulnak, pl. a Nap színe, vagy éjszaka egy sötét szobának a színei között több mint 10000-szeres fényerősségbeli különbség van. A másik gond, hogy a byte színekkel nehéz műveletet végezni, pl. a valóságban két fehér fény összege egy még fényesebb fehér, míg az egy byte-on leírt színeknél a fehér már önmagából a lehető legvilágosabb szín, amit meg tudunk jeleníteni. Ennek az orvoslására a színeket komponensenként floatokkal írjuk le. Nem véletlen egybeesés, hogy a megvilágítást a videókártya számolja az OpenGL-ben, ami mint tudjuk, floatokkal szeret dolgozni. Egy fényt két dolog is jellemez, az egyik a színe (hullámhossza), ami jelen esetben az RGB komponensek aránya. Ha csak ezt akarjuk megadni, akkor a komponenseket a (0, 1) tartományon írjuk le. De a fényt jellemzi még az erőssége (luminanciája) is, ami független magától a színtől. A fényerősség tetszőlegesen nagy, vagy kicsi, de akár még negatív is lehet. Ha egy fényforrást akarunk leírni, akkor a szín és a fényerősség szorzatára vagyunk kíváncsiak, a (-végtelen, végtelen) tartományon komponensenként (erre a sugárkövetésnél lesz szükség), de ha az OpenGL-nek akarunk megadni egy színt, akkor azt a (0, 1), esetleg a (-1, 1) tartományon tegyük. Technikailag byte-ot is lehet adni az OpenGL-nek, de pedagógia okokból a házikban kötelező float színeket használni.
Az OpenGL csak a rajzolással foglalkozik, az, hogy hogyan jön létre az a valami (célszerűen egy ablak), amire ő tud rajzolni, az viszont már nem az ő dolga. Itt jön a képbe a GLUT.

A GLUT

A GLUT egy platformfüggetlen ablak- és eseménykezelő, lényegében egy híd az oprendszer és az OpenGL context között. A GLUT beállításának nagy része a keretben előre meg van írva, csak az eseménykezelő függvényekről kell gondoskodnunk, amiket majd a GLUT meghív (ezek a függvények határozzák meg, hogy mit csinál a programunk).
GLUT eseménykezelő függvények:
- onDisplay() - a legfontosabb függvény, ide írjuk a képernyő törlését, majd a szükséges rajzoló részeket. Ha valami változás hatására frissíteni szeretnénk a képernyőt, azaz szeretnénk az onDisplay()-t lefuttatni, hívjuk meg a glutPostRedisplay() függvényt (ne közvetlenül az onDisplay-t!). Fontos hogy az onDisplay()-en belül tilos meghívni a glutPostRedisplay()-t, az így megírt program elvi hibás (a képernyő mindig érvénytelen marad), ez a beadón nem fog működni.
- onInitialization() - inicializáló rész, pl. globális változók inicializálására. Tipikus hiba, hogy a globális változóknak egy gl/glu/glut függvény visszatérési értéket adjuk, vagy a változó konstruktorában meghívunk ilyen függvényt. Így ugyanis még a main() kezdete előtt futattnánk le egy ilyen típusú függvényt, amikor még ezek a könyvtárak nincsenek inicializálva. Ennek az elkerülésére van ott az onInitialization - ebben már nyugodtan használhatunk bármilyen függvényt az inicializációhoz.
- onKeyboard() - Itt tudjuk kezelni egy billentyű lenyomását. Erre a házikban általában csak minimális szükség van.
- onMouse() - Itt kapunk értesítést arról, ha valamelyik egérgomb állapota megváltozott, és azt is megtudjuk, hogy az ekkor az egér az ablak koordinátái szerint (figyelem itt bal felül van az origó!) hol volt.
- onMouseMotion() - Itt tudjuk meg, ha a felhasználó lenyomott egér gomb mellett mozgatta az egeret. A koordinálta értékére ugyan az vonatkozik, mint az onMouse esetén.
- onIdle() - Ez a függvény az idő múlását hivatott jelezni, így itt kell kezelni mindent ami az időtől függ (animáció).

Az első házihoz szükséges elmélet

Rajzolás az OpenGL segítségével

Az OpenGL néhány csak néhány típusú primitívet tud rajzolni, ezekből kell építkeznünk.
A típusok:
- Pontok: GL_POINTS
- Vonalak: GL_LINES, GL_LINE_STRIP, GL_LINE_LOOP
- Háromszögek: GL_TRIANGLES, GL_TRIANGLE_STRIP, GL_TRIANGLE_LOOP
- Háromszögekből összetett alakzatok:
  - Négyszögek (igazándiból 2 háromszög): GL_QUADS, GL_QUAD_STRIP
  - Sokszög (ez is háromszögenként rajzolódik ki): GL_POLYGON

A rajzolás az alábbi módon történik:

glBegin("Primitív típus");

"Pontok felsorolása"

glEnd();

A pontok megadásához glVertex{2,3}f függvények valamelyikét kell használnod, az alapján, hogy hány dimenzióban dolgozol.
- Tehát 2 dimenzióban a glVertex2f-et, 3 dimenzióban a glVertex3f-et kell használnod.
A pontok sorrendje nagyon fontos, már egy quad esetében sem lehet "csak úgy" felsorolni a négy pontot, ha rossz sorrendben adjuk meg őket, akkor két egymásba csúszott háromszöget fogunk látni.

2D rajzolás

A koordináták amiket átadsz azok a normalizált eszköz koordináta-rendszerben vannak értelmezve, ahol a (0,0) a képernyő közepe, a (-1, -1) pedig a bal alsó sarok.
- Példaprogram: Háromszögek

glBegin(GL_TRIANGLES);

glVertex2f(0.0f, 0.0f);
glVertex2f(0.2f, 0.2f);
glVertex2f(0.2f, 0.0f);

glVertex2f(0.6f, 0.8f); // Egy pass-on belül több háromszög csúcspontjait is fel lehet sorolni.
glVertex2f(0.9f, 0.3f);
glVertex2f(0.5f, 0.9f);

glEnd();

Az eredménye:

Minden egyes ponthoz külön színt is tudunk megadni. A glColor3f()-el lehet állítani a rajzolószínt, ami utána az összes glVertex hívásra érvényes lesz. Az összetettebb alakzatoknál az egyes pontok színei interpolálódnak, és szép színátmenetet kapunk.
- Példaprogram: Smiley

#define CIRCLE_RESOLUTION 32

// Piros kor, a képernyő bal oldalán
glBegin(GL_TRIANGLE_FAN); {
  float radius = 0.25f, center_x = -0.5f, center_y = 0.4f;

  glColor3f(1.0f, 0.0f, 0.0f);
  glVertex2f(center_x, center_y);

  for(int i = 0; i <= CIRCLE_RESOLUTION; i++) {
    float angle = float(i) / CIRCLE_RESOLUTION * 2.0f * M_PI;
    // Itt a kor paramtetrikus alakjat hasznaljuk: x = x0 + r*cos(t), y = y0 + r * sin(t)
    glVertex2f(center_x + radius*cos(angle), center_y + radius*sin(angle));
  }
} glEnd();

// Színátmenetes kör, a képernyő jobb oldalán
glBegin(GL_TRIANGLE_FAN); {
  float radius = 0.25f, center_x = 0.5f, center_y = 0.4f;

  glColor3f(0.0f, 1.0f, 1.0f);
  glVertex2f(center_x, center_y);
  
  for(int i = 0; i <= CIRCLE_RESOLUTION; i++) {
    float angle = float(i) / CIRCLE_RESOLUTION * 2.0f * M_PI;
    glColor3f(0.0f, 0.5f + 0.5f*cos(angle), 0.5f + 0.5f*sin(angle));
    glVertex2f(center_x + radius*cos(angle), center_y + radius*sin(angle));
  }
} glEnd();

// Félkörív
glBegin(GL_LINE_STRIP); {
  float radius = 0.75f, center_x = 0.0f, center_y = 0.0f;

  glColor3f(1.0f, 1.0f, 1.0f);
  
  for(int i = CIRCLE_RESOLUTION/2; i <= CIRCLE_RESOLUTION; i++) {
    float angle = float(i) / CIRCLE_RESOLUTION * 2.0f * M_PI;
    glVertex2f(center_x + radius*cos(angle), center_y + radius*sin(angle));
  }
} glEnd();

Az eredménye:

Eseménykezelés

A grafikus programok általában eseményvezéreltek, azaz a felhasználó által generált események (pl. egérkattintás) vezérlik a programot. A GLUT ehhez nagyon sok segítséget ad, nekünk csak be kell regisztrálnunk egy-egy függvényt, hogy melyik esemény hatására mi történjen, pl az egérkattintásokat az onMouse() függvényben kezeljük.
A három legfontosabb eseménytípus:
- Billentyűzet esemény:
  - Billentyű lenyomás - onKeyboard
  - Billentyű felengedés - onKeyboardUp
- Idő múlása (lényegében ez is egy esemény) - onIdle
- Egér esemény:
  - Egér mozgatás - onMouseMotion
  - Egér gombbal kattintás - onMouse
  - Az egér eseményekkel kapcsolatban egy apró kellemetlenség, hogy a GLUT a kattintások helyét az oprendszer koordináta rendszerében adja át nekünk (ablak bal fölső sarka az origó, x jobbra, y lefelé nő, az egység pedig a pixel), míg mi normalizált eszközkoordinátákkal dolgozunk (az ablak közepe az origó, a x jobbra, az y felfele nő, és mindkét dimenzióban az ablak méretének a fele az egység). Ezért kénytelenek vagyunk átszámolni azokat az értékeket, amiket a GLUT ad nekünk. Erre egy lehetséges megoldás:

struct Vector {
  float x, y;
}

const int kScreenWidth = 600, kScreenHeight = 600;

Vector convertToNdc(float x, float y) {
  Vector ret;
  ret.x = (x - kScreenWidth/2) / (kScreenWidth/2);
  ret.y = (kScreenHeight/2 - y) / (kScreenHeight/2);
  return ret;
}

Példa: Egyszerű rajzolóprogram

void onMouse(int button, int state, int x, int y) {
  if(button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN) {
    glClear(GL_COLOR_BUFFER_BIT); // Jobb klikkre toroljuk a kepernyot.
    glutPostRedisplay(); // Szolunk, hogy az ablak tartalma megvaltozott, kerjuk a GLUT-ot, hogy hívja meg az onDisplay-t.
  } else if(button == GLUT_LEFT_BUTTON) { // Ha a bal gomb allapota megvaltozott.
    if(state == GLUT_DOWN) {
      drawing = true; // Ha lenyomtuk akkor rajzolni akarunk.
      Vector pos = convertToNdc(x, y); // Atvaltjuk a pontot.
      glBegin(GL_POINTS); { // Kirajzoljuk.
        glVertex2f(pos.x, pos.y);
      } glEnd();
      last_mouse_pos = pos; // Elmentjuk, hogy az elso szakasz, majd ebbol a pontbol indul.
      glutPostRedisplay(); // Szolunk, hogy az ablak megvaltozott, kerjuk az ujrarajzolasat.
    } else if(state == GLUT_UP) {
      drawing = false; // Ha most engedtuk fel, akkor mar nem akarunk rajzolni.
    }
  }
}
 
void onMouseMotion(int x, int y) {
  if(drawing) {
    Vector pos = convertToNdc(x, y); // Kiszamoljuk az eger jelenlegi helyzetet NDC-ben.
    glBegin(GL_LINES); { // Kirajzolunk egy vonalat az elozo es a mostani helyzete koze.
      glVertex2f(last_mouse_pos.x, last_mouse_pos.y);
      glVertex2f(pos.x, pos.y);
    } glEnd();
    glutPostRedisplay(); // Szolunk, hogy az ablak megvaltozott, kerjuk az ujrarajzolasat.
    last_mouse_pos = pos; // Frissitjuk a elozo helyzetet.
  }
}

Az eredménye:

Animáció

Az animáció annyit jelent, hogy az egyes objektumok állapota az időnek is a függvénye. A pillanatnyi időt a glutGet(GLUT_ELAPSED_TIME); függvényhívással tudjuk lekérdezni, célszerűen az onIdle függvényben.
Egy mozgó testet legjobban a fizika törvényeivel tudunk leírni, egy egyenes vonalú egyenletes mozgás leírásához mindössze a v = s / t képletre van szükségünk.
Az animáció onnantól kezd bonyolulttá válni, hogy ha több mozgó test állapota egymástól függ (pl: mikor ütköznek). Ilyenkor ugyanis a korrekt szimuláció egy differenciálegyenlet megoldását jelentené. Ennek egy egyszerű közelítése a diszkrét idő-szimuláció, ahol az ötlet az, hogy válasszunk egy időegységet, amennyi idő alatt a testek állapota csak minimálisan változik meg, ez tipikusan pár milliszekundum, és legfeljebb ilyen időközönként kiválasztott statikus pillanatokban vizsgáljuk csak az egymásra hatásokat. Manapság a számítógépes játékok nagy része is ezt a módszert használja.
Egyszerű példaprogram: Pattogó labda

const float ball_radius = 0.1f;
Vector ball_pos, ball_speed(-0.46f, 1.13f);

void onIdle() {
  static int last_time = glutGet(GLUT_ELAPSED_TIME); // Visszaadja a jelenlegi időt milliszekundumban
  int curr_time = glutGet(GLUT_ELAPSED_TIME);
  int diff = curr_time - last_time; // Az előző onIdle óta eltelt idő
  last_time = curr_time; // A következő meghíváskor az előző idő majd a mostani idő lesz.

  // Két onIdle között eltelt idő nagyon változó tud lenni, és akár elég nagy is lehet
  // ahhoz, hogy a labda látványosan bele menjen a falba, mielőtt visszapattan. Ezért
  // osszuk fel az eltelt időt kisebb részekre, pl. max 5 milliszekundumos egységekre,
  // és ilyen időközönként nézzük meg, hogy a labda ütközött-e a fallal.
  const int time_step = 5;
  for(int i = 0; i < diff; i += time_step) {
    // Az időosztás végén egy kisebb egység marad, mint az idő egység. Pl. ha a diff 11,
    // akkor azt akarjuk, hogy 5, 5, 1 egységekre bontsuk azt, ne 5, 5, 5-re. 
    // Meg is kell számolnunk másodperce, azaz osztanunk kell 1000-el.
    float dt = min(diff-i, time_step) / 1000.0f;

    // Módosítsuk a sebességet ha ütközött a fallal, teljesen rugalmas ütközést feltételezve.
    // Ilyenkor a labda a fal irányára merőlegesen pontosan ellentétes irányba halad tovább.
    if(ball_pos.x + ball_radius > 1) {
      ball_speed.x = -fabs(ball_speed.x);
    } else if(ball_pos.x - ball_radius < -1) {
      ball_speed.x = fabs(ball_speed.x);
    }
    if(ball_pos.y + ball_radius > 1) {
      ball_speed.y = -fabs(ball_speed.y);
    } else if(ball_pos.y - ball_radius < -1) {
      ball_speed.y = fabs(ball_speed.y);
    }

    // Mozgassuk a labdát a ds = v * dt képlet alapján.
    ball_pos += ball_speed * dt;
  }

  glutPostRedisplay(); // Megváltozott a jelenet, újra kell rajzolni
}

Az eredménye:

A második házihoz szükséges elmélet

Koordináta rendszerek

Az első háziba valószínűleg feltűnt, hogy a pontok NDC (normalizált eszköz koordináta) megadása nem túl kényelmes, még akkor se ha, a világnak mindig ugyan azt a részét nézzük. De mit tegyük akkor, ha a képzeletbeli kamera amivel "lefényképezzük" a jelenetet mozoghat, sőt akár még foroghat is.
Az OpenGL kitalálóinak az ötlete az volt erre, hogy a kamera mindig maradjon egy helyben, de ha pl. balra akarnánk forgatni, akkor helyette inkább a világ forogjon jobbra, a kamera viszont maradjon ugyanott, és ezzel ugyanazt a hatást érjük el. Persze nem kell minden egyes pontot nekünk elforgatni, ezt rábízhatjuk az OpenGL-re is, hogy mindig mielőtt rajzolna, azelőtt végezzen el valamilyen transzformációt a pontokat amiket kapott.
- A lineáris (és affin) transzformációkat a legkényelmesebb a mátrixuk segítségével tudjuk megadni, több egymás utáni transzformáció pedig egyszerűen a mátrixok szorzatát jelenti. Viszont fontos megjegyezni, hogy 3D-ben az eltolás nem lineáris transzformáció, és nem is lehet mátrixszal felírni. Ennek kiküszöbölésére használhatunk 4D-be 'w' = 1 koordinátával beágyazott 3D-s koordináta-rendszert, ahol az eltolás is egy lineáris trafó.
- Az OpenGL két mátrixot ad nekünk, amiknek módosíthatunk, és amivel az összes kirajzolandó pontot mindig beszorozza helyettünk. Az egyik a GL_MODELVIEW, a másik a GL_PROJECTION. A GL_MODELVIEW-val mozgathatunk objektumokat egymáshoz képest, és itt tudjuk megadni, hogy hogyan kell transzformálni a világot, hogy az origóban lévő, -z irányba néző képzeletbeli kamera azt lássa, amit meg akarunk jeleníteni. A GL_PROJECTION pedig azt adja meg, hogy a kamerával hogyan kell fényképezni.
  - Két dimenzióban a két mátrix különválasztása gyakorlatilag fölösleges, ennek csak 3D-be lesz szerepe, majd a megvilágításkor. 2D-ben a kényelmesebb a GL_PROJECTION-ra bízni a kamera mozgatást is, és a GL_MODELVIEW-t pedig meghagyni csak az objektumok közötti transzformációk leírására.
Projekció 2D-ben: a fényképezés módja nagyon egyszerű, egyszerűen eldobjuk a 'z' koordinátát, és az x-y pozíció alapján rajzolunk. Vagy legalábbis ezt csináltuk eddig, de az NDC nem volt kényelmes. Itt viszont lehetőséget kapunk saját koordináta-rendszer megválasztására, ahol az egység lehet pl. 1 méter, és a kamera pedig mondjuk követhet egy karaktert egy játékban.

Példaprogram: Sidescroller

// Megmondjuk a OpenGL-nek, hogy ezután a projekciós mátrixot 
// akarjuk módosítani a transzformációs mátrix műveletekkel.
glMatrixMode(GL_PROJECTION);
// Egység mátrixot töltünk be a jelenleg módosítható 
// mátrix helyére (ez a projekciós mátrix). 
glLoadIdentity(); 
// Ez egy olyan merőleges (ortogonális) vetítés mátrixát "írja be" a GL_PROJECTION-be, 
// aminek eredményeképpen a karakter az x tengely mentén középen lesz, és 10 egység 
// (méter) széles részt látunk a világból míg az y tengely mentén a képernyő alsó egy 
// ötödében lesz, és itt is 10 egység magas részt látunk. Fontos megjegyezni, hogy ez
// csak akkor működik, ha a GL_PROJECTION előtte egység mátrix volt!
gluOrtho2D( 
  stickman.pos.x - 5, stickman.pos.x + 5,
  stickman.pos.y - 2, stickman.pos.y + 8
);

Az eredménye:

Transzformációk

GL_MODELVIEW egyik legfontosabb használata, hogy segítségével könnyebben tudjuk elhelyezni az objektumokat a világban. Például ha van egy összetett, mondjuk 10 000 háromszögből álló alakzatunk, akkor annak elforgatását manuálisan úgy tudnánk megoldani, hogy az alakzat összes pontján elvégzünk valami undorító trigonometrikus képletet. Egy másik lehetőség, hogy a GL_MODELVIEW segítségével az egész világot elforgatjuk az ellenkező irányba, kirajzoljuk az alakzatot normál állapotában, majd visszaforgatjuk a világot. Ez első ránézésre bonyolultabbnak tűnik, de mindössze 2 sor kód.
A világ transzformálásához használható függvények:
- glTranslatef(GLfloat x, GLfloat y, GLfloat z);
- glRotatef(GLfloat angle, GLfloat x, GLfloat y, GLfloat z);
- glScalef(GLfloat x, GLfloat y, GLfloat z);
A projekciós mátrixot állító függvényekkel ellentétben, ezeket akkor is szoktuk használni, ha a modellezési mátrix nem egységmátrix.
Ezen függvényeknek tetszőleges kombinációját lehet használni, de a sorrend nem mindegy.
Egy transzformáció meghívásakor annak a mátrixa hozzászorzódik a GL_MODELVIEW mátrixhoz (balról). Emlékeztető: a mátrix szorzás, és a mátrix-vektor szorzás asszociatív. Ez azt jelenti, hogy két transzformációs mátrix összeszorzása után az eredmény ugyan úgy transzformál egy tetszőleges vektort, mint ha a két mátrixszal külön szoroztuk volna be.
A transzformációk fordított sorrendben fejtik ki hatásukat, mint ahogy meghívjuk őket, de ez így intuitív, így haladhatunk a hierarchiában föntről lefele, ha nem így lenne, akkor pl. egy autó kirajzolásánál, azzal kéne kezdenünk, hogy megmondjuk, hogy a dísztárcsa a kerékhez képest hogy helyezkedik el, és csak a legvégén mondhatnánk meg, hogy az autó egyáltalán hol van.
Példa a transzformációk sorrendjére:

 
glTranslatef(2.7f, -3.1f, 0.0f); 
glRotatef(67, 0, 0, 1);
glScalef(2, 2.5f, 1);

Ami a koordináta-rendszerrel történik:

- Intuitív, pontosan az történik, mint amit a kódról első ránézésre hinnénk, hogy csinál, az origó a transzformáció után a (2.7, -3.1) pontba kerül, a nagyítás az x tengely mentén 2, az y tengely mentén 2.5.

Egy másik lehetséges sorrend:

glScalef(2, 2.5f, 1); 
glRotatef(67, 0, 0, 1);
glTranslatef(2.7f, -3.1f, 0.0f);

Ami a koordinátarendszerrel történik:

- Egyáltalán nem intuitív, az origó a (7.817, 3.185) pontba kerül, és a két tengely nagyítása 2.084 és 2.43. Ezeknek az értékeknek semmi köze a kódban szereplő konstansokhoz!!

Tanulság: általában az eltolás - forgatás - nagyítás sorrendet szeretjük. Ez nem jelenti azt, hogy más sorrendnek ne lenne értelme, vagy egy konkrét problémának ne lehetne egyszerűbb megoldása másmilyen sorrendet használva.

A probléma ami felmerül, hogy a transzformációk hatása permanens, azaz, ha egyszer elforgattad a világot, akkor az úgy marad, amíg vissza nem forgatod. Tehát ha egy objektum kirajzolása miatt akarsz használni egy transzformációt akkor a rajzolás után azt mindenképpen, mindig vissza is kell csinálnod. De mi van ha egy összetett objektum kirajzolásához akár több száz transzformáció is kellet? Akkor a végén az összeset egybe vissza kell csinálni? Nincs erre jobb megoldás? A válasz természetesen az, hogy van, ez a megoldás a mátrix stack.

Matrix stack

Az OpenGL két függvényt ad amivel a matrix stack-et használhatjuk:
- glPushMatrix();
  - A jelenleg aktív mátrixot ( GL_PROJECTION vagy GL_MODELVIEW ) elmenti annak a stackjébe.
- glPopMatrix();
  - A jelenleg aktív mátrix stackjéből a legutóbb elmentett mátrixot visszaállítja. A következő glPopMatrix() mátrix az az előtt elmentett mátrixot állítja vissza.
Megjegyzések:
- A GL_MODELVIEW stack mélysége legalább 32, a GL_PROJECTION mátrixé pedig legalább 2.
  - Ez azt jelenti, hogy lehet, hogy nálad mindkét érték tízszer ekkora, de ha hordozható kódot akarsz írni, ekkor ennél nagyobb számokat nem feltételezhetsz.
  - Overflow / Underflow esetén a mátrix értéke meghatározatlan lesz.
Pl:

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

glPushMatrix(); {
 glRotatef(90, 0, 0, 1);
 rajzolas(); // A rajzolaskor a világ el van forgatva
} glPopMatrix();

rajzolas2(); // It a világ már nincs elforgatva.

A mátrix stack hierarchikusan felépülő testek rajzolását nagy mértékben megkönnyíti.
- Hierarchikus test pl: az emberi kéz.
  - Ha a felkarod elforgatod a vállad körül, akkor azzal az alkarod a csuklód és az ujjaid elmozdulnak. Minden ízület transzformációja befolyásolja az összes csontot, ami belőle nő ki, és az összes csontot, ami a belőle kinövő csontokból nő ki, rekurzívan. Ha ezt manuálisan akarnánk leprogramozni, egy olyan fát kéne felépítenünk az ízületekből, ahol a gyerekek száma változó. Ez nem lehetetlen, de is kifejezetten izgalmas, viszont a mátrix stack segítségével ez nagyon egyszerűen megoldható.
  - Pszeudokóddal, feltételezve, hogy origó középpontú, egység hosszú, x-el párhuzamos főtengelyű hengert tudunk rajzolni a "henger kirajzolása" utasítással:

glPushMatrix(); {

  váll körüli forgatás
  felkar hosszának a felével eltolás az x tengely mentén

  glPushMatrix(); { 
    nagyítás a felkar méreteivel
    henger kirajzolása
  } glPopMatrix();
 
  felkar hosszának a felével eltolás az x tengely mentén
  könyök körüli forgatás
  alkar hosszának a felével eltolás az x tengely mentén

  glPushMatrix(); {
    nagyítás a alkar méreteivel
    henger kirajzolása
  } glPopMatrix();

  alkar hosszának a felével eltolás az x tengely mentén

  kéz kirajzolása

} glPopMatrix();

Sajnos ezt 2D-be nem lehet jól megmutatni, ezért kivételesen az ehhez kapcsolódó példaprogram 3D-s lesz.
- Technikailag a 3D rajzolást rábízzuk a glut-ra.
  - Kizárólag a glutSolidCube(GLdouble size); függvényt fogjuk használni.
  - Ez a függvény - nem meglepő módon - egy 'size' élhosszúságú kockát rajzol ki:

Ezt felhasználva a példaprogram: Robot kar
- A program irányítása:
  - 'q' - Ujjak szétnyitása, 'a' - Ujjak összezárása
  - 'w' - Alkar felemelése, 's' - Alkar lehajtása
  - 'e' - Felkar felemelése, 'd' - Felkar lehajtása
  - 'r' - Az alap forgatása jobbra, 'f' - Az alap forgatása balra

struct Vector {
  float x, y, z;
  Vector(float x, float y, float z) : x(x), y(y), z(z) { }
  void translate() { glTranslatef(x, y, z); }
  void rotate(float angle) { glRotatef(angle, x, y, z); }
  void scale() { glScalef(x, y, z); }
};

Vector x_axis(1, 0, 0), y_axis(0, 1, 0), z_axis(0, 0, 1);
Vector pos_crate(0, 0, -5), pos_left_base(1, 0, 0), pos_right_base(-1, 0, 0), scale_base(1, 1, 3),
       pos_main_arm(0, 0, -2), scale_main_arm(1, 1, 4), pos_lower_arm(0, 0, -1.5f), 
       scale_lower_arm(0.7f, 0.7f, 3.0f), scale_wrist(1, 1, 1), pos_left_finger(0.5f, -1.0f, 0.0f),
       pos_right_finger(-0.5f, -1.0f, 0.0f), scale_finger(0.2f, 1.0f, 0.2f);

float rot_base = 0, rot_main_arm = 70, rot_lower_arm = -60, 
      rot_finger = 20, rot_finger_relative = 20;

void onDisplay() {
  glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

 glPushMatrix(); {
    y_axis.rotate(rot_base);
 
    // Jobb oldali alap
    glPushMatrix(); {
      pos_right_base.translate();
      scale_base.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
   
    // Bal oldali alap
    glPushMatrix(); {
      pos_left_base.translate();
      scale_base.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
    x_axis.rotate(rot_main_arm);
    pos_main_arm.translate();
 
    // Felkar
    glPushMatrix(); {
      scale_main_arm.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
    pos_main_arm.translate();
 
    x_axis.rotate(rot_lower_arm);
    pos_lower_arm.translate();
 
    // Alkar
    glPushMatrix(); {
      scale_lower_arm.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
    pos_lower_arm.translate();
 
    // Csukló
    glPushMatrix(); {
      scale_wrist.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
    // Jobb 'ujj'
    glPushMatrix(); {
      z_axis.rotate(-rot_finger);
 
      glTranslatef(0, pos_right_finger.y, 0);
 
      glPushMatrix(); {
        glTranslatef(pos_right_finger.x, 0, 0);
        z_axis.rotate(-rot_finger_relative);
        scale_finger.scale();
        glutSolidCube(1.0f);
      } glPopMatrix();
 
      pos_right_finger.translate();
      z_axis.rotate(rot_finger_relative);
      scale_finger.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
    // Bal 'ujj'
    glPushMatrix(); {
      z_axis.rotate(rot_finger);
     
      glTranslatef(0, pos_left_finger.y, 0);
 
      glPushMatrix(); {
        glTranslatef(pos_left_finger.x, 0, 0);
        z_axis.rotate(rot_finger_relative);
        scale_finger.scale();
        glutSolidCube(1.0f);
      } glPopMatrix();
 
      pos_left_finger.translate();
      z_axis.rotate(-rot_finger_relative);
      scale_finger.scale();
      glutSolidCube(1.0f);
    } glPopMatrix();
 
  } glPopMatrix();
 
  // Láda
  glPushMatrix(); {
    pos_crate.translate();
    glutSolidCube(1.0f);
  } glPopMatrix();

  glutSwapBuffers();
}

Az eredménye:

Görbék

Görbék alatt grafikában olyan függvényeket értünk, amik diszkrét ponthalmazból folytonos ponthalmazt állítanak elő.
- Példa: A Nyugatitól el akarunk jutni az egyetemig, de úgy, hogy közbe megadott sorrendben érinteni akarjuk a három kedvenc kocsmánkat. Az útvonal, amin ezt megtudjuk tenni, az egy görbe. Az öt helyet, amit érinteni akarunk, kontrollpontnak nevezzük. Nem csak egy ilyen útvonal létezik, mint ahogy a különböző típusú görbéknek is lehet más a kimenete, ugyan az a bemenet mellett.
- A görbéket szinte mindig valamilyen mozgás leírására használjuk. A görbe kimenete egy hely-idő pontpárokból álló halmaz (vagy ezzel ekvivalens egy folytonos függvény aminek az idő a paramtére, és a hely a visszatérési értéke), ami azt jelenti, hogy a görbéből még a sebesség és a gyorsulás is kiolvasható.
- A görbék egyik legfontosabb tulajdonsága a folytonosság mértéke, vagyis, hogy mekkora az a legnagyobb szám (n), amennyiedik deriváltja még folytonos. Jelölése: c(n).
  - c0 folytonos görbe az, aminek nincs szakadása. Ha egy valós útvonal nem c0 folytonos, akkor azt jelenti, hogy valahol teleportálnunk is kell. Tekintve, hogy 3 kocsmát is érinteni akarunk, ez nem tűnik lehetetlennek :)
  - A valós tárgyak mozgása legalább c2 folytonos (azaz a gyorsulás folytonosan változik). Ezt a agyunk megszokta, és a nem c2 folytonos mozgás nem tűnik valóságosnak. Ebből fakadóan az olyan egyszerűbb függvények, mint hogy a pontokat egyenes vonalakkal összekötjük, nem eredményeznek hihető mozgást.
A tipikus görbék amiket a grafikában használni szoktunk:
- Bézier-görbe.
  - Egyszerű implementálni, de a megfelelő kontrollpontok megadása nehézkes.
- B-Spline görbe család (több görbéből összetett görbék).
  - Lokálisan vezérelhetőek, nagyon kényelmes velük dolgozni, viszont az implementálásuk általában bonyolult.
  - Pl: Kochanek–Bartels görbe
    - Gyakori implementációja a közelítőleg c2 folytonos Catmull-Rom görbe (Ezt akkor kapjuk, ha a Kochanek–Bartels összes paraméterét nullának választjuk).

Példaprogram: Tenziós Catmull-Rom görbe

A harmadik házihoz szükséges elmélet

A harmadik házinál a programod teljes mértékben a CPU-n fog futni, ami a videókártya segítsége nélkül nagyon meg fog izzadni, hogy a képet előállítsa neked. Az előző házikkal ellentétben itt az optimalizálás nagyon sokat segít, egy release build (-O3) és egy debug build (-O0) között akár több mint ötszörös sebességkülönbség is lehet. Ezért, ha éppen nem debuggolsz, mindenképpen release buildet fordíts.

A Sugárkövetés alapjai

A második házihoz szükséges példaprogramok között volt egy 3D-s is. Most ezzel a témakörrel fogunk foglalkozni. Technikailag abban a példaprogramban a 3D rajzolást a GLUT csinálta helyettünk. De mielőtt belemennénk a részletekbe, hogy pontosan mit is csinált (ezt majd a 4. háziba), vegyük észre, mi is ki tudunk rajzolni egy olyan kockát, mint amit a GLUT csinált, akár az OpenGL segítsége nélkül is.
Először gondoljuk át hogy a valóságban hogyan csinálnánk képet egy kockáról. Először is szükségünk van egy fényforrásra, enélkül garantáltan nem látnánk semmit, és szükségünk van egy ernyőre is (pl: retina), amin a képet felfoghatjuk. Továbbá nem árt, ha van egy kocka is, amit lefényképezhetünk.
Ha pontosan azt akarnánk lemodellezni, ahogy a valóságban a kép keletkezik, akkor gondba lennénk, mert a számítógép teljesítményéhez képest gyakorlatilag végtelen fotonnal kéne dolgoznunk. És ráadásul a fényforrásból kiinduló fotonok döntő többsége még csak nem is megy az ernyőnek a közelébe se. Viszont, mint tudjuk a fotonok megfordíthatóak.
A sugárkövetés egyik alapötlete, hogy az ernyőből induljuk ki, ne a fényforrásból, és megfordított irányú fotonokat kövessünk, így csak a releváns fotonokkal fogunk foglalkozni.
A másik alapötlet, hogy a fotonok olyan sokan vannak, hogy a Nagy Számok Törvénye alapján gyakorlatilag teljesen pontos becsléseket kaphatunk a fotonok viselkedéséről, anélkül, hogy azokkal egyesével foglalkoznunk kellene. Ezt felhasználva igazándiból nagy mennyiségű fotonból álló csomagok úgynevezett sugarak útját követjük, és nem fotonokét. Ez talán megmagyarázza, hogy miért hívjuk a technikát sugárkövetésnek.
A sugárkövetéshez szükségünk van egy képzeletbeli kamerára, és egy téglalapra, amit ernyőként használhatunk (jelen esetben négyzet lesz, mert 600x600-as ablak). A téglalapot felosztjuk annyi egyenlő részre, ahány pixelből áll az ablakunk. Ezek után az ablak minden egyes pixelére azt a színt rajzoljuk ki, amit a képzeletbeli kamera látna a téglalapnak a pixelhez tartozó részén keresztül.
- Az OpenGL használata nélkül ezt úgy kivitelezhetnénk, hogy képet mint egy színekből álló tömböt eltároljuk magunknak, abba renderelünk, majd valamilyen megfelelő kép formátumába kiírjuk ezt egy fájlba. Ezt a megoldást viszont nem lenne túl kényelmes használni.
- Az OpenGL-t is megkérhetjük arra, hogy jelenítse meg a képet, amit lerendereltünk a glDrawPixel() függvény segítségével.
  - Pl:

 
struct Screen {
  static const int width = 600;
  static const int height = 600;
  static Color image[width * height];
  static void Draw() {
    glDrawPixels(width, height, GL_RGB, GL_FLOAT, image);
  }
};

A kamera megvalósítása már egy picit trükkösebb
- Meg kell adnunk a képzeletbeli kamera pozícióját. Kódban pl: pos.
- Meg kell adnunk, hogy a kamera, merrefelé néz. Kódban pl: fwd (egységvektor).
- Azt is tudnunk kell, hogy melyik iránynak felel meg a felfele ("What's up?"). Kódban pl nevezzük up-nak.
- Tegyük fel, hogy téglalap (vagy sík) egységnyi távolságra van a kamerától. Ekkora annak a középpontja: pos + fwd.
- Tudnunk kell még, hogy melyik irány van jobbra. Ezt az előre és a felfele pozícióból ki tudjuk számolni: right = cross(fwd, up).
- A felfele vektor amit megadtunk nem biztos, hogy merőleges az előre vektorra, pedig nekünk olyanra van szükségünk. Pl: ha rézsútosan előre és lefele nézünk, de az 'up' vektor az ég fele mutat. Ez igazándiból nem baj, mert a jobbra és előre vektor ismeretében már ki tudjuk számolni a pontos felfele vektort: up = cross(right, fwd).
- Ha ezek megvannak, akkor ki kell tudnunk számolni, hogy egy (x, y) koordinátájú pixelnek a téglalap (ami most egy egység oldalhosszúságú négyzet) melyik része felel meg. Ezt így tehetjük meg:

 
Vector pos_on_plane = Vector(
  (x - Screen::width/2) / (Screen::width/2),
  // Itt nem kell megfordítani az y tengelyt. A bal fölső sarok az origó most.
  (y - Screen::height/2) / (Screen::height/2), 
  0
);

Ezt az értéket pedig át kell számolnunk a világ koordináta rendszerébe:

Vector plane_intersection = plane_pos + pos_on_plane.x * right + pos_on_plane.y * up;

És innen már tudunk mindent a sugárról, amit követnünk kell. Ezeket az adatok célszerű egy struktúrába zárni:

struct Ray {
  Vector origin, direction;
};
Ray r = {pos, (plane_intersection - pos).normalize()};

Megjegyzések az algoritmussal kapcsolatban:
- Az ernyő (a téglalap) az, amin a kép keletkezik, az viselkedik úgy mint a szemünk. Ha a téglalap helyére állnánk, akkor látnánk ugyan azt a képet, mint amit meg fogunk jeleníteni. Ezért célszerű kezdetben a kamera pozíciója helyett a téglalap pozícióját megadni. A kamera pozíciója amúgy irreleváns, az tetszőlegesen távol lehet a téglalaptól, ha a távolsággal arányosan növeljük a téglalap méretét, akkor ugyan azt a képet fogjuk kapni.
- Azzal, hogy kijelentettük, hogy téglalap egység négyzet, és egységnyi távolságra van a kamerától, implicit kimondtuk, hogy a kamera látószöge arctg(1) = 45 fok. De nem biztos, hogy ennyit szeretnénk, úgyhogy a látószög (Field of View - Fov) is legyen inkább paraméter. A kamera-téglalap távolságot célszerűbb változtatni, mint a téglalap méretét, mert így nem kell eltárolni a FoV-ot. Az arány amit akarunk az 0.5*ctg(fov/2)
- Ha teljesen korrektek akarnánk lenni, akkor fél pixellel el kéne tolni a síkot metsző pontokat, hogy azok ne a pixelek bal fölső sarkán keresztül haladjanak át, hanem a közepén. Bár én szabad szemmel nem látok különbséget ezek után.
- Ezeket a változtatásokat is felhasználva egy lehetséges megvalósítás:

struct Camera {
  Vector pos, plane_pos, right, up;

  Camera(float fov, const Vector& eye, const Vector& target, const Vector& plane_up) 
      : pos(eye - (target-eye).normalize() / (2*tan((fov*M_PI/180)/2))), plane_pos(eye) 
   { 
      Vector fwd = (plane_pos - pos).normalize();
      right = cross(fwd, plane_up).normalize();
      up = cross(right, fwd).normalize();
   } 

  void takePicture() {
    for(int x = 0; x < Screen::height; ++x)
      for(int y = 0; y < Screen::width; ++y)
        capturePixel(x, y);
  }

  void capturePixel(float x, float y) {
    Vector pos_on_plane = Vector(
      (x + 0.5f - Screen::width/2) / (Screen::width/2),
      // Itt nem kell megfordítani az y tengelyt. A bal fölső sarok az origó most.
      (y + 0.5f - Screen::height/2) / (Screen::height/2), 
      0
    );

    Vector plane_intersection = plane_pos + pos_on_plane.x * right + pos_on_plane.y * up;

    Ray r = {pos, (plane_intersection - pos).normalize()};
    Screen::Pixel(x, y) = scene.shootRay(r);
  }
}

Most már mindent tudunk a sugárkövetésről, azt leszámítva, hogy hogyan kell egy sugarat követni.

Hogyan kövessük a sugarakat?

Az ötlet az, hogy keressük meg a kamerához legközelebbi objektumot, aminek van metszéspontja a sugárral.
Ha találtunk egy metszéspontot, akkor minket a metszéspontja helye és a felületi normál is érdekel (az a vektor, ami merőleges a felületre abban a pontban). Továbbá valahogy azt is jeleznünk kell, ha nem találtunk metszéspontot. Erre egy lehetséges struktúra:

 
struct Intersection {
  Vector pos, normal;
  bool is_valid;
};

Ahhoz, hogy eldöntsük, hogy egy objektumnak van-e metszéspontja a sugárral, fel kell írnunk annak az alakzatnak az egyetlenét, és meg kell oldaniuk egy 't' ismeretlenre azt az egyenletet, hogy ha a sugár kiindulási pontjából 't' egységet megyünk előre a sugár irányába, akkor ki fogjuk elégíteni az alakzat egyenletét.
- Nagyon sok esetben az okoskodás, pl transzformációk használata nagyon le tud egyszerűsíteni egy ilyen problémát.
- A síkbeli (elsőrendű) alakzatok követésekor első fokú egyenleteket fogunk kapni, míg a "görbülő" (másodrendű) alakzatok, pl kör, ellipszis, henger palást, kúp palást, hiperboloid stb... másodfokú egyenletekre vezetnek.
- Általában véges objektumokat szoktunk rajzolni, így ha a hozzá tartozó alakzat nem véges, akkor meg kell néznünk, hogy a sugár mely pontokban metszi az alakzatot, és ezekről a pontokról eldönteni, hogy azok a véges részbe is benne vannak-e. Ez utóbbi művelet lehet bonyolultabb mint az előző. Pl. egy háromszög követése lényegesen több ötletet igényel mint egy gömbbé.
  - Egy háromszög követésére egy lehetséges algoritmus:
    - Spoiler alert - ha ez kell a házidhoz, akkor ezt a részt csak akkor nézd meg, ha nagyon elakadtál, és sehogy nem tudod megoldani. De ne feledd amit innen másolsz, az nem számít bele a saját kontribúcióba.

 
struct Triangle {
  Vector a, b, c, normal; 

  // Az óra járásával ellentétes (CCW) körüljárási irányt feltételez ez a kód a pontok megadásakor.
  Triangle(const Vector& a, const Vector& b, const Vector& c) 
    : a(a), b(b), c(c) {
      Vector ab = b - a;
      Vector ac = c - a;
      normal = cross(ab.normalize(), ac.normalize()).normalize();
  }

  // Ennek a függvénynek a megértéséhez rajzolj magadnak egyszerű ábrákat!
  Intersection intersectRay(Ray r) {
    // Először számoljuk ki, hogy melyen mekkora távot 
    // tesz meg a sugár, míg eléri a háromszög síkját
    // A számoláshoz tudnunk kell hogy ha egy 'v' vektort 
    // skalárisan szorzunk egy egységvektorral, akkor
    // az eredmény a 'v'-nek az egységvektorra vetített 
    // hossza lesz. Ezt felhasználva, ha a sugár kiindulási 
    // pontjából a sík egy pontjába mutató vektort levetítjük 
    // a sík normál vektorára, akkor megkapjuk, hogy milyen 
    // távol van a sugár kiindulási pontja a síktól. Továbbá,
    // ha az a sugár irányát vetítjük a normálvektorra, akkor meg
    // megtudjuk, hogy az milyen gyorsan halad a sík fele.
    // Innen a már csak a t = s / v képletet kell csak használnunk. 
    float ray_travel_dist = dot(a - r.origin, normal) / dot(r.direction, normal);

    // Ha a háromszög az ellenkező irányba van, mint 
    // amerre a sugár megy, akkor nincs metszéspontjuk
    if(ray_travel_dist < 0)
      return Intersection(); 

    // Számoljuk ki, hogy a sugár hol metszi a sugár síkját.
    Vector plane_intersection = r.origin + ray_travel_dist * r.direction;

    /* Most már csak el kell döntenünk, hogy ez a pont a háromszög
       belsejében van-e. Erre két lehetőség van: 
     
       - A háromszög összes élére megnézzük, hogy a pontot a háromszög 
       egy megfelelő pontjával összekötve a kapott szakasz, és a háromszög
       élének a vektoriális szorzata a normál irányába mutat-e.
       Pl:
     
                 a
               / |
              /  |
             /   |
            /  x |  y
           /     |
          b------c

       Nézzük meg az x és y pontra ezt az algoritmust.
       A cross(ab, ax), a cross(bc, bx), és a cross(ca, cx) és kifele mutat a 
       képernyőből, ugyan abba az irányba mint a normál vektor. Ezt amúgy a 
       dot(cross(ab, ax), normal) >= 0 összefüggéssel egyszerű ellenőrizni.
       Az algoritmus alapján az x a háromszög belsejében van.

       Míg az y esetében a cross(ca, cy) befele mutat, a normállal ellenkező irányba,
       tehát a dot(cross(ca, cy), normal) < 0 ami az algoritmus szerint azt jelenti, 
       hogy az y pont a háromszögön kívül van. 
      
       - A ötlet lehetőség a bary-centrikus koordinátáknak azt a tulajdonságát használja
       ki, hogy azok a háromszög belsejében lévő pontokra kivétel nélkül nem negatívak, 
       míg a háromszögön kívül lévő pontokra legalább egy koordináta negatív.
       Ennek a megoldásnak a használatához ki kell jelölnünk két tetszőleges, de egymásra 
       merőleges vektort a síkon, ezekre le kell vetítenünk a háromszög pontjait, és 
       kérdéses pontot, és az így kapott koordinátákra alkalmaznunk kell egy a Wikipédiáról
       egyszerűen kimásolható képletet: 
       http://en.wikipedia.org/wiki/Barycentric_coordinate_system#Converting_to_barycentric_coordinates
      
       Én az első lehetőséget implementálom. */

    const Vector& x = plane_intersection;

    Vector ab = b - a;
    Vector ax = x - a;

    Vector bc = c - b;
    Vector bx = x - b;

    Vector ca = a - c;
    Vector cx = x - c;

    if(dot(cross(ab, ax), normal) >= 0) 
      if(dot(cross(bc, bx), normal) >= 0) 
        if(dot(cross(ca, cx), normal) >= 0) 
          return Intersection(x, normal, true);

    return Intersection();
  }
};

A legközelebbi metszéspont kiszámolásához a legegyszerűbb (de leglassabb) megoldás, ha végigmegyünk az összes objektumon, és amikkel találtunk metszéspontot, azokra a metszéspontokra kiszámoljuk a kamerától vett távolságot, és ezeknek az értékeknek nézzük a minimumát.
- Ehhez persze el kell tárolni az összes objektumot egy helyre, hogy végig tudjuk iterálni rajtuk. De az objektumok persze különböző osztályúak is lehetnek, itt sokat segít a heterogén kollekció használata. Az objektumok az én implementációmba azt is eltárolják, hogy milyen anyagból vannak.

 
struct Object {
  Material *mat;
  Object(Material* m) : mat(m) { }
  virtual ~Object() { } // Ne feletkezzünk el a virtuális destruktorról.
  virtual Intersection intersectRay(Ray) = 0;
};

És kell egy struktúra, ami tárolja ezeket, és végig tud menni rajtuk. Nem győzöm ismételni, hogy én csak egy lehetséges megoldást mutatok, hogy te ennél jobbat írhass, de semmiképpen se másold:

 
struct Scene {
  static const size_t max_obj_num = 100;
  size_t obj_num;
  Object* objs[max_obj_num];

  // Dinamikus foglalt objektumokat felételezek itt
  void AddObject(Object *o) { 
    objs[obj_num++] = o;
  }
  
  Scene() : obj_num(0) { } 

  ~Scene() {
    for(int i = 0; i != obj_num; ++i) {
      delete objs[i];
    }
  }

  Intersection getClosestIntersection(Ray r) const {
    Intersection closest_intersection;
    float closest_intersection_dist;
    int closest_index = -1;

    for(int i = 0; i < obj_num; ++i) {
      Intersection inter = objs[i]->intersectRay(r);
      if(!inter.is_valid)
        continue;
      float dist = (inter.pos - r.origin).length();
      if(closest_index == -1 || dist < closest_intersection_dist) {
        closest_intersection = inter;
        closest_intersection_dist = dist;
        closest_index = i;
      }
    }
    return closest_intersection;
  }
}

Ha ennél gyorsabb algoritmusra van szükséged, akkor ajánlom egy BSP-fa implementálását, mármint konkrétan egy KD-fát csinálj, ne általános BSP-t. Ez nagyon gyors, és nem nehéz implementálni... csak meg kell írni...
Ami a kódból is látszódik, hogy még nem vagyunk készen, amikor meghatároztuk a legközelebbi metszéspontot, ugyanis nekünk egy színre van szükségünk, amit megjeleníthetünk, nem egy helyvektorra.

Megvilágítás

A hihető, valóságosnak tűnő képek hatásának kb. 90%-át a megvilágítás adja. De ahhoz, hogy ilyeneket tudjuk renderelni előbb bele kell hatolnunk a fényforrások lelki világába, és egy kis fizikára is szükségünk lesz.

Az ambiens fényforrás

A legegyszerűbb fényforrás, amit bevezethetünk, az a környezeti világítás. Ez a valóságban nem létezik, csak egy modell, azt hivatott utánozni, hogy nappal a tárgyaknak az a része sem teljesen fekete, amit közvetlenül nem világít meg egy fényforrás se. Ugyanis a tárgyakról a környezetében minden irányba verődik vissza fény, nem csak a szemünk irányába, és ez pl. egy szobába létrehoz egy nagyjából konstans, iránytól független háttérvilágítást. Ez a modell nagyon sok környezetben nem állja meg a helyét, pl nagy nyílt terepen, bár vannak technikák a hibáinak kiküszöbölésére, vagy helyettesítésére (SSAO, Hemisphere lighting, Light probes stb...). Ez kódban csak annyit fog jelenteni a környezeti (ambiens) fényerőt változtatás nélkül hozzáadjuk az objektum színéhez.

Az irány fényforrás

Egy mások fontos fényforrás az irányfényforrás. Ilyen például a Nap. A Nap olyan távol van tőlünk, hogy a szobámon belül teljesen mindegy, hogy hol helyezkedik el egy objektum, a nap mindig ugyan olyan irányból és intenzitással világítja meg. Itt viszont már az iránynak fontos szerepe van. Egy megvilágított szobában az asztal teteje sokkal világosabb, mint az asztal alja. Hogy ezt meg tudjuk valósítani, egyszerű fizikára van szükségünk. Tegyük fel, hogy egy anyagra két azonos erősségű fénysugár esik, az egyik merőlegesen, a másik theta szögben.
- Így ha a merőlegesen eső sugár átmérője egységnyi, akkor a theta szögben eső sugár esetében az a felület amin ugyan annyi energia eloszlik sokkal nagyobb. Könnyen levezethető, hogy az egységnyi felületre eső energia (azaz a megvilágítás ereje) cos(theta)-val arányos.
- A beesési szög kiszámításához szükségünk van a felületi normálra. Még jó, hogy korábban gondoltunk erre. A cos(theta) kiszámításának egy egyszerű módja a skaláris szorzat használata. Ugyanis definíció szerint u * v = |u| * |v| * cos(theta).
  - De ha u-t és v-t úgy választjuk meg, hogy egységnyi hosszúak legyenek, akkor a skaláris szorzat a cos(theta)-t adja. Ha a cos(theta) negatív, akkor a test takarásban van, és az irányfény semmit nem befolyásol a színén.
Azokat az anyagokat, amiknek a színét csak ebből az összefüggésből ki lehet számolni, diffúz anyagoknak mondjuk. Ilyenek az a nem tükröző és a nem átlátszó anyagok, pl. a műanyagok nagy része.
Ezt felhasználva:

 
struct Light {
  enum LightType {Ambient, Directional} type;
  Vector pos, dir;
  Color color;
};

struct Material {
  virtual ~Material() { }
  virtual Color getColor(Intersection, const Light[], size_t) = 0;
};

struct DiffuseMaterial : public Material {
  Color own_color;

  DiffuseMaterial(const Color& color) : own_color(color) { }

  Color getColor(Intersection inter, const Light* lgts, size_t lgt_num) {
    Color accum_color;

    for(int i = 0; i < lgt_num; ++i) {
      const Light& light = lgts[i];
      switch(light.type) {
        case Light::Ambient: {
          accum_color += light.color * own_color;
        } break;
        case Light::Directional: {
          float intensity = max(dot(inter.normal, light.dir.normalize()), 0.0f);
          accum_color += intensity * light.color * own_color;
        } break;
      }
    }

    // Negatív vagy egynél nagyobb fényerősségeket nem szabad odaadni az OpenGLnek 
    // rajzolásra. Egyelőre legyen az a megoldás, hogy az invalid részt levágjuk (szaturáljuk).
    return accum_color.saturate(); 
  }
};

Az eddigi elmélet összerakva egy programmá: Kocka-tracer
Az eredménye, összehasonlítva azzal, amit az OpenGL tud, ugyan olyan beállítások mellett:

___________Sugárkövetett kocka---------------------------------------------- glutSolidCube(1.0f)_____________

A pont fényforrás

A pont fényforrás egy grafikában nagyon gyakran használt fényforrás, de a valóságban nem létezik. A valóságos izzóknak egyáltalán nem elhanyagolható a kiterjedése, nem pontszerűek, viszont ha pontszerűnek tekintjük őket, akkor sokkal könnyebb számolni velük. A pont fényforrás az irányfényforrástól annyiban különbözik, hogy az intenzitása és az iránya se állandó. Az intenzitásról annyit tudunk mondani, hogy bármely, a fényforrást körülvevő zárt térfogat felületén állandó (hiszen a fotonok nem vesznek el a semmibe, és nem is születnek a semmiből), így a fényforrás középpontú gömbök felületén is állandó az energia. Viszont erről a felületről tudjuk, hogy a távolság négyzetével arányos (A = 4*r^2*Pi), így az egy pontra jutó energia a távolság négyzetének reciprokával arányos. A fény iránya pedig egyszerűen a fényforrásból az megvilágítandó anyag felületi pontjába mutató egységvektor, és erre is ugyan úgy igaz a koszinuszos képlet.
A pont fényforrásnak fontos, hogy ne csak a színét adjuk meg, hanem az energiáját is, pl. egy húsz wattos zölden világító izzó "színének" adjunk meg Color(0.0f, 20.0f, 0.0f). Természetesen itt egy egység nem fog pontosan megfelelni egy wattnak, ez függ attól is, hogy a távolságot hogyan választottuk meg.
Egy lehetséges implementáció:

  
case Light::Point: {
  Vector pos_to_light = light.pos - inter.pos;
  float attenuation = pow(1/pos_to_light.length(), 2); 
  float intensity = max(dot(inter.normal, pos_to_light.normalize()), 0.0f);
  accum_color += attenuation * intensity * light.color * own_color;
} break;

A kamera fölül - fejlámpaként - világító pont fényforrás hatása:

A spot lámpa

A spot lámpa a pont fényforrásnak egy változata. Majdnem mindenben ugyanúgy viselkedik, azt leszámítva, hogy csak egy bizonyos térszög alatt fejti ki hatását.
Az ötlet egyszerű, tároljuk a lámpa irányát, és a maximális még megvilágított szög koszinuszát. Azt nem magát a szöget, mert a koszinuszát a skaláris szorzatból nagyon egyszerűen ki tudjuk számolni, míg ahhoz képest az acos() függvény nagyon nagyon drága (és amúgy fölösleges). Tehát nézzük meg, hogy az adott pontot megvilágítja-e a spot lámpa, és ha igen, akkor kezeljük azt utána pont fényforrásként.
Ez egy fall-through switchel nagyon egyszerűen megírható:

  
case Light::Spot: {
  Vector light_to_pos = inter.pos - light.pos;
  if(dot(light_to_pos.normalize(), light.dir) < light.spot_cutoff) {
    break; // Ha nincs megvilágítva, akkor ne csináljuk semmit.
  } // Különben számoljuk pont fényforrással.
} // NINCS break!
case Light::Point: {
...
} break;

A spot lámpa segítségével sokkal meggyőzőbb fejlámpát lehet csinálni. Az más kérdés, hogy nekem nem sikerült... :D

Árnyékok

Eddig úgy tűnik, hogy minden erőfeszítésünk ellenére az agyunk a képekről szinte gondolkodás nélkül el tudja dönteni, hogy azok nem valóságosak. Vagy az is lehet, hogy csak ritkán látunk semmi közepén lebegő kék színű diffúz kockákat, amin környezeti világítás is megjelenik, annak ellenére, hogy a kockának semmi sincs a környezetében.
Ezen változtassuk, rakjuk rá a kockát valami talajra, hogy ne lebegjen (így legalább csak a talaj lebeg, nem a kocka), és használjunk valami hihetőbb háttérszínt, mint a teljesen fekete, a megvilágítás szemléltetéséhez.

Például: Egyszerű környezet

Ez máris egy fokkal jobb, de sajnos a valósághűbb környezet választása nem oldotta meg minden problémánkat, hanem inkább újakat vetett fel, például, hogy a kocka nem vet árnyékot a síkra, mint ahogy azt a valóságban tenné.
A sík azon részeinek kéne árnyékban lenni, ahol valami útban van a fényforrásból az adott pontba menő sugárnak. Ezt úgy tudjuk felhasználni, hogy ha a fényforrásból egy sugarat lövünk az adott pont felé, és megnézzek, hogy a legközelebbi tárgy, amit eltalált, az az-e, amit éppen rajzolni akarunk, vagy praktikusan a metszéspont fényforrástól vett távolsága megegyezik-e, az adott pont távolságával a fényforrástól. Mert ha nem, akkor amit rajzolni akarunk az árnyékban van. Egy másik ezzel ekvivalens módszer, hogy a tárgyból lövünk egy sugarat a lámpa felé, és ha nem metsz semmit, vagy amit metsz, az távolabb van mint a fényforrás, csak akkor számolunk megvilágítást.
Technikailag mindkét algoritmust fogjuk használni. A második - bár bonyolultabbnak tűnhet - de irányfényforrásokra csak az módszer működik. Az irányfényforrások ugyanis végtelen távol vannak, ahonnan nem tudok elindulni, viszont a felületi pontból a fény irányába el tudunk. A pont fényforrások esetén viszont az első algoritmus egyszerűbb egy picivel.
Fontos megjegyezni, hogy pl. irány fényforrások esetén a sugarat nem indíthatjuk pontosan a felületi pontról, hiszen akkor az ahhoz legközelebbi metszéspont maga a felületi pont lenne amiből indítottuk. Ez persze nem mindig teljesülne, a számolási pontosság miatt, ezért az anyag kisebb foltokban lenne árnyékos, amit "árnyék pattanás"-nak hív a szakirodalom (shadow acne). A megoldás erre, hogy az indításkor a kezdő pontot eltoljuk egy kis számmal, epszilonnal a haladási iránnyal. Pl. 0.0001f-el. A pont fényforrás esetén is szükség van erre, csak ott a távolság összehasonlításánál.
Egy lehetséges implementáció:

case Light::Directional: {
   // Lőjjünk egy sugarat a fényforrás irányába
   Ray shadow_checker = {inter.pos + 1e-3*light.dir, light.dir}; // Az irányfény iránya nálam a forrás felé futat.
   Intersection shadow_checker_int = scene.getClosestIntersection(shadow_checker);
   if(shadow_checker_int.is_valid) {
     break; // Ha bármivel is ütközik, akkor árnyékban vagyunk
   }

   /* Megvilágítás számolása */ 
}
case Light::Point: {
  // Lőjjünk egy sugarat a fényforrás felől a konkrét pont irányába
  Ray shadow_checker = {light.pos, (inter.pos - light.pos).normalize()};
  Intersection shadow_checker_int = scene.getClosestIntersection(shadow_checker);
  if(shadow_checker_int.is_valid && 
    (shadow_checker_int.pos-light.pos).length() + 1e-3 < (inter.pos-light.pos).length()) {
      break; // Ha bármivel is ütközik, ami közelebb van a fényhez, mint mi, akkor árnyékban vagyunk
  }

   /* Megvilágítás számolása */ 
}

Az így létrehozott árnyékok:
Pont fényforrás esetén:

Irány fényforrás esetén:

Irány és pont fényforrás esetén egyszerre:

Tonemapping

Eddig a képalkotáskor a színeknek a (0, 1) tartományon kívül eső részét levágtuk. Ha nagyon sok esetben nem túl valósághű eredményhez vezet. Például vegyünk két 20 W-os izzót és világítsunk meg vele egy kockát. Ez a valóságban annyira nem ritka / lehetetlen összeállítás.
- Az eddigi módszereinkkel ez így néz ki:

A kép baloldala jól néz ki, van két egészen hihető árnyékunk. Maga a kocka is egész jó.
Viszont a képnek szinte a teljes jobb oldala kiégett, és minden ugyan olyan fehér, ordít róla, hogy mű. És ezek csak 2 db 20 W-os izzó...
Vegyünk két 50 W-os izzót:

A kocka még mindig jól néz ki. Ellenben itt már árnyékok is kiégtek, és az árnyékok nagy része ugyan olyan fényes, mint az, ami közvetlenül meg van világítva. És ezek még mindig teljesen hétköznapi értékek, két db 50 W-os izzó... Ha ez nem megy, akkor a Nappal mit kezdjünk?
- Egy megoldás lehetne, hogy mindent sokkal sötétebbre veszünk, úgy, hogy a Nap fénye legyen a teljesen fehér. Annál világosabbal nem nagyon szoktunk dolgozni. Igen ám, de az emberi szem egy sötét szobában se teljesen vak, ha hihető képet akarunk, akkor egy olyan algoritmus kéne, ami ilyen körülmények között is működik.
A megoldás az, hogy ne lineáris színskálát használjuk. Ez azt jelenti, hogy pl. kétszer akkora fényerősségű képponthoz ne kétszer olyan fényes pixelt rajzoljunk ki, hanem csak egy picivel világosabbat. Például használjuk logaritmikus skálát, ahol ha egy fényerősség értékét négyzetre emeljük, akkor kétszer olyan fényes pixelt rajzolunk hozzá. Ez persze csak 1-nél nagyobb fényerősségekre működik, és ez mindig véges tartományt eredményez. Olyan függvény kéne, ami a (0, végtelen) tartományt (ún. High Dynamic Range - HDR) a (0, 1) tartományra (Low Dynamic Range - LDR) képzli le, de úgy, hogy még a (0, 1) tartománybeli értékekből is élvezhető képet állítson elő.
A HDR színből LDR szín előállítását tonemappingnek hívjuk.

Reinhard operátor

Egy lehetséges megoldás a Reinhard operátor. Előadáson ez szokott szerepelni.
- Először is kell számolnunk az adott fénynek a luminanciáját (jele: Y).
  - Ez azt adja meg, hogy az adott fény az emberi szem számára mennyire látszódik fényesnek.
  - A látható spektrum szélén lévő színek (pl a kék és a piros) adott fényerősség mellet nem látszanak nagyon fényesnek.
  - Viszont a spektrum közepén lévő színek, főleg a zöld, ugyan akkora fényerősség mellett, mint a többi szín, sokkal világosabbnak látszik.
- A kísérletileg meghatározott képlet, ami az érzékelt fényerősséget meghatározza:
  - Y = 0.2126f*r + 0.7152f*g + 0.0722f*b
- Az új luminancia értéke: Y' = Y / (Y + 1);
- Az új szín pedig: color' = color * Y' / Y;
- Az új szín luminanciája garantáltan a (0, 1) tartományba esik, de szín komponenseire ez nem feltétlen igaz. Pl: Color(0, 0, 10) -> Color(0, 0, 4.1928)
- Az eredményt továbbra is szaturálni kell
  - Ez igazándiból nem zavaró. Nagyon ritkán okoz különbséget, és akkor se feltűnő.
- Az eredmény viszont lényegesen sötétebb lesz mint az eredeti kép.
Pl 2 db 50 W-os izzó esetén:

Bal oldalt tone map nélkül, Jobb oldalt Reinhard tonemappel.

Nagyon fényes képek élvezhetőségén a Reinhard operator nagyon sokat javít.
Viszont az alapból sötét képeken csak tovább ront.
Pl: Két db 5 W-os izzó esetén:

Bal oldalt tonemap nélkül, Jobb oldalt Reinhard tonemap-pel.

A Reinhard operátor a semminél jobb, de nem az igazi.

Filmic tonemap operátor

Az egyik legszebb tonemap, az a fény leképezés, amit Kodak filmek használnak.
- Ki gondolta volna, hogy Kodak ért ahhoz, hogy hogyan kell szép képet csinálni...
- Az algoritmus, ami ezt leutánozza a "filmic tonemap" nevet kapta, az eredetére utalva.
- A pontosan algoritmus lassú, és bonyolult, egy logaritmus képzésen alapul, de 3 texture lookup is van benne.
  - Jim Hejl (az EA games egyik fejlesztője) talált hozzá egy nagyon egyszerű, de meglepően pontos közelítést.

  x = max(0, InputColor-0.004);
  OutputColor = (x*(6.2*x+0.5))/(x*(6.2*x+1.7)+0.06);

WTF????
Ennek a "random képletnek" egy apró szépséghibája, hogy sRGB színtérbe állítja elő a színt, viszont nekünk sima RBG színt adnunk az OpenGL-nek, ezért az eredményt komponensenként 2.2-edik hatványra kell emelnünk, hogy használni tudjuk.
Az eredményt nem kell szaturáni.
De működik!

_____ Tonemap nélküli kép ____________ Reinhard tonemap ______________ Filmic tonemap _______

A filmic operátor a túl sötét képeket világosabbá, élvezhetőbbé teszi.
A túl világos képeken továbbra is érződik, hogy ott világos van.
Szinte az összes képet élvezhetőbbé teszi.
Csak egyszerű ALU műveleteket használ.

Spekulráis anyagok

Az anyagok amikkel eddig dolgoztunk teljesen diffúzak voltak.
A teljesen diffúz anyag egy pontja, konstans megvilágítás mellett mindig ugyan úgy néz ki, akárhonnan, akármilyen szögből is nézzük. A valós anyagok viszont nem mind így viselkednek.
Most azzal fogunk foglalkozni, hogy bizonyos anyagokon egy lámpa fénye meg tud csillanni, ha megfelelő irányból nézzük. Ilyen pl. egy lakkozott fa felület. Fontos megjegyezni, hogy ez nem úgy viselkedik mint egy tükör, nem látjuk rajta a tükörképünket, csak esetleg egy megcsillanó foltot.
A viselkedésének leíráshoz meg kell értenünk, hogy ez a hatás hogy jön létre.
- A simának tűnő anyag felülete is valójában rücskös mikroszkóppal nézve. De a legtöbb anyagra igaz, hogy egy mérettartomány alatt már simának tekinthető mikro-lapokból (micro facet) épül fel. Ezek a kis lapok teljesen tükrözőnek tekinthetőek, és az anyagról a szemünkbe érkező fény, valójában a megfelelő irányba álló mikro-lapokról visszaverődő fényt jelenti.

A mikro-lapok iránya normál-eloszlást követ. A várható értékük - nyilván - a felületi normál. A szórás viszont az anyag jellemzője, ez legyen paraméter. Ha a szórás nagyon nagy, akkor a lapok elhelyezkedése szinte teljesen véletlenszerű, és így minden irányba ugyanannyira tükrözőek, vagyis egy teljesen diffúz anyagot alkotnak.
De ha a szórás kicsi... Akkor a lapok nagyobb része fog a normál irányába elhelyezkedni, így ha olyan szögből nézzük az objektumot, hogy a fény beesési irányának és a nézeti vektornak (a szemünkből a felületi pontba mutató vektornak) az átlaga a normál közelébe van, akkor abból az irányból nézve sokkal több fény a szemünkbe fog tükröződni, mint a többi irányból.
- De mit jelent az, hogy a "közelébe"? Mennyire a közelébe? És a normál közelébe mennyivel gyengébb ez a hatás, mint pont a normálban.
- A lapok irányát egy harang görbe jellemzi. Hogy megtudjuk, hogy abba az irányba a lapok hányadrésze néz, ami a visszatükröződésnek kedvez, be kell helyettesítenünk a normál eloszlás sűrűségfüggvényébe. A képlet nem bonyolult, de van benne egy exponenciális függvény, aminek kiszámítása lassú. Viszont skaláris szorzattal egy koszinuszt ki tudunk számolni, ami egy picit hasonlít a haranggörbére. Ha a koszinusznak vesszük egy polinomját, pl az a*cos(x)^b, azzal nagyon jól közelíteni lehet a haranggörbét. Én ezt az ötlet fel fogom használni az implementációhoz, mert így az egy picit egyszerűbb.
Az egyik lehetőség, hogy a visszaverődési normál (a fényből a felületi pontba menő, és az abból a szemünk felé mutató egységvektorok átlaga) és a tényleges felületi normál által bezárt szög koszinuszát használjuk. Az előadáson ez szokott elhangozni, mert ez az egyszerűbb módszer, de én egy másik lehetőséget fogok implementálni, mert én azt jobban szeretem.
Először is ki kell tudnunk számolni, hogy 'N' normálvektorral rendelkező tükör merre ver vissza egy beérkező 'I' sugarat. A visszavert sugarat jelöljük 'R'-el. Azt tudjuk, hogy a három vektor egy síkban van, és a beesési szög megegyezik a visszaverődési szöggel. De mégse így fogunk számolni, egyszerű vektor műveletekkel is ki lehet fejezni.

Próbáld a visszavert sugarat csak a négy alapművelet és a skaláris szorzás segítségével kifejezni. Ha nem megy, ajánlom hogy nézd át újra a BSZ I. anyagot.
Az legegyszerűbb megoldás:

inline Vector reflect(Vector I, Vector N) {
  return I - (2.0 * dot(N, I)) * N;
}

Ezt felhasználva legyen 'R' legyen a visszaverődő fény iránya, 'V' pedig a felületi pontból a szemünk felé mutató egységvektor.
A haranggörbét közelíthetjük e két vektor által bezárt szög koszinuszával is: dot(R, V). Persze a negatív értékek nekünk nem jók és ennek még a polinómját is kell vennünk. A képlet így specular_power = a * pow(max(0, dot(R, V)), shininess). Megjegyzés: az 'a' konstans elhagyható, az implicit benne lehet az anyagra jellemző spekuláris színben.
A spekuláris anyag egyben diffúz is. A spekuáris megcsillanás (specular_power * specular_color) hozzáadódik a diffúz megvilágításból származó színhez.
Pl. irányfényforrásokra én így implementáltam.

 
float specular_power = 
  pow(
    max(0.0f, dot(
      reflect(-light.dir.normalize(), inter.normal), 
      (camera.pos-inter.pos).normalize())
    ), shininess
  );
accum_color += specular_power * light.color * specular_color;

Persze itt se feledkezzünk el az árnyékokról. Szerencsére az árnyékszámítás itt is teljesen ugyan az.
A 'shininess' meghatározása teljesen mértékben hasra-ütésre, próbálgatással szokott menni. Én személy szerint a kettő hatvány shinnines értékekkel szoktam először próbálkozni (8 - 16 - 32 - 64 a leggyakoribb nálam), és utána esetleg "finom hangolom" az értéket, az alapján, hogy mi néz ki jól.
A spekuláris megcsillanások nagyon sokat tudnak dobni egy kép hihetőségén:

A tökéletes tükör

A mikroszkopikus tükrök figyelembevételével a fényforrások fénye tükröződni tud. De mi van a valódi tükrökkel? Amikben más objektumok képeit is látjuk, nem csak a fényforrások hatását?
Sugárkövetéssel ilyen tükröket renderelni meglepően egyszerű. Az egyetlen dolog amit a tükör tulajdonságú anyag csinál a modellünkbe az az, hogy a tükröződés irányába továbblövi a sugarat.
Implementálni ezt nagyon egyszerű, pl.:

 
Color getColor(Intersection inter, const Light* lgts, size_t lgt_num) {
  Ray reflected_ray;
  reflected_ray.direction = reflect(inter.ray.direction, inter.normal);
  reflected_ray.origin = inter.pos + 1e-3*reflected_ray.direction;
  return scene.shootRay(reflected_ray);
}

Az egyetlen kényelmetlenséget az okozhatja, hogy ha az eddig használt adatstruktúránk nem tárolta, hogy milyen irányból érkezett a sugár, mert az nyilván kell ahhoz, hogy tudjuk, hogy melyik irányba verődik vissza.
Pl ha padló anyagát lecserélem egy tükörre, akkor az eredmény így néz ki:

Ez valóban egy tükörnek néz ki, de egy apró probléma még akad vele... Mi van, ha két tükröt rakunk egymással szembe? A sugár a végtelenségig fog pattogni a kettő között? Nem egészen. Ugyanis ez egy rekurzív algoritmus, ahol a függvényhívásoknak a stackbe is lesz nyoma, ahol viszont a hely előbb utóbb elfogy, és ilyenkor a programunk megáll.
- A sugárkövető függvényünkbe követnünk kell, hogy ez hanyadik függvényhívás volt, és ha ez a szám, meghalad valamilyen értéket, pl. 8-at, akkor a sugarat már ne lőjük tovább.
- Pl:

Color shootRay(Ray r, int recursion_level = 0) const {
  if(recursion_level >= 8) {
    return env_color;
  }
  //...
} 
Color getColor(Intersection inter, const Light* lgts, size_t lgt_num, int recursion_level) {
  // ...
  return scene.shootRay(reflected_ray, recursion_level + 1);
}

Két szemben lévő tükör hatása:

A valós tükröző anyagok

A valós tükröző anyagok, nem csak a tükrök, de pl. a fényesre csiszolt fémek is, nem viselkednek tökéletes tükörként. A különbség az, hogy ezek az anyagok nem a fény 100%-át verik vissza, hanem egy részét elnyelik (az nagyrészt hővé alakul). Az elnyelt fény mértéke a hullámhossztól is függhet, ezért pl. egy sima aranyfelület elszínezi a tükörképet. Egy fürdőszobai tükör persze minden hullámhosszon nagyjából ugyanannyi fényt nyel el.
A képlet amire szükségünk lenne, az egy adott hullámhosszon a törésmutató, és a kioltási tényező függvényében megmondaná, hogy a fény hanyad része verődik vissza.
- Elég nagy problémát okoz, hogy ebben a képletben a bemenet és a kimenet is hullámhossz függő. Egy lehetséges egyszerűsítés, hogy mi csak három kitüntetett színre (a pirosra a zöldre és a kékre) számoljuk ki a képlet eredményét, és ezt ezzel megszorozzuk az RGB színskálán leírt színünket.
- Ez közvetlenül a Maxwell-egyenletekből levezethető, bár az eredmény, a Fresnel-egyenletek jóval bonyolultabb, mint amit mi használni szeretnénk.
  - Én csak a képletnek egy közelítését írom itt le, ami eltekint a polaricázótól (Schlick's approximation), mert a grafikában általában ezt szokták használni.
    - n - törésmutató (RGB vektor)
    - k - kioltási tényező (RGB vektor)
    - F0 - egy az anyagra jellemző konstans
      - F0 = ((n-1)*(n-1) + k*k) / ((n+1)*(n+1) + k*k);
    - theta - beesési szög
    - F(theta) - a visszaverődő relatív intenzitást adja meg, komponensenként:
      - F(theta) = F0 + (1-F0) * pow(1-cos(theta), 5)

Pl:

struct ReflectiveMaterial : public Material {
  const Color F0;
 
  ReflectiveMaterial(Color n, Color k)
    : F0(((n-1)*(n-1) + k*k) /
         ((n+1)*(n+1) + k*k))
  { }
 
  Color F(float cosTheta) {
    return F0 + (Color(1)-F0) * pow(1-cosTheta, 5);
  }
 
  Color getColor(Intersection inter, const Light* lgts, size_t lgt_num, int recursion_level) {
    Ray reflected_ray;
    reflected_ray.direction = reflect(inter.ray.direction, inter.normal);
    reflected_ray.origin = inter.pos + 1e-3*reflected_ray.direction;
    return F(dot(-inter.ray.direction, inter.normal)) * scene.shootRay(reflected_ray, recursion_level+1);
  }
};

Ezüst esetén (n = (0.14, 0.16, 0.13), k = (4.1, 2.3, 3.1)):

A fényt megtörő anyagok

A Fresnel egyenlet eddigi felhasználásakor azt feltételeztük, hogy a fénynek az a része, ami nem verődik vissza, az megpróbál továbbmenni, de pl. egy fém belsejében ezt nem tudja megtenni, ezért elnyelődik, energiává alakul. De nem minden anyag viselkedik így.
Pl. az üveg esetében a fény, ha nem verődik vissza, akkor továbbmegy az üvegben, de egy picit el is térül. Az irányának a megváltozását a Snelius-Descart törvény írja le sin(Alpha1) / sin(Alpha2) = n1 / n2 .
- Az irány kiszámoláshoz jobb lenne egy képlet, ami egyszerű vektorműveleteket használ.
- A kiszámolásnál figyelnünk kell a teljes visszaverődés esetére is. Ilyenkor gyakorlatilag a fény 100%-ka visszaverődik, még az a rész is, ami a Fresnel egyenlet szerint továbbmenne.
Én az irány kiszámolásához az alábbi képletet fogom használni. A képlet másolása helyett inkább próbáld meg levezetni magadnak.

inline Vector refract(Vector I, Vector N, double n) {
  double k = 1.0 - n * n * (1.0 - dot(N, I) * dot(N, I));
  if (k < 0.0) {
    return Vector();
  } else {
    return n * I - (n * dot(N, I) + sqrt(k)) * N;
  }
}

Fontos megjegyezni, hogy ebben a képletben az 'n' a relatív törésmutató. Pl. ha a sugár levegőből üvegbe megy, akkor - mivel a levegő törésmutatója 1-nek tekinthető - így a relatív törésmutató az üveg törésmutatója: 1.5 / 1 = 1.5. Viszont amikor a sugár az üvegből távozik, akkor a relatív törésmutató 1 / 1.5 = 0.666.
- Gyakori hiba ennek a reciprok képzésnek a lehagyása.
Egy másik hibalehetőség ezzel a függvénnyel kapcsolatban, hogy ha normálvektor ellentettjét használjuk, akkor rossz eredményt ad. Erre fontos figyelni, pl. amikor a kocka belsejéből kifele jön a sugár, hiszen ilyenkor a befele mutató normállal kell számolni, nem a kifele mutatóval. Ugyanígy a Fresnel egyenlet is rossz eredményre vezet, ha a normál ellentettjével számolunk, ezért célszerű a függvény legelején megfordítani a normált, ha arra szükség van:

if(dot(inter.ray.direction, inter.normal) > 0) {
  inter.normal = -inter.normal;
}

Fontos még, hogy a Fresnel egyenletben kifele menet is ugyan azt a törésmutatót kell használni. Az F0 kiszámolásakor az egyesek a levegő törésmutatója helyén állnak, általános esetben a képlet a ((n1 - n2)^2 + k*k) / ((n1 + n2)^2 + k*k) alakot veszi fel. Ez a képlet viszont n1 és n2 szempontjából szimmetrikus, így nem kell két F0-t számolni, egyet a befele, egyet meg a kifele menő sugarakhoz.
Csak olyan törő anyagokkal foglalkozunk, amiknek a törésmutatója a hullámhossztól független. A nem így viselkedő anyagok, a prizmák nagyon látványos képeket tudnak eredményezni, de sokkal számításigényesebbek és bonyolultabbak, ezért most nem fogok velük foglalkozni.
Ezt felhasználva:

struct RefractiveMaterial : public ReflectiveMaterial {
  float n, n_rec;
 
  RefractiveMaterial(float n, Color k)
    : ReflectiveMaterial(n, k), n(n), n_rec(1/n)
  { }
 
  Color getColor(Intersection inter, const Light* lgts, size_t lgt_num, int recursion_level) {
    if(dot(inter.ray.direction, inter.normal) > 0) {
      inter.normal = -inter.normal;
    }

    Ray reflected;
    reflected.direction = reflect(inter.ray.direction, inter.normal);
    reflected.origin = inter.pos + 1e-3*reflected.direction;
 
    Color reflectedColor, refractedColor;
 
    Ray refracted;
    refracted.direction = refract(inter.ray.direction, inter.normal, inter.ray.in_air ? n : n_rec);
    if(!refracted.direction.isNull()) {
      refracted.origin = inter.pos + 1e-3 * refracted.direction;
      refracted.in_air = !inter.ray.in_air;
 
      Color F_vec = F(dot(-inter.ray.direction, inter.normal));
      reflectedColor = F_vec * scene.shootRay(reflected, recursion_level+1);
      refractedColor = (1 - F_vec) * scene.shootRay(refracted, recursion_level+1);
    } else {
      reflectedColor = scene.shootRay(reflected, recursion_level+1);
    }
 
    return reflectedColor + refractedColor;
  }
};

Az eredménye: Üveg kocka

A kocka egészen hihetően néz ki, viszont a talaj megvilágítása teljesen rossz. Az árnyékszámító algoritmus azt feltételezte, hogy fény a nem megy át a - jelenleg átlátszó - kockán. De ha az árnyékokat elhagynánk, akkor is teljesen rossz képet kapnánk. Az üveg kocka megtöri a fényt, de néhol tükröz is, esetleg sok fénysugarat ugyanabba a pontba fókuszál... ezeknek a jelenségeknek a hatását az eddigi megvilágítási modellünk egyáltalán nem vette figyelembe.
A klasszikus megvilágítási modell (ahol az anyagok színe az ambiens, diffúz és spekuláris tagok összege) azt feltételezte, hogy a fény, a fényforrásból a jelenet bármely pontjába csak egyenes úton juthat el. Ennek az a nagy előnye, hogy egy felületi pont színéhez nem kell tudnunk a többi pont színéről semmit. Az ezzel a tulajdonsággal rendelkező világításszámoló algoritmusokat lokális illuminációnak nevezzük. Ha a jelenetben van tükröző vagy törő anyag akkor ez értelemszerűen nem működik. Az ilyen jelenteknél másképp kell megvilágítást számolnunk. Ilyenkor globális illuminációra van szükségünk.

A globális illumináció

A lokális illuminációt azért szerettük, mert nagyon lecsökkentik a probléma számításigényét. A ténylegesen jelen lévő fotonok számától függetlenül, pixelenként egyetlen sugár követésével megtudtuk oldani a feladatot. Azonban a törő vagy tükröző anyagok ezt az algoritmust reménytelenül elbonyolítják. Ilyenkor a valóság utánzása nyers erővel a leginkább járható út.
- Az ötlet, hogy a fényforrásból lőjünk nagyon sok fotont random irányba, és nézzük meg, hogy miután a törő / tükröző anyagok továbblőtték a fotonokat, hova csapódnak be.
- A diffúz anyagokat osszuk fel részekre, és egy textúrába tároljuk el az egyes részeibe becsapódó fotonok színeinek összegét.
- A rendereléskor ezt a színt jelenítsük meg az adott részhez.
- Így nagyon szép eredményeket érhetünk el - de nagyságrendekkel lassabban...
Először szükségünk van egy függvényre, ami a diffúz felület térbeli pontjaihoz hozzárendel egy pontot a textúrán.
- A textúra koordináták x komponensét 'u'-nak az y komponenst pedig 'v'-nek szokás hívni.
- Célszerű a textúrán belüli koordinátát is valós értéknek tekinteni, nem egészeknek, és bilineáris elérést használni.
  - Ez azt jelenti, hogy ha egy 'c' színű fotonnak 4.7 az 'u' koordinátája, akkor 0.3*c-t írjuk a 4-es 'u' koordinátára és 0.7*c-t az 5-ös koordinátára. Két dimenzióban analóg módon 4 helyre is írunk.
  - A kiolvasáshoz is használjuk bilineáris elérést.
- Profiknak célszerű textúra helyett KD-fába tárolni a fotonok becsapódását. Sokkal szebb eredményt lehet így elérni, és ráadásul még a spekuláris megcsillanások is implementálhatóak, hiszen a fotonok iránya is könnyen eltárolható.
Pont fényforrás esetén sem kell számolni azzal, hogy a foton mekkora távolságot tett meg. A foton nem lesz gyengébb, attól, hogy x utat megtett, csak minél távolabb vagyunk a fényforrástól, egy adott pontra annál kevesebb foton fog esni. De ez nem a foton tulajdonságából adódik, ez a fotontérképből implicit ki fog jönni.
A fotontérkép méretének és a fotonok számának megválasztása teljesen ad-hoc. De nem érdemes túlzásba vinni, hiszen a globális illumináció nagyon számításigényes. A házihoz reális értékek pl: fotontérkép mérete: 2^5 * 2^5 - 2^7 * 2^7, fotonok száma: 10^4 - 10^6.
A "foton" igazándiból foton csomagot jelent, pl. a törő anyagok kétfelé választhatnak egy ilyen csomagot.
A foton tudja magáról, hogy milyen színű. A kölcsönhatásokkor a Fresnel egyenlet következtében a foton színe megváltozhat.
Az egyes fotonok energiája legyen fordítottan arányos a fotonok számával. A fényforrás energiája az összes fotonra egyenletesen oszlik szét. Ha megkétszerezzük a fotonok számát, akkor is ugyan olyan fényes jelentet akarunk kapni.
A törő és tükröző anyagok pont ugyan úgy lépnek kölcsönhatásba a fotonokkal, mint ahogy a sugarakkal is. Ennek az implementáláshoz semmi új ötlet nem kell.
Például egy felülről megvilágított üvegkocka így szórja a fényt:

A kétirányú sugárkövetés

A globális illumináció implementálásakor sokak fájó szívvel válnak meg a kódban a lokális illumináció résztől, lévén, hogy hiába írták meg, ha nem jó semmire. De ez nem így van. Egyrészt a negyedik és az ötödik házihoz nagyon nagy segítséget fog nyújtani, hogy érted, hogy hogyan működik a lokális illumináció, hiszen az OpenGL is ezt fogja használni. Másrészt még a sugárkövetés házi végleges formájába is hasznos lehet az a kód.
A kétirányú sugárkövetés ötlete, hogy használjuk a lokális és a globális illuminációt egyszerre. A diffúz anyagot világítsuk meg lokálisan, és csak azok a fotonok keltsenek rajta kausztikát, amik nem triviális úton (egyenes vonalon, végig a levegőben, kölcsönhatás nélkül) jutottak el a fényforrásból az anyagig.
- Ha a foton ütközésekor a rekurziós szint 0, akkor az közvetlenül a fényforrásból jutott el hozzánk, azt ne mentsük el.
A kétirányú sugárkövetés előnyei:
- Rengeteg erőforrást meg tud spórolni. Az üvegkocka esetében tized annyi foton elég egy ugyanolyan minőségű kép előállításához.
- A spekuláris hatást is figyelembe tudjuk venni.
A kétirányú sugárkövetés hátrányai:
- Nem triviális a konstansokat úgy beállítani, hogy a lokális és a globális illumináció konzisztens legyen.
- Az árnyékok széle recésebb lesz. A bilineáris szűrés miatt a globális illumináció pontosabban határozza meg az árnyékok szélét, mint az a módszer, amit a lokális illuminációnál használtunk.
A korábbi jelenet, csak globális (bal oldalt) és kétirányú (jobb oldalt) sugárkövetéssel, mindkét esetben 500 000 fotonnal:

Utóhang

Én nagyon élveztem az összefoglaló megírását, remélem Te is hasonló élményekkel gazdagodtál a házijaid megírásakor. Amikor én a tárgyat csináltam ilyen részletes segédlet még nem volt, bár nekem hasznos lett volna. Annak ellenére, hogy már a tárgy felvétele előtt is rengeteget foglalkoztam grafikával, még a beadott házijaimba is voltak elvi hibák, amikre itt külön felhívtam a figyelmet, hogy ti ne kövessétek el. Ha ez az összefoglaló segített a házijaidban, vagy valami újat tanultál belőle, próbálj meg te is segíteni az utánad jövőknek azokból a tárgyakból, amikből Te jó vagy!

RohamCsiga - 2014.01.

Számítógépes grafika házi feladat tutorial

Tartalomjegyzék

Előszó

Az OpenGL és GLUT alapjai

Az OpenGL

A GLUT

Az első házihoz szükséges elmélet

Rajzolás az OpenGL segítségével

2D rajzolás

Eseménykezelés

Animáció

A második házihoz szükséges elmélet

Koordináta rendszerek

Transzformációk

Matrix stack

Görbék

A harmadik házihoz szükséges elmélet

A Sugárkövetés alapjai

Hogyan kövessük a sugarakat?

Megvilágítás

Az ambiens fényforrás

Az irány fényforrás

A pont fényforrás

A spot lámpa

Árnyékok

Tonemapping

Reinhard operátor

Filmic tonemap operátor

Spekulráis anyagok

A tökéletes tükör

A valós tükröző anyagok

A fényt megtörő anyagok

A globális illumináció

A kétirányú sugárkövetés

Utóhang

Navigációs menü

Keresés