3D számítógépes geometria és alakzatrekonstrukció 13. Felületmetszések, párhuzamosan eltolt és lekerekítő felületek
http://cg.iit.bme.hu/portal/node/312 https://www.vik.bme.hu/kepzes/targyak/VIIIMA01 Dr. Várady Tamás, Dr. Salvi Péter BME, Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék Algoritmusok
1
Tartalom I. Felületmetszések
alkalmazások, követelmények algebrai módszerek diszkrét módszerek görbekövetés
II. Párhuzamosan eltolt görbék és felületek
alkalmazások önmetszések algebrai módszerek közelítő módszerek
III. Lekerekítő felületek
algebrai módszerek gördülő gömb parametrikus approximáció
Algoritmusok
2
Felület-felület metszések1 Alkalmazások • • • •
halmazműveletek kontúrok, szintvonalak sziluett vonalak lekerekítő felületek
Követelmények • • • •
automatikus pontos hatékony megbízható
Algoritmusok
3
Felület-felület metszések2
Algoritmusok
4
Felület-felület metszések3 Felületmetszési problémák • sokféle reprezentáció kombinációja • implicit & implicit: F1(x,y,z)=0, F2(x,y,z)=0 • implicit & parametrikus: F1(x,y,z)=0, r(u,v) • parametrikus & parametrikus: r(u,v), p(s,t) • a metszésgörbe több darabból állhat • szinguláris esetek: cusp (csúcspont), elágazás, érintőleges felületek, pici hurkok, önmetszés
Algoritmusok • direkt (speciális esetek) • algebrai • felosztásos (subdivision) +: nem kell kezdőpont -: szinguláris pontok, kis hurkok • görbekövetés (tracing) +: explicit görbék -: kezdőpont beállítás, lépéstávolság Algoritmusok
Két henger metszése
5
Felület-felület metszések4 Metszésgörbe explicit algebrai formában • 1. implicit, 2. parametrikus ⇒ behelyettesítés
F(x,y,z)=0, r(u,v) → F(x(u,v),y(u,v),z(u,v))=0, u=u0 → v0 → {ui,vi} → görbeapproximációk: {r(ui,vi)}, {F(xi,yi,zi)} HENGER : x 2 + y 2 − R 2 = 0, SÍK : [ Ax + By + Cz + D = 0] → r (u , v) = au + bv + c, ELLIPSZIS : (a xu + bx v + c x ) 2 + (a y u + by v + c y ) 2 − R 2 = F (u, v) = 0 • konverziók (i) parametrikus → implicit: mindig lehetséges • implicit konverzió (racionális polinomból): r(u,v)→ F(x,y,z), • bonyolult algebra, magas fokszám (n X m) felület - implicit forma: 2nm két harmadfokú metszésgörbéje algebrailag: 2*2*9*9=324 fokú! (ii) implicit → parametrikus: általánosan nem lehetséges • lineáris és másodfokú - OK, • egyébként csak speciális esetekben Algoritmusok
6
Ujjgyakorlat* - metszések Egyenes - parabola metszés
e1 : r1 ( s ) = Q + sR, s ∈ [0,1] ⇒ Ax + By + C = 0
P0
C
p1 : r2 (t ) = P0 (1 − t ) 2 + P1 2(1 − t )t + P2t 2 , t ∈ [0,1]
P2
Feladat:
P1
P0 : (−1,2), P1 : (0,0), P2 : (3,1), e1 : 2 x + y − 3 = 0 p1 : r2 (t ) = ( x(t ), y (t )) = (?, ?) Behelyettesítés után, másodfokú egyenlet t-re
2(?) + (?) − 3 = 0, ? t 2 + ? t + ? = 0, t = ?
Algoritmusok
7
Ujjgyakorlat - metszések Egyenes - parabola metszés
e1 : r1 ( s ) = Q + sR, s ∈ [0,1] ⇒ Ax + By + C = 0
P0
C
p1 : r2 (t ) = P0 (1 − t ) 2 + P1 2(1 − t )t + P2t 2 , t ∈ [0,1]
P2
Feladat:
P1
P0 : (−1,2), P1 : (0,0), P2 : (3,1), e1 : 2 x + y − 3 = 0 p1 : r2 (t ) = ( x(t ), y (t )) = (−(1 − t ) 2 + 3t 2 , 2(1 − t ) 2 + t 2 ) Behelyettesítés után, másodfokú egyenlet t-re
2(−1 + 2t + 2t 2 ) + (2 − 4t + 3t 2 ) − 3 = 0, 7t 2 − 3 = 0, t =
Algoritmusok
3 7
8
Felület-felület metszések5 Iteratív felosztás • • • • •
burkoló téglatestek - iteratív finomítás konvex burok min-max vagy orientált téglatestek hízlalt ívek (fat arcs) & hízlalt gömblapok számításigény: (i) burok számítás (ii) metszési teszt (iii) az algoritmus konvergenciájának sebessége
• problémák: szinguláris pontok, kis hurkok, pontatlanság
Algoritmusok
Fat arc
9
Felület-felület metszések6 Diszkrét módszerek (i) implicit & szabadformájú felület példa:
párhuzamos síkmetszetek adaptív cellázás sétáló négyzetek Problémás esetek
(ii) rács & rács (iii) felület & törtvonalas paramétervonalak problémák: szinguláris pontok kis hurkok pontatlanság
Algoritmusok
10
Felület-felület metszések7 Metszésgörbe követése • kezdőpont(ok) keresése • terminálás - önmagába zárul vagy kiér a szélre • pont szekvencia: (u0 , v0 , s0 , t0 ) → ... (ui , vi , si , ti ) → (ui +1 , vi +1 , si +1 , ti +1 ) → ...
r (u, v), N1 (u, v), p( s, t ), N 2 ( s, t ), T = N1 × N 2
N1 (u, v)
• lépéshossz megkötése:
konstans vagy adaptív harmadik felület
p( s, t )
N2 (s, t )
• metszésgörbére kényszerítés:
Newton-Raphson iteráció tolerancia vezérelt
• problémák:
r(u, v)
kezdőpont hirtelen irányváltás (adaptív lépéshossz!) pontatlanság Algoritmusok
11
Ofszet görbék1 Ofszet: • párhuzamosan eltolt vagy normális irányú eltolás • hízlalás vagy zsugorítás Alkalmazások • NC megmunkálás (zsebmarás) • felületek vastagsággal • cső-felületek vezérgörbéből • lekerekítő felületek
Algoritmusok
12
Ofszet görbék és felületek Ofszet görbék • általános egyenlet:
rd (t ) = r (t ) + N 0 (t ) d , N 0 (t ) = • pontos ofszet görbe --- egyenes, kör, PH görbék • görbületi sugár, görbület:
ρd = ρ + d , κ d =
( y& (t ),− x& (t )) x& 2 (t ) + y& 2 (t ) N
r
rd
κ 1 + κd
Ofszet felületek • általános egyenlet:
s d ( u , v ) = s( u , v ) + N 0 ( u , v ) d
• az ofszet felület normálisa párhuzamos az eredetivel • a görbületi ellipszoid eltolódik:
ρ1,d = ρ1 + d , ρ 2,d = ρ 2 + d , Algoritmusok
13
Lekerekítő felületek1 Éles élek helyett lekerekítő felületek: • • • •
sima kapcsolódás esztétikai követelmények anyagminőség NC megmunkálás
Él-lekerekítés & csúcs-lekerekítés Lekerekítő algoritmusok: (i) algebrai (ii) gördülő gömb (iii) parametrikus
Algoritmusok
14
Lekerekítő felületek2 Illusztráció 2D-ben (Liming módszere): (i) három egyenes implicit formában (ii) végponti megkötések teljesülnek, teltség állítható
S i ( x, y ) = Ai x + Bi y + Ci = 0, i = 1,2,3
S1 = 0 F =0
S2 = 0
S3 = 0
F ( x, y ) = (1 − λ ) S1S 2 + λS 32 = 0 S1 ( x0 , y0 ) = 0, S3 ( x0 , y0 ) = 0 → F ( x0 , y0 ) = 0 ∂S ∂ ∂S ∂S ∂S F ( x0 , y0 ) = (1 − λ )( 1 S 2 + S1 2 ) + 2λ 3 S3 = const. × 1 ( x0 , y0 ) ∂x ∂x ∂x ∂x ∂x ∂ ∂S F ( x0 , y0 ) = .... = const. × 1 ( x0 , y0 ) ∂y ∂y ∇F ( x0 , y0 ) = const. × ∇S1 ( x0 , y0 ) Algoritmusok
15
Lekerekítő felületek3 G ( x, y , z ) = 0 H ( x, y , z ) = 0
3D általánosítás F ( x, y , z ) = 0 Implicit lekerekítő felületek • két implicit felület: • szorzatfelület: • lineáris kombináció λ teltségi tényező: • lekerekítő felület az F vágófelület segítségével:
G ( x, y, z ) = 0, H ( x, y, z ) = 0 S ( x , y , z ) = G ( x , y , z ) H ( x, y , z ) = 0 S ( x, y, z ) = (1 − λ )G ( x, y, z ) + λH ( x, y, z ) = 0 S ( x, y, z ) = (1 − λ )G (.) H (.) + λF 2 (.) = 0
Algoritmusok
16
Lekerekítő felületek4
q 2 (λ )
c(λ )
Gördülő gömb lekerekítés: • érinti a két szomszédos felületet • ponthármas három összerendelt görbén gerincgörbe: c(λ ) q1 (λ ) = r (u (λ ), v(λ )), határgörbe: q 2 (λ ) = p( s (λ ), t (λ )) • a középpont mértani helye az ofszet-felületek metszésvonala • normálvektorok alapján görbekövetés • mintavételezés, söprő sík: π ( λk )
q1 (λ )
N 1 (u, v )
p R ( s, t )
N 2 ( s, t )
rR ( u , v )
• minden körív Bézier alakban (racionális másodfokú) adott:
{b 0 (λk ), b1 (λk ), b 2 (λk ), w(λk )} • felület: 10-dimenziós hosszanti görbeapproximáció Algoritmusok
b2 c(λ )
b1 b0
17
Ujjgyakorlat* - lekerekítés Feltétel: T2
| C − T1 | = | C − T2 | = R
R
C R
Feladat:
T1
r1 : x 2 + y 2 = 25 r2 : y = 0 R = +2
r1R
r1R : ? r2 R : ? C : ( x0 , y0 )
C
r2 R r2
x0 = ? y0 = ?
r1
Összes megoldás (+/-) száma: ? Algoritmusok
18
Ujjgyakorlat - lekerekítés Feltétel: T2
| C − T1 | = | C − T2 | = R
R
C R
Feladat: T1
r1 : x 2 + y 2 = 25 r2 : y = 0 R = +2
r1R
r1R : x + y = 49 2
2
r2 R : y = 2 C : ( x0 , y0 )
C
r2 R
x0 = ± 49 − 4, y0 = 2
r2 r1
Összes megoldás (+/-) száma: 8 Algoritmusok
19