3D-s számítógépes geometria és alakzatrekonstrukció 2b. Háromszöghálók
http://cg.iit.bme.hu/portal/node/312 https://www.vik.bme.hu/kepzes/targyak/VIIIAV08 Dr. Várady Tamás, Salvi Péter BME, Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék
1
Tartalom háromszöghálók egyszerűsítése csúcspontok klaszterezése inkrementális eljárások progresszív hálók egyenletes mintavételezés és újrahálózás
normálvektorok és görbületek numerikus becslése felületek minőségének javítása
3D-s számítógépes geometria
2
Háromszöghálók egyszerűsítése1 (decimálás) háromszögháló ⇒ kisebb háromszögháló komplexitás csökkentése − hatékonyság növelése adattárolás, adatátvitel hierarchikus reprezentáció optimalizálás (energiafüggvények)
minőség megőrzése távolság tolerancia alaksajátosságok grafikus paraméterek, textúra
négy algoritmus csúcspontok klaszterezése inkrementális eljárások progresszív hálók (visszaépíthető) mintavételezés és új háló létrehozása
Háromszöghálók egyszerűsítése
3
Háromszöghálók egyszerűsítése2
1. példa (Botsch et al.): 577 512 háromszög → 10 % → 1 % → 0.1 %
2. példa: (Garland, Heckbert): a háromszögek követik a textúra struktúrát − 18050 →
1000
Háromszöghálók egyszerűsítése
4
Háromszöghálók egyszerűsítése3 Hátsó lap
Távoli lap
Nem része a nézeti tartománynak
3. példa (Hoppe): nézőpont függő egyszerűsítés − 100000 → 29400 Háromszöghálók egyszerűsítése
5
Csúcspontok klaszterezése1 approximációs tolerancia: ε adaptív osztás: minden cella átmérője ≤ ε reprezentáns mintapontok meghatározása az eredeti háromszögek degenerálódnak ⇒ törlés, egyszerűsítés klaszterek közötti élek újraszámolása P klaszter, reprezentáns: p, eredeti pontok: p0, p1, ...pn Q klaszter, reprezentáns: q, eredeti pontok: q0, q1, ...qm ha van (pi,qj) él ⇒ új (p,q) él beillesztése
aránylag gyors algoritmus (lineáris lépésszám) topológiai változások − a minőség nem mindig megfelelő
Klaszterezés
6
Négyzetes hiba
v D
π
adott egy π sík; a v=(x,y,z) pont π -től mért távolsága:
n p
D(v)= |v-p |cos α=(n,v-p)=(n,v)+d ahol n=(nx,ny,nz) egységvektor; p - tetszőleges pont a síkban, d konstans négyzetes hiba:
D 2 ( v ) = ((n, v) + d ) 2 = (( v, nT ) + d )((n, v T ) + d ) = v[nT , n]v T + 2d (n, v) + d 2 másodfokú felület:
{
≡ Q( v ) = vAvT + 2(b, v) + c, Q = {A, b, c} = [nT , n], dn, d 2
}
két hiba (két felület) esetén - összeadás komponensenként:
Q1 ( v ) + Q2 ( v ) = {A1 + A 2 , b1 + b 2 , c1 + c2 }
négyzetes hiba k síkra:
Q * ( v ) = ∑ Qk ( v ) = {A * , b* , c* } k
Klaszterezés
7
Csúcspontok klaszterezése2
a) eredeti
b) átlag
c) medián
d) négyzetes
(Botsch et al.)
minden cellára feltételezés: síkszerű háromszöghalmaz kiszámítandó az optimális reprezentáns csúcs: ~ v a legkisebb négyzetes eltérés a háromszögek síkjától:
Q * ( v ) = vAv T + 2bv + c = min, ∂Q * / ∂x = ∂Q * / ∂y = ∂Q * / ∂z = 0 1 1 ~ v = − A −1bT , Q * ( ~ v ) = − bA −1bT + c 2 4 Klaszterezés
8
Ujjgyakorlat* - quadtree
Klaszterezés • ha egy cellában n>4, tovább osztunk • ha a cella kicsi és n≥2 → reprezentáns pontot kell számolni Végül hány cellát (.....) és hány új reprezentáns pontot kapunk (.....) ? Quadtree
9
Ujjgyakorlat - quadtree
Klaszterezés • ha egy cellában n>4, tovább osztunk • ha a cella kicsi és n≥2 → reprezentáns pontot kell számolni Cellák száma: 19, reprezentáns pontok száma: 3 Quadtree
10
Inkrementális decimáció1 Euler szabály (poliéderek): v-e+f = 2 csúcs (v), él (e), lap (f)
elemi műveletek: v ↔ v-1, e ↔ e-3, f ↔ f-2
(a) csúcstörlés − beszúrás a belső háromszögelés módja szabad
(b1) élösszehúzás − ketté vágás az új csúcs választása szabad, optimalizálható
(b2) fél-él összehúzás − ketté vágás az új csúcs az eredeti ponthalmaz tagja Inkrementális decimáció
11
Ujjgyakorlat* - decimáció
- mindig a legrövidebb élet írtjuk ki - az új csúcs a régi él közepére kerül - két lépés
Decimáció
12
Ujjgyakorlat - decimáció
- mindig a legrövidebb élet írtjuk ki - az új csúcs a régi él közepére kerül - két lépés
Decimáció
13
Inkrementális decimáció2 közelítési hibaösszeg becslése minden lépésnél, mindegyik érintett háromszögre − a hibák összegződnek hiba: skalár vagy vektor vagy négyzetes
v1
v
v2
négyzetes hibák esetén minden kiinduló pontra Qi=0, egyszerű összegzés minden új v csúcsra; az optimális v meghatározható (korábbi slide) cél: minimális „összenergia”, illetve „összköltség”
v1
v v2
az algoritmus lépései 1. minden pontra a négyzetes hiba meghatározása 2. elsőbbségi sor (priority queue): összehúzható élek és ezek költsége 3. legolcsóbb élösszehúzás végrehajtása ⇒ az adatstruktúra lokális frissítése 4. iteráció, amíg a terminálási feltétel(ek) teljesülnek Inkrementális decimáció
14
Progresszív hálók1 (Hoppe) háromszöghálók hierarchiája nincs információvesztés cél: hatékony grafika, adattárolás, adatátvitel
él-összehúzás (edge collapse) adatsor: (vs, vt, vs’)
csúcs-széthúzás (vertex split) adatsor: (vs, vl, vr, vt’, vs’+ attribútumok)
Progresszív hálók
15
Progresszív hálók2
? Progresszív hálók
16
Progresszív hálók3 az összehúzandó él kiválasztása – energia minimumra való törekvés E1: geometriai jellemzők (távolság, normálvektor eltérés) E2: skalár jellemzők (pl. színek) E3: élek, határok
nézőpont specifikus finomítás hátsó lapok, távoli lapok, kis méretű lapok
Progresszív hálók
?
17
Önálló feladat** Progresszív hálók rövid szeminárium és prototípus implementáció input: mesh output: animált progresszív háromszögháló az animáció megállítható, valamint tovább és vissza léptethető az egyszerűsítés módszerei: (i) nézőpont szerint (ii) síklapuság szerint (iii) háromszögméret szerint
Progresszív hálók
18
Mintavételezés és új háló létrehozása Dióhéjban: új topológiai struktúra izotrópiára való törekvés mintavételezés szigorú – távolsági és minőségi – kritériumok alapján
Mintavételezés és új háló
19
Geometriai jellemzők becslése1 a) normálvektor: n b) görbületek: Gauss-görbület: G = κ1 κ 2,, Átlaggörbület: H = (κ 1 + κ 2) / 2 Főgörbületek (κ 1, κ 2), főirányok (k1, k2)
q3 q2
q4 p
Normálvektor becslése sík-illesztés alapján q5 adott pont: p, körülötte:
q1
qi=(xi,yi,zi),
ismeretlen normálvektor : n=(nx,ny,nz), legkisebb négyzetes távolság:
2 2 ∑ Di = ∑ ( n, q i − p) = min i
kényszer (euklideszi távolság):
i
n + n + n z2 = 1 2 x
2 y
Lagrange-féle multiplikátor: F ( x, y , z ) = min, G ( x, y , z ) = c
H ( x, y , z , λ ) = ( F ( x, y , z ) + λ (G ( x, y , z ) − c ) = min ∂H / ∂x = ∂H / ∂y = ∂H / ∂z = ∂H / ∂λ = 0 (négy ismeretlenes egyenletrendszer) Geometriai jellemzők
20
Geometriai jellemzők becslése2 q3
Lokális paraboloid-illesztés
q4
q2
adott pontokon keresztül q5
p
q1
legyen p az origó a lokális koordináta rendszerben:
qi=(ui,vi,wi), (i=1,..n, n ≥ 5), wi= (n, qi-p) a paraboloid egyenlete: ismeretlenek:
f (u, v ) = au 2 + buv + cv 2 + du + ev
x = [a , b, c, d , e]
azonosak a deriváltakkal (u=0,
v=0)-ban:
x = [ 12 f uu , f uv , 12 f vv , f u , f v ]
legkisebb négyzetes (algebrai) távolság: 2 2 ∑ Di = ∑ ( f (ui , vi ) − wi ) = min i
i
Geometriai jellemzők
21
Opcionális
Geometriai jellemzők becslése3 Legkisebb négyzetes minimalizálás mátrix alakban: 2 2 ∑ Di = ∑ ( f (ui , vi ) − wi ) = min i
i
( Ax − b) 2 = min. ⇒ A T Ax − A Tb = 0, ⇒ x = ( A T A ) −1 A Tb ahol . . . ( Ax − b) = 2 ui . .
.
.
.
. . ui vi . .
. . vi2 . .
. . ui . .
. . a . . b . . c − vi wi d . . e . .
Geometriai jellemzők
22
Geometriai jellemzők becslése4 Háromszög alapú normálvektor-becslés i-edik háromszög:
n i = (q i − p) × (q i +1 − p) Ai =
1 | ni | 2
q3 q4
q2 p
a) egységvektorok átlagolása:
1 n n p = ∑ ni 0 , ni 0 = i n i | ni |
q5
q1
b) területarányos súlyozás:
np =
1 1 A n , A = A , → n = ni ∑ ∑ ∑ i i0 i p A i 2A i i
Geometriai jellemzők
23
Geometriai jellemzők becslése5 Háromszögalapú görbület-becslések qi-1
p
• az i-edik háromszögben:
ni-1
e i = (q i − p), α i = ∠(e i , e i+1 ), β i = ∠( n i , n i−1 )
βi
A( p) = ∑ Ai
ei
i
Gauss-görbület • klasszikus differenciálgeometria (Gauss-Bonet tétel):
αi
ni qi+1
qi
ei+1
∫∫A GdA = δ (p)
• szöghiány:
δ (p) = 2π − ∑ α i
• diszkrét becslés: (körlapocska)
δ (p) G ( p) = 1 3 A( p)
Átlaggörbület (hengerdarabok)
1 ∑ βi | ei | H (p) = 4 i 1 A(p) 3
i
Geometriai jellemzők
qi-1
p
qi
qi+1 24
Geometriai jellemzők becslése6
Átlag (H) és Gauss (G) görbület1
Átlag (H) és Gauss (G) görbület2 Geometriai jellemzők
25
Háromszöghálók simítása1 • Energia-minimalizálás (fairing) − minőségmérő integrálok: a „tökéletlenséget” büntetik • A simaság fontos: pl. megjelenítésnél, anyagtulajdonságok, megmunkálás stb.
(Kobbelt)
Membrán energia: - a felület legyen kicsi
2 2 + κ κ ∫ 1 2 dA = min.
∫ dA = min.
s
s
∫∫ | r Ω
u
| + | rv | dudv 2
Rugalmas lap energia (thin plate): - ne legyen nagy a görbület
2
∫∫ | r Ω
uu
| + 2 | ruv | + | rvv | dudv 2
2
Simítás
2
Minimális görbület variáció: - ne változzon gyorsan a görbület
∫
s
∂ κ 2 ∂ κ 1 2 ∂ k + ∂ k 1 2
2 dA = min.
26
Háromszöghálók simítása2 Lokális, iteratív módszerek:
q3
(i) Laplace-féle simítás
q4
− a pontokat a szomszédok konvex kombinációjának irányába mozgatja − esernyő operátor, súlyozott átlag U (p) = ∑ w j (q j − p), (a) : w j = 1 / n, j
(b) : w j 0 =| q j − p |−1 , w j =
pold
q2
pnew q5
q1
wj0
∑
k
wk 0
− λ simítási mérték
p new = p old + λ U ( p old )
(ii) Görbület-áramlás (mean curvature flow)
p new = p old + λ H ( p old )n( p old ) Simítás
27
Háromszöghálók simítása3 Globális módszerek - numerikus vagy diszkrét simítás (fairing) • minden iterációs lépésben módosul a háló és csökken az energia; valamennyi pont módosul: energiaminimalizáló egyenletrendszrer:
M n = { pin }, E n ⇒ M n +1 = { pin +1 }, E n +1 ≤ E n (i) mi az energia ? (ii) hogyan módosítjuk a pontokat ? simasági mértékek 1. parametrikus görbületbecslés 2. diszkrét átlaggörbület
(Desbrun et al.) Simítás
28
Háromszöghálók simítása4 1. eljárás: simasági mérték − parametrikus görbület, diszkretizálva
E ≈ ∫ f uu + 2 f uv + f vv 2
2
2
E = ∑iω i ((∑ j α ij pij ) + 2(∑ j β ij pij ) + (∑ j γ ij pij ) 2
2
2
)
(ωi az i-edik pont körüli háromszögek területének összege; αi, βi, γi a deriváltakból adódó együtthatók, pij a pi pont szomszédai) • E másodfokú, → lineáris egyenletrendszer, ritka mátrix, k − első- és másodfokú szomszédok
∂E ( S ) = ∑k wik pk = 0 ∂p i
• közelítő megoldás - Gauss-Seidel iteráció, csak a diagonális elemekre
pi = −
Simítás
új
1 wii
∑
k ≠i
wik pk
29
Háromszöghálók simítása5 2. eljárás:
simasági mérték − diszkrét átlaggörbület
H (p i )n(p i ) =
1 4 Ai
∑ (cot γ
ij
+ cot δ ij ) (q ij − p i )
j
• minimalizáló egyenletrendszer, az új görbületekre kell megoldani:
∑ (cot γ
ij
+ cot δ ij )( H (p i ) − H (q ij )) = 0
j
q i , j −1
pi
γ ij
δ ij
q ij
q i , j −1
• közelítő megoldás → új átlaggörbület becslések, pont módosítás az új célgörbületek szerint:
p inew = p iold + λ H (p inew )n(p inew ) Gyorsítás: először durva felbontás, utána finomítás Peremfeltételek: az első (és a második) háromszögsor változatlan marad
30
Háromszögháló simítás6 − Demó
Simítás
31