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

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

← Vissza az előző oldalra – Számítógépes_grafika_és_képfeldolgozás

Ez a tutorial alapvetően azt hivatott elmagyarázni, hogy hogyan kell az OpenGL-t használni, csak abba ad segítséget, hogy hogyan oldd meg a házidat. A háziknak pont az a célja, hogy az órán elsajátított elméletet gyakorolni tudd, így ha az elmélet ismerete nélkül vágsz neki a házinak, az lehet, hogy sikerülni fog, de a tárgy szempontjából semmi értelme nem lesz... Ez a tutorial nem helyettesíti az órán való jelenlétet.

Az oldalról kódot a saját házidba átemelni TILOS! Még ha pár sornyi kódról is van szó, gépeld be szépen magadtól, addig is gyakorlod a dolgot. Meg persze nem is érdemes másolgatni, mert csak borzolod vele a plágiumkereső idegeit, és sokban ronthat az esélyeiden az aláírás megszerzésére

Ez a lap még erősen fejlesztés alatt áll, ha van ötleted akkor írd bele nyugodtan, vagy egészítsd ki az egyik hiányzó TODO részt

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

http://i.imgur.com/if8gaHR.gif

• 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:

http://i.imgur.com/bOSuMin.png

• 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:

http://i.imgur.com/6yfh7q2.png

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:

http://i.imgur.com/4WDimmL.png

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:

http://i.imgur.com/ezFQ4l4.png

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:

http://i.imgur.com/S3m5Lmv.gif

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 (jobbró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:

http://i.imgur.com/gUqk4pi.gif

- 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:

http://i.imgur.com/XQcsrHs.gif

- 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:

http://i.imgur.com/PA2A3eQ.png

• 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:

http://i.imgur.com/tpAuxBa.gif

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 szakadása van. Egy valós útvonal esetében ez 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

http://i.imgur.com/C1iKaHx.gif

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

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ék 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, í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 (jelen esetben négyzetre). 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: up .
  • 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 .
  • Szükségünk van arra, hogy melyik irányra van jobbra. Ezt a 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 (amiről 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) * 2*tan(fov/2) / Screen::width,
  // Itt nem kell megfordítani az y tengelyt. A bal fölső sarok az origó most.
  (y - Screen::height/2) * 2*tan(fov/2) / Screen::height, 
  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:
  • A téglalap az, amin a kép keletkezik, az viselkedik úgy mint a szemünk. ha a téglalap helyére állnák, akkor kapnánk ugyan azt a képet, mint amit meg akarunk jeleníteni. Ezt 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)
  • 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 - Screen::width/2) / Screen::width,
      // Itt nem kell megfordítani az y tengelyt. A bal fölső sarok az origó most.
      (y - Screen::height/2) / Screen::height, 
      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.
  • Enélkül csak egy fekete képernyőt látnánk, ezért ehhez a fejezethez nincs példaprogram.

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(Material* mat, const Vector& a, const Vector& b, const Vector& c) 
    : Object(mat), 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őpontokra 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 segít sokat a heterogén kollekció használata. Az objektumok az én implementációmba azt is eltárolják, hogy milyen anyagból vannak, de ezt nem kötelező az ősosztályba rakni.

 
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, de ne másold ezt:

 
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() {
    for(int i = 0; i != obj_num; ++i) {
      delete objs[i];
    }
  }

  static const size_t max_lgt_num = 10;
  size_t lgt_num;
  Light lgts[max_obj_num];

  void AddLight(const Light& l) {
    lgts[lgt_num++] = l;
  }

  static const Vector env_color;

  Scene() : obj_num(0) { } 

  Color shootRay(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;
      }
    }

    if(closest_index != -1) {
      return objs[closest_index]->mat->getColor(closest_intersection, lgts, lgt_num);
    } else {
      return env_color;
    }
  }
}

• 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.
  • Tesztelésképpen kipróbálhatod, hogy ha találsz metszéspontot, akkor mondjuk fehér színt rajzolsz ki, amúgy feketét. Ez egy ronda és unalmas eredményt ad, de legalább észre tudod venni, ha eddig valamit elrontottál.

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 és statisztikára lesz szükségünk.
• 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 az ambiens fényerőt változtatás nélkül hozzáadjuk az objektum színéhez.
• 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. Ez a különbség 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)-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;
  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.pos), 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:

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

http://i.imgur.com/tgmGj7A.png http://i.imgur.com/PA2A3eQ.png

-- RohamCsiga - 2014.01.