[Tutorial] Izrada 3D/scenegraph enginea

3D engine, u osnovi osnova, sastoji se od elementarnog 3D vektora, te transformacije tog vektora u 2D ravninu.

Vecina nasih 'matematickih' podataka biti ce izrazena kroz vektore - pozicija, boja, os rotacije, uv koordinate, skaliranje, bla bla bla... dakle, kao osnovu, bilo bi odlicno napraviti Vector klasu (nemojte ovo, molim vas, pomijesati sa vector kolekcijom iz STL-a).

Problemu se moze, kao i uvijek, pristupiti na nekoliko nacina:

1. Vektori koji nama trebaju imaju dvije, tri i cetiri dimenzije. Dakle, mogli bismo napraviti 3 klase: Vector2, Vector3 i ColorRGBA

2. Mogli bismo izvuci superklasu koja objedinjuje matematicke operacije izvedene nad elementima vektora, te subklasirati ovisno o tipu ili broju elemenata

3. Mogli bismo napraviti Vector klasu koja prima dinamicki alociran array i velicinu istog, te vrsi operacije nad arrayem

4. Mozemo se praviti pametni i premature optimizirati, zgroziti se nad dinamicki alociranim arrayem, pa to rijesiti kao svaki pametan covjek preko jedne template klase ;-)

O vektoru kao jedinici mozete najvise procitati na Wolfram Math. Vektori podrzavaju vecinu operacija kao i skalari, dakle mogu se zbrajati, oduzimati, multiplicirati (pardon, mnoziti), dijeliti. Za razliku od skalara, vektori podrzavaju nekoliko dodatnih operacija kao sto su dot-produkt i cross-produkt (ispricavam se, ne znam hrvatske nazive za ovo).

Bilo bi idealno, dakle, kad bi nasa klasa podrzavala bilo koju velicinu vektora, a jos idealnije ako bi podrzavala bilo koji tip.

Zapocnimo sa strukturom naseg project-direktorija. Ja to volim rijesiti "po Mavenu" :-)

project-root
- src
 - main
  - cpp
 - test
  - cpp 
- target

Napravimo file 'Vector.hpp' u direktoriju src/main/cpp, i unesimo tipicne header guardove:

#ifndef VECTOR_HPP_
#define VECTOR_HPP_


#endif /* VECTOR_HPP_ */

Bilo bi uredno i odijeliti vektor u svoj namespace. S obzirom da cemo vjerojatno s vremenom dodati jos nekoliko matematickih konstrukta (matrica, quaternion), namespace 'math' bi bio dobar izbor. Takodjer, dobra praksa je slijediti namespaceove sa strukturom direktorija, pa dodajte 'math' unutar src/main/cpp/math

project-root
- src
 - main
  - cpp
   - math

Kod. Primjetite da su promjenjeni i header guardovi.

#ifndef MATH_VECTOR_HPP_
#define MATH_VECTOR_HPP_

namespace math {

}

#endif /* VECTOR_HPP_ */

Nadalje, htjeli smo da vektor bude templatiziran po velicini i po tipu, i idealno bi bilo da drzi svoje podatke na stacku - tako kad se budu vrsile operacije, mozemo hintati compileru da zgura membere u registre. Neki medju vama ce takodjer primjetiti da premature optimiziram pa se idem sad kazniti.

#ifndef MATH_VECTOR_HPP_
#define MATH_VECTOR_HPP_

namespace math {

template<typename Type, int Size>
class Vector {
private:
  Type data[Size];
}

}

#endif /* VECTOR_HPP_ */

Kad promislim bolje, cisti arrayi su zlo. Zlo kakvog nema. Bolje da ja iskoristim nesto sto su pametniji od mene vec napravili, i zavucem ruku u Boost i izvucem njihovu array klasu (primjetite i #include):

#ifndef MATH_VECTOR_HPP_
#define MATH_VECTOR_HPP_

#include <boost/array.hpp>

namespace math {

template<typename Type, int Size>
class Vector {
private:
  boost::array<Type, Size> data;
}

}

#endif /* VECTOR_HPP_ */

Tako je vec bolje.

Trebat ce nam i par konstruktora, cisto zbog jednostavnije inicijalizacije.

#ifndef MATH_VECTOR_HPP_
#define MATH_VECTOR_HPP_

#include <boost/array.hpp>

namespace math {

template<typename Type, int Size>
class Vector {
private:
  boost::array<Type, Size> data;

public:
   Vector() {
       for (int i = 0; i < Size; ++i) {
          data[i] = 0;
       }
    }

    Vector(const Type x, const Type y) {
       data[0] = x;
       data[1] = y;
    }

    Vector(const Type x, const Type y, const Type z) {
       data[0] = x;
       data[1] = y;
       data[2] = z;
    }

    Vector(const Type r, const Type g, const Type b, const Type a) {
       data[0] = r;
       data[1] = g;
       data[2] = b;
       data[3] = a;
    }

    Vector(const boost::array<Type, Size>& values) : data(values) {}

    Vector(const Type values[Size]) {
       for (int i = 0; i < Size; ++i) {
          data[i] = values[i];
       }
    }

    ~Vector() {
    }

}
}


#endif /* VECTOR_HPP_ */

K. Treba nam nacin za dobiti podatke iz vektora. Iako u poslu ne volim operator overloading, zgodan je to feature za hobi projekte pa cemo ga ovdje iskoristiti.

Overloadat cemo indeks-operator, i to na nacin da ne dopusta mijenjanje vektora. To znaci da vrijednost overload funkcije ne vracamo po referenci.

Od sad nadalje necu kopirati cijeli kod, nego samo dodatke.

Type operator[](const int i) const {
    return data[i];
}

Trebat ce nam i neke osnovne operacije. Evo zbrajanja, vama ostavljam da sredite oduzimanje, mnozenje, i dijeljenje:

Vector<Type, Size> operator+(const Vector<Type, Size>& that) {
    Type resultData[Size];
    for (int i = 0; i < Size; ++i)
       resultData[i] = data[i] + that[i];

    Vector<Type, Size> result(resultData);
    return result;
}

I jos nekoliko dodataka za kraj.
Prvo, bilo bi odlicno da mozemo ispisati vektor na neki stream, tako da mu se vide vrijednosti. U C++-u se to obicno radi overloadanjem "<<" operatora, sto osobno smatram katastrofom, pa cemo to ostaviti za neku buducnost, i posluziti se C#-ovskim (pokradeno iz Jave ;-)) ToString().

Na vrhu filea treba dodati, ofc:

#include <string>
#include <sstream>

A negdje unutar Vector klase, recimo na dno:

std::string ToString() const {
    std::ostringstream oss;
    oss << "{";
    for (int i = 0; i < Size - 1; ++i) {
       oss << (data[i]) << ", ";
    }
    oss << (data[Size - 1]);
    oss << "}";
    return oss.str();
}

K. To bi bilo to za danas, jer sam lijen tipkati dalje.

Slijedeci put dodat cemo jos nekoliko bitnih operacija u Vector, kao sto su kalkulacija duzine, normalizacija, i jos par bitnih operacija.

Takodjer, ustolicit cemo globalnu "Object" klasu sa par generalnih funkcionalnosti korisnih svagdje.

Cheers!

Edit:

Refactorirao sam  kod da ga napravim citljivijim, te da se aritmetika overloadanih operatora drzi iskljucivo na jednom mjestu.

Trik se sastoji u tome da se iskoristi mutabilni operator za zbrajanje i oduzimanje (ie. operatori  +=   i -=) te copy constructor.

Kako to rijesiti?

Prvo, C++ automatski generira copy-constructor, no cisto radi sigurnosti, bolje da mi to rijesimo na ruke. Definirajmo copy constructor:

    Vector(const Vector<Type, Size>& that) {
       for (int i = 0; i < Size; ++i) {
          data[i] = that.data[i];
       }
    }

Nakon toga, definirajmo operator koji mutira this objekt (na primjer +=):

    Vector<Type, Size>& operator+=(const Vector<Type, Size>& that) {
       for (int i = 0; i < Size; ++i)
          data[i] += that[i];
       return *this;
    }

Nakon toga, definirajmo ne-mutirajuci operator zbrajanja (+) koristeci copy constructor i assign-sum operator:

    Vector<Type, Size> operator+(const Vector<Type, Size>& that) const {
       Vector<Type, Size> result(*this);
       result += that;
       return result;
    }

Eto, uz malo promjena, postigli smo puno citljiviji kod, i fokusirali pogreske u aritmetici na samo jednom mjestu (operator+=). Takvom nacinu programiranja uvijek treba teziti - pozivati metode sto je cesce moguce, umjesto kopiranja slicnih dijelova koda.

Primjetite da operator+= pod obavezno vraca referencu na this, dok operator+ bez problema moze biti const metoda, jer ne mutira this objekt.

Hullo,

dan odsustva, pa eto danas cemo odraditi dvije stvari :-)
Prvo, bilo bi fino da mozemo izbuildati ono sto pisemo. Nekako, to je dosta korisno :-D Kao sto je napomenuto u prvom postu, posluzit cemo se odlicnim cmake. Nema smisla drzati tutorial iz CMakea ovdje, pa cemo odraditi to kroz listu koraka koji se moraju poduzeti.
Nulto, treba napraviti osnovni runnable file, tj. file koji ce biti glavni exe naseg tutoriala. Unutar src/main/cpp napravite file 'Tutorial1.cpp', i unutra napisite obicni hello world:
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
    cout << "Hello world!" << endl;
    return 0;
}

Ovaj file je potreban tako da ne moramo u buducnosti mijenjati build skriptu, i odmah srediti build za production i za testove.
Nakon toga:

1. Normalno, instalirati cmake
2. Napraviti file CMakeLists.txt u rootu projekta
3. Iskopirati ovo u CMakeLists.txt
## The minimum version of cmake that we support
cmake_minimum_required(VERSION 2.6)

## Identify the project
project(scenegraph-tutorial)

## Make sure that we run tests with each build
## enable_testing()

## Flags that will be passed as arguments to the compiler
add_definitions(-g -O2 -fsigned-char -freg-struct-return -Wall -W -Wpointer-arith -Wcast-qual)

## Some custom variables
set(MAIN_EXECUTABLE "${CMAKE_CURRENT_SOURCE_DIR}/src/main/cpp/Tutorial1.cpp")
set(TESTSUITE_EXECUTABLE "${CMAKE_CURRENT_SOURCE_DIR}/src/test/cpp/TestSuite.cpp")
file(GLOB_RECURSE SOURCES src/main/cpp/*.cpp)
file(GLOB_RECURSE TEST_SOURCES src/test/cpp/*.cpp)

## Fix lists to exclude main files
list(REMOVE_ITEM SOURCES ${MAIN_EXECUTABLE})
list(REMOVE_ITEM SOURCES ${TESTSUITE_EXECUTABLE})

## Set libs
set(LIBS GL GLU)
set(TEST_LIBS cppunit ${LIBS})

## Target executables
add_executable(scenegraph-tutorial ${MAIN_EXECUTABLE} ${SOURCES})
add_executable(testsuite ${TEST_EXECUTABLE} ${SOURCES} ${TEST_SOURCES})
add_test(testsuite testsuite)

## Linker data
target_link_libraries(scenegraph-tutorial ${LIBS})
target_link_libraries(testsuite cppunit ${TEST_LIBS})

## We specify the directories where are located the include files (include and lib) with the INCLUDE_DIRECTORIES directive
include_directories(src/main/cpp src/main/resources src/test/cpp)

4. Otvoriti direktorij u konzoli i utipkati
cmake .

Korak 4 dovoljno je napraviti samo jednom, nakon (uspjesnog) generiranja Makefileova, 'make' ce se potruditi da pozove cmake i regenerira sve promjene. Svaki IDE se moze konfigurirati da koristi externi build sistem, te je vas IDE potrebno konfigurirati da za Build poziva 'make', a za clean 'make clean'. Takodjer, moguce je pozivati make sa opcijom -j, koja ce vrtiti make na vise coreova, sto je preporucljivo jer dobrano ubrzava buildanje. Dakle, komande bi bile 'make -j' i 'make -j clean'.

Ako ste ovo uspjesno odradili, u project rootu nalazit ce se dva filea, 'scenegraph-tutorial' i 'testsuite'. Jedan pokrece nas hello world (u buducnosti test-aplikaciju za engine) a drugi pokrece test suite.


Kad je to rijeseno, idemo dopuniti nas vektor test, prije svega. U math::VectorTest klasu dodajmo testove za bitne vektorske operacije: duljinu vektora, normalizaciju, dot produkt i cross produkt. O tome se (opet) moze procitati na Wolfram Math, no ukratko:
- duljina vektora se kalkulira uz pomoc pitagorinog poucka
- normalizacija vektora svodi bilo koji vektor na jedinicni vektor, tj. vektor cija je duzina = 1
- dot produkt je operacija koja vraca skalar (float), te kalkulira kosinu izmedju dva vektora
- cross produkt je 'posebna' operacija u tome sto funkcionira iskljucivo na 3D vektorima, te vraca vektor koji je ortogonalan na dva vektora s kojima izvodimo cross

Sad kad znamo ove informacije, krenimo s testovima. Prvo cemo testirati duljinu. Za primjer, uzet cemo 3D vektor {3, 4, 5}, te uz pomoc kalkulatora izracunati duljinu (7.071067812).
Nakon toga, napisimo test koji provjerava da rezultat kalkulacije duljine iznosi upravo taj broj. Nemojte zaboraviti registrirati test u CPPUNIT bloku:
    void TestLength() {
       float values[] = { 3.0F, 4.0F, 5.0F };
       v1.Set(values);
       CPPUNIT_ASSERT_EQUAL(50.0F, v1.LengthSquared());
       const float squareOf50 = 7.071067812F;
       CPPUNIT_ASSERT_EQUAL(squareOf50, v1.Length());
    }

Sad, pokrenite build i provjerite da compiler puca jer nema metode koju pozivamo. Super, dodajmo metodu unutar math::Vector klase:
    float Length() const {
       return -1.0F;
    }

Pokrenimo build, provjerimo da compilira. Nakon toga pokrenite testsuite i provjerite da test puca, jer vrijednost koju ocekujemo nije vrijednost koju vracamo.
Ovaj korak se vjerojatno cini nepotreban, no bitan je zbog toga jer na ovaj nacin testiramo ispravnost samog testa. Neispravan test nije bas koristan :-D
Sad je vrijeme za implementaciju. Negdje pri vrhu filea dodajte
#include <cmath>
a negdje unutar klase:
    float Length() const {
       float lengthSquared = 0;
       for (int i = 0; i < Size; ++i) {
          lengthSquared += (data[i] * data[i]);
       }
       return sqrt(lengthSquared);
    }

Sad, razmislimo da cemo cesto usporedjivati duljine vektora, i tocna duljina nam u tim slucajevima nece biti bitna. Korijen koji vucemo na kraju je beskoristan u tim slucajevima, pa cemo ovu metodu rastaviti na dvije:
    float LengthSquared() const {
       float lengthSquared = 0;
       for (int i = 0; i < Size; ++i) {
          lengthSquared += (data[i] * data[i]);
       }
       return lengthSquared;
    }

    float Length() const {
       return sqrt(LengthSquared());
    }

Tako je bolje. Sad kad mozemo iskalkulirati duljinu, mozemo napraviti normalizaciju. Opet, kalkulator u ruke i izracunajte da vektor {1.0, 1.0, 0.0} ima duljinu 1.414213562, te onda izracunajte da 1.0 / 1.414213562 = 0.707106781. Sa tim brojevima, jednostavno je napisati prvo test:
    void TestNormalize() {
       float values[] = { 1.0F, 1.0F, 0.0F };
       v1.Set(values);

       v1.NormalizeLocal();
       const float lengthOfComponent = 0.707106792F;
       CPPUNIT_ASSERT_EQUAL(lengthOfComponent, v1[0]);
       CPPUNIT_ASSERT_EQUAL(lengthOfComponent, v1[1]);
       CPPUNIT_ASSERT_EQUAL(0.0F, v1[2]);
    }

Nakon toga ponovite sve one korake sa buildanjem i padanjem testa. Nakon toga, dodajmo kod za normalizaciju:
    void NormalizeLocal() {
       float len = Length();
       for (int i = 0; i < Size; ++i) {
          data[i] /= len;
       }
    }

Nazvali smo metodu NormalizeLocal i nije const jer zelimo kroz ime naznaciti da cemo modificirati 'this'.
Dodajmo dot produkt i cross product testove:
    void TestDot() {
       // Cosine of pi/4 should be 0.707106781
       float values[] = { 1.0F, 0.0F, 0.0F };
       float values2[] = { 1.0F, 1.0F, 0.0F };
       v1.Set(values);
       v2.Set(values2);

       v1.NormalizeLocal();
       v2.NormalizeLocal();

       const float cosineOfQuarterPi = 0.707106781;
       CPPUNIT_ASSERT_EQUAL(cosineOfQuarterPi, v1.Dot(v2));
    }

    void TestCross() {
       // Perpendicular to X and Z is Y
       float values[] = { 1.0F, 0.0F, 0.0F };
       float values2[] = { 0.0F, 0.0F, -1.0F };
       v1.Set(values);
       v2.Set(values2);

       v1.NormalizeLocal();
       v2.NormalizeLocal();

       math::Vector3f v3(v1.Cross(v2));
       CPPUNIT_ASSERT_EQUAL(0.0F, v3[0]);
       CPPUNIT_ASSERT_EQUAL(1.0F, v3[1]);
       CPPUNIT_ASSERT_EQUAL(0.0F, v3[2]);
    }

Te dodajmo implementacije:
    float Dot(const Vector<Type, Size>& that) const {
       float cosine = 0.0F;
       for (int i = 0; i < Size; ++i) {
          cosine += data[i] * that.data[i];
       }
       return cosine;
    }

    Vector<Type, 3> Cross(const Vector<Type, 3>& that) const {
       assert(Size == 3); // Works only for 3D vectors :-)

       float resultData[] = {0.0F, 0.0F, 0.0F};
       resultData[0] = ((data[1] * that[2]) - (data[2] * that[1]));
       resultData[1] = ((data[2] * that[0]) - (data[0] * that[2]));
       resultData[2] = ((data[0] * that[1]) - (data[1] * that[0]));
       Vector<Type, 3> result(resultData);
       return result;
    }


I to je to! Nasa Vector klasa je gotova. Onako kao secer na kraju, van klase, ali unutar namespacea, dodajte nesto sintaktickog secera, cisto da se nadje ;-)
typedef Vector<float, 2> Vector2f;
typedef Vector<float, 3> Vector3f;
typedef Vector<float, 4> ColorRGBA;

Ipak je ljepse i jednostavnije pisati Vector3f nego template ;-)


To je to za danas. Sutra cemo ustoliciti Object klasu sa nesto osnovnih funkcionalnosti, po uzoru na moderne OOP jezike.

Za lijencine koji nisu pratili od pocetka, downloadirajte Vector.hpp i VectorTest.hpp.
Cheers!


P.S. Vidim da se topic cita, ali cini se ko da se svi boje spammati. Slobodno pitajte pitanja ili javljajte ako nesto nije jasno.

Naravno! Macro to radi sam - testira floatove do (ako se dobro sjecam) 4 decimale.

Pa, nakon sto uspostavimo scenegraph i neki loader, tako da uopce mozemo dobiti podatke za rendanje, bez beda ;-) Jedna od idejnih znacajki je abstraktni renderer, pa ne vidim razloga zasto ne bi implementirali svoj raytracer umjesto rasterizera :-)

Nego, zbog cega fixed-point brojevi?

Ma to mi nema nikakvog smisla? Floating point ima gresaka u zaokruzivanju iskljucivo ako je renderer napisan tupasto, pa se ocekuje velika preciznost s obje strane tocke, recimo castas zraku od nule prema objektu koji je smjesten negdje na udaljenosti od 10 000 000 000 jedinica, a zelis preciznost na 0.000000001 decimalu. Prvo, tako nesto ne mozes ni vidjeti jer su pikseli puno puno veci, drugo to se ne radi tako, zato imas scenegraph da bi lokalizirao kalkuliacije u maleni segment i spasio greske u dijeljenjima :-)

Trece, nema nacina da sa fixed point brojevima i ostatcima dijeljenja iskalkuliras dijeljenja brze nego uz moderne reprezentacije floating pointova (http://en.wikipedia.org/wiki/IEEE_754-2008). Cak i da nesto tako uspijes (jer recimo, nisi napravio fp unite na FPGA-u), greske u dijeljenjima bi bile monstrouzne, osim u slucajevima da si koristio ogromne brojeve - sto mozes i sa floating pointovima, uz vecu preciznost.

Rauzmijem tvoju zelju da probas nesto originalno, ali floating point se koristi u 3D grafici s razlogom :-) Cheers.

Deus sam sa sobom pričaSvaka čast na impresivnom znanju, žalosno je vidjeti da baš nema ozbiljnih korisnika koji kad vide kod nezaboli ih glava.

Osobno nisam ni ukupno rečenice pročitao, no čim uhvatim vremena budem provjerio kod, pa cu sebi zadati domaci uradak da napišem isit kod ali na neki drugi način ;)

Poslat ću link idući tjedan, mislim da ga imam spremljenog na poslu.

Nisam ja protiv floata, znam da su univerzalniji i precizniji i sve, da moram napraviti nešto zaozbiljno naravno da bih ih koristio, ali svejedno zanima me vidjeti koja su ograničenja fixed pointa...

Svaka čast i izdrži od kraja (relativnog). Odlično objašnjeno.

Svaka čast autore! Svjetski post! Nisan shvatio ništa!

Ovo bi bilo korisno...

Ne. Nikako.

Možemo s dvije strane krenuti.

Ako krenemo s te o Q2 engineu, onda je važno napomenuti da je to prastara stvar. Q2 (ma i Q3) enginei su prastari vrlo specijalizirani BSP enginei, puni hackova, optimizacija i cca. 10x više nerazumljivi od bilo čega modernijeg, a pogotovo nečega što se piše u edukacijske svrhe.

S druge strane, Deus već uvodi ono što je potrebno - dakle, ne izmišlja toplu vodu, već koristi ono što se može i što ima smisla.

Svakako ne, a pogotovo ne Tech.

  Kao što naxeem reče, taj code iz Quake Engine-a (kompletnog, sve do Q4 koji je baziran na DooM 3 Tehnologij) je;

  a) Prestar. Fixni Pipeline + GL, ako ćeš danas učiti svakako se kreće odmah od programbilnih shadera, jer čak ni DX10 više nepodrzava FF Pipeline. Osim toga, tona drugih stvari u tom engineu su stari pola tisućljećja.

  b) Užasno je sam code neuredan; Sve je zbrda zdola, ali na kraju čudno brzo i efikasno na ekranu.

Definitivno što dalje od Quake Engine-a, daleko daleko lakši primjera ima na tržištu. Taj engine je bio namjenjen samo id softwareu i njegovim igrama, a takve igre su koncept soba-tunel-soba-pokupi health, dakle užasno zatvoreni prostori - Korištena BSP tehnologija za optimizaciju takvih slučajeva.

Isto tako i Q1, Q2, Q3, sve je to samo nadograđivani engine tehnologijama koje su u to vrijeme bile aktualne, Q4 je nešto sasvim drugo iako i on vjerovatno daleko kompleksnij nego bilo kakav primjer za početnike.

Taj engine je namjenjen samo id softwareu, i eto tko ima želju da kupi pa ga licencira za svoju igru.

  Pa dobro nemoze se reci da je bio sranje. Bio je vrhunski u svoje vrijeme. Ali to vrijeme je bilo prije 12 godina. Tehnologija se strašno mjenja, a pogotovo kroz 12 godina.

Staro, teško, danas neupotrebljivo.

U svoje vrijeme vrhunski tech.

1) Quake 2 je pisam u c-u 2) nema abstraktin render layer 3) ne koristi shadere 4) ne postoje post processing efekti 5) kod je jako nečtitljiv 6) netko tko može taj kod čitati sigurno mu ne treba tutorijal 7) sve migracije quake 2 svode se na pisanje wraper klasa 8) molim vas nemojte trovati ovaj tutorijal nepotrebnim komentarima

github!

Eh da, skoro sam zaboravio, pa cu zaspamati s doublepostom zbog ovoga:

S R E T A N   N A M   S V I M A   D A N   P R O G R A M E R A !!!!

Hugs & kisses and succesfull compiles, everyone :-)

http://en.wikipedia.org/wiki/Programmers%27_Day