@@ 552. sor: / 552. sor: @@
 </div>
+== 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 <code> glDrawPixel() </code> függvény segítségével.
+*** Pl:
+<br/> <syntaxhighlight lang="c">
+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);
+  }
+};
+</syntaxhighlight> <br/>
+* 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: <code> pos </code>.
+** Meg kell adnunk, hogy a kamera, merrefelé néz. Kódban pl: <code> fwd </code> (egységvektor).
+** Azt is tudnunk kell, hogy melyik iránynak felel meg a felfele ("What's up?"). Kódban pl: <code> up </code>.
+** 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: <code> pos + fwd </code>.
+** 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: <code> right = cross(fwd, up) </code>.
+** 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: <code> up = cross(right, fwd) </code>.
+** 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:
+<br/> <syntaxhighlight lang="c">
+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,
+);
+</syntaxhighlight> <br/>
+* Ezt az értéket pedig át kell számolnunk a világ koordináta rendszerébe:
+<br/> <syntaxhighlight lang="c">
+Vector plane_intersection = plane_pos + pos_on_plane.x * right + pos_on_plane.y * up;
+</syntaxhighlight> <br/>
+* É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:
+<br/> <syntaxhighlight lang="c">
+struct Ray {
+  Vector origin, direction;
+};
+Ray r = {pos, (plane_intersection - pos).normalize()};
+</syntaxhighlight> <br/>
+* 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:
+<br/> <syntaxhighlight lang="c">
+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,
+    );
+    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);
+  }
+}
+</syntaxhighlight> <br/>
+* 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:
+<br/> <syntaxhighlight lang="c">
+struct Intersection {
+  Vector pos, normal;
+  bool is_valid;
+};
+</syntaxhighlight> <br/>
+* 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.
+<br/> <syntaxhighlight lang="c">
+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();
+  }
+};
+</syntaxhighlight> <br/>
+* 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.
+<br/> <syntaxhighlight lang="c">
+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;
+};
+</syntaxhighlight> <br/>
+* É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:
+<br/> <syntaxhighlight lang="c">
+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;
+    }
+  }
+}
+</syntaxhighlight> <br/>
+* 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:
+<br/> <syntaxhighlight lang="c">
+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();
+  }
+};
+</syntaxhighlight> <br/>
+* Az eddigi elmélet összerakva egy programmá: [http://pastebin.com/emY17SB3 Kocka-tracer]
+<br/>
+Az eredménye:
+<div style="text-align:center;margin:0px auto;">
+http://i.imgur.com/tgmGj7A.png
+</div>
 == Régi wikiről áthozott rész, frissítésre szorul ==
 === Projekciós mátrixok, transzformációk ===

„Számítógépes grafika házi feladat tutorial” változatai közötti eltérés