3D - geometriai modellezés, alakzatrekonstrukció, nyomtatás

3D - geometriai modellezés, alakzatrekonstrukció, nyomtatás 8. Rekurzív felosztáson alapuló felületek

http://cg.iit.bme.hu/portal/node/312 https://www.vik.bme.hu/kepzes/targyak/VIIIAV54 Dr. Várady Tamás, Dr. Salvi Péter BME, Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék 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

1. Doo-Sabin algoritmus, 2. Catmull-Clark algoritmus, 3. Középosztás, 4. Loop-féle osztás, 5. √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 kontrol 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




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 → következő óra




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 szubdivízió) (összeillesztett spline felületek)

Áttekintés

?

Subdivision video

3

Rekurzív poligon-felosztás1 Rekurzív poligon-felosztás

p in + 2

{p , p , K, p } ⇒ {p , p , K, p i 1

• •

i 2

i ki )

i +1 1

i +1 2

i +1 k i +1

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 j =1

p i2+n1

p in −1

kérdések:

• • •

p

i +1 2 n −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

Ujjgyakorlat*- rekurzív poligon osztás

Chaikin-féle osztás

Rekurzív felosztáson alapuló görbék

5

Ujjgyakorlat - rekurzív poligon osztás

Chaikin-féle osztás Rekurzív felosztáson alapuló görbék

6

Rekurzív poligon-felosztás2 2. Felosztás alternatív súlyokkal (húrfelezés) 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 i2+n1

p

i n −1

p i2+n1−1

p in +1 p i2+n1+1

a folytonossági analízis elve (sajátértékek): p1n −1  p n −1   4 4 0 1   D =  p n , D1 =  p1n  = 1 6 1 D = AD 8 p1n +1  p n +1  0 4 4  

diagonizálás (sajátvektorok, sajátértékek):

A = EΛE −1 0  1 1 2  . . . 1 0 E = 1 0 − 1, E −1 = . . ., Λ = 0 0.5 0  1 − 1 2  . . . 0 0 0.25 D2 = A1D1 = A 2 D, A 2 = EΛE −1EΛE −1 = EΛ 2E −1 D R = A R D = EΛ R E −1 ⇒ A ∞ Poligonok rekurzív felosztása

p n −1   p  ⇒ p* n  n  p n +1  7

Rekurzív poligon-felosztás3

?

3. Interpoláló felosztás (négy-pont):

Curves applet

•

középső pont meghatározása: harmadfokú Lagrange interpoláció

p i2+n1 = p in ; p i2+n1+1 =

•

⇒ konvergál,

C1

1 ( − p in −1 + 9p in + 9p in +1 − p in + 2 ) 16

p

határgörbe

i +1 2n

p

p

i n −1

Poligonok rekurzív felosztása

i n

pi2+n1+1

p i2+n1+ 2

pin +1 p in + 2 8

Rekurzív poliéder-felosztás1

(Doo-Sabin)

(Loop)

(Pixar) Rekurzív felosztáson alapuló felületek

9

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 (konverzió sebessége) affin leképzésre invariáns sima felület hierarchikus reprezentáció konvex burok

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

10

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

• • • •

.

2 12

.

8 12

Rekurzív felosztáson alapuló felületek

.

2 12

. 11

Ujjgyakorlat* Doo-Sabin-féle rekurzív felosztás

3-oldalú:

1 db

4-oldalú:

4 db

5-oldalú:

1 db

3-oldalú: Cs: ?, É: , L:?, Össz. = ? 4-oldalú: Cs: ?, É: , L:?, Össz. = ? 5-oldalú: Cs: ?, É: , L:?, Össz. = ? Rekurzív felosztáson alapuló felületek

12

Ujjgyakorlat Doo-Sabin-féle rekurzív felosztás

3-oldalú:

1 db

3-oldalú: Cs: 2, É: 0, L:1, Össz. = 3

4-oldalú:

4 db

4-oldalú: Cs: 1, É: 8, L:4, Össz. = 13

5-oldalú:

1 db

5-oldalú: Cs: 0, É: 0, L:1, Össz. = 1 Rekurzív felosztáson alapuló felületek

13

Ujjgyakorlat* - Doo-Sabin súlyok n+5 , α1 j = n = 4, i = 1, α11 = 4n

2π (i − j ) n , j = 2,3,4 4n

3 + 2 cos

?

α 14

α 13

α 11

?

? α 12 Rekurzív felosztáson alapuló felületek

? 14

Ujjgyakorlat - Doo-Sabin súlyok n+5 , α1 j = n = 4, i = 1, α11 = 4n

2π (i − j ) n , j = 2,3,4 4n

3 + 2 cos

3 16

α 14

α 13

α 11

1 16

9 16

α 12 Rekurzív felosztáson alapuló felületek

3 16

15

Rekurzív poliéder-felosztás4 2. Catmull-Clark felületek

• • • •

harmadfokú B-spline felületek általánosítása (középponti osztás central split) i +1 (i) új LAP-csúcs – középpont, f j

(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 i +1 körülvéve: v

1 n i+1 2 n i +1 n − 3 i v = 2 ∑fj + 2 ∑ej + v n j =1 n j =1 n i +1

• •

ú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

?

Human Face-Subdivision 16

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ÚCSlapok négyoldalú lapok dominálnak szabályos csúcsok (n=4) különleges csúcsok – az eredeti csúcsok körül ⇒ konvergál, G1 határfelület

Rekurzív felosztáson alapuló felületek

17

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

18

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: 1 2π  αn n i i +1 i , α = 4 − 2 cos v = (1 − α n ) v + v   ∑ j n n j =1 9 n  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

Rekurzív felosztáson alapuló felületek

19