3D-s számítógépes geometria 7a. Rekurzív felosztáson alapuló felületek http://cg.iit.bme.hu/portal/node/312 https://www.vik.bme.hu/kepzes/targyak/VIIIAV01
Dr. Várady Tamás BME, Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék 3D-s számítógépes geometria
1
Tartalom
Áttekintés
Poligonok rekurzív felosztása (subdivision)
saroklevágó algoritmusok
interpoláló algoritmus
Poliéderek rekurzív felosztása
követelmények
alapkérdések
Doo-Sabin algoritmus, Catmull-Clark algoritmus, Közép-osztás
Loop-féle osztás, √3 osztás
3D-s számítógépes geometria
2
Szabadformájú felületek - áttekintés 1. Tenzor szorzat alapú felületek
négyoldalú (n = 4) paramétertartomány, N x M-es kontroll háló Bézier felületek (polinomiális) s(u, v ) = [α(u )][C][β( v )]T B-spline felületek (szakaszonként polinomiális)
2. Bézier és B-spline felületek kiterjesztése
(S-patch-ek - n ≠ 4 oldal, speciális kontrollháló) racionális Bézier felületek (n = 4) racionális B-spline felületek (n = 4) T-spline-ok (n = 4, szakaszos polinomok, hiányos kontrollháló)
3. Interpoláló (transzfinit) felületek
határgörbék és keresztderivált függvények Coons patch (n = 4) általános n-oldalú felületek
4. Poliéder-alapú általános topológiájú felületek
felosztásos felületek (rekurzív szubdivizió) (összeillesztett spline felületek) Áttekintés
3
Rekurzív poligon-felosztás1 Rekurzív poligon-felosztás
• •
i +1 1
i +1 2
{p , p , K, p } ⇒ {p , p , K, p i 1
i 2
i ki )
i +1 k i +1
j =1
kérdések:
• • •
p in
}
korábbi poligon pontok lineáris kombinációja: l i +1 p m = ∑ α j p ij ( m ) , m = 1,K, k i +1
p in + 2
p
i +1 2 n −1
p i2+n1
p in −1
p in +1
konvergál valamilyen görbéhez ?
(3,4)
polinomiális görbe ?
(1,2)=(2,1)
milyen mértékben sima ? (1.5,1)
(2,1.5)
1. Chaikin algoritmus (sarok levágás): p
i +1 2 n −1
(3,2.5)
3 1 3 1 = p in + p in −1 ; p i2+n1 = p in + p in +1 . 4 4 4 4
• ⇒ másodfokú B-spline (!), C1
(2,2.5) (0,1)
(2,3)=(3,2) (0,1,2,3,4)→(0,1,1.5,2,2.5,3,4)
Poligonok rekurzív felosztása
4
Rekurzív poligon-felosztás2 2. Felosztás alternatív súlyokkal p
i +1 2n
• •
•
p in
1 3 1 1 1 = p in −1 + p in + p in +1 ; p i2+n1+1 = p in + p in +1 . 8 4 8 2 2 ⇒ konvergál, harmadfokú B-spline, C2
p
i n −1
p i2+n1−1
p i2+n1
p in +1
p i2+n1+1
a folytonossági analízis elve (sajátértékek): ⎡p1n−1 ⎤ ⎡p n−1 ⎤ D = ⎢ p n ⎥, D1 = ⎢ p1n ⎥ = AD ⎢ ⎥ ⎢ ⎥ ⎢⎣p1n+1 ⎥⎦ ⎢⎣p n+1 ⎥⎦ diagonizálás (sajátvektorok, sajátértékek):
A = EΛE−1 , D r = A r D1 = EΛ r E−1 ⇒ A ∞
•
3. Interpoláló felosztás (négy-pont): p
i +1 2n
• •
=p ; p i n
i +1 2 n +1
1 = ( − p in −1 + 9p in + 9p in +1 − p in + 2 ) 16
középső pont meghatározása: harmadfokú Lagrange interpoláció ⇒ konvergál, C1 határgörbe Poligonok rekurzív felosztása
p
i +1 2n
p in p in −1
p i2+n1+1
p i2+n1+ 2
p in +1 p in + 2 5
Rekurzív poliéder-felosztás1
(Doo-Sabin)
(Loop)
(Pixar) Rekurzív felosztáson alapuló felületek
6
Rekurzív poliéder-felosztás2 Követelmények:
• • • • • • • •
általános topológia lokális módosíthatóság egyszerű szabályok (maszk) hatékony algoritmus affin leképzésre invariáns sima felület hierarchikus reprezentáció konvex burok
?
Subdivision video
Alapkérdések:
• • • • •
finomítási szabály: sarok-levágás vagy csúcs-beszúrás a polidérsorozat „háromszög” vagy „négyszög” alapú approximáció vagy interpoláció simaság (G1 vagy G2) szabályos csúcsok vs. különleges (extraordinary) csúcsok Rekurzív felosztáson alapuló felületek
Felosztás problémák
7
Rekurzív poliéder-felosztás3 1. Doo-Sabin felületek • a Chaikin algoritmus általánosítása • minden n-oldalú lap összezsugorodik, és n új csúcs keletkezik rajta: n
v i(1) = ∑ α ij v j j =1
α ii =
n+5 , α ij = 4n
2π (i − j ) n 4n
3 + 2 cos
• • • •
LAP-lap – az eredeti lap belsejében ÉL-lap – mindig négyoldalú, az élek mentén CSÚCS-lap – csúcs körül a négyoldalú lapok száma nő ⇒ másodfokú B-spline felület darabok ⇒ G1 • szabályos csúcsok (n=4) • különleges csúcsok is keletkeznek: – n≠4 oldalú lapok, n≠4 fokú csúcsok
3 16
2 12
1 16
9 16
8 12
Rekurzív felosztáson alapuló felületek
2 12
3 16
8
Rekurzív poliéder-felosztás4 2. Catmull-Clark felületek
•
harmadfokú B-spline felületek általánosítása
• •
(i) új LAP-csúcs – középpont,
•
• •
f ij +1
(ii) új ÉL-csúcs – az él végpontjainak és a i +1 szomszédos LAP-csúcsok átlaga, e j (iii) új CSÚCS-csúcs – n lap által körülvéve: 1 n i +1 2 n i +1 n − 3 i i +1 v = 2 ∑fj + 2 ∑ej + v n j =1 n j =1 n új lapok, az első osztás után négyoldalú hurkok:
f i +1 − e i +1 − v i +1 − e i +1 − f i +1
konvergál, szabályos csúcs (n=4) − G2 határfelület , különleges csúcsok (n≠4) − G1
Rekurzív felosztáson alapuló felületek
9
Rekurzív poliéder-felosztás5 3. Középosztásos felületek (Peters & Reif)
• • •
a „legegyszerűbb” séma minden élre – új felező pont új lapok
• •
befoglalt LAP-lapok csúcskörüli CSÚCS-lapok
• • •
négyoldalú lapok dominálnak
•
⇒ konvergál, G1 határfelület
szabályos csúcsok (n=4) különleges csúcsok – az eredeti csúcsok körül
Rekurzív felosztáson alapuló felületek
10
Rekurzív poliéder-felosztás6 4. Loop-féle felosztás
• • • •
háromszöghálók finomítása i i (i) az adott él csúcsai: v1 , v 2 (ii) a csatlakozó csúcsok: v i3 , v i4 új ÉL-csúcs: 3 1 e ij+1 = ( v 1i + v i2 ) + ( v i3 + v i4 ) 8 8
•
új CSÚCS-csúcs n szomszéd alapján: n
v i +1 = (1 − nα ) v i + α ∑ v ij , j =1
2 3 1⎛5 ⎛3 1 2π ⎞ ⎞ α = , n = 3; α = ⎜⎜ − ⎜ + cos ⎟ ⎟⎟ , n > 3 16 n ⎝8 ⎝8 4 n ⎠ ⎠
• •
⇒ sima határfelület szabályos csúcsok (n=6) − G2, (negyedfokú Bézier háromszögek); különleges csúcsok (n≠6) − csak G1 (Maszkok) Rekurzív felosztáson alapuló felületek
11
Rekurzív poliéder-felosztás7 5. √3 felosztás
• • • •
háromszögháló ⇒ finomított háromszögháló (i) minden háromszöget három részre hasítunk (ii) a keletkező négyszögátlókat megcseréljük (flip) → középponti csúcsok összekötése az eredeti csúcsokat újraszámoljuk n szomszédos csúcs alapján: v
i +1
n
= (1 − α n ) v + α n ∑ v ij , i
1 2π α n = ⎛⎜ 4 − 2 cos ⎞⎟
•
n ⎠ 9⎝ minden iteráció cseréli a struktúra irányítását, két iteráció egy háromszögből 9-et készít
• •
⇒ sima határfelület szabályos csúcsok (n=6) − G2, különleges csúcsok (n≠6) − csak G1
j =1
Rekurzív felosztáson alapuló felületek
12
Önálló feladat**
A Loop-féle rekurzív felosztás számítógépes implementációja
Input: háromszögháló
Output: finomított háromszögháló n lépés után
3D grafika; interaktív lokális módosítás
Lepke (butterfly) séma (interpoláló maszk)
Rekurzív felosztáson alapuló felületek
13
A következő előadás tartalma A Bézier és B-spline reprezentációk kiterjesztése (7b)
Racionális polinomok
Projektív transzformáció Kúpszeletek Racionális görbék és felületek Forgásfelületek
Hiányos csomóvektor struktúrák
motíváció lokális kontrollpont alapú spline felületek T-spline konstrukció
Következő előadás
14
