´ vilag ´ tarol ´ asa ´ - kerd ´ esek ´ Virtualis
´ ıtog ´ epes ´ Szam´ Grafika
´ Gergely Klar
[email protected] ¨ os ¨ Lorand ´ ´ Eotv Tudomanyegyetem Informatikai Kar
´ Hol taruljuk az adatokat? Mem. vagy HDD? ´ ´ vagy szerkesztes? ´ Mire optimalizalunk? Rajzolas ´ ´ ˝ ´ vagy Milyen koordinata-rendszerben taroljuk oket? Vilag modell kr?
˝ ´ ev ´ 2010/2011. oszi fel
´ asa ´ Geometria ”brute force” tarol
Legyenek a primit´ıveink poligonok. ´ es ´ minden poligont tartsuk ny´ılvan ´ az Legyunk ¨ lustak, ¨ ´ osszes csucs ´ aval. Poligonokkal kapcsolatos feladatok:
´ as ´ tarol ´ as ´ transzformal ´ agi ´ lekerdez ´ ´ szomszeds esek
´ asa ´ Geometria ”brute force” tarol
struct float float float };
triangle { x1 , y1 , z1 ; x2 , y2 , z2 ; x3 , y3 , z3 ;
´ as ´ elemzese ´ A ”brute force” tarol
´ as: ´ ha vannak poligonoknak koz ¨ os ¨ csucsai, Tarol akkor ´ ¨ ¨ taroljuk ´ ´ ezeket tobbsz or – feleslegesen Ñ nem tul ´ jo. ´ as: ´ a koz ¨ os ¨ csucsokra Transzformal annyiszor fogjuk el ´ ´ ´ okat, ´ ´ vegezni a transzformaci ahanyszor szerepelnek Ñ ´ nem hatekony. ´ ´ ´ Lekerdez esek: fogalmunk sincs, ki kinek a szomszedja, ¨ ´ as ´ aval ´ ´ csak az osszes csucs tudunk eredmenyre jutni ´ bejar ´ Ñ katasztrofa.
Index buffer-ek
¨ ´ Alapotlet: taroljunk minden csucsot egyszer, egy nagy ´ ¨ os ¨ tombben! ¨ koz
¨ ´ A poligonok csak hivatkozzanak a csucsok tombj enek ´ elemeire.
Ez az index buffer. ´ Minden GPU tamogatja.
˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni.
Index buffer-ek
´ Pelda
struct triangle { unsigned i n t a , b , c ; }; s t r u c t vec3 { float x,y,z; }; s t d : : v e c t o r
i n d e x B u f f e r ;
´ ˝ all ´ o´ racsot! ´ Vegyunk ol ¨ egy N N db negyzetb ´ ´ ul: ´ Merete index buffer nelk egyzet, N N ¨ 4 csucs/n ´ ´ negyzet: 4N 2 . ´ ¨ Merete index buffer-rel: osszesen pN 1q pN 1q csucs: ´ pN 1q2 N 2 2N 1. 4N 2 vs. N 2
2N
1
¡N 2 2N 1 0 ¡ 3N 2 2N N ¡1, ha N P Z
4N 2
1
´ Pelda – folyt.
Pl. ha N 10 ´ ´ ul: ´ ´ Merete index buffer nelk tarolunk es ¨ 400 csucsot ´ ´ transzformalunk
´ artya, ´ ´ nem gyujtenek Minden videok amit meg a muzeumok ˝ ´ ´ tamogatja az index buffer-eket.
´ ´ ´ Merete index buffer-rel: 121 csucsot tarolunk es ´ ´ transzformalunk
¨ ´ A csucspontok tombje (vertex buffer) nem csak pozicokat ´ ´ ´ akat, ´ tartalmaz, hanem normalvektorokat, textura-koordin at ´ ´ meg ´ sok mast. ´ es
´ a vertex buffer-ra mindezekre egyutt Egy hivatkozas ¨ hivatkozik.
¨ mint egyetlen negyzet ´ ´ megeri. ´ Ha tobb unk ¨ van, mar
´ Kocka problema
Index buffer-ek GPU-n
´ rakunk ossze ¨ ´ ¨ ˝ akkor egy Ha egy kockat haromsz ogekb ol, ´ o˝ csucs ´ ´ ¨ sarokban lev max. hat haromsz ognek ´ min. harom, a csucsa. ´ ´ lenne 8 csucsot ´ Index buffer-rel eleg ny´ılvantartani. ´ ´ ´ Mi lesz a normalisokkal? Hogy eles sarkai legyenek a ´ ´ ˝ kockanak a normalisoknak merolegesnek kell lennie a lapokra! ´ kul ¨ meg kell adni a csucsokat: ¨ Oldalankent osszesen ¨ on ´ 3 8 csucs ´ kerul ¨ az vertex buffer-ba.
´ Kocka problema
´ as ´ elemzese ´ Az Index buffer-es tarol
´ agi ´ viszonyok Szomszeds
´ as: ´ alt. ´ hatekony. ´ Tarol ´ as: ´ hatekony. ´ Transzformal
´ ´ ¨ os ¨ csucsokat ´ tudunk, de igazab ´ ol ´ Lekerdez esek: koz mar ´ ´ mindig fogalmunk sincs. meg
´ ´ adatszerkezet Szarnyasel
´ ´ ´ ´ Neha kellenek a szomszedok, pl. felulet-feolszt asokn al. ¨ ´ ıthato´ mi, minek a Ismertek a csucsok ñ szam´ ´ ´ szomszedja.
˝ ´ u´ poligon talalkozhat ´ Egy csucsban tetszoleges szam ñ ´ ´ dinamikus adatszerkezet kene. ´ Szarnyas´ ´ (winged-edge) adatszerkezet! Jobb megoldas: el
´ adatai Egyetlen el
´ el
a ´ ulet Hatarfel ¨ le´ıro´ (B-rep) szerkezet. ´ ´ ol ´ taroljuk ´ Az elek szempontjab a feluletet. ¨ ´ ´ u´ adat tartozik. Minden elhez fix szam ´ evel ´ ¨ ´ ´ Seg´ıtseg gyorsan korbe lehet jarni egy poligon eleit, ¨ ´ kozben megkapva minden szomszedot.
csucs ´ ´ start veg B A
lap bal jobb 0 1
balra ˝ o˝ kov. ¨ eloz c b
jobbra ˝ o˝ kov. ¨ eloz d e
´ tabl ´ azatok ´ Egyeb
´ aja ´ Csucsok tabl ´
csucs ´ ID ´ indulo´ el ´ csucsb ol ´
´ ´ Pelda: tetraeder
´ aja ´ Lapok tabl
lap ID
´ lap egy ele
Shirley, Fundamentals of Computer Graphics
¨ ´ egy lapra Pl.: Osszes szomszed
d e f a l l N e i g h b o u r s ( face , edges , v e r t i c e s , f a c e s ) : startEdge = faces [ face ] edge = s t a r t E d g e i f edges [ s t a r t E d g e ] . f a c e L e f t == f a c e : w h i l e edges [ edge ] . s u c c L e f t ! = s t a r t E d g e : p r i n t edges [ edge ] . f a c e R i g h t edge = edges [ edge ] . s u c c L e f t else : w h i l e edges [ edge ] . s u c c R i g h t ! = s t a r t E d g e : p r i n t edges [ edge ] . f a c e L e f t edge = edges [ edge ] . s u c c R i g h t
¨ ´ Pl.: Osszes lap egy csucsb ol ´
d e f a l l F a c e s ( v e r t e x , edges , v e r t i c e s , f a c e s ) : startEdge = v e r t i c e s [ vertex ] edge = s t a r t E d g e done = False w h i l e n o t done : i f edges [ edge ] . v e r t S t a r t == v e r t e x : p r i n t edges [ edge ] . f a c e L e f t edge = edges [ edge ] . p r e d L e f t else : p r i n t edges [ edge ] . f a c e R i g h t edge = edges [ edge ] . p r e d R i g h t
Hierarchikus adatszerkezetek
´ benne Vilag,
Objektumok, ami ˝ allnak, ´ Primit´ıvekbol amiket
´ Pontok hataroznak meg. !
´ af ´ – motivaci ´ o´ 1. Sz´ıntergr
´ ´ Minden ”szint” a hozzatartoz o´ tulajdonsagokat tartja ´ ny´ılvan. Objektum
Primit´ıv
´ nev, ´ transzformaci ´ o, ´ modellezesi befoglalo´ doboz, stb. ´ primit´ıvre jellemzo˝ tulajdonsagok
Pont
´ ak ´ koordinat
´ vagyok ott van a karom is. (Jobb esetben...) Ahol en ´ erben) ´ Ha mozgatom a karom, elmozdulnak (vilagt az ujjaim is. ¨ Tudom ugy se a karom, ´ mozgatni az ujjaimat, hogy kozben ´ nem mozdulok el. se en
´ af ´ – motivaci ´ o´ 2. Sz´ıntergr
Ha mozog egy bicikli, mozognak vele a kerekei meg a ´ kormanya is.
´ ¨ forgatni, es ´ forgatja az elso˝ kereket. A kormanyt lehet kul ¨ on ´ kerek ´ tud forogni a tengelye kor ¨ ul, ´ ul A ket ¨ anelk ¨ hogy a ´ biciklit forgatni kene.
´ af ´ Sz´ıntergr
´ ıtott, kormentes ¨ ´ (DAG). Irany´ graf ´ ( vilag) ´ osszes ¨ ´ tartalmazza. A sz´ınter elemet ´ ol ¨ erendelts ´ ´ viszonyaik szerint Az egyes elemek ala-/f egi ´ ´ kapcsolodnak egymashoz. ˝ ahonnan kiindul az el ´ Szul ¨ o˝ vagy os: ´ Gyerek: ahova mutat az el ´ ¨ okl ¨ odnek ˝ A szul or a gyerekre, amiket a ¨ o˝ tulajdonsagai ´ ok), ´ gyerek pontos´ıthat (pl. transzformaci vagy felul´ ¨ ırhat (pl. sz´ınek)
´ Csomopontok
´ egy csomopontja ´ A graf (csucsa, node-ja) lehet ´
geometria,
´ o, ´ transzformaci ˝ anyagjellemzok,
´ ´ fenyforr as,
kamera.
´ ´ Csomopontok tulajdonsagai
´ ´ Csomopontok tulajdonsagai
Geometria
´ ´ ˝ ´ Pl. A rendszer altal tamogatott tetszoleges modell le´ıras. Mesh. ´ ´ ent ´ szerepel. A grafban levelk
´ o´ Transzformaci
´ os ´ matrix. ´ Gyak. 4 4-es transzformaci ´ os ´ csomopont ´ Az uj nem felul´ ´ transzformaci ¨ ırja a ˝ oket, ˝ megeloz hanem azokkal egyutt ¨ hat.
˝ Anyagjellemzok
´ ´ Fenyforr as
´ ´ stb. Sz´ınek, optikai tulajdonsagok, textur ´ ak, ´ es: ´ hogyan abr ´ azoljuk, ´ ¨ Nyitott kerd ha egy modellunk ¨ tobb ´ is hasznal? ´ textur ´ at
´ iranya, ´ Pozicioja, t´ıpusa, sz´ıne, stb. ´ Levele a grafnak.
Kamera
´ nezeti ´ ´ ´ osz ´ oge, ¨ Poz´ıcioja, iranya, lat stb. ´ Levele a grafnak.
´ af ´ a gyakorlatban Sz´ıntergr
´ af ´ OGRE-ben Sz´ıntergr
´ hasznal ´ valamilyen Minden komolyabb 3D alakalmazas ´ ´ szintergrafot. ´ ak: ´ Peld
Maya, Java3D OpenSceneGraph OGRE
´ anos ´ ´ amihez az aktualis ´ Ogre::SceneNode: altal osztaly, elemeket hozza´ lehet csatolni az Ogre::MovableObject ´ osztalyon keresztul. ¨ ´ Tulajdonsagai:
Ogre::MovableObject
Bounding box ´ osszes´ ¨ poz´ıcio´ es ıtett poz´ıcio´ ´ ora ´ hasonloan ´ orientaci ´ ´ meretez es ˝ ´ oi ´ adat tetszoleges felhasznal
Ogre::MovableObject
´ Tulajdonsagok:
´ bounding box Sajat Rejtett vagy sem? ´ ´ Vethet arny ekot? ´ ´ Milyen fenyek tartoznak hozza?
´ okat ´ Transformaci nem tartalmaz!
Ogre::Entity
Egy kirajzolhato´ objektum!
´ se nem az Se nem maga az objektum geometriaja, ˝ anyagjellemzoi. ¨ objektumok tarolj ´ ak, ´ ez az osztaly ´ csak Ezeket kul ¨ on ´ hivatkozik rajuk.
´ afot ´ erdemes ´ ´ Valamilyen sz´ıntergr implementalni. ´ alasztja ´ ´ a format ´ es ´ a megjelenest. ´ Szetv az elhelyezest, ˝ e´ teszi az egymashoz ´ ´ ´ Lehetov kepesti relat´ıv elhelyezest. ˝ kell tartani, hogy milyen szintig erdemes ´ DE, szem elott elbonyol´ıtani.
´ meg ´ sok mas ´ objektum. ...es ´ Tanulsag:
Geometria: Ogre::Mesh ˝ Ogre::Material Anyagjellemzok:
´ af ´ osszefoglal ¨ Sz´ıntergr o´
´ af ´ OGRE-ben Sz´ıntergr
´ osztaly, ´ mindegyik csak a maga Rengeteg specializalt ´ feladataval foglalkozik. ¨ helyen is fel lehet hasznalni ´ (Mesh, Material), Amit tobb ¨ ¨ letrehozni. ´ azt nem kell feleslegesen tobbsz or ¨ os ¨ tulajdonsagok ´ Ahol koz vannak, azok magasabb szinten ¨ vannak osszefogva.
CSG modell
¨ or ¨ test Constructive solid geometry: konstrukt´ıv tom geometria
A modellunket = primit´ıvek + muveletek ¨ ˝ ´ ´ ´ kupok, Primit´ıvek: teglatestek, hasabok, hengerek, gul ´ ak, ´ ¨ ¨ gomb ok.
´ kul ¨ ´ metszet. Muveletek: boolean muveletek, unio, eg, ˝ ˝ ¨ onbs
CSG fa
¨ ´ Kul eg ¨ onbs
Captain Sprite, en.wikipedia
Captain Sprite, en.wikipedia
Unio´
Metszet
Captain Sprite, en.wikipedia
´ ´ A muveletek eredmenyein ujabb muvelet hajthato´ vege. ˝ ´ ˝
object = primitive
object = object operation object ´ faval ´ ´ le´ırhato! ´ Binaris jol
Belso˝ csucsok: muveletek ´ ˝
Levelek: primit´ıvek ¨ er: ´ vegleges ´ Gyok objektum
´ CSG modellek megjelen´ıtese
CSG fa
Zottie, wikipedia
´ kepszint ´ ´ ´ kell. Inkrementalis ezis: tesszelalni ´ ovet ¨ es: ´ specialis ´ sugar/model ´ ´ Sugark metszespont ´ ıtas ´ Ñ CSG-fa bejar ´ asa. ´ szam´
´ CSG modellek metszese
´ CSG modellek metszese
´ triv., metszespontok: ´ ´ p t2 ~v Level: p t1 ~v es ´ pp t1 ~v , p t2 ~v q szakaszon a primit´ıv A sugar ´ belsejeben halad. ¨ ´ ol: ˝ t1 ¤ . . . ¤ tn , eleg ´ ezeket vizsgalnunk. ´ Osszes levelb
´ ´ Szakasz-listakat fogunk ny´ılvantartani.
˝ szarmaz ´ ´ Belso˝ csucsok: a gyerekektol o´ szakasz-listakra is ´ ´ vegrehajtjuk a muveletet ˝
Y
X z
¨ ´ o˝ szakaszokat egyes´ıtjuk, ¨ ´ Ossze er hozzavessz uk ¨ kul ¨ onben ¨ ´ a listahoz. ´ ıtjuk a szakaszok metszeteit. Kiszam´ ´ ol. ´ Kivonjunk a szakaszokat egymasb
¨ erben: ´ ´ ek ´ u˝ pont lesz a Gyok a legkisebb pozit´ıv t ert ¨ ´ szemhez legkozelebbi metszes. ´ ´ ´ Ha a metszesek szama paros: k´ıvul ¨ vagyunk az objektumon, ´ ´ ha paratlan, akkor a belsejeben.
