´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ ıtog ´ epes ´ Szam´ Grafika ´ Gergely Klar
[email protected] ¨ os ¨ Lorand ´ ´ Eotv Tudomanyegyetem Informatikai Kar
´ ev ´ 2010/2011. tavaszi fel
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
Tartalom
1
´ vilag ´ tarol ´ asa ´ Virtualis
2
´ asa ´ Geometria tarol
3
Hierarchikus adatszerkezetek
4
CSG modellek, CSG fa
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ vilag ´ tarol ´ asa ´ - kerd ´ esek ´ Virtualis
´ Hol taruljuk az adatokat? Mem. vagy HDD? ´ ´ vagy szerkesztes? ´ Mire optimalizalunk? Rajzolas ´ ´ ˝ ´ vagy Milyen koordinata-rendszerben taroljuk oket? Vilag modell kr?
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ vilag ´ tarol ´ asa ´ - kerd ´ esek ´ Virtualis
´ Hol taruljuk az adatokat? Mem. vagy HDD? ´ ´ vagy szerkesztes? ´ Mire optimalizalunk? Rajzolas ´ ´ ˝ ´ vagy Milyen koordinata-rendszerben taroljuk oket? Vilag modell kr?
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ vilag ´ tarol ´ asa ´ - kerd ´ esek ´ Virtualis
´ Hol taruljuk az adatokat? Mem. vagy HDD? ´ ´ vagy szerkesztes? ´ Mire optimalizalunk? Rajzolas ´ ´ ˝ ´ vagy Milyen koordinata-rendszerben taroljuk oket? Vilag modell kr?
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
Tartalom
1
´ vilag ´ tarol ´ asa ´ Virtualis
2
´ asa ´ Geometria tarol ´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
3
Hierarchikus adatszerkezetek
4
CSG modellek, CSG fa
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ asa ´ Geometria ”brute force” tarol
struct float float float };
triangle { x1 , y1 , z1 ; x2 , y2 , z2 ; x3 , y3 , z3 ;
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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. ˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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. ˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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. ˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ 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. ˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
Index buffer-ek
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 ;
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda ´ ˝ all ´ o´ racsot! ´ Vegyunk ol ¨ egy N N db negyzetb ´ ´ ul: ´ Merete index buffer nelk egyzet, N N ¨ 4 csucs/n ´ 2 ´ negyzet: 4N . ´ ¨ 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
http://cg.elte.hu
˝ as ´ 9. eload
1
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda ´ ˝ all ´ o´ racsot! ´ Vegyunk ol ¨ egy N N db negyzetb ´ ´ ul: ´ Merete index buffer nelk egyzet, N N ¨ 4 csucs/n ´ 2 ´ negyzet: 4N . ´ ¨ 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
http://cg.elte.hu
˝ as ´ 9. eload
1
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda ´ ˝ all ´ o´ racsot! ´ Vegyunk ol ¨ egy N N db negyzetb ´ ´ ul: ´ Merete index buffer nelk egyzet, N N ¨ 4 csucs/n ´ 2 ´ negyzet: 4N . ´ ¨ 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
http://cg.elte.hu
˝ as ´ 9. eload
1
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda ´ ˝ all ´ o´ racsot! ´ Vegyunk ol ¨ egy N N db negyzetb ´ ´ ul: ´ Merete index buffer nelk egyzet, N N ¨ 4 csucs/n ´ 2 ´ negyzet: 4N . ´ ¨ 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
http://cg.elte.hu
˝ as ´ 9. eload
1
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda – folyt.
¨ mint egyetlen negyzet ´ ´ megeri. ´ Ha tobb unk ¨ van, mar
Pl. ha N 10 ´ ´ ul: ´ ´ Merete index buffer nelk tarolunk es ¨ 400 csucsot ´ ´ transzformalunk ´ ´ ´ Merete index buffer-rel: 121 csucsot tarolunk es ´ ´ transzformalunk
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Pelda – folyt.
¨ mint egyetlen negyzet ´ ´ megeri. ´ Ha tobb unk ¨ van, mar
Pl. ha N 10 ´ ´ ul: ´ ´ Merete index buffer nelk tarolunk es ¨ 400 csucsot ´ ´ transzformalunk ´ ´ ´ Merete index buffer-rel: 121 csucsot tarolunk es ´ ´ transzformalunk
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
Index buffer-ek GPU-n
´ artya, ´ ´ nem gyujtenek Minden videok amit meg a muzeumok ˝ ´ ´ tamogatja az index buffer-eket. ¨ ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
Index buffer-ek GPU-n
´ artya, ´ ´ nem gyujtenek Minden videok amit meg a muzeumok ˝ ´ ´ tamogatja az index buffer-eket. ¨ ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
Index buffer-ek GPU-n
´ artya, ´ ´ nem gyujtenek Minden videok amit meg a muzeumok ˝ ´ ´ tamogatja az index buffer-eket. ¨ ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Kocka problema
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Kocka problema
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Kocka problema
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Kocka problema
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ Kocka problema
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ as ´ elemzese ´ Az Index buffer-es tarol
´ as: ´ alt. ´ hatekony. ´ Tarol ´ as: ´ hatekony. ´ Transzformal ´ ´ ¨ os ¨ csucsokat ´ tudunk, de igazab ´ ol ´ Lekerdez esek: koz mar ´ ´ mindig fogalmunk sincs. meg
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ as ´ elemzese ´ Az Index buffer-es tarol
´ as: ´ alt. ´ hatekony. ´ Tarol ´ as: ´ hatekony. ´ Transzformal ´ ´ ¨ os ¨ csucsokat ´ tudunk, de igazab ´ ol ´ Lekerdez esek: koz mar ´ ´ mindig fogalmunk sincs. meg
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ as ´ elemzese ´ Az Index buffer-es tarol
´ as: ´ alt. ´ hatekony. ´ Tarol ´ as: ´ hatekony. ´ Transzformal ´ ´ ¨ os ¨ csucsokat ´ tudunk, de igazab ´ ol ´ Lekerdez esek: koz mar ´ ´ mindig fogalmunk sincs. meg
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ agi ´ viszonyok Szomszeds
´ ´ ´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ agi ´ viszonyok Szomszeds
´ ´ ´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ agi ´ viszonyok Szomszeds
´ ´ ´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ agi ´ viszonyok Szomszeds
´ ´ ´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ ´ adatszerkezet Szarnyasel
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ ´ adatszerkezet Szarnyasel
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ ´ adatszerkezet Szarnyasel
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ ´ adatszerkezet Szarnyasel
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ adatai Egyetlen el ´ el a
csucs ´ ´ start veg B A
bal 0
lap jobb 1
http://cg.elte.hu
balra ˝ o˝ kov. ¨ eloz c b
˝ as ´ 9. eload
jobbra ˝ o˝ kov. ¨ eloz d e
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ tabl ´ azatok ´ Egyeb
´ aja ´ Lapok tabl
´ aja ´ Csucsok tabl ´
lap ID
csucs ´ ID ´ indulo´ el ´ csucsb ol ´
´ lap egy ele
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
´ ´ Pelda: tetraeder
Shirley, Fundamentals of Computer Graphics
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
¨ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ as ´ ”Brute force” tarol Index buffer-ek ´ ´ adatszerkezet Szarnyasel
¨ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Tartalom
1
´ vilag ´ tarol ´ asa ´ Virtualis
2
´ asa ´ Geometria tarol
3
Hierarchikus adatszerkezetek ´ af ´ Sz´ıntergr OGRE
4
CSG modellek, CSG fa
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Hierarchikus adatszerkezetek
´ benne Vilag, Objektumok, ami ˝ allnak, ´ Primit´ıvekbol amiket ´ Pontok hataroznak meg.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Hierarchikus adatszerkezetek
´ benne Vilag, Objektumok, ami ˝ allnak, ´ Primit´ıvekbol amiket ´ Pontok hataroznak meg.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Hierarchikus adatszerkezetek
´ benne Vilag, Objektumok, ami ˝ allnak, ´ Primit´ıvekbol amiket ´ Pontok hataroznak meg.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Hierarchikus adatszerkezetek
´ benne Vilag, Objektumok, ami ˝ allnak, ´ Primit´ıvekbol amiket ´ Pontok hataroznak meg.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
!
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Minden ”szint” a hozzatartoz o´ tulajdonsagokat tartja ´ ny´ılvan. Objektum ´ nev, ´ transzformaci ´ o, ´ modellezesi befoglalo´ doboz, stb.
Primit´ıv ´ primit´ıvre jellemzo˝ tulajdonsagok
Pont ´ ak ´ koordinat
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Minden ”szint” a hozzatartoz o´ tulajdonsagokat tartja ´ ny´ılvan. Objektum ´ nev, ´ transzformaci ´ o, ´ modellezesi befoglalo´ doboz, stb.
Primit´ıv ´ primit´ıvre jellemzo˝ tulajdonsagok
Pont ´ ak ´ koordinat
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Minden ”szint” a hozzatartoz o´ tulajdonsagokat tartja ´ ny´ılvan. Objektum ´ nev, ´ transzformaci ´ o, ´ modellezesi befoglalo´ doboz, stb.
Primit´ıv ´ primit´ıvre jellemzo˝ tulajdonsagok
Pont ´ ak ´ koordinat
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Minden ”szint” a hozzatartoz o´ tulajdonsagokat tartja ´ ny´ılvan. Objektum ´ nev, ´ transzformaci ´ o, ´ modellezesi befoglalo´ doboz, stb.
Primit´ıv ´ primit´ıvre jellemzo˝ tulajdonsagok
Pont ´ ak ´ koordinat
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ – motivaci ´ o´ 1. Sz´ıntergr
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ – motivaci ´ o´ 1. Sz´ıntergr
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ – motivaci ´ o´ 1. Sz´ıntergr
´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ 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)
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ Csomopontok
´ egy csomopontja ´ A graf (csucsa, node-ja) lehet ´ geometria, ´ o, ´ transzformaci ˝ anyagjellemzok, ´ ´ fenyforr as, kamera.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Csomopontok tulajdonsagai ˝ Anyagjellemzok ´ ´ stb. Sz´ınek, optikai tulajdonsagok, textur ´ ak, ´ es: ´ hogyan abr ´ azoljuk, ´ ¨ Nyitott kerd ha egy modellunk ¨ tobb ´ is hasznal? ´ textur ´ at
´ ´ Fenyforr as ´ iranya, ´ Pozicioja, t´ıpusa, sz´ıne, stb. ´ Levele a grafnak.
Kamera ´ nezeti ´ ´ ´ osz ´ oge, ¨ Poz´ıcioja, iranya, lat stb. ´ Levele a grafnak.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Csomopontok tulajdonsagai ˝ Anyagjellemzok ´ ´ stb. Sz´ınek, optikai tulajdonsagok, textur ´ ak, ´ es: ´ hogyan abr ´ azoljuk, ´ ¨ Nyitott kerd ha egy modellunk ¨ tobb ´ is hasznal? ´ textur ´ at
´ ´ Fenyforr as ´ iranya, ´ Pozicioja, t´ıpusa, sz´ıne, stb. ´ Levele a grafnak.
Kamera ´ nezeti ´ ´ ´ osz ´ oge, ¨ Poz´ıcioja, iranya, lat stb. ´ Levele a grafnak.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ ´ Csomopontok tulajdonsagai ˝ Anyagjellemzok ´ ´ stb. Sz´ınek, optikai tulajdonsagok, textur ´ ak, ´ es: ´ hogyan abr ´ azoljuk, ´ ¨ Nyitott kerd ha egy modellunk ¨ tobb ´ is hasznal? ´ textur ´ at
´ ´ Fenyforr as ´ iranya, ´ Pozicioja, t´ıpusa, sz´ıne, stb. ´ Levele a grafnak.
Kamera ´ nezeti ´ ´ ´ osz ´ oge, ¨ Poz´ıcioja, iranya, lat stb. ´ Levele a grafnak.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ a gyakorlatban Sz´ıntergr
´ hasznal ´ valamilyen Minden komolyabb 3D alakalmazas ´ afot. ´ szintergr ´ ak: ´ Peld Maya, Java3D OpenSceneGraph OGRE
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ OGRE-ben Sz´ıntergr
´ anos ´ ´ amihez az aktualis ´ Ogre::SceneNode: altal osztaly, elemeket hozza´ lehet csatolni az Ogre::MovableObject ´ osztalyon keresztul. ¨ ´ Tulajdonsagai: Bounding box ´ osszes´ ¨ poz´ıcio´ es ıtett poz´ıcio´ ´ ora ´ hasonloan ´ orientaci ´ ´ meretez es ˝ ´ oi ´ adat tetszoleges felhasznal
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Ogre::MovableObject
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
Ogre::MovableObject
´ Tulajdonsagok: ´ bounding box Sajat Rejtett vagy sem? ´ ´ Vethet arny ekot? ´ ´ Milyen fenyek tartoznak hozza?
´ okat ´ Transformaci nem tartalmaz!
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
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. Geometria: Ogre::Mesh ˝ Ogre::Material Anyagjellemzok:
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ OGRE-ben Sz´ıntergr
´ meg ´ sok mas ´ objektum. ...es ´ Tanulsag: ´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ af ´ Sz´ıntergr OGRE
´ af ´ osszefoglal ¨ Sz´ıntergr o´
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
Tartalom
1
´ vilag ´ tarol ´ asa ´ Virtualis
2
´ asa ´ Geometria tarol
3
Hierarchikus adatszerkezetek
4
CSG modellek, CSG fa
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
¨ ´ Kul eg ¨ onbs
Captain Sprite, en.wikipedia
Unio´
Metszet
Captain Sprite, en.wikipedia
http://cg.elte.hu
Captain Sprite, en.wikipedia
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
´ ´ 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
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
CSG fa
Zottie, wikipedia
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek megjelen´ıtese
´ kepszint ´ ´ ´ kell. Inkrementalis ezis: tesszelalni ´ ovet ¨ es: ´ specialis ´ sugar/model ´ ´ Sugark metszespont ´ ıtas ´ Ñ CSG-fa bejar ´ asa. ´ szam´
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek megjelen´ıtese
´ kepszint ´ ´ ´ kell. Inkrementalis ezis: tesszelalni ´ ovet ¨ es: ´ specialis ´ sugar/model ´ ´ Sugark metszespont ´ ıtas ´ Ñ CSG-fa bejar ´ asa. ´ szam´
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek metszese ˝ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek metszese ˝ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek metszese ˝ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek metszese ˝ 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.
http://cg.elte.hu
˝ as ´ 9. eload
´ vilag ´ tarol ´ asa ´ Virtualis ´ asa ´ Geometria tarol Hierarchikus adatszerkezetek CSG modellek, CSG fa
´ CSG modellek metszese ˝ 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.
http://cg.elte.hu
˝ as ´ 9. eload
