3D-s számítógépes geometria 13. Illesztés kényszerekkel 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 Görbék és felületek illesztése kényszerekkel
kényszerek egyenletrendszer segédelemek szekvenciális megoldás távolsághű közelítés hatékony reprezentáció
Következő előadás
2
Alkatrészek tökéletesítése – mérnöki kényszerek - kényszerek: • • • • • •
merőleges párhuzamos koncentrikus érintőleges kerekített érték rácspontba rendezett
- felület csoportok: • közös felület geometria • közös eltolásos irány • közös forgástengely - pontok, tangensek, normálvektorok, egyenes szakaszok, körívek, 2D profilok... - síkok, hengerek, kúpok, tóruszok, transzlációs irányok, rotációs tengelyek... Illesztés kényszerekkel
3
Körök illesztése1
Kör egyenlete: F ( x, y ) = A( x 2 + y 2 ) + Bx + Cy + D = 0
Gradiens egységnyi a körön, normalizálási feltétel: |(
∂F ∂F , ) | = 1 ⇒ ( 2 Ax + B ) 2 + ( 2 Ay + C ) 2 = 1 ∂x ∂y
Az egyenlet baloldalából levont tag 4 AF ( x, y ) = 0, így a kényszer egyenlet:
B 2 + C 2 − 4 AD = 1.
i-edik szegmentált kör; ismeretlen paraméterek, adott pontok, : { Ai , Bi , Ci , Di }, {Pij = ( xij , yij ), j = 1,..., ni }
Minimalizálandó:
∑ d ij2 = ∑ i, j
i
1 ∑ ( Ai ( xij2 + yij2 ) + Bi xij + Ci yij + D ) 2 ni j Körök illesztése
4
Körök illesztése2
Három normalizálási egyenlet a három körre:
Bi2 + Ci2 − 4 Ai Di = 1, i = 1,2,3
Két tangenciális egyenlet,
pl. első és második kör ( A1 B2 − A2 B1 ) 2 + ( A1C2 − A2C1 ) 2 − ( A1 ± A2 ) 2 = 0
Ha
A=0 → egyenes
F ( x, y ) = A( x 2 + y 2 ) + Bx + Cy + D = 0 → Bx + Cy + D = 0
Körök illesztése
5
Illesztés kényszerekkel1 • Szegmentált tartományok az i-edik tartomány pontjai : { pij }, j = 1,..., ni Si az i-edik felület: • Az általános illesztési feladat:
f ( x ) = ∑ α i ∑ d ( pij , Si ) 2 i
• Súlyzó tényező:
(i) α i =
j
1 1 ; (ii) α i = ni Areai
• Paramétervektor (a felületek összes paraméterei): x = ( x1 ,..., xn ) • Kényszer egyenletek:
C( x ) = ( c1 ( x ),..., ck ( x ))
• Probléma: több kényszer, mint szabad paraméter; ezek ellentmondhatnak prioritási sorrend: c1 a legfontosabb, ck a legkevésbé fontos
Kényszerek - egyenletrendszer
6
Illesztés kényszerekkel2 f ( x ) = min, c( x ) = 0 • Módosított Newton iteráció • Jelenlegi paraméter vektor: x0, új érték: x0 +d • Megoldandó:
c( x 0 + d ) ≈ c( x 0 ) + c′( x 0 )d • Sorbafejtés: 1 f ( x 0 + d ) ≈ f ( x 0 ) + f ′( x 0 )d + dT f ′′( x 0 )d 2 df df } i, j = 1,...n f ′ = { } f ′′ = { ∂xi ∂xi ∂x j
• Jelölések:
~
C = [c′( x 0 ) | c( x 0 )], d = ( d1 , K , d n ,1)T ~
• Mátrixalakban: Cd = 0,
~ ~ d T Ad = min .
⎡ f ′′( x 0 ) A=⎢ T ⎣f ′( x 0 )
f ′( x 0 )⎤ 0 ⎥⎦
[n + 1 × n + 1]
Kényszerek - egyenletrendszer
7
Illesztés kényszerekkel3 d* ~ * A kényszeregyenletek változói: d = Md
• Független változók vektora: •
• Ismeretlen mátrix: • Ha
CM = 0
M ismert, kényszer nélküli minimalizálás:
• Közönséges lineáris egyenlet rendszer: •
A * = MT AM, d*T A *d* = min
~ d* → d
M meghatározása C-ből • Gauss elimináció-szerű lépések felülről lefelé, minden lépésben kiiktatunk egy di-t
C1d1 + L + Cn d n + Cn +1 = 0 • a kényszer egyenletek nem függetlenek, ha egy sorban
- az összes együttható nulla, tovább lépünk, mert nem lehet eliminálni - ha csak a konstans tag nem nulla, tovább lépünk, mert ellentmondás van opcionális anyag Kényszerek - egyenletrendszer
8
Illesztés kényszerekkel4
opcionális anyag
Eliminációs lépések - a C mátrix első sorával indulunk és azt a dl-et fejezzük ki, amelyiknek a legnagyobb abszolút értékű tagja van:
C C C C C1 d1 − L − l −1 d l −1 − l +1 d l +1 − L − n d n − n +1 Cl Cl Cl Cl Cl L 0 0 0 ⎤ ⎡ 1 L ⎢ M O M M O M ⎥ ⎢ ⎥ L 1 0 0 ⎥ ⎢ 0 L C C C ⎥ ⎢ C1 L − l −1 − l +1 L − k +1 ⎥ M1 = ⎢ − C Cl Cl Cl ⎢ 0l L ⎥ L 0 1 0 ⎢ ⎥ ⎢ M O M M O M ⎥ ⎢ ⎥ 0 L 0 0 L 1 ⎦ ⎣ ~ Az M1 mátrix kiküszöböl egy változót, d = M1d1 ~ és ezáltal egy rövidebb d1 vektorra redukálja d -t dl = −
d1 = ( d1 ,K, d l −1 , d l +1 , K, d n ,1)
Kényszerek - egyenletrendszer
9
Távolsághű közelítés
felületparaméterek:
x = {xi }, i = 1,..., n; pontok: {p k }, k = 1,....m m
minimalizálandó:
∑ d ( x, p k )2 = min k =1
m
2 ∑ (F ( pk ) ) = min
algebrai távolság, nagyon torzít:
euklideszi távolság - általában csak iteratív eljárással; ⇒ távolsághű közelítés (faithful approximation)
Legyen
k =1
g − h2 ~ ( g − h )( g + h ) d = d ( x, pi ) = g ( x ) − h( x ), d ≅ )= , 2h 2h ~ ekkor ∂d ∂d ~ (q ) = (q ) d (q) = 0 ↔ d (q) = 0; ∂xi ∂xi Bizonyítás: ~ d2 ∂d ∂d ∂d d ~ g − h 2 (d + h)2 − h 2 d = = =d + , = + 2h 2h 2h ∂xi ∂xi ∂xi h Távolsághű közelítés
10
Hatékony reprezentáció Cél: az iteráció számításigényének optimalizálása Ideális esetben a távolságfüggvény alakja:
d ( p, x ) = S ( x )T P ( p ) = P ( p )T S ( x ) A minimalizálandó kifejezés:
f ( x ) = ∑ d ( p, x ) 2 = S ( x )T ⎛⎜ ∑ P( p ) P( p )T ⎞⎟ S ( x ) p ⎝ p ⎠ A Q mátrix csak az adatpontoktól függ:
Q = ∑ P ( p ) P ( p )T p
Általános esetben:
f ′ = 2 S T QS ′ f ′′ = 2( S ′T QS ′ + S T QS ′′)
Ha
S ( x ) = ( x1 , x2 , x3 , K) →
f ′( x ) = 2Qx f ′′( x ) = 2Q
Körök illesztése
opcionális anyag 11
Körillesztés - példa d =|| p − o || − r
kör: {o, r};
2 2 2 ~ ( p − o ) 2 − r 2 p − 2 p, o + o − r távolsághű közelítés : d = = 2r 2r
a hatékony reprezentáció paramétervektora:
euklideszi távolság:
S ( x) = S (ox , o y , r ) = (1 / 2r ,−ox / r ,−o y / r , (o 2 − r 2 ) / 2r )
P ( p ) = ( p 2 , p x , p y ,1)
továbbegyszerűsített reprezentáció (4 változó!):
x = (o x , o y , r ) ⇒ κ=
1 , o* = −2κo, 2r
x* = S ( x ) = (κ , o*x , o*y , A) A = (o 2 − r 2 ) / 2 r ⇒
(o*)2 − 4 Aκ = 1
deriváltak számítása egyszerűsödik, ha: S ( x*) = x * Körillesztés
12
Segédelemek Segédelemek (auxiliary elements):
több változó több egyenlet de egyszerűbb egyenletrendszer
Kiinduló állapot
Egyszerű segédelemek:
pontok pont + normál vektor párok irányvektorok forgástengelyek Iteráció - 7 lépés után Segédelemek
13
Ellentmondó kényszerek1 Példa - egy négyzet és három kör:
C1: a körök sugara megegyezik C2: a körök középpontja egy egyenesen helyezkedik el C3: ez az egyenes vízszintes C4: a középpontok felosztják a négyzet szélességét és egymástól 30 egységre vannak C5: a négyzet oldalhossza 100 egység
Kiinduló állapot
Oldalhossz <> 100, utolsó: C5 Ellentmondó kényszerek
14
Ellentmondó kényszerek2 Segédobjektum:
egyenes körközéppontok ráillesztve
Távolságok <> 30, utolsó: C4
Nem vízszintes, utolsó: C3
Ellentmondó kényszerek
C1: sugarak C2: egyenes C3: vízszintes C4: 30 egység távolság C5: oldalhossza 100 egység
Nem kollineáris, utolsó: C2
15
A következő előadás tartalma Digitális Alakzatrekonstrukció IV.:
szabadformájú felületillesztési algoritmusok
görbék és felületek simítása
Vizsgával kapcsolatos kérdések
Következő előadás
16