3d Engine - ali za mobilne uređaje!

[Patton]

UVOD U CELU PRICU

Pa ovako. U poslednje vreme imam nesto vise slobodnog vremena, a i javila se neka potreba za ispoljavanje kreativnosti kod mene; stoga sam resio da zapocnem jedan programerski projekat, onako za sebe posle duzeg vremena. Nisam razradio sve detalje, nisam trosio vreme na organizaciju, a i ne gledam daleko u buducnost projekta, niti znam kuda ce me sve ovo odvesti. Resio sam onako da ga zapocnem, pa da vidimo kako ce se razvijati i da li ce imati neki potencijal. Mozda napravim nesto pametno, mozda se smorim posle mesec dana, videcemo, sve je moguce. Uostalom, ovim projektom ne bezim daleko od svog pravog posla, tako da ako nista drugo, usavrsavam se i skupljam nova iskustva.

Dakle, kao sto se iz naslova moze videti, zapoceo sam rad na 3D engine-u. Iskustva iz te oblasti imam, jer sam nesto slicno radio pre 8 godina u asembleru za DOS i malo posle toga u C++ koristeci OpenGL. Ovo sto sad planiram se ipak malo razlikuje od toga. To je 3D engine za "pametne" mobilne telefone. Krajnji cilj mi je naravno, da ga napravim tako da moze lako da se portuje na bilo koju mobilnu platformu; ali otom potom.

Po cemu se mobilni uredjaji razlikuju od desktop masina? Pre svega imaju mnogo slabije procesore i mnogo manje memorije, tako da kod mora biti jako optimizovan. Imaju ekrane mnogo manje rezolucije i ta rezolucija varira od 176x208 (stariji Symbian telefoni) do 320x320 (noviji Palm uredjaji), tako da grafika mora biti optimizovana za sve rezolucije. Nemaju nikakve 3D akceleratore i rad sa bilo kakvim realnim (float) brojevima je jako sporo, tako da sve sto se pise mora se pisati "rucno". Sta znati to rucno? To znaci da koristeci OpenGL, treba vam tacno 13 naredbi da biste dobili 4-ugaoni texturirani poligon u kojem svaki vertex ima svoju boju, pa se na osnovu tih boja i textura drugacije farba. Ako hocete to isto da uradite softverski, pored solidnog znanja matematike, trebace vam i jedno 300 linija koda (po mogucstvu bez bagova). Cemu ovakav mazohizam? Kazem vam, imam viska slobodnog vremena + jedino ako rucno pisete neke stvari, shvaticete kako te stvari zaista rade i gde se primenjuje ta silna matematika koju svi ucimo u skolama i na fakultetima.

Odlucio sam takodje da „dnevnik“ tog projekta vodim na ovom forumu. Mozda se nekom svidi, mozda neko ima neki predlog, sugestiju, mozda ce neko nesto da nauci od mene, mozda cu ja nauciti nesto od nekoga; ako sve propadne i odustanem od svega, imacu barem materijala za knjigu, da je objavim i zaradim koji filer. Vasi komentari su dobrodosli, isto tako i pitanja; sa druge strane, svaki offtopic ce se momentalno brisati.

[Patton]

Posto svako ko se pojavi na ovom forumu sa ovako lepom uvodnom recju, a da pritom, nista nije uradio, biva momentalno proteran i ismejavan naredne dve stranice, ja sam odlucio da odmah i postujem neke stvarcice koje sam radio protekla tri dana

Na vasu veliku zalost, (za sada) postovacu samo screenshotove, jer se radi o programu za mobilne uredjaje, tako da cete morati da mi verujete da ove slike nisam radio u Mayi i posle obradjivao u Photoshopu. Test platforma je Treo u PalmOS verziji. Ekran je rezolucije 320x320 sa 16bit paletom boja (5:6:5). Kolicina memorije je oko 20mb, ali to i nije toliko bitno.

[Patton]

PRVI KORAK – CRTANJE POLIGONA

Dakle pocinjemo… moj prvi korak u ovom projektu... sta je ono sto cini jednu 3d scenu, sta je ono sto mi zapravo vidimo na ekranu? To su poligoni. Svaka scena se sastoji iz objekata, svaki objekat se sastoji iz poligona. Za pocetak, ne interesuje me kako cu organizovati scenu, ne interesuje me kako cu organizovati objekte, ne interesuje me (a i tek treba da naucim) kako cu pomerati kameru kroz scenu; interesuje me samo kako cu nacrtati proizvoljno definisan poligon. Na brzaka sam sklepao par stvari, cisto da bih imao sa cime da radim:

- da mogu da definisem koordinate vertexa nekog 3d objekta
- da mogu da definisem stranice tog objekta (koji vertexi cine koju stranicu)
- da mogu te vertexe da rotiram u prostoru oko sve tri ose
- da mogu te izrotirane vertexe da transformisem u 2d tacke koje cu prikazivati na ekran

Trenutno nije bitno kako ove stvari koje sam do sad uradio rade, a verujem da mogu jos dosta i da se optimizuju; objasnicu ih kada bude bilo vreme za to. Bitno je: da sam dobio te transformisane 2d tacke pomocu kojih cu crtati poligone. Svaki takav poligon se sastoji iz cetiri tacke, a svaka tacka za sada ima:

- X koordinatu na 2d ekranu
- Y koordinatu na 2d ekranu
- BOJA koja se sastoji iz R, G, B komponente i Alfa kanala

Bitna stavka o kojoj treba razmisljati. Na koje sve nacine planiramo da crtamo poligone? Na raspolaganju nemamo azdaju od masine, tako da moramo paziti na performanse. Kakve 3d igre postoje sada za telefone? Maximum koji sam ja video jeste texturirani poligon bez osvetljenja ili eventualno sa nekim laznim osvetljenjem (kao npr. Doom II). Tako da sam (opet) za pocetak odlucio da napravim funkcije za crtanje:

- tackastih poligona svaka tacka poligona predstavljena je... hmm... tackom
(ovo ce se koristiti samo za neka testiranja i debagovanje)

- wireframe poligona gde su tacke poligona spojene obicnim linijama
http://en.wikipedia.org/wiki/Wire_frame_model

- flatshade poligona gde je ceo poligon obojen jednom bojom
http://en.wikipedia.org/wiki/Shading (slika pri dnu stranice)

- gouraud shade poligona gde svaka tacka ima odredjenu boju i interpoliranjem i
mesanjem tih boja dobija se poligon koji nije obojen konstantnom bojom
http://en.wikipedia.org/wiki/Gouraud_shading

- texture mapped poligona kod kojih se slika lepi na stanicu
http://en.wikipedia.org/wiki/Texture_mapping

Uradio sam prva cetiri nacina, pre nego sto se bacim na ovaj poslednji (najtezi), hajde prvo da vidimo kakvi su rezultati. Kao primer koristim najprostiji moguci objekat – kocku. Kako vam se cini

[Andross]

Pa... Kockasto
Ne znam koliko je tesko uraditi kocku na mobile uredjaju, ali verovatno je to dobro sto si do sada postigao. Samo tako nastavi!!!

[Stevvan]

Ako se ta kocka rotira/pomera da li bi mogao da kazes koliki je fps. Mislim da bi to dalo najbolju sliku koliko je engine trenutno napredovao.

[EclipsE]

kad zavrsish dajesh source?

[Patton]

@Andross
Ja sam samo primera radi uzeo kocku dok ne napravim sve shading funkcije za poligone. U ovaj program sto imam sad mozes ubaciti bilo koji objekat, problem je samo sto rucno moras da mu definises tacke i stranice, pa je to malo zamarajuce. Kasnije cu verovatno napraviti funkcije za importovanje objekata. Evo kako je definisana ta kocka:

vertex_Assign(&vertex[0], -UNIT,-UNIT,-UNIT, 0, 0, 255, 0);
vertex_Assign(&vertex[1],  UNIT,-UNIT,-UNIT, 0, 0, 96, 0);
vertex_Assign(&vertex[2], -UNIT, UNIT,-UNIT, 0, 0, 160, 0);
vertex_Assign(&vertex[3],  UNIT, UNIT,-UNIT, 0, 0, 255, 0);
vertex_Assign(&vertex[4], -UNIT,-UNIT, UNIT, 0, 0, 0, 0);
vertex_Assign(&vertex[5],  UNIT,-UNIT, UNIT, 0, 0, 96, 0);
vertex_Assign(&vertex[6], -UNIT, UNIT, UNIT, 0, 0, 160, 0);
vertex_Assign(&vertex[7],  UNIT, UNIT, UNIT, 0, 0, 255, 0);
face_Assign(&faces[0], 0, 1, 3, 2, 0, 0, 255, 0);
face_Assign(&faces[1], 1, 5, 7, 3, 0, 0, 224, 0);
face_Assign(&faces[2], 4, 6, 7, 5, 0, 0, 192, 0);
face_Assign(&faces[3], 0, 2, 6, 4, 0, 0, 160, 0);
face_Assign(&faces[4], 0, 4, 5, 1, 0, 0, 128, 0);
face_Assign(&faces[5], 2, 3, 7, 6, 0, 0, 96, 0);

Ovaj UNIT mi je neka proizvoljna jedinica za pocetak.
Svaki vertex dobija parametre: x, y, z, r, g, b, a.
Svaka stranica dobija parametre: vertex1, vertex2, vertex3, vertex4, r, g, b, a.

@Stevvan
Da, kocka se naravno rotira, na slikama sam samo fixirao uglove kako bi se najbolje video dosadasnji rad. Ovo za sada ide jaaako sporo... gouraud shading ide ispod 10fps sigurno; raduje me samo sto ima dosta prostora za optimizaciju:

1. U svakom frejmu ja brisem ceo ekran - nepotrebno, jer ako prikazujem samo jedan objekat na sceni, treba naci tacku koja je skroz gore i tacku skroz dole i brisati ekran samo izmedju tih tacaka.
2. Koristim 16bit mod ekrana, to znaci da je i pisanje po ekranu mnogo sporije i da su kalkulacije za boje utrostrucene (r,g,b). Svaka brza 3d igra radi u 8bit modu sa indexiranom paletom. Takva igra ima na raspolaganju mnooogo manje boja, ali se i kalkulacije ubrzaju tri puta.
3. Planiram da koristim sve prednosti svake platforme. Objasnicu prvo kako radi Palm. Pre su procesori u tim uredjajima bili Motorola 68K. Noviji uredjaji imaju ARM procesore, ali da bi zadrzali kompatibilnost sa starim aplikacijama, ti uredjaji sad emuliraju M68K; tako da svaka aplikacija radi mnogo sporije, jer se emulira. Postoji nacin da se pise ARM kod i to nije nikakav problem. Tako da trenutno za Palm... 8bit ekran + ARM je moj kec u rukavu

@EclipsE
Naravno da NE
Svaki put kad zavrsim neki korak dajem objasnjenje kako se to radi uz slike i pseudo kod. Pod uslovom da vas zanima kako su nekada davno radjene 3d igre

[MG-RAY]

Pa naravno da nas zanima...makar mene

Hajde "baci" trenutni .prc, hocu da vidim kako izgleda (Pod uslovom da je PalmOS4, jel... )

btw. da li ovo znaci da si napustio projekat tvoje davno najavljene igre ?

[Patton]

MG-RAY kaže:

Pa naravno da nas zanima...makar mene

OK, objasnicu kako crtam poligone, cim mi proradi texture mapping. Trenutno imam nekih problema sa time

MG-RAY kaže:

Hajde "baci" trenutni .prc, hocu da vidim kako izgleda (Pod uslovom da je PalmOS4, jel... )

Ovo je za PalmOS5 i treba ti uredjaj sa ekranom 320x320x16 da bi radilo. Mozda bude neki .prc kad malo odmaknem sa projektom.

MG-RAY kaže:

btw. da li ovo znaci da si napustio projekat tvoje davno najavljene igre ?

Uf, nazalost nisam imao vremena cak ni da ga zapocnem. Btw, hteo sam da uradim remake neke stare igre u OpenGL-u. Medjutim suvise je to veliki i komplexan projekat, da bih mogao da izdvojim vreme za njega pored sadasnjeg posla. Zato sam zapoceo ovaj projekat, koji je mnogo prostiji, ali meni barem, i mnogo zanimljiviji.

[bobi]

Iako se ne razumem u programiranje... bla...bla...

Samo ću napomenuti da je po meni mnogo bolje da se radi flatshade algoritmom, negoli gouraud algoritmom. Zašto? Pa zato što flat shade algoritam ljudske oči kapiraju mnogo bolje nego gouraud. Dok flat shade sa svojim jednobojno obojenim svetlećim poligonima može da podseća i na crtani film (što je super iskoristiti za neku avanturu npr.), gouraud svojim navodnim senčenjem i oponašenjem fizičkih atributa svetlosti deluje jako CG. Senčenjem u ovom slučaju ništa ne dobijamo, sem da poligoni deluju ružnije, t.j. stiče se utisak u oku posmatrača da nešto nije u redu sa svetlom i kako ono pada na objekte.
Dakle, po meni, daleko je bolje raditi sa stilizovanom crtanom varijantom u kojoj će svaki poligon imati svoju boju, nego pribegavati polu-četvrt rešenjima, koje samo mogu da izgledaju, ponavljam, computer generated.
Uostalom, i ja kad sam igrao prvi alien breed 3D na mojoj Amigi 1200, bez trunke razmišljanja sam odmah birao flat shade tehniku senčenja

[EclipsE]

Lepse nije ali treba mu manje vremena za racunanje u odnosu na g shading...

[MG-RAY]

Pa... sada sami odredite sta je lepse

(per vertex shading, no tex.)

Naravno, imao sam priliku da probam par igara za PalmOS za MDBVX CPU, znaci na 33MHZ za 5.1MIPS... Jedna bez teksturiranja sa flat shadingom, poprilicno brzo radi, druga sa teksturiranjem, takodje bez osvetljenja...pa, vuce se.

[EclipsE]

stavi i jedan per pixel

[MG-RAY]

EclipsE kaže:

stavi i jedan per pixel

Mislim da to jednostavno nema smisla

evo iste stvari sa teksturom, ponovo sencenje po vertexu, jer ovo drugo u ovom slucaju, rekoh, nema smisla

no, jedna je stvar odraditi ovo u shaderu, potpuno druga napisati ceo algoritam za sencenje od 0 (mada se i ovde to radi rucno ).

[Patton]

Evo mene posle par dana. U velikoj sam guzvi na poslu, tako da ne stizem puno da radim na projektu, jer obicno dodjem mrtav kuci

Gouraud shading se moze koristiti za sencenje objekata na ekranu. Recimo imate kocku, pa uradite jedan texture mapping, a onda primenite gouraud shading na alfa kanal teksture u odnosu na poziciju svetla i dobijate time fenomenalnu osencenu kocku. Medjutim, to bi najverovatnije islo veoma sporo i pitanje je da li cu raditi takve stvari; bitno mi je da sam uradio mogucnost i za tako nesto, pa posle svih hardcore optimizacija koje planiram da uradim, ako ostane nesto cpu time-a i gouraud shading ce naci svoju primenu

I dalje me muci texture mapper. Napravio sam mali napredak u odnosu na onu vikend verziju engine-a, ali opet se desava... hmmm... kao da u proracunima dobijem neki offset koji "izleti" van texture, pa mi upise neku brlju na ekran. Da ne bude sada da postujem samo svoje uspehe, evo sada postujem i nesto sto ne radi bas kako treba. Dobro izcrtana textura se vidi na donjoj stranici, dok je gornja sacuvaj boze

[bobi]

Verovatno ti ovo ništa neće biti od koristi...

Elem, to se dešava ponekad u 3ds maxu i rešenje je promeniti offset ili tileing za trunku... znači sa 0.0 na 0.001
Uvek sam mislio da je to bug do maxa.

[Patton]

Konacno sam uspeo!!!

Juce sam pokusavao svasta, trazio gresku u texturemap rutini, ali nije mi se dalo da je nateram da proradi. Danas posle posla sam se bas zainatio. Seo oko 19h da radim i posle dva sata mucenja resio da ipak otvorim knjigu i da pokusam da prokljuvim sta to radim pogresno

Imam dobre tutorijale, dobro sam naucio teoriju iz njih, i cisto onako iz zezanja resio da umesto cetvorougaonih poligona pokusam da nacrtam texturirani trougao prateci neke primere iz jednog od tih tutorijala. Woalaa, upornost je urodila plodom. Na mom ekranu je oko 1:30am zaigrao jedan trougao sa polovinom texture. Da bi mapirali celu texturu, potrebna su naravno dva trougla koja cine kvadrat. Nisam 100% siguran, ali nekako mi se cini da crtanje 2 trougla ide brze nego crtanje jednog cetvorougla

Metoda kojom se koristim zove se linear texture mapping i ustvari je laznjak, jer taj metod podrazumeva da sve tacke poligona stoje uvek poravnate po Z osi (a to se desava skoro nikad). Ovom metodom se dobija malo "lelujanje" texture unutar poligona (vidi sliku u sredini; textura izgleda malo razvuceno), ali neverovatan speedup sto se tice samih performansi. Kako se to lelujanje moze zamaskirati? Prvo, koriscenjem textura kod kojih ce se to manje primetiti. Drugo, trougao koji crtamo mozemo podeliti na dva manja trougla i time radimo dupli posao, ali ce i rezultat izgledati vise nego duplo lepse. Trece, koriscenjem perspective texture mapping-a, kod koga se za svaku liniju u trouglu racuna Z vrednost izmedju tacaka koje se spajaju. Ubacicu i ovaj metod, ali mislim da ce biti isuvise spor.

Kod je totalno u haosu od debagovanja i isprobavanja svega i svacega. Morace da padne jedno generalno oranje i da se sve sredi sada kada je konacno proradilo. Planiram da uradim i prvi talas optimizacija i bolju organizaciju podataka. Uradicu speed test i predpostavljam da cu preci na trouglove, sto znaci prepravka flat i gouraud shader-a. Jedva cekam da ponovo prionem na posao. Sutra poslepodne i za vikend nisam tu, tako da ce to pricekati sve ponedeljak ili mozda utorak

[MG-RAY]

I... kako napreduje projekat ?

[Patton]

Hvala MG-RAY sto si me podsetio da treba malo da updateujem ovu temu

Vidim nisam postovao citavih 8 dana, od kako mi je proradio texture mapper. Nisam imao puno vremena da radim na projektu, od silnog posla. Nikada nemojte govoriti nadleznima na poslu kog datuma idete na odmor, jer ce vas do tog datuma muciti kao roba. Ja se zahebo, pa sam mojima rekao mesec i po dana unapred

Vratio sam se sa "oranja"; kod sada izgleda mnogo lepse i dodao sam mnostvo komentara. Glavna stvar jeste da sam presao na trouglove, umesto 4-ugaonih poligona koje sam koristio prvobitno. Cini mi se kao da se renderuju brze pa cu za sada ostaviti tako. Ubacio sam i klipovanje poligona, tj. da se ceo poligon pravilno izcrtava iako su mu jedna ili dve tacke van ekrana. Uradio sam i bolju organizaciju podataka, strukture trouglova i njihovih stranica, mada verovatno cu jos dosta raditi na tome. Trenutno me muce dve stvari: definisanje objekata je mukotrpan posao (jos uvek nisam napravio nacin da se nekako importuju ili lakse definisu), rutina za texture mapping ima neki bag koji je bas uocljiv kada se poligon uvelica preko citavog ekrana, a sto je najgore taj bag se ne pojavljuje uvek, vec samo kod odredjenih uglova kada se rotira poligon. Deluje bas kao zeznuta stvar, tako da sam i to ostavio po strani za sada (hej barem se prepoznaje textura na njemu)

Pre nego sto uradim bolji sistem za definisanje objekata, pre toga bih zeleo da zapocnem igranje sa kamerom. Eh da mi je sada OpenGL, resio bih to jednom funkcijom... ovako, moram opet malo da otvorim tutorijale i knjigu iz matematike kako bih savladao ovaj malo veci korak.

[MG-RAY]

Ovde ima nesto o textrure mappingu, radjeno je za Javu, ali princip je isti, zar ne...