3D-s számítógépes geometria 1. Bevezetés, alapfogalmak 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 • Bevezetés • Digitális reprezentációk • Pontok, vektorok, transzformációk • Görbék és felületek egyenletei • Parametrikus görbék differenciál-geometriája • Parametrikus felületek differenciál-geometriája
3D-s számítógépes geometria
2
Bevezetés • Két tudományág: (i) Computer Aided Geometric Design (CAGD) Számítógéppel segített geometriai tervezés (ii) Digital Shape Reconstruction (DSR) Számítógépes alak(zat) rekonstrukció (Reverse Engineering – Mérnöki visszafejtés) • 3D-s geometria - digitális reprezentáció - számítógépes algoritmusok - alkalmazások
Bevezetés
3
Számítógéppel segített geometriai tervezés koncepció, mérnöki dokumentáció műszaki rajz, formatervezői vázlat absztrakt, pontos geometriai elemek
tervezés számítógépes modell alkalmazások: • megjelenítés, virtuális valóság • paraméterek számítása • újratervezés, módosítás, variánsok • végeselem-analízis (FEA) szilárdságtan, termodinamika, áramlástan • numerikusan vezérelt (NC) megmunkálás Bevezetés
fizikai objektum 4
Számítógépes tervezés: input-output
formatervezői vázlatok
műszaki rajz
paraméterek módosítása, alkatrész családok
végeselemanalízis Bevezetés
automatikus megmunkálás 5
Digitális alakzat rekonstrukció létező fizikai objektum mért, zajos, strukturálatlan elemek
3D mérés, szkennelés nagyméretű ponthalmazok alakzat rekonstrukció
alkalmazások
számítógépes modell
Bevezetés
6
Digitális informatika
Digital Signal Processing 1970
Digital Image Processing 1980-90
Digital Shape Processing 2000
Fő technológiai komponensek: • érintésmentes 3D-s szkennerek • nagyteljesítményű grafikus számítógépek • digitális alakrekonstrukciós szoftver rendszerek Bevezetés
7
Rekonstrukció - alkalmazások - nem létezik digitális modell - nem CAD technológiával készült, nincs gyártási dokumentáció - egyéni organikus felületek, “testre kell szabni”; illeszkedő felületek használata: térdprotézis, fogsor, hallókészülék, bukósisak stb. - egyedi művészeti alkotások; a kulturális örökség megőrzése - van digitális referencia modell, de ellenőrizni kell a minőségét
Bevezetés
8
Az űrsikló biztonságos visszatérése Geomagic, Inc. : minőségellenőrzés - a hőálló csempék esetleges károsodásának felismerése
Bevezetés
9
Tervezés és alakzat rekonstrukció KONCEPCIÓ
TERVEZÉS
SZÁMÍTÓGÉPES MODELL
ALKALMAZÁSOK DIGITÁLIS ALAKZAT REKONSTRUKCIÓ
3D-s MÉRÉS
Bevezetés
GYÁRTÁS
FIZIKAI OBJEKTUM
10
Digitális reprezentációk
• • • • •
pontok, pontfelhők háromszögek, háromszöghálók görbék, görbehálózatok, drótvázak felületek, felület-csoportok tömör (merev) testek
Reprezentációk
11
Digitális reprezentációk1 1 Pontok, pontfelhők 2 Háromszöghálók, (poligonok)
5 Tömör testek
3 4
Görbék, görbehálózatok
Felületek
Reprezentációk
1. pontfelhők egyesítése, szűrése, egyszerűsítése... 2. háromszögelés (háló generálás) 3. görbe interpoláció és approximáció 4. felület interpoláció és approximáció 5. celluláris (voxel) reprezentáció 12
Digitális reprezentációk2 Pontok, pontfelhők 5
1
Háromszöghálók, (poligonok) 2 Görbék, görbehálózatok
4
Tömör testek
3
Felületek
Reprezentációk
1. decimálás, simítás, újraháromszögelés, deformálás 2. szegmentálás, jellegzetes görbék kiemelése 3. felület approximáció, rekurzív felosztásos felületek 4. digitális alakzat rekonstrukció 5. mintavételezés 13
Digitális reprezentációk3 Pontok, pontfelhők 4 Háromszöghálók, (poligonok)
3
Tömör testek
5 1
Görbék, görbehálózatok
2 Felületek
Reprezentációk
1. görbehálózat építés, speciális műveletek, simítás... 2. felületek létrehozása profilgörbékből (eltolás, forgatás), görbeháló interpoláció,... 3. testek él struktúrája 4. mintavételezés 5. törött vonalak, poligonok 14
Digitális reprezentációk4 Pontok, pontfelhők
Háromszöghálók, (poligonok)
3
Tömör testek
4 2 Görbék, görbehálózatok
5
Felületek 1
Reprezentációk
1. speciális műveletek – offszet, lekerekítő felületek, simítás,... 2. metszések, trimmelt lapok (felületdarabok), primitív testek... 3. mintavételezés 4. tesszelláció (poligonközelítés) 5. felület-felület metszés, felületen futó görbék,... 15
Digitális reprezentációk5 Pontok, pontfelhők 2 Háromszöghálók, (poligonok)
3
1 Tömör testek
4 5 Görbék, görbehálózatok
Felületek
Reprezentációk
1. Bool műveletek, primitív testek... 2. mintavételezés 3. tesszelláció (poligon közelítés) 4.-5. határolóelem-reprezentáció előállítása, élek, hurkok, trimmelt lapok 16
Pontok1 p = ( x, y ) ∈ R 2 , p = ( x, y , z ) ∈ R 3 n
3 Lineáris kombináció: r = ∑ α i p i , α i ∈ R, p i ∈ R i =1
n
Baricentrikus kombináció:
∑αi = 1
Konvex kombináció:
αi ≥ 0
i =1
pl. α i =
1 n
αi =
mi n
∑ mk k =1
Példák:
r (t ) = p 0 (1 − t ) + p1t , r (t ) = p 0 (1 − t ) 2 + p1 2(1 − t )t + p 2 t 2
Affin leképzés:
r1 = Φ(r ) = rA + v ⎡ a11 [ x1 , y1 , z1 ] = [ x, y , z ] ⎢a21 ⎢ ⎢⎣a31 Pontok, vektorok
a12 a22 a32
a13 ⎤ a23 ⎥ + [vx, vy , vz ] ⎥ a33 ⎥⎦ 17
Pontok2 n
Affin tulajdonságok: Φ : R 3 → R 3 Φ (r ) = ∑ α i Φ ( p i ) invariáns a baricentrikus kombinációra egyenes ⇒ egyenes R2: háromszög − háromszög → Φ R3: tetraéder − tetraéder → Φ
i =1
r1 = Φ(r ) = rA + v
Affin transzformációk: ⎡1 0 ⎤ A=⎢ , ⎥ ⎣0 1 ⎦
v=0
Eltolás:
⎡ cos α A = I, v ≠ 0 Forgatás: A = ⎢ ⎣ − sin α
Skálázás:
⎡ a 0⎤ A=⎢ ⎥ ⎣ 0 b⎦
Nyírás:
Azonosság:
Egybevágóság:
AT A = I Pontok, vektorok
sin α ⎤ , v=0 ⎥ cos α ⎦
⎡ 1 0⎤ A=⎢ ⎥ ⎣ a 1⎦ ( x, y ) → ( x + ay , y ) 18
Vektorok a = (a x , a y , a z ) ∈ R 3 Elemi vektor műveletek:
R 3 → R 3 , c = a + b, d = a − b, e = λa
Skalárszorzás (dot product):
(a, b) = a b cosϕ
b
(a, b) = ( b, a) (a + b, c ) = (a, c ) + (b, c) (a, b) = 0 ⇔ a ⊥ b 2 (a, b) = a x bx + a y by + a z bz ; (a, a) = a Vektorszorzás (cross product):
φ a
| a × b |= a b sin ϕ
a × b = − b × a! (a + b) × c = a × c + b × c a × b = 0 ⇔ a || b
⎡i a × b = ⎢a x ⎢ ⎢⎣ bx
j ay by
axb
k⎤ az ⎥ ⎥ bz ⎥⎦
b φ a
Pontok, vektorok
19
Görbe és felület egyenletek1
y
Függvény:
z = f ( x, y )
Implicit:
F ( x, y , z ) = 0, R 3 → R1
Parametrikus:
r (u, v ) = ( x (u, v ), y (u, v ), z (u, v )); R 2 → R 3 y
y = f ( x)
F ( x, y ) > 0
y
r (t )
F ( x, y ) < 0
x
F ( x, y ) = 0
x x
• egyértelmű hozzárendelés • y0 =? f(x0) • mintavételezés egyszerű • CAD: ritkán használják
• végtelen félterek • F(x0,y0) =?0 mintavételezés nehéz • CAD: szabályos felületek Egyenletek
t ∈ [0,1] • véges felületdarab • (x0,y0) →? t0 • mintavételezés egyszerű • CAD: szabadformájú felületek 20
Görbe és felület egyenletek2 Példa (2D): parabola Függvény: y=ax2+b, (elforgatva nem függvény !) Implicit:
F ( x, y ) = ax 2 + 2bxy + cy 2 + 2dx + 2ey + f = 0 B = ac − b2 , B > 0 ellipszis, B = 0 parabola, B < 0 hiperbola
Parametrikus:
r (t ) = p 0 (1 − t ) 2 + p1 2(1 − t )t + p 2 t 2
Ideális reprezentáció • koordináta rendszer független • paraméterei geometriailag értelmezhetők p0
y
y
p1 R
r(t)
P p2 x
x Egyenletek
21
Ujjgyakorlat* - implicit görbék Ellipszis
x2 y2 F ( x, y ) = 2 + 2 − 1 = 0 a b
Hiperbola
x2 y2 F ( x, y ) = 2 − 2 − 1 = 0 a b
Nem görbe
F ( x, y ) = x 2 + y 2 + 1 = 0
1. példa
F ( x, y ) = x 4 − x 2 + y 2 = 0
2. példa
F ( x, y ) = xy 2 − y 2 − 4 x = 0 1 1 P1 = ( 2,5, ), P2 = ( − ,1), P3 = ( − ,1), 2 3 Parametrikus görbék
22
Ujjgyakorlat* - parametrikus görbék y a1
Polinomiális bázis
a0
[a 2 , a1 , a0 ] [t , t ,1] r (t ) = a 2t + a1t + a0 , t ∈ [0,1] 2
2
a2
a 2 = (6,1) a1 = ( −4,4), a0 = (4,1)
Kezdőpont: (__,__), végpont: (__,__), felezőpont: (__,__)
Bernstein bázis [b 0 , b1 , b 2 ] [(1 − t )2 ,2t (1 − t ), t 2 ] r (t ) = b 0 (1 − t ) 2 + b1 2t (1 − t ) + b 2t 2 , t ∈ [0,1]
b0 = ( 4,1) b1 = (2,3), b 2 = (6,6)
b2
y
Kezdőpont: (__,__), végpont: (__,__), felezőpont: (__,__) b1 b0 Parametrikus görbék
23
Ujjgyakorlat - parametrikus görbék y a1
Polinomiális bázis
a0
[a 2 , a1 , a0 ] [t , t ,1] r (t ) = a 2t + a1t + a0 , t ∈ [0,1] 2
2
a2
a 2 = (6,1) a1 = ( −4,4), a0 = (4,1)
Kezdőpont: (4,1), végpont: (6, 6), felezőpont: (3.5, 3.25)
Bernstein bázis [b 0 , b1 , b 2 ] [(1 − t )2 ,2t (1 − t ), t 2 ] r (t ) = b 0 (1 − t ) 2 + b1 2t (1 − t ) + b 2t 2 , t ∈ [0,1]
b0 = ( 4,1) b1 = (2,3), b 2 = (6,6)
b2
y
Kezdőpont: (4, 1), végpont: (6, 6), felezőpont: (3.5, 3.25) b1 b0 Parametrikus görbék
24
Parametrikus görbék1 differenciál-geometriája n Parametrikus görbe: t ∈ [a , b] → R : r (t ) = ( x (t ), y (t ), z (t ))
Csavarvonal:
r (t ) = ( ρ cos t , ρ sin t , at )
y
Egyszerű görbe (reguláris): r (t1 ) = r (t2 ) ⇔ t1 = t2 Első derivált:
r& (t ) = rt (t ) = lim h →0
r(t+h) r(t)
r (t + h ) − r (t ) h
r(b)
r(a) x
Átparaméterezés mindig lehetséges: Átparaméterező függvény - folytonos, szigorúan monoton, differenciálható Ekvivalens görbe: r (t ) → r (u );
t (u ) = c1u + c2 , u =
A deriváltak megváltoznak, pl.:
r&u (u ) =
t − c2 , [a, b] → [α , β ] c1
∂r ∂r ∂t = = r&t (t ) c1 ∂u ∂t ∂u
Parametrikus görbék
25
Parametrikus görbék2 Görbébe írt poligon:
a = t0 < t1 < ... < tn = b; sab ,n ≅ ∑in=1 | r (ti ) − r (ti −1 ) | = ∑in=1
sab,n korlátos → rektifikálható → az ívhossz létezik b
| r (ti −1 + Δt ) − r (ti−1 ) | Δt Δt
b
sab = ∫ r&x (t ) + r&y (t ) + r&z (t ) dt = ∫ r&(t ) dt 2
2
2
a
a
Az ívhossz a paraméter függvényeként:
t
s(t ) = ∫ r& (τ ) dτ ; s&(t ) = r& (t ) a
Természetes (ívhossz szerinti) paraméterezés: Tulajdonságok:
r (t ( s )); r' =
( a ) | r ' |= 1; (b) r ' ⊥ r ' '
dr ; ds
dr dt 1 = r& = 1; (b) r ' ( s ) 2 = 1 → 2(r' , r' ' ) = 0 ds dt ds dt Érintő egységvektor: e = r' (s ) ( a ) | r ' |=
Parametrikus görbék
26
Önálló feladat Görbék ívhosszának számítása: b
b
s = ∫ r&x (t ) + r&y (t ) + r&z (t ) dt = ∫ r&(t ) dt 2
2
2
a
a
Szeminárium: mikor polinomiális az ívhossz Æ pitagoraszi hodográf görbék Implementáció: pitagoraszi hodográf görbék létrehozása, görbe interpoláció ötödfokú PH görbékkel Reprezentációk
27
Parametrikus görbék3 α
Simulókör:
r2
r1
Δα =κ Δs → 0 Δ s
e1 = r ' ( s ), e 2 = r ' ( s + Δs ), lim
e2
e1
Görbület:
r& (t ) × &r&(t ) 1 = κ ( s ) = r ' ' ( s ) , κ (t ) = ρ (t ) r& (t ) 3 Középpont és evolúta:
r1
1 c(t ) = n(t ), κ (t ) ≠ 0 κ (t )
c(t) c(t)
r1 r2=r(t) r2=r(t)
Parametrikus görbék
r3
r3
28
Parametrikus görbék4 Simulósík és binormális:
b(t)
n = n(t ), b = e × n Kísérő triéder (Frenet frame):
n(t)
r(t)
e(t)
[e(t ), n(t ), b(t )] Torzió:
Δβ b1 = b' ( s ), b 2 = b' ( s + Δs ), lim =τ Δs →0 Δs 1
det(r& , &r&,&r&&) τ ( s ) = 2 det(r ' , r ' ' , r ' ' ' ), τ (t ) = 2 κ r& × &r&
(Vegyes szorzat: (a, b, c ) = (a × b, c ) = det(a, b, c ) ) Parametrikus görbék
b1 β n1 r1
e1
b2
r2
n2 e2
? 29
Parametrikus felületek1 differenciál-geometriája Parametrikus felület: r (u, v ) = ( x (u, v ), y (u, v ), z (u, v ));
E 2 : [a , b] → Ε 3
r (u0 , v ), r (u, v0 ) ∂r ∂x ∂y ∂z ∂r ru (u, v ) = ( ) = ( , , ); rv (u, v ) = ( ) Deriváltak: ∂u ∂u ∂u ∂u ∂v Normálvektor: n = ru × rv
Konstans paramétervonalak:
?
Felületi görbék: rv
u = u(t ), v = v (t ), t ∈ [t1 , t2 ], r (u(t ), v (t )) = r (t )
r
ru
Elsőrendű főmennyiségek:
E = ru2 , F = ru rv , G = rv2 Parametrikus felületek
30
Parametrikus felületek2 ΔA = | (r (u + Δu, v ) − r (u, v )) × (r (u, v + Δv ) − r (u, v )) |=
Elemi felületdarab:
| Felszín:
r (u + Δu, v ) − r (u, v ) r (u, v + Δv ) − r (u, v ) | Δu Δv × Δu Δv
A = ∫∫ ru × rv du dv = ∫∫ EG − F 2 du dv
Felületi görbesereg, normálmetszet :
nc (ϕ ) || ns ⇒ κ (ϕ ) Főgörbületek:
κ 1 = κ min , κ 2 = κ max
Főgörbületi irányok:
k1 , k 2
Euler-egyenlet:
k1 ⊥ k 2
κ (ϕ ) = κ 1 cos 2 ϕ + κ 2 sin 2 ϕ
κ2k2 κ(φ)
Másodrendű főmennyiségek:
L = ruu n, M = ruv n, N = rvv n Parametrikus felületek
κ1k1 31
Parametrikus felületek3
Görbületi vonalak és umbilikus pontok Alliez et al.: Anisotropic Polygonal Remeshing, SIGGRAPH’2003 Parametrikus felületek
32
Parametrikus felületek4 Görbület meghatározása egy adott pontban:
⎡λ2 det ⎢ E ⎢ ⎢⎣ L
−λ F M
1⎤ G ⎥ = 0, λ1 , λ2 ⇒ k 1 , k 2 κ 1 , κ 2 ⎥ N ⎥⎦
L + 2 Mλ + Nλ2 λ = dv / du = tan ϕ , κ (λ ) = E + 2 Fλ + Gλ2
Gauss-(szorzat-) és átlaggörbületek: Felület pontok környezetének osztályozása: G>0 → elliptikus, G<0 → hiperbolikus, G=0, (M≠0) → parabolikus Umbilikus pontok:
1 G = κ 1κ 2 ; M = (κ 1 + κ 2 ) 2
L: M : N =E : F :G → Parametrikus felületek
κ 1 = κ 2 = c, κ ( f ) = c; 33
Parametrikus felületek5 Az Euler egyenlet más formában: Polárkoordináták: r =
ρ , x = ρ cosϕ , y = ρ sin ϕ
Dupin-indikátor (lokális kúpszelet):
G>0
G<0
κ (ϕ ) = κ 1 cos 2 ϕ + κ 2 sin 2 ϕ x2
ρ1
+
y2
ρ2
=1
G=0 (M≠0)
Parametrikus felületek
34
2. előadás - tartalom • Háromszöghálók alkalmazásai • Háromszöghálók jellemzése • Voronoi diagramok és Delaunay háromszögelés, egyszerű algoritmusok • Háromszögelés három dimenzióban • Háromszöghálók számítógépes reprezentációja
Bevezetés
35