Tartalom
´ ıtog ´ epes ´ Szam´ Grafika
´ topologia ´ ´ asa ´ Geometria es tarol ´ asa ´ Geometria tarol ´ ´ asa ´ Topologia tarol ´ ´ adatszerkezet Szarnyasel ´ el ´ adatszerkezet Fel-
´ Valasek Gabor
[email protected] ¨ os ¨ Lorand ´ ´ Eotv Tudomanyegyetem Informatikai Kar
˝ ´ ev ´ 2015/2016. oszi fel
¨ ´ asa ´ Geometria kozvetlen tarol
I
I
I
´ haromsz ´ ¨ A mai modern grafikus API-k pont, szakasz es og ´ primit´ıveket hasznalnak ´ uk, ´ Ebben a pontban megnezz ¨ hogy milyen modon ´ ´ el ezek hatekonyan ´ tarolhat oak ´ a´ azt is, hogy mikepp ´ ´ ´ Tovabb tudunk szomszedoss agi ´ okat ´ informaci is kinyerni
¨ ek ´ reprezentaci ´ oja ´ Gorb ´ interpolaci ´ o´ Linearis ´ gorb ¨ ek ´ hatvanyb ´ ´ Polinomialis azisban ´ o´ Hermite interpolaci ´ ¨ ek ´ es ´ spline-ok Bezier gorb ¨ ek ´ Subdivision gorb
´ asa ´ - brute force Geometria tarol
I
I
´ anosabban ´ ´ Altal nezve, legyenek a primit´ıveink s´ıkbeli ´ aval ´ poligonok, amiket csucspontjaik felsorolas ´ ´ ¨ ıtett bejar ´ asi ´ irany ´ szerint) reprezentalunk (valamilyen rogz´ Poligonokkal kapcsolatos feladatok: I I I
´ as ´ tarol ´ as ´ transzformal ´ ´ lekerdez ´ ´ szomszedoss agi esek
´ asa ´ Geometria ”brute force” tarol
´ as ´ elemzese ´ A ”brute force” tarol
I
struct triangle { f l o a t x1 , y1 , z1 ; f l o a t x2 , y2 , z2 ; f l o a t x3 , y3 , z3 ; };
Index pufferek
I
¨ ´ Alapotlet: taroljunk minden csucsot egyszer, egy nagy ´ ¨ os ¨ tombben! ¨ koz
I
¨ ´ A poligonok csak hivatkozzanak a csucsok tombj enek ´ elemeire.
I
Ez az index puffer. ´ Minden GPU tamogatja.
I
I
´ 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 ´ ´ ´ okat, ´ ´ elvegezni a transzformaci ahanyszor szerepelnek → ´ nem hatekony
I
´ ´ ´ Lekerdez esek: fogalmunk sincs, ki kinek a szomszedja, ¨ ´ as ´ aval ´ ´ csak az osszes csucs tudunk eredmenyre jutni ´ bejar ´ → katasztrofa
I
˝ ´ egyszerubben ´ nem is Egyetlen elonye, hogy ennel mar ˝ ´ lehetne tarolni
Index puffer-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
v e r t e x B u f f e r ; s t d : : v e c t o r i n d e x B u f f e r ;
Index puffer
Index puffer
Index puffer
Index puffer
Index puffer
Index puffer
´ Pelda
´ Pelda – folyt.
I
I
I
I
´ ˝ all ´ o´ racsot! ´ Vegyunk ol Mennyi ¨ egy N × N db negyzetb ´ adatot kell eltarolnunk ehhez? ´ ´ ul: ´ Merete index puffer nelk egyzet, N ×N ¨ 4 csucs/n ´ 2 ´ negyzet: 4N csucspont. ´ ´ Merete index puffer-rel: (N + 1) × (N + 1) = N 2 + 2N + 1 ´ szam, ´ csucs index) ´ (+ 4N 2 egesz ´ meg? Azaz hogyan viszonyul egymashoz ´ ´ Mikor eri 4N 2 es N 2 + 2N + 1? 4N 2 >N 2 + 2N + 1 0 > − 3N 2 + 2N + 1 N >1, ha N ∈ Z+
I
¨ mint egyetlen negyzet ´ ´ megeri! ´ Ha tobb unk ¨ van, mar
I
Pl. ha N = 10 ´ ´ ul: ´ ´ Merete index puffer nelk tarolunk es ¨ 400 csucsot ´ ´ transzformalunk
I
I
´ ´ ´ Merete index puffer-rel: 121 csucsot tarolunk es ´ ´ transzformalunk
Index puffer-ek GPU-n
I
I
I
´ artya, ´ ´ nem gyujtenek Minden videok ”amit meg a ˝ ´ ˝ tamogatja ´ muzeumok” (idezet 2010-bol) az index ´ puffer-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.
´ Kocka problema
´ Kocka problema
I
´ Figyeljunk: az index puffer csak akkor tud seg´ıteni, ha bar ¨ ¨ oz ¨ o˝ haromsz ´ ¨ ´ hasznaljuk ´ kul ogekn el fel ugyanazt a ¨ onb ´ ¨ ugyanannak a feluletnek csucsot, de mindegyik haromsz og ´ ¨ ¨ ıtese! ´ a kozel´
I
´ rakunk ossze ¨ ´ ¨ ˝ akkor egy Ha egy kockat haromsz ogekb ol, ´ o˝ csucs ´ ´ ¨ sarokban lev max. hat haromsz ognek ´ min. harom, ´ ¨ oz ¨ o˝ de minden egyes csucspont harom kul a csucsa ´ ¨ onb ´ ¨ ´ o˝ harom ´ felulet er lap) pontja ¨ (az ott ossze ´ bar ´ index puffer-rel eleg ´ lenne csak 8 csucsot Tehat ´ ´ ´ ıtunk es ´ feluleti ´ nyilvantartani, amint megvilag´ normalisokra ¨ ´ unk lesz szuks ¨ eg ¨ baj lesz!
I
´ Kocka problema
I
´ ´ egyetlen terbeli ´ ¨ egy sarok, A problema: bar pontot jelol ´ aban ´ ´ ¨ oz ¨ o˝ felulet valoj harom kul pontja ¨ onb ¨ feluleti ¨
I
´ Mivel a csucspontokban poz´ıciokon k´ıvul ´ ¨ feluleti ¨ ´ ´ ´ ´ ilyenkor meg ´ tulajdonsagokat is tarolunk (normalis), ezert ´ ´ ´ index pufferrel sem sporolhatjuk ki a terbeli redundanciat!
I
´ kul ¨ meg kell adni a csucsokat, Oldalankent ugyanolyan ¨ on ´ ´ de a harom ´ ˝ ´ poz´ıcio, oldalnak megfeleloen harom ¨ oz ¨ o˝ normalis ´ seg´ıtseg ´ evel: ´ ¨ ´ 3×8 kul osszesen tehat ¨ onb csucs ´ kerul ¨ az vertex buffer-ba
´ as ´ elemzese ´ Az index pufferes tarol
´ agi ´ viszonyok Szomszeds
I I I I
´ as: ´ alt. ´ hatekony. ´ Tarol ´ as: ´ hatekony. ´ Transzformal
I
´ ´ ¨ os ¨ csucsokat ´ tudunk, de igazab ´ ol ´ Lekerdez esek: koz mar ´ ´ mindig fogalmunk sincs. meg
I
I
´ ´ adatszerkezet Szarnyasel
I
I
I I I
´ Az alakzatokat hatarukkal le´ıro´ (B-rep) (boundary ´ o´ egyik gyakran hasznalt ´ representation) reprezentaci ´ ´ o´ adatszerkezete manifold poliederek ´ ´ topologiat arol eseten ´ as ´ soran ´ csucsokat, ´ ´ lapokat kul ¨ oztet ¨ Tarol eleket es ´ ¨ onb meg ´ ´ ol ´ taroljuk ´ Az elek szempontjab a feluletet ¨ ´ ´ u´ adat tartozik Minden elhez fix szam ´ evel ´ ¨ ´ Seg´ıtseg pl. gyorsan korbe lehet jarni egy poligon ´ ¨ ´ eleit, kozben megkapva minden szomszedot
´ ´ ´ ´ Neha kellenek a szomszedok, pl. felulet-feloszt asokn al, ¨ ´ primit´ıvek kiszur ´ ´ oi ´ degeneralt egyes felhasznal ˝ esekor, ´ inputok kezelesekor stb. ´ ı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
´ ´ adatszerkezet Szarnyasel
I
I
´ ´ Minden lapot egy elsorozat hatarol - minden laphoz ´ ´ ´ ˝ ´ taroljunk egy, az elsorozat ahoz tartozo´ tetszoleges elre mutato´ pointert ´ ˝ indul ki, A csucspontok elekhez illeszkednek (vagy belole ´ ´ ´ vagy o˝ a celja) - taroljuk valamelyiket a csucsokhoz! ´
´ adatai Egyetlen el
´ adatai Egyetlen el
´ el I I
I
´ ket ´ csucsot ¨ ossze ¨ ´ ´ Egy el kot - taroljuk ezeket az elben ´ ´ legfeljebb ket ´ laphoz tartozhat - az egyik a baloldali, Egy el ´ a masik a jobboldali lap lesz, ezekre mutato´ pointereket ´ (vagy indexeket) tarolunk ´ lapon egyuttal ´ A fenti ket egy-egy elsorozat (az adott lapot ´ ´ ´ ´ - mindket ´ alkoto´ elsorozat) resze is az adott el ´ ´ ´ ovetkez ¨ ˝ et ´ es ´ megeloz ˝ oj ˝ et ´ az elsorozatban taroljuk a rak oj ´ ´ asi ´ irany ´ anak ´ ˝ (!) adott elnek az adott lap bejar megfeleloen
´ tabl ´ azatok ´ Egyeb
´ aja ´ Csucsok tabl ´ I I
csucs ´ ID ´ indulo´ el ´ csucsb ol ´
a
csucs ´ ´ start veg B A
´ ´ Pelda: tetraeder
´ aja ´ Lapok tabl I
lap ID
I
´ lap egy ele
Shirley, Fundamentals of Computer Graphics
bal 0
lap jobb 1
balra ˝ o˝ kov. ¨ eloz c b
jobbra ˝ o˝ kov. ¨ eloz d e
¨ ´ lapjanak ´ ´ Pl.: Egy lap osszes szomszed felsorolasa
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.: Egy adott csucsot tartalmazo´ osszes lap ´ ´ felsorolasa 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
¨ ´ lapjanak ´ ´ Pl.: Egy lap osszes szomszed felsorolasa
I
I
I
I
´ el ´ eb ´ ol ˝ (amit Azaz: induljunk el az adott lap reprezentans ´ tarolunk a laphoz) ´ ´ Ha ennek az elnek a baloldali lapja az adott lap: iteraljunk ´ ´ ´ es ´ ´ırjuk ki a jobboldali lapokat (a vegig a baloldali ellist an ´ ´ kivalt ´ o´ lap) baloldali a lekerdez est ¨ ´ ´ Kul a jobboldali lap az adott lap, iteraljunk vegig a ¨ onben ´ ´ an ´ jobboldali lap ellist aj ´ o´ erjen ´ ´ ´ unk Az iteraci veget, amint visszaer ¨ az adott lap ´ el ´ ebe ´ reprezentans
´ el ´ adatszerkezet Fel-
I I
´ et ´ vegyuk ´ ket ´ fel´ elre! ´ A winged-edge el ¨ szet ´ ´ ´ ´ → lenyeg eben az elek lapra vett vetulet dolgozunk! ¨ evel
I
´ elhez ´ A felcsak egy lap tartozhat + meg kell jegyeznunk ¨ a ´ fel´ el ´ et ´ (az adott el ´ masik ´ ´ testver oldali lapra vett vetulet ¨ et)
I
´ o´ kozponti ¨ ´ el ´ A reprezentaci eleme a fel-
Half-edge
Half-edge
´ el ´ adatszerkezet Fel-
¨ ´ asa ´ Pl.: Adott lap korbej ar
I
I
I
I I
´ ´ egy fel´ elhez ´ Szigoru´ ertelemben veve pontosan egy ´ es ´ lap tartozik (de gyakorlatban ennel ´ tobbet ¨ csucs, el ´ ´ tarolni hasznos lehet) ¨ ˝ taroljuk ´ ´ elben: ´ ´ el ´ cel ´ A kovetkez ot egy felaz fel´ el ´ testvere ´ (sym), a fel´ el ´ lapja csucspontja (vertex), a fel´ ´ a lapot korbefog ¨ ´ elsorozatban ´ (face) es o´ fela ´ ovetkez ¨ ˝ (next) rak oje ˝ ´ el ´ pointeret ´ A lapokhoz egy tetszoleges alkoto´ feljegyezzuk ¨ fel ´ elt ´ A csucspontokhoz egy befuto´ fel´ → HE→sym→sym = HE, HE→next→sym→vertex = HE→vertex stb.
d e f faceLoop (HE ) : l o o p = HE do : p r i n t HE l o o p = HE. n e x t w h i l e l o o p ! = HE
´ o´ Reprezentaci
´ o´ Reprezentaci
´ o´ Reprezentaci
´ o´ Reprezentaci
¨ ek ´ megadasa ´ Gorb
I
¨ ek ´ megadasa ´ Gorb
´ ´ ´ ´ gorb ¨ ek ´ reprezentaci ´ oj ´ ara: ´ Harom modot lattunk mar I
explicit: y = f (x)
I
parametrikus: p(t) =
I
x(t) y (t) implicit: x 2 + y 2 − 9 = 0
,t ∈ R
I
´ mod ´ seg´ıtseg ´ evel ´ Ezt most a paramterikus megadasi ´ uk nezz ¨ meg
´ interpolaci ´ o´ Linearis
´ pont, a, b ∈ E3 . A ket ´ ponton atmen ´ Legyen adott ket o˝ egyenes parametrikus egyenlete:
p(t) = (1 − t)a + tb, ahol t ∈ R. I
´ Most azt vizsgaljuk meg, hogy milyen adatokat kell ´ ˝ ´ u) ¨ et ´ eltarolni, hogy egy tetszoleges (un. ´ szabadformaj ´ gorb ´ ´ egyertelm uen reprezentaljunk ˝
´ interpolaci ´ o´ Linearis
I
I
¨ ¨ o˝ egyenes Ha t ∈ [0, 1], akkor az a, b pontokat osszek ot szakaszt kapjuk.
I
´ Az egyenes szakaszt egyertelm uen azonos´ıtja a szakasz ˝ ´ vegpontja, ´ ´ b ket a es
I I
¨ ´ pont koz ¨ ott ¨ Ez a legegyszerubb a ket ˝ ”gorbe” ˝ ”szep” ´ gorbe? ¨ Hogyan lesz ebbol
I
´ ≈ valami szepen, ´ ´ ”Szep” folytonosan valtoz o´
´ eg ´ - parametrikus folytonossag ´ Szeps
´ eg ´ - derivaltak ´ Szeps
I I
I
I
¨ eben/fel ´ C 0 : a gorb uletben nincsenek lyukak, nem szakad ¨ meg sehol ´ is folytonosan valtozik ´ ´ C 1 : a derivalt (DE: a derivalt ´ ´ ol ˝ fugg!) parameterez est ¨ ¨ ´ ´ C 2 : a gorbe/fel ulet derivaltjai is folytonosan ¨ masodik ´ valtoznak
I
I
I
´ Parametrikus folytonossag
´ parametrikus gorbe, ¨ Legyen adott ket r(t), s(t) : [0, 1] → E3 , ¨ os ¨ pontja, azaz pl. r(1) = s(0) = p. amelyeknek van egy koz ´ gorbe ¨ Ekkor a ket a p-ben I
C 0 ⇔ r(1) = s(0)
I
C 1 ⇔ C 0 ∧ r0 (1) = s0 (0)
I
C 2 ⇔ C 1 ∧ r00 (1) = s00 (0)
I
C n ⇔ C n−1 ∧ r(n) (1) = s(n) (0)
x(t) ¨ Ne feledjuk, p(t) = alaku´ ¨ parametrikus gorbe y(t) 0 00 x (t) x (t) 0 00 ´ a derivaltak ´ Tehat p (t) = 0 , p (t) = 00 stb. y (t) y (t) alakuak ´ 2 t +t ´ ´ ¨ enek ´ Pelda: mi a derivaltja a p(t) = gorb at =0 t3 ´ t = 1 pontokban? es ´ ´ masodik ´ ´ orb ¨ eje ´ Pelda: mi lesz az elso˝ es derivaltg ´ ¨ enek? ´ (hodografja) a p(t) = (1 − t)a + tb gorb
´ Parametrikus folytonossag
´ Parametrikus folytonossag
´ Parametrikus folytonossag
¨ ott ¨ vonal Tor
¨ ott ¨ vonal Tor
I
I
I
´ mindegyik Adottak pi ∈ E3 , i = 0, ..., n pontok es ´ ¨ ¨ pi , pi+1 , i = 0, ..., n − 1 pontpart kossunk egy ¨ ossze szakasszal! ´ Legyenek t0 ≤ t1 ≤ ... ≤ tn ∈ R parameterek a pi ´ pontokhoz hozzarendelve ´ tor ¨ ott ¨ vonal fel´ırhato´ egyetlen Ekkor az eredmeny ´ ´ ´ ert ´ ek ´ ere ´ parameterrel is: ha a t ∈ [t0 , tn ] parameter aktualis ´ t ∈ [ti , ti+1 ] igaz, akkor a hozzatartoz o´ pont ti+1 − t t − ti pi + pi+1 ti+1 − ti ti+1 − ti
I
´ o´ megkozel´ ¨ ıtes, ´ azaz a reprezentaci ´ ot ´ Ez egy interpolal ´ ¨ ´ athalad ´ ´ kepez o˝ ponthalmaz osszes elemen a reprezentalt ¨ gorbe
¨ et ´ szeretnenk ´ abr ´ azolni, ´ Ha egy ”sima” gorb akkor szakaszokkal ¨ ıtenunk ´ ´ ´ kell kozel´ eben: tesszellalni) ¨ (lenyeg
´ gorb ¨ ek ´ Polinomialis
I
I I
I
´ gorb ¨ ek ´ Polinomialis
´ magasabb foku´ garantalt ´ ´ (!) folytonossagot Ha C 0 -nal ´ alkozhatunk ´ akarunk, akkor prob polinomokkal A p0 , ..., pn pontokra illesztheto˝ egy n-edfoku´ polinom Pn i ´ ismert hatvanyb ´ azisban ´ A jol ez p(t) = i=0 ai t , t ∈ R 1 2 0 1 alaku´ (pl.: p(t) = t + t+ ) 2 1 1
´ ´ ´ ´ ot ´ → masik bazist keressunk ahol a reprezentaci ¨ inkabb, ´ ´ ´ van kepez o˝ elemeknek szemleletesebb jelentese
I
˝ ´ meg a feladatot! De elotte oldjuk meg
´ gorb ¨ ek ´ Polinomialis ´ az Megoldando´ tehat 1 t0 t02 1 t1 t 2 1 .. .. .. 1 tn tn2 | {z
I
p(ti ) = pi , i = 0, 1, .., n
I
.. t0n a0 p0 a1 .. t1n = .. .. .. .. pn an .. tnn | {z } } | {z } b a
´ egyenletrendszer, az ismeretlen a0 , .., an ∈ R3 linearis ´ egyutthat okra ¨ I
´ Legyenek adottak p0 , ..., pn ∈ E3 pontok es ´ ert ´ ekek ´ t0 < t1 < .. < tn ∈ R parameter P Keressuk ¨ azt az n-edfoku´ p(t) = ni=0 ai t i , t ∈ R ¨ et, ´ amely az adott pontokat interpolalja ´ parametrikus gorb ˝ ırt parameter ´ ert ´ ekekn ´ ´ azaz amelyre az elo´ el,
´ gorb ¨ ek ´ - parabola pelda ´ Polinomialis
V
I
I
´ ´ az ai ∈ R3 De mi lenne a geometriai ertelmez ese ´ ´ azolnak? ´ egyutthat oknak? Mit abr ¨
I
I
I
´ Ha det(V ) 6= 0, akkor van megoldas ´ ´ De vegyuk V egy Vandermonde matrix → ¨ eszre: ´ determinansa nem nulla (mivel nincs i 6= j, hogy ti = tj ) ´ tehat ´ a = V −1 b A keresett egyutthat ok ¨
I
I
´ ha peld ´ aul ´ egy parabolaval ´ ´ a t = 0, 1, 2 Tehat szeretnem ´ a p0 , p1 , p2 pontokat, akkor pontokban interpolalni 1 0 0 a0 p0 1 1 1 · a1 = p1 1 2 4 a2 p2 egyenletet kell megoldanom ´ Azaz a keresett egyutthat ok ¨ 1 0 0 a0 p0 a1 = − 3 2 − 1 · p1 2 2 1 a2 p2 −1 12 2 A parabola pedig p(t) = a2 · t 2 + a1 · t + a0
´ o´ Harmadfoku´ Hermite interpolaci
´ o´ Harmadfoku´ Hermite interpolaci
I I
I
´ pont koz ¨ ott, ¨ [0, 1]-re megfogalmazza, keressuk Ket ¨ a p(t) = H00 (t)p0 + H01 (t)m0 + H10 (t)p1 + H11 (t)m1
¨ enk ´ tarol ´ as ´ ahoz ´ A gorb bizonyos pontokban jegyezzuk ¨ fel a ¨ ´ at ´ es ´ egy bejar ´ as ´ ahoz ´ ´ gorbe poz´ıcioj tartozo´ sebesseg, ´ stb. ... vektorat ´ (azaz legyenek adottak gyorsulas ´ derivalt ´ adatok, i = 0, 1, ...) x(ti ), x0 (ti ), x00 (ti ), ...) pont es ´ Keressunk amibe ezeket a fenti adatokat ¨ egy olyan bazist, ´ ent ´ be´ırva az adott szinten a be´ırt adatot koordinatak kapjuk vissza
¨ et ´ amelyre alaku´ parametrikus gorb p(0) = p0 p(1) = p1 p0 (0) = m0 p0 (1) = m1
´ ´ Harmadfoku´ Hermite bazisf uggv enyek ¨ p(t) = H00 (t)p0 + H01 (t)m0 + H10 (t)p1 + H11 (t)m1 I Keressuk ´ polinomkent ´ az ismeretlen ¨ harmadfoku, ´ egesz j ´ ´ Hi (t) bazisf uggv enyeket, azaz legyen ¨
´ Harmadfoku´ Hermite bazis I
Hij (t) = aij t 3 + bij t 2 + cij t + dij
´ ¨ A harmadfoku´ bazisunk ekkor a kovetkez o˝ lesz: H00 (t) = 2t 3 − 3t 2 + 1 H01 (t) = t 3 − 2t 2 + t
I
I
H10 (t) = −2t 3 + 3t 2
Azt akarjuk, hogy p(0) = p0 , p(1) = p1 , p0 (0) = m0 , p0 (1) = m1 teljesuljenek ¨ Ekkor megoldando´ aij , bij , cij , dij , i, j = 0, 1-re H00 (0) = 1 H01 (0) = 0 H10 (0) = 0 H11 (0) = 0 (H00 )0 (0) = 0 (H01 )0 (0) = 1 (H10 )0 (0) = 0 (H11 )0 (0) = 0 H00 (1) = 0 H01 (1) = 0 H10 (1) = 1 H11 (1) = 0 (H00 )0 (1) = 0 (H01 )0 (1) = 0 (H10 )0 (1) = 0 (H11 )0 (1) = 1
H11 (t) = t 3 − t 2
I
¨ o˝ adatunk, akkor minden par ´ koz ¨ e´ Ha van n + 1 bejov ¨ et ´ az osszeilleszt ¨ ´ ol ˝ kapott n szerkesztve egy-egy gorb esb ˝ all ´ o´ spline C 1 lesz harmadfoku´ szegmensbol
´ Harmadfoku´ Hermite bazis
´ o˝ - geometriai folytonossag ´ Kiter
I
I
I
A szemunknek nem csak az lesz folytonos, ami ¨ parametrikusan is az ´ Nem teljesen szabatos matematikai defin´ıciokat ¨ kovetkeznek ´ al ´ parameterez ´ ´ ol ˝ fuggetlen A geometriai folytonossagn est ¨ ´ megkot ¨ eseket ´ folytonossagi teszunk: ¨ I
I
I
Catmull-Rom spline
I
Kochanek-Bartels spline
¨ ´ hanem a pontokbol ´ Ne legyen kozvetlen ul ¨ adott a derivalt, ´ ˝ ¨ ˝ epp: ´ szamoljuk oket a kovetkez ok
I
´ ´ ıtott adat A Catmull-Rom spline-hoz hasonloan itt is szam´ ´ ´ ´ lesz a tangens, de most harom parameter is adott hozza: I
p − pi−1 mi = i+1 ti+1 − ti−1 I
¨ eben/fel ´ G0 : a gorb uletben nincsenek lyukak, nem szakad ¨ meg sehol ´ ´ ha a derivaltak ´ G1 : a csatlakozasokn al nem is egyeznek meg, de ∃α > 0 ugy, hogy mi = αmi+1 ´ ¨ ¨ ulete ´ G2 : a gorbe/fel ulet folytonos a csatlakozasban is ¨ gorb ¨
´ a megadott pi es ´ a fentiek szerint szam´ ´ ıtott mi Ezutan ´ ´ illesszunk ¨ eket ´ adatokra paronk ent ¨ Hermite-gorb
I I
I
T : tension, T ∈ [−1, 1] B: bias, B ∈ [−1, 1] ´ (simasag), ´ C: folytonossag C ∈ [−1, 1]
A Catmull-Rom spline-t kapjuk, ha T = B = C = 0
Kochanek-Bartels spline
Kochanek-Bartels spline I
´ as ´ aval ´ ´ A fentiek felhasznal az i-edik szegmens ket ´ ´ ´ ert ´ ekei ´ vegpontj anak derivaltlegyenek (1 − T )(1 + B)(1 + C) (pi − pi−1 ) 2 (1 − T )(1 − B)(1 − C) + (pi+1 − pi ) 2 (1 − T )(1 + B)(1 − C) mi+1 = (pi+1 − pi ) 2 (1 − T )(1 − B)(1 + C) (pi+2 − pi+1 ) + 2 mi =
´ ¨ ´ o˝ de Casteljau algoritmus Bezier-g orbe kiter
´ ¨ Bezier-g orbe Bin (t)
n i
t i (1 − t)n−i
I
´ ´ Hasznaljuk a Bernstein-bazist:
I
´ ´ A b0 , ..., bn ∈ R3 kontrollpontok altal meghatarozott ´ ¨ n-edfoku´ Bezier-g orbe ekkor
b(t) =
n X
:=
Bin (t)bi ,
i=0
I I
I
ahol t ∈ [0, 1]. P HF: ni=0 Bin (t) = 1 teljesul, ¨ ∀t ∈ [0, 1] ¨ ´ ol” ´ koveti ¨ ´ opontok ˝ ´ A gorbe ”nagyjab a vezerl poligonjanak ´ de nem halad at ´ mindegyiken! Ez egy az alakjat, ´ o´ sema ´ approximal ´ ´ ´ MSc, Anal´ızis Tovabbi reszletek: Geometriai Modellezes ´ os ´ tetel) ´ (Stone-Weierstrass approximaci
´ ¨ Bezier-g orbe
I I
´ ´ az egesz ´ gorb ¨ ere ´ hat Egyetlen kontrollpont modos´ ıtasa ´ ´ any ´ n-re: Bernstein-bazis neh I I I
I
´ interpolaci ´ o! ´ B01 (t) = 1 − t, B11 (t) = t → linearis B02 (t) = (1 − t)2 , B12 (t) = 2t(1 − t), B22 (t) = t 2 n = 3: HF
´ ´ ¨ Lenyeg eben ”osszemossuk” a kontrollpontjainkat ´ ´ ˝ egymassal a fenti fuggv enyekkel sulyozva oket, ezzel ¨ ´ ´ ert ´ ekn ´ el ´ megmondva, hogy egy adott t ∈ [0, 1] parameter ´ melyik kontrollpont mennyire jatszik ”fontos” szerepet a ¨ ´ ´ ´ aban ´ gorbe alakjanak meghataroz as
´ ¨ ´ ´ Bezier-g orbe - bazisf uggv enyek ¨
´ ¨ ´ Bezier-g orbe tulajdonsagok
I
I
I
I
´ ¨ ´ ´ vegponton ´ ´ bn A Bezier gorbe athalad a ket (b0 es pontokon) ´ ¨ ´ A Bezier gorbe alakja valtozatlan marad, ha [0, 1] helyett t−a ¨ ott ¨ rajzolom fel, azaz a b( b−a [a, b] fol ), t ∈ [a, b] ugyanaz a ¨ gorbe (mint ponthalmaz), mint a b(t), t ∈ [0, 1] ´ ¨ ´ az affin Azaz a Bezier gorbe invarians ´ ´ okra ´ parametertranszform aci ´ ¨ ´ ezekre! Vegyuk az Hermite gorbe nem invarians ¨ eszre:
´ o´ vagy approximaci ´ o? ´ Interpolaci ´ o: ´ a gorb ¨ enek ´ ´ kell haladnia a vezerl ´ opontokon ˝ Interpolaci at
´ o´ vagy approximaci ´ o? ´ Interpolaci
´ opont ˝ Sok vezerl esete
´ o: ´ a gorb ¨ enek ´ ¨ ıtenie kell a Approximaci csak kozel´ ´ opontokat ˝ vezerl I
´ opontok ˝ ´ aval ´ ´ → egy ido˝ A vezerl szam egyutt ¨ no˝ a fokszam ´ lehet meg kell elegedn ´ ´ oval, ´ utan unk de az ¨ az approximaci sem lesz jo´
I
´ u´ polinomok erosen ˝ ´ A magas fokszam ”hullamozhatnak” 1 ´ aja: ´ ´ (piros) Runge-problem az f (x) = 1+25x 2 fuggv eny ¨ ¨ ıtese ´ soran ´ ot ¨ odfok ¨ ´ es ´ kilencedfoku´ (zold) ¨ kozel´ u´ (kek) polinomokkal
I
´ opont ˝ Sok vezerl esete
¨ ek ´ Spline gorb
I
´ aljuk ´ ´ vagy Ne egyetlen polinommal prob interpolalni ´ az adatpontjainkat (vezerl ´ opontjainkat)! ˝ approximalni
I
´ ¨ ¨ et, ´ amely alacsonyabb Hasznaljunk osszetett gorb ´ ˝ ´ fokszamu´ szegmensekbol all ´Igy kikusz ¨ ohet ¨ ´ ´ o´ oszcillaci ´ o, ´ o˝ a magas fokszammal jar ¨ ob ´ ´ anak ´ ´ az egesz ´ illetve a kontrollpontok modos´ ıtas kihatasa ¨ ere, ´ ´ szegmensek folytonos gorb de a polinomialis ´ ara ´ kul ¨ figyelni kell csatlakozas ¨ on ´Es meg ´ sok minden masra ´ is, de...
I
I I
´ ´ Reszletek: NumAnal - BSc.; Geometriai Modellezes, ´ Testmodellezes ´ - MSc. Felulet ¨ es
¨ ek ´ Spline gorb
¨ ek ´ Subdivision gorb
I
¨ ´ rogt ¨ on ¨ egy polinomot Egy otlet: az eddigiek soran ´ ıtottunk elo˝ a kontrollpontjainkbol ´ (lenyeg ´ ´ all´ eben: a ´ ´ ´ kontrollpontok altal meghatarozott kontroll-poligonbol)
I
´ soran ´ viszont ugyis Megjelen´ıtes szakaszokkal kell ´ ´ ¨ kozel´ıteni! → dolgozzunk magan a kontroll-poligonon! ´ ´ sem ´ ak ´ a A subdivision, vagy rekurz´ıv felosztassal definialt ´ kiindulo´ ponthalmazunkat (kontrolpontok halmazat) ´ kozel´ ¨ ıtest ´ is rekurz´ıvan sur´ ˝ ıtik, egyre finomabb linearis ¨ ¨ adva (legtobbsz or)
I
¨ ek ´ Subdivision gorb
¨ ek ´ - Chaikin saroklevag ´ asi ´ algoritmus Subdivision gorb I I
I
I
´ ´ ¨ enek ´ A kiindulo´ ponthalmaz altal meghatarozott gorb a ´ hatarg ´ orb ¨ ej ´ et ´ (”vegtelen ´ ´ rekurz´ıv sur´ sok” finom´ıtas ¨ ıtest ´ pontok halmazat) ´ tekintjuk utani ¨ ˝ o˝ (peld ´ aul ´ a Chaikin saroklevag ´ asi ´ Nagy kifejezoer ´ ¨ et ´ ad), de algoritmus egy masodfok u´ B-spline gorb ¨ ekn ´ el ´ lehet hatekonyabban ´ ´ gorb is szamolni sok esetben
´ vezerl ´ opont ˝ Legyen az aktualis halmazunk {pi ∈ R3 }ni=0 ´ os ´ lep ´ es ´ soran ´ az uj ´ opont ˝ Az iteraci halmazunk ´ vezerl {qi , ri ∈ R3 }n−1 lesz, ahol i=0 1 3 pi + pi+1 4 4 1 3 ri = pi + pi+1 4 4
qi =
¨ ek ´ - Chaikin saroklevag ´ asi ´ algoritmus Subdivision gorb
